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.

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

1 Answer 1


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)$


$\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

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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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