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

Problem Detail: 

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.

Asked By : AkshaiShah

Answered By : Raphael

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/4918