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.
How to make a parse tree for the following propositional logic formula?
formal languages;logic;binary trees;parsing
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$.