3
$\begingroup$

I have a formula $ \neg((q \implies \neg q) \vee p \vee (\neg q \implies (r \wedge p))) $.

As it contains 3 subformulas between the $\vee$'s, how can i put it into a parse tree, as a parse tree contains 2 branches from each node.

$\endgroup$
  • $\begingroup$ @TheUnfunCat that's all the information I have $\endgroup$ – AkshaiShah Oct 7 '12 at 12:45
  • $\begingroup$ @TheUnfunCat would it be just one branch? As in just the $\vee$? $\endgroup$ – AkshaiShah Oct 7 '12 at 12:47
  • 1
    $\begingroup$ You would need to rewrite it such that each level of parentheses only includes one binary operator. $\endgroup$ – The Unfun Cat Oct 7 '12 at 12:50
8
$\begingroup$

As it is, your formula is ambiguous; it is not clear which pair of parentheses to insert in order to get a binary tree. Both

$\qquad \displaystyle \varphi_1 \lor (\varphi_2 \lor \varphi_3)$

and

$\qquad \displaystyle (\varphi_1 \lor \varphi_2) \lor \varphi_3$

are feasible. Luckily for you, $\lor$ is associative, so you can choose either one:

enter image description here
[source]

For the purposes of parsing, you would either require formulae to be completely parenthesised, or specify operators to be left- (or right-) associative. Operator precedences would be the next thing to look into, in order to disambiguate formulae like

$\qquad \displaystyle a \land b \lor c$.

$\endgroup$

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.