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

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

As it contains 3 subformulas between the $\vee$'s, how can I put it into a parse tree. Would it be just the one branch, the node being the $\vee$?

-
Depends if you want a binary tree or not since it is associative. – xavierm02 Oct 7 '12 at 13:00
You don't have a propositional logic formula. ∨ has arity of 2, and thus it is not clear what the string means. There does not exist a parse tree for this string. If you have a convention, such as p ∨ q ∨ r means ((p ∨ q) ∨ r), then you have an abbreviation for a formula, and then you can have a parse tree for that abbreviation. If this is homework, what's the convention for strings like "p ∨ q ∨ r"? – Doug Spoonwood Oct 7 '12 at 18:11

1. It is possible that $\vee$ is taken to have arbitray (finite) arity, meaning it could take any finite number of disjuncts. In this case the root of the parse tree would be a single $\vee$ having 3 children.
2. If $\vee$ is certainly binary, then
• it could be that $p \vee q \vee r$ is an abbreviation for a specific formula, say $( p \vee q ) \vee r$, and then take the parse tree of this un-abbreviated version; or
• as $p \vee ( q \vee r )$ and $( p \vee q ) \vee r$ are easily seen to be logically equivalent, if no specific formula have been designated the un-abbreviation of $p \vee q \vee r$, then you can just choose one of these, and parse it accordingly.