# Study if a tree represents a tautological proposition

I have difficulties to solve this excercise:

1. The following path of a given tree in customary infix notation: $$[(\neg(p\wedge q)\Rightarrow r)\wedge ((r\vee q)\Rightarrow s)]$$ represents a tautological proposition (do not make truth table).
2. It is not possible to go through the 1) tree in preorder.

For the first one, I don't know why there is the data of how the tree is traversed (usual infix notation): is it because it is the classical (or only) way to reduce a complex proposition in classical logic? Because with another notation it is not valid (as it says in point 2., which I think is true).

However, it is clear that 1. is not a tautology, because if $q$ is true and $s$ is false, the expression is false. So this excercise is solved like this, or do we have to apply logical laws?: $$\begin{matrix} (\neg(p\wedge q)\Rightarrow r)\wedge ((r\vee q)\Rightarrow s)&\underbrace{\Leftrightarrow}_{\textrm{Conditional equiv.}\\\;\;\textrm{and involution}}\\ ((p\wedge q)\vee r)\wedge (\neg (r\vee q)\vee s)&\underbrace{\Leftrightarrow}_{\textrm{De Morgan}}\\ ((p\wedge q)\vee r)\wedge ((\neg r\wedge \neg q)\vee s)&\underbrace{\Leftrightarrow}_{\textrm{Distributive}}\\ (p\vee r)\wedge (q\vee r)\wedge (\neg r\vee s)\wedge (\neg q\vee s),& \end{matrix}$$ but from here I do not know how to continue.

For the second I made the tree path:

Looking at the graph the preorder path would be $$\wedge\Rightarrow\neg\wedge pqr\Rightarrow\vee rqs,$$

and this in logic does not represent anything; it has no meaning, therefore we can't go through the tree in preorder.

Any help would be appreciate!

Thanks!

• If r is true and s false, then the statement is false, not a tautology. – William Elliot Feb 19 '18 at 21:10
• The preorder path makes perfect sense in prefix notation. – William Elliot Feb 19 '18 at 21:14
• @WilliamElliot We are agree on that, but the question I am asking has to do with why there is the fact that the tree is traversed in usual infix notation. Also in this case, if the path in preorder as the tree is made, does not make any sense, because it does not represent a logical proposition. It is clear that given a tree can be traversed in any order, but this exercise asks to know (I think) if this path has "logical" coherence. I gave the example that if $q$ is true and $s$ is false, the proposition is not a tautology. – manooooh Feb 19 '18 at 21:20