Useful tautologies

Propositional Logic: Logical consequence and consistency

Useful tautologies

In the following theorem a number of 'useful' tautologies and the name by which they are known are put together.

Tautologies Suppose \(\varphi\), \(\psi\), and \(\chi\) are logical formulas. Then the following formulas are tautologies. \[\begin{array}{lcl} \textit{Tautology} && \textit{Name} \\ \hline
(\varphi\lor \psi) \leftrightarrow (\psi\lor \varphi) && \text{commutativity}\\[0.2cm]
(\varphi\land \psi) \leftrightarrow (\psi\land \varphi) &&\\[0.2cm]
\bigl((\varphi\lor \psi)\lor \chi\bigr) \leftrightarrow \bigl(\varphi\lor (\psi\lor \chi)\bigr) && \text{associativity}\\[0.2cm]
\bigl((\varphi\land \psi)\land \chi\bigr) \leftrightarrow \bigl(\varphi\land (\psi\land \chi)\bigr) \\[0.2cm]
\bigl(\varphi\lor (\psi\land \chi)\bigr) \leftrightarrow \bigl((\varphi\lor\psi)\land (\varphi\lor \chi)\bigr) && \text{distributivity}\\[0.2cm]
\bigl(\varphi\land (\psi\lor \chi)\bigr) \leftrightarrow \bigl((\varphi\land\psi)\lor (\varphi\land \chi)\bigr) \\[0.2cm]
(\varphi\lor \psi) \leftrightarrow \varphi \quad\text{for any contradiction }\psi&& \text{identity} \\[0.2cm]
(\varphi\land \psi)\leftrightarrow \varphi\quad\text{for any tautology }\psi && \\[0.2cm]
(\varphi\lor \psi) \leftrightarrow \psi \quad\text{for any tautology }\psi&& \text{dominance} \\[0.2cm]
(\varphi\land \psi)\leftrightarrow \psi\quad\text{for any contradiction }\psi && \\[0.2cm]
(\varphi\lor \varphi) \leftrightarrow \varphi && \text{idempotence} \\[0.2cm]
(\varphi\land \varphi)\leftrightarrow \varphi && \\[0.2cm]
\bigl((\varphi\lor \psi)\land \varphi\bigr) \leftrightarrow \varphi && \text{absorption}\\[0.2cm]
\bigl((\varphi\land \psi)\lor \varphi\bigr) \leftrightarrow \varphi\\[0.2cm]
(\varphi\lor \neg\,\varphi)\leftrightarrow \text{any tautology }\psi && \text{inversion}\\[0.2cm]
(\varphi\land \neg\,\varphi) \leftrightarrow \text{any contradiction }\psi && \\[0.2cm]
\neg(\varphi\lor \psi)\leftrightarrow (\neg\,\varphi\land\neg\,\psi) && \text{rules of De Morgan}\\[0.2cm]
\neg(\varphi\land \psi)\leftrightarrow (\neg\,\varphi\lor\neg\,\psi) && \\[0.2cm]
(\neg\,\neg\,\varphi)\leftrightarrow \varphi && \text{double negation}\\[0.2cm]
(\varphi\rightarrow\psi)\leftrightarrow (\neg\,\psi\rightarrow \neg\,\varphi) && \text{contraposition}\\[0.2cm]
(\varphi\rightarrow\psi)\leftrightarrow (\neg\,\varphi \lor \psi)&&
\end{array}\]

Metalanguage In metalanguage you need fewer parentheses because a symbol in the metalanguage distinguishes formulas in the language of propositions. For example, we can also write the contraposition \[(\varphi\rightarrow\psi)\leftrightarrow (\neg\,\psi\rightarrow \neg\,\varphi)\] as \[\varphi\rightarrow\psi \iff \neg\,\psi\rightarrow \neg\,\varphi\] using the "if and only if" symbol \(\iff\).

The above list of tautologies might lead you to the idea that simultaneous replacement of all occurrences of \(\land\) with \(\lor\) and replacement of all occurrences of \(\lor\) with \(\land\) replaces most of the tautologies with yet another tautology. Only for the contraposition \((\varphi\rightarrow\psi)\leftrightarrow (\neg\,\varphi \lor \psi)\) in the list this does not apply. Suppose that \(\varphi\) is a formula that contains only the connectives \(\neg\), \(\land\), and \(\lor\). Then the dual formula \(\varphi^{\mathrm{d}}\) is defined as the formula resulting from replacing every occurrence of \(\land\) in \(\varphi\) with \(\lor\) and replacing every occurrence of \(\lor\) in \(\varphi\) with \(\land\).

Principle of duality Suppose \(\varphi\) and \(\psi\) are logical formulas in which only the connectives \(\neg\), \(\land\) and \(\lor\) occur. Then we have: the formulas \(\varphi\) and \(\psi\) are logically equivalent if and only if the dual formulas \(\varphi^{\mathrm{d}}\) and \(\psi^{\mathrm{d}}\) are logically equivalent.

Metalanguage In metalanguage the principle of duality can be formulated as follows.

Suppose \(\varphi\) and \(\psi\) are logical formulas containing only the connectives \(\neg\), \(\land\), and \(\lor\). Then we have: \[\varphi\leftrightarrow \psi \iff \varphi^{\mathrm{d}}\leftrightarrow \psi^{\mathrm{d}}\]

We end up with even more logically equivalent formulas containing an implication or equivalence symbol. This time we write the formulas in metalanguage with the "if and only if" symbol \(\iff\); this symbol indicates an equivalence relation.

Tautologies with implication or equivalence symbol Suppose \(\varphi\), \(\psi\) and \(\chi\) are logical formulas. Then the following formulas are tautologies. \[\begin{array} {lcl} \textit{Tautology} && \textit{Tautology} \\ \hline
\varphi\lor \psi \iff \neg\,\varphi\rightarrow \psi && \varphi\land \psi \iff \neg(\varphi\rightarrow \neg\,\psi) \\[0.2cm]
\neg(\varphi\rightarrow \psi) \iff \varphi\land \neg\,\psi && (\varphi\rightarrow \psi)\land (\varphi\rightarrow \chi)\iff \varphi\rightarrow(\psi\land \chi)\\[0.2cm]
(\varphi\rightarrow \chi)\land (\psi\rightarrow \chi)\iff (\varphi\lor \psi)\rightarrow \chi &&
(\varphi\rightarrow \psi)\lor (\varphi\rightarrow \chi)\iff \varphi\rightarrow (\psi\lor \chi)\\[0.2cm]
(\varphi\rightarrow \chi)\lor (\psi\rightarrow \chi)\iff (\varphi\land \psi)\rightarrow \chi && \varphi\leftrightarrow \psi\iff (\varphi\rightarrow \psi)\land(\psi\rightarrow\varphi)\\[0.2cm]
\varphi\leftrightarrow \psi\iff \neg\,p\leftrightarrow \neg\,\psi && \varphi\leftrightarrow \psi\iff (\varphi\land \psi)\lor (\neg\,\varphi\land \neg\,\psi)\\[0.2cm] \neg(\varphi\leftrightarrow \psi)\iff \varphi\leftrightarrow \neg\,\psi &&\end{array}\]