Tautology/Examples/Arbitrary Example 2

Example of Tautology

The WFF of propositional logic:

$\paren {\paren {\lnot p} \implies \paren {q \lor r} } \iff \paren {\paren {\lnot q} \implies \paren {\paren {\lnot r} \implies p} }$

is a tautology.

Proof

Proof by truth table:

$\begin{array}{|cccccc|c|ccccccc|} \hline ((\lnot & p) & \implies & (q & \lor & r)) & \iff & ((\lnot & q) & \implies & ((\lnot & r) & \implies & p)) \\ \hline \T & \F & \F & \F & \F & \F & \T & \T & \F & \F & \T & \F & \F & \F \\ \T & \F & \T & \F & \T & \T & \T & \T & \F & \T & \F & \T & \T & \F \\ \T & \F & \T & \T & \T & \F & \T & \F & \T & \T & \T & \F & \F & \F \\ \T & \F & \T & \T & \T & \T & \T & \F & \T & \T & \F & \T & \T & \F \\ \F & \T & \T & \F & \F & \F & \T & \T & \F & \T & \T & \F & \T & \T \\ \F & \T & \T & \F & \T & \T & \T & \T & \F & \T & \F & \T & \T & \T \\ \F & \T & \T & \T & \T & \F & \T & \F & \T & \F & \T & \F & \T & \T \\ \F & \T & \T & \T & \T & \T & \T & \F & \T & \T & \F & \T & \T & \T \\ \hline \end{array}$

As can be seen by inspection, the truth value under the main connective is true for all rows.

$\blacksquare$

Sources

• 1988: Alan G. Hamilton: Logic for Mathematicians (2nd ed.) ... (previous) ... (next): $\S 1$: Informal statement calculus: $\S 1.2$: Truth functions and truth tables: Exercise $4$