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:

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!


  • $\begingroup$ If r is true and s false, then the statement is false, not a tautology. $\endgroup$ – William Elliot Feb 19 '18 at 21:10
  • $\begingroup$ The preorder path makes perfect sense in prefix notation. $\endgroup$ – William Elliot Feb 19 '18 at 21:14
  • $\begingroup$ @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. $\endgroup$ – manooooh Feb 19 '18 at 21:20

Whence this nonsense? From a text on parsing statements?

The tree is traversed with infix notation because our logic is built using infix notation. Polish notation and reverse Polish notation use prefix notation and postfix notation respectively. VonNeuman notation, infix notation, requires infix trees. The same logic with Polish notation requires prefix trees and with reverse Polish notation requires postfix trees. p -> q, Cpq, pqC is VonNeuman, Polish, reverse Polish notation for 'p implies q', respectively.

Are natural languages infix? English seems to be.
Perhaps languages that place the verb last are postfix

| cite | improve this answer | |
  • $\begingroup$ Sorry for the negative vote but I think this answer does not add anything useful to my two questions. This nonsense appeared in a final exam of my university and the truth that I do not understand either, that's why I opened this topic. I only saw the Polish, Polish reverse and infix notations. $\endgroup$ – manooooh Feb 19 '18 at 22:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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