Nuttige tautologieën

Propositielogica: Geldig gevolg en consistentie

Nuttige tautologieën

In de volgende stelling zijn een aantal 'nuttige' tautologieën en de naam waaronder ze bekend staan bij elkaar gezet.

Tautologieën Stel dat \(\varphi\), \(\psi\) en \(\chi\) logische formules zijn. Dan zijn de volgende formules tautologieën. \[\begin{array}{lcl} \textit{Tautologie} && \textit{Naam} \\ \hline
(\varphi\lor \psi) \leftrightarrow (\psi\lor \varphi) && \text{commutativiteit}\\[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{associativiteit}\\[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{distributiviteit}\\[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{voor elke contradictie }\psi&& \text{identiteit} \\[0.2cm]
(\varphi\land \psi)\leftrightarrow \varphi\quad\text{voor elke tautologie }\psi && \\[0.2cm]
(\varphi\lor \psi) \leftrightarrow \psi \quad\text{voor elke tautologie }\psi&& \text{dominantie} \\[0.2cm]
(\varphi\land \psi)\leftrightarrow \psi\quad\text{voor elke contradictie }\psi && \\[0.2cm]
(\varphi\lor \varphi) \leftrightarrow \varphi && \text{idempotentie} \\[0.2cm]
(\varphi\land \varphi)\leftrightarrow \varphi && \\[0.2cm]
\bigl((\varphi\lor \psi)\land \varphi\bigr) \leftrightarrow \varphi && \text{absorptie}\\[0.2cm]
\bigl((\varphi\land \psi)\lor \varphi\bigr) \leftrightarrow \varphi\\[0.2cm]
(\varphi\lor \neg\,\varphi)\leftrightarrow \text{elke tautologie }\psi && \text{inversie}\\[0.2cm]
(\varphi\land \neg\,\varphi) \leftrightarrow \text{elke contradictie }\psi && \\[0.2cm]
\neg(\varphi\lor \psi)\leftrightarrow (\neg\,\varphi\land\neg\,\psi) && \text{regels van De Morgan}\\[0.2cm]
\neg(\varphi\land \psi)\leftrightarrow (\neg\,\varphi\lor\neg\,\psi) && \\[0.2cm]
(\neg\,\neg\,\varphi)\leftrightarrow \varphi && \text{dubbele negatie}\\[0.2cm]
(\varphi\rightarrow\psi)\leftrightarrow (\neg\,\psi\rightarrow \neg\,\varphi) && \text{contrapositie}\\[0.2cm]
(\varphi\rightarrow\psi)\leftrightarrow (\neg\,\varphi \lor \psi)&&
\end{array}\]

Metataal In metataal hoef je minder haakjes te gebruiken omdat een symbool in de metataal formules in de taal van proposities onderscheidt. Zo kunen we bijvoorbeeld de contrapositie \[(\varphi\rightarrow\psi)\leftrightarrow (\neg\,\psi\rightarrow \neg\,\varphi)\] ook opschrijven als \[\varphi\rightarrow\psi \iff \neg\,\psi\rightarrow \neg\,\varphi\] met behulp van het "dan en slecht dan" symbool \(\iff\).

Bovenstaande lijst van tautologiën brengt je misschien op het idee dat je bij simultane vervanging van alle voorkomens van \(\land\) met \(\lor\) en vervanging van alle voorkomens van \(\lor\) met \(\land\) de meeste tautologiën vervangen worden door weer een tautologie. Alleen voor de contrapositie \((\varphi\rightarrow\psi)\leftrightarrow (\neg\,\varphi \lor \psi)\) in de lijst gaat dit niet op. Stel dat \(\varphi\) een formule is waarin alleen de connectieven \(\neg\), \(\land\) en \(\lor\) voorkomen. Dan wordt de duale formule \(\varphi^{\mathrm{d}}\) gedefinieerd als de formule die ontstaat door elk voorkomen van \(\land\) in \(\varphi\) te vervangen door \(\lor\) en elk voorkomen van \(\lor\) in \(\varphi\) te vervangen door \(\land\).

Principe van dualiteit Stel dat \(\varphi\) en \(\psi\) logische formules zijn waarin alleen de connectieven \(\neg\), \(\land\) en \(\lor\) voorkomen. Er geldt dan: de formules \(\varphi\) en \(\psi\) zijn logisch equivalent dan en slechts dan als de duale formules \(\varphi^{\mathrm{d}}\) en \(\psi^{\mathrm{d}}\) logisch equivalent zijn.

Metataal In metataal kan het principe van dualiteit als volgt geformuleerd worden.

Stel dat \(\varphi\) en \(\psi\) logische formules zijn waarin alleen de connectieven \(\neg\), \(\land\) en \(\lor\) voorkomen. Er geldt dan: \[\varphi\leftrightarrow \psi \iff \varphi^{\mathrm{d}}\leftrightarrow \psi^{\mathrm{d}}\]

We eindigen met nog meer logisch equivalente formules die een implicatie of equivalentie symbool bevatten. We schrijven de formules dit keer in metataal met het "dan en slechts dan"symbool \(\iff\) op; dit symbool duidt een equivalentierelatie aan.

Tautologieën met implicatie of equivalentie symbool Stel dat \(\varphi\), \(\psi\) en \(\chi\) logische formules zijn. Dan zijn de volgende formules tautologieën. \[\begin{array} {lcl} \textit{Tautologie} && \textit{Tautologie} \\ \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}\]