1. The problem statement, all variables and given/known data How can we proof that a decision tree can be written as a DNF? 2. Relevant equations http://en.wikipedia.org/wiki/Disjunctive_normal_form A boolean form made of literals (X1 and X2 and X3) or'ed with other literals f = ( (X1 and X2 and X3) or (X4 and X5 and X6) ) 3. The attempt at a solution I am able to take a decision tree and turn it into a DNF but I am not sure how to prove that any tree can be turned into a DNF. I would love some help to get started.