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?
$\begingroup$
$\endgroup$
2
-
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, 2016 at 18:31
-
1$\begingroup$ Parse trees structure syntax, BDDs describe semantics. $\endgroup$– Raphael ♦Jul 14, 2016 at 5:58
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
0
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.
answered Jul 13, 2016 at 20:02