TU/e
Mike Boldy en Hans Cuypers

Logische wetten

Voor de quantoren gelden allerlei eigenschappen en stellingen. Op deze pagina zie je de meest gebruikte bij elkaar in een tabel. Ook voor de quantoren geldt het dualiteitsprincipe. Als je in een logische equivalentie de \wedge vervangt door \vee (en omgekeerd), en tegelijkertijd de \forall door \exists (en omgekeerd), krijg je weer een logische equivalentie.

Verwisselen van quantoren
1 \forall_x\forall_y[p(x,y)]\Leftrightarrow\forall_y\forall_x[p(x,y)] \exists_x\exists_y[p(x,y)]\Leftrightarrow\exists_y\exists_x[p(x,y)]
2 \multicolumn{2}{c}{\exists_x\forall_y[p(x,y)]\Rightarrow\forall_y\exists_x[p(x,y)]}
Conjunctie en disjunctie
3 p\wedge\forall_x[q(x)]\Leftrightarrow\forall_x[p\wedge q(x)] p\vee\exists_x[q(x)]\Leftrightarrow\exists_x[p\vee q(x)]
4 p\vee\forall_x[q(x)]\Leftrightarrow\forall_x[p\vee q(x)] p\wedge\exists_x[q(x)]\Leftrightarrow\exists_x[p\wedge q(x)]
5 \forall_x[p(x)]\wedge\forall_x[q(x)]\Leftrightarrow\forall_x[p(x)\wedge q(x)] \exists_x[p(x)]\vee\exists_x[q(x)]\Leftrightarrow\exists_x[p(x)\vee q(x)]
6 \forall_x[p(x)]\vee\forall_x[q(x)]\Rightarrow\forall_x[p(x)\vee q(x)] \exists_x[p(x)]\wedge\exists_x[q(x)]\Rightarrow\exists_x[p(x)\wedge q(x)]
Ontkenning
7 \neg\forall_x[p(x)]\Leftrightarrow\exists_x[\neg p(x)] \neg\exists_x[p(x)]\Leftrightarrow\forall_x[\neg p(x)]

Let er op dat niet alle regels uit logische equivalenties bestaan. Regels 2 en 6 bevatten slechts een implicatiepijl \Rightarrow.

Regels 3 en 4 kun je gebruiken om quantoren ``buiten haakjes'' te halen. Beschouw de bewering

\forall_y\left[\forall_x[p(x)]\wedge q(y)\right].
We definiëren p_0\Leftrightarrow\forall_x[p(x)], dan
\begin{array}{lll} \forall_y\left[\forall_x[p(x)]\wedge q(y)\right] & \Leftrightarrow & \forall_y[p_0\wedge q(y)] \\ & \displaystyle\mathop{\Leftrightarrow}_{3} & p_0\wedge\forall_y[q(y)] \\ & \Leftrightarrow & \forall_x[p(x)]\wedge\forall_y[q(y)] \\ & \Leftrightarrow & \forall_x[p(x)]\wedge\forall_x[q(x)] \\ & \displaystyle\mathop{\Leftrightarrow}_{5} & \forall_x[p(x)\wedge q(x)]. \end{array}

Regel 7 vertelt je waarom het handig is om voor een leeg universum af te spreken dat \forall_x[p(x)] waar is. De ontkenning \neg\forall_x[p(x)] is volgens regel 7 equivalent met \exists_x[\neg p(x)], en dat is onwaar als het universum leeg is. De bewering \forall_{x\in\emptyset}[p(x)] is dus waar voor ieder predicaat~p.

Voorbeeld

Een functie f neemt een globaal maximum aan in a als f(x)\leq f(a) voor alle x. Dit betekent

\forall_x[f(x)\leq f(a)].
Een functie f heeft een maximum als er een a bestaat met deze eigenschap, dus als
\exists_a\forall_x[f(x)\leq f(a)].
Een functie heeft dus geen maximum als de ontkenning hiervan waar is, dus als
\forall_a\exists_x[f(x)> f(a)].

Voorbeeld

Regel 7 is goed te begrijpen met behulp van het schakelaarmodel.

De ontkenning \neg\forall_x[p(x)] is waar als er tenminse één schakelaar open staat, dus als \exists_x[\neg p(x)].
De ontkenning \neg\exists_x[p(x)] is waar als alle schakelaars open staan, dus als \forall_x[\neg p(x)].

Voorbeeld

De definitie van het begrip `priemgetal' luidt als volgt:

Een natuurlijk getal p is een priemgetal als het ongelijk aan 0 of 1 is, en als het alleen de delers 1 en p heeft.
Hoe kun je deze definitie opschrijven in predicatenlogica?

We beginnen eerst met het begrip ``a is een deler van b''. We noteren dit als a|b. De definitie luidt

a|b\Leftrightarrow\exists_q[a\cdot q=b].

De bewering ``p is een priemgetal'' kun je als volgt formuleren:

p\geq2\wedge\forall_d[d|p\rightarrow d=1\vee d=p].
Met behulp van de logische wetten kun je nu eenvoudig bepalen wanneer een getal p geen priemgetal is:
\begin{array}{lll} p \mbox{ is niet priem} & \Leftrightarrow & \neg\left(p\geq2\wedge\forall_d[d|p\rightarrow d=1\vee d=p]\right) \\ & \Leftrightarrow & p<2\vee\neg\left(\forall_d[d|p\rightarrow d=1\vee d=p]\right) \\ & \Leftrightarrow & p<2\vee\exists_d[\neg(d|p\rightarrow d=1\vee d=p)] \\ & \Leftrightarrow & p<2\vee\exists_d[\neg(\neg(d|p)\vee d=1\vee d=p)] \\ & \Leftrightarrow & p<2\vee\exists_d[d|p\wedge d\neq1\wedge d\neq p] \end{array}
In woorden: p is geen priemgetal als p=0 of p=1 of als p een deler heeft die ongelijk is aan 1 en p.