Drzewo decyzyjne typu Boolean jest równoważne logicznemu stwierdzeniu postaci:
gdzie każde Pathi jest koniunkcją formy gdzie każde Pathi jest koniunkcją formy 
testów wartości atrybutów odpowiadających ścieżce od korzenia do prawdziwego liścia. Zatem całe wyrażenie jest w rozłącznej formie normalnej, co oznacza, że każda funkcja w logice zdań może być wyrażona jako drzewo decyzyjne. W przypadku wielu problemów format drzewa decyzyjnego daje ładny, zwięzły i zrozumiały wynik. Rzeczywiście, wiele podręczników „jak to zrobić” (np. dotyczących naprawy samochodu) jest napisanych jako drzewa decyzyjne. Jednak niektóre funkcje nie mogą być przedstawione zwięźle. Na przykład funkcja większości, która zwraca prawdę wtedy i tylko wtedy, gdy więcej niż połowa danych wejściowych jest prawdziwa, wymaga wykładniczo dużego drzewa decyzyjnego, podobnie jak funkcja parzystości, która zwraca prawdę wtedy i tylko wtedy, gdy parzysta liczba atrybutów wejściowych jest PRAWDA. W przypadku atrybutów o wartościach rzeczywistych funkcja y > A1 + A2 jest trudna do przedstawienia w drzewie decyzyjnym, ponieważ granicą decyzji jest linia ukośna, a wszystkie testy drzew decyzyjnych dzielą przestrzeń na prostokątne, wyrównane do osi prostokąty. Musielibyśmy ułożyć wiele pudeł, aby ściśle zbliżyć się do linii ukośnej. Innymi słowy, drzewa decyzyjne są dobre dla niektórych funkcji, a złe dla innych. Czy istnieje jakaś reprezentacja, która jest efektywna dla wszystkich rodzajów funkcji? Niestety, odpowiedź brzmi nie – jest po prostu zbyt wiele funkcji, aby móc je wszystkie przedstawić za pomocą niewielkiej liczby bitów. Nawet biorąc pod uwagę funkcje logiczne z n atrybutami boolowskimi, tabela prawdy będzie miała 2n wierszy, a każdy wiersz może wyprowadzić prawdę lub fałsz, więc istnieje 22n różnych funkcji. Przy 20 atrybutach mamy 21,048;576 ≈ 10300,000 funkcji, więc jeśli ograniczymy się do reprezentacji miliona bitów, nie możemy reprezentować wszystkich tych funkcji.