I have created a parse tree for the formula: a∧¬(b∨c)∨¬d∧(¬b) successfully. I am now asked to create a decision tree for the same formula. What are the main differences between a parse tree and a decision tree?

  • 3
    $\begingroup$ What have you tried? What progress have you made? What have you come up with so far? What self-study have you done so far? Have you checked standard textbooks? If so, which ones? Have you searched thoroughly? Please edit the question to incorporate this information. We expect you to search thoroughly and study standard books/references before asking. $\endgroup$ – D.W. Jul 13 '16 at 18:31
  • $\begingroup$ Parse trees structure syntax, BDDs describe semantics. $\endgroup$ – Raphael Jul 14 '16 at 5:58

A decision tree is an algorithm for computing a function, in your case the truth value of the formula. In your setting, each internal node of the decision tree is labeled by a variable, and it has two children; you go to the left one if the variable is false, and to the right one if it is true. Leaves are labeled by True or False, and this is the returned value.

For example, one decision tree for $a \land b$ is as follows. The root is labeled $a$. Its left child is a leaf labeled False. Its right child $x$ is labeled $b$. The left child of $x$ is a leaf labeled False, and the right child of $x$ is a leaf labeled True.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.