0
$\begingroup$

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

  • 0
    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"?2012-10-07

1 Answers 1

2

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.