Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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
up vote 1 down vote accepted

I believe that there are (at least) a couple of options.

  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.
share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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