С точки зрения логики любая конкретная гипотеза из дерева решений для целевого предиката willWait может рассматриваться как утверждение в следующей форме:

где каждое условиепредставляет собой конъюнкцию проверок, соответствующих пути от корня дерева к листу с положительным результатом. Хотя это выражение с виду напоминает высказывание в логике первого порядка, оно в определенном смысле является пропозициональным, поскольку содержит только одну переменную, а все предикаты являются унарными. Это дерево решений фактически описывает связь между предикатом WillWait и некоторой логической комбинацией значений атрибутов. Деревья решений не могут использоваться для представления проверок, относящихся к двум или нескольким разным объектам, например, таких проверок, как показано ниже ("Есть ли поблизости более дешевый ресторан?").

Очевидно, что можно было бы ввести еще один булев атрибут с именем CheaperRestaurantNearby (Наличие поблизости более дешевого ресторана), но задача введения всех подобных атрибутов является трудно осуществимой. В главе 19 приведены дополнительные сведения о задаче правильного обучения в логике первого порядка.

Деревья решений в рамках класса пропозициональных языков являются полностью выразительными; это означает, что в виде дерева решений может быть оформлена любая булева функция. Такую задачу можно выполнить тривиально, предположив, что каждая строка в истинностной таблице для данной функции соответствует определенному пути в дереве. Но подобный подход приводит к получению представления в виде дерева решений с экспоненциальными размерами, поскольку количество строк в истинностной таблице увеличивается экспоненциально, тогда как очевидно, что деревья решений позволяют представить многие функции с помощью гораздо меньших деревьев.