# How to make a parse tree for the following propositional logic formula?

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.

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

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:

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