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.

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

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.

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