TU/e
Mike Boldy en Hans Cuypers

Logische wetten

Logische equivalenties worden vaak gebruikt als rekenregels om proposities te herleiden. Als voorbeeld herleiden we de implicatie p\rightarrow q tot de implicatie \neg q\rightarrow\neg p. We gebruiken de volgende equivalenties:

p\rightarrow q\Leftrightarrow\neg p\vee q,
\neg\neg p\Leftrightarrow p
en
p\vee q\Leftrightarrow q\vee p.
Een afleiding gaat dan als volgt
\begin{array}{lll} p\rightarrow q & \Leftrightarrow & \neg p\vee q \\ & \Leftrightarrow & q\vee\neg p\\ & \Leftrightarrow & \neg\neg q\vee\neg p\\ & \Leftrightarrow & \neg q\rightarrow\neg p\\ \end{array}

Er zijn twee manieren om logische equivalenties te gebruiken.

Zonder bewijs vermelden we hier de meest gebruikte rekenregels. In sommige proposities komt een 1 of een 0 voor. Strikt genomen mag dat niet, want 0 en 1 zijn geen propositieletters. In de praktijk echter kom je als deel van een propositie vaak tautologiën en contradicties tegen. Die vervang je dan door 1 respectievelijk 0. Bijvoorbeeld p\vee(q\wedge\neg q)\Leftrightarrow p\vee0.

De eerste 13 regels komen voor in paren. Dit noemt men het dualiteitsprincipe. Het houdt in dat als je in een regel \wedge vervangt door \vee en omgekeerd, en je doet hetzelfde met 0 en 1, dan krijg je weer een rekenregel.

En, of
1 p\vee q\Leftrightarrow q\vee p p\wedge q\Leftrightarrow q\wedge p
2 (p\vee q)\vee r\Leftrightarrow p\vee(q\vee r) (p\wedge q)\wedge r\Leftrightarrow p\wedge(q\wedge r)
3 p\vee(q\wedge r)\Leftrightarrow(p\vee q)\wedge(p\vee r) p\wedge(q\vee r)\Leftrightarrow(p\wedge q)\vee(p\wedge r)
4 p\vee 0\Leftrightarrow p p\wedge 1\Leftrightarrow p
5 p\vee 1\Leftrightarrow 1 p\wedge 0\Leftrightarrow 0
6 p\vee p\Leftrightarrow p p\wedge p\Leftrightarrow p
7 p\vee(p\wedge q)\Leftrightarrow p p\wedge(p\vee q)\Leftrightarrow p
8 p\Rightarrow p\vee q en q\Rightarrow p\vee q p\wedge q\Rightarrow p en p\wedge q\Rightarrow q
9 Als p\Rightarrow r en q\Rightarrow r, dan p\vee q\Rightarrow r Als p\Rightarrow q en p\Rightarrow r, dan p\Rightarrow q\wedge r
Niet
10 \neg 0\Leftrightarrow 1 \neg 1\Leftrightarrow 0
11 \multicolumn{2}{l}{\neg\neg p\Leftrightarrow p}
12 p\vee\neg p\Leftrightarrow 1 p\wedge\neg p\Leftrightarrow 0
13 \neg(p\vee q)\Leftrightarrow\neg p\wedge\neg q \neg(p\wedge q)\Leftrightarrow\neg p\vee\neg q
Implicatie
14 p\rightarrow q\Leftrightarrow\neg p\vee q
15 p\rightarrow p\Leftrightarrow 1
16 (p\rightarrow q)\wedge(q\rightarrow r)\Rightarrow(p\rightarrow r)
17 p\rightarrow q\Leftrightarrow\neg q\rightarrow\neg p
Equivalentie
18 p\leftrightarrow q\Leftrightarrow(p\rightarrow q)\wedge(q\rightarrow p)
19 p\leftrightarrow q\Leftrightarrow(p\wedge q)\vee(\neg p\wedge\neg q)
20 \neg(p\leftrightarrow q)\Leftrightarrow (p\wedge\neg q)\vee(\neg p\wedge q)
21 p\leftrightarrow q\Leftrightarrow q\leftrightarrow p
22 p\leftrightarrow p\Leftrightarrow 1
23 (p\leftrightarrow q)\wedge(q\leftrightarrow r)\Rightarrow(p\leftrightarrow r)

Voorbeeld

We leiden regel 20 af uit 19.

