$\models p \ \vee \ ( \lnot(q \ \wedge \ (r \rightarrow q)))$ is established or not?

Question

I am learning propositional logic and I get a formula like this:

$\models p \ \vee \ ( \lnot(q \ \wedge \ (r \rightarrow q)))$

I want to prove it is established or not by drawing a parse tree, but I don't know it is mathematical rigor. If not, what kinds of ways I should use to prove it?

If not mind, could anyone tell me the mathematical rigor way and prove it?

Thanks in advance.

Answer 1

In order to show that a propositional formlua $\varphi$ is a tautology (in symbols : $\vDash \varphi$) we have two possible ways:

either (i) use truth table method, or (ii) use some proof system, like e.g. Natural Deduction or Truth Trees method.

---

The above formula is not a tautology.

It is enough to check it for a variable assignment $v$ such that :

$v(p)= \text { F and } v(q)= \text T$.

In this case, we have that $v(q \land (r \to q))= \text T$ and thus the complete formula is evaluated to $\text F$.

---

To use Truth Trees, we have to start with the negation of the formula and apply the rules in order to try to derive a contradiction.

Doing this, we can check that not all paths of the tree will close. Specifically, the path with : $\lnot p, q, \lnot r$ will not close.

This proves that the formula is not a tautology (and gives use the counterexample above, with $p$ evaluated to False and $q$ to True).