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.

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$ .

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.

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}$