\begin{array}{lll} \neg(p\leftrightarrow q) & \displaystyle\mathop{\Leftrightarrow}_{19} & \neg((p\wedge q)\vee(\neg p\wedge\neg q)) \\ & \displaystyle\mathop{\Leftrightarrow}_{13} & \neg(p\wedge q)\wedge\neg(\neg p\wedge\neg q) \\ & \displaystyle\mathop{\Leftrightarrow}_{13} & (\neg p\vee\neg q)\wedge(\neg\neg p\vee\neg\neg q) \\ & \displaystyle\mathop{\Leftrightarrow}_{11} & (\neg p\vee\neg q)\wedge(p\vee q) \\ & \displaystyle\mathop{\Leftrightarrow}_{3} & (\neg p\wedge p)\vee(\neg p\wedge q)\vee (\neg q\wedge p)\vee(\neg q\wedge q) \\ & \displaystyle\mathop{\Leftrightarrow}_{12} & 0\vee(\neg p\wedge q)\vee(\neg q\wedge p)\vee0 \\ & \displaystyle\mathop{\Leftrightarrow}_{4} & (\neg p\wedge q)\vee(\neg q\wedge p) \\ & \displaystyle\mathop{\Leftrightarrow}_{1} & (\neg q\wedge p)\vee(\neg p\wedge q) \\ & \displaystyle\mathop{\Leftrightarrow}_{1} & (p\wedge\neg q)\vee(\neg p\wedge q) \end{array}

Voorbeeld

De exclusieve of \oplus is gedefinieerd met een waarheidstabel. Uit deze tabel blijkt dat p\oplus q logisch equivalent is met \neg(p\leftrightarrow q). Uit regel 20 blijkt dat p\oplus q\Leftrightarrow (p\wedge\neg q)\vee(q\wedge\neg p).

Voorbeeld

Het Sheffer-streepje of NAND poort is gedefinieerd met een waarheidstabel. Uit deze tabel blijkt dat p\uparrow q logisch equivalent is met \neg(p\wedge q). Het blijkt dat je alle logische connectieven kunt beschrijven met behulp van de Sheffer streep. Practisch gezien betekent dit dat alle logische schakelingen zijn te bouwen met behulp van NAND poorten. Hier zie je een overzicht van de vervangingsregels:
Connectief met Sheffer streep
\neg p p\uparrow p
p\wedge q (p\uparrow q)\uparrow(p\uparrow q)
p\vee q (p\uparrow p)\uparrow(q\uparrow q)
Met behulp van regels 14 en 19 kun je dan ook de implicatie en de equivalentie herschrijven tot een uitdrukking met allen Sheffer streepjes.

De ontkenning kun je als volgt met de Sheffer streep maken:

p\uparrow p\Leftrightarrow\neg(p\wedge p)\displaystyle\mathop{\Leftrightarrow}_{6}\neg p.

Op soortgelijke wijze zie je dat p\vee q volgens regel 11 equivalent is met \neg\neg(p\vee q), welke volgens 13 equivalent is met \neg(\neg p\wedge\neg q). Dus

p\vee q\Leftrightarrow\neg(\neg p\wedge\neg q)\Leftrightarrow(\neg p)\uparrow(\neg q) \Leftrightarrow(p\uparrow p)\uparrow(q\uparrow q).

Voorbeeld

Een belangrijke regel is de modus ponens. In de taal van de propositielogica luidt deze regel

p\wedge(p\rightarrow q)\Rightarrow q.
De modus ponens drukt uit dat je de conclusie q pas uit de implicatie p\rightarrow q mag trekken als aan de voorwaarde p voldaan is. De modus ponens kun je als volgt bewijzen:
\begin{array}{lll} p\wedge(p\rightarrow q) & \displaystyle\mathop{\Leftrightarrow}_{14} & p\wedge(\neg p\vee q) \\ & \displaystyle\mathop{\Leftrightarrow}_{3} & (p\wedge\neg p)\vee(p\wedge q) \\ & \displaystyle\mathop{\Leftrightarrow}_{12} & 0\vee(p\wedge q) \\ & \displaystyle\mathop{\Leftrightarrow}_{4} & p\wedge q \\ & \displaystyle\mathop{\Rightarrow}_{8} & q. \end{array}
Let op de laatste stap. Hier wordt geen logische equivalentie gebruikt, maar een een implicatie.