TU/e
Mike Boldy en Hans Cuypers

Propositielogica en verzamelingen

Je kunt alle rekenregels voor verzamelingen bewijzen met behulp van de propositielogica. Daarvoor moet je x\in A opvatten als een propositie. Het complement van A bestaat uit alle elementen die niet in A zitten, dus de propositie x\in\overline{A} is equivalent met \neg x\in A.

Voor de doorsnede en de vereniging kun je hetzelfde kunstje doen. De propositie x\in A\cap B kun je dan herschrijven als x\in A\wedge x\in B. En de propositie x\in A\cup B kun je dan herschrijven als x\in A\vee x\in B. Op die manier is iedere verzameling die is opgebouwd uit doorsnede, vereniging en complement om te schrijven naar een propositie.

Dit principe kun je toepassen om de gelijkheid van twee verzamelingen aan te tonen. Twee verzamelingen A en B zijn gelijk als de proposities x\in A en x\in B logisch equivalent zijn.

Opmerking

Eigenlijk is x\in A geen propositie maar een predicaat, omdat er een onbekende x in zit. Voor de methode die we hier behandelen maakt het echter niets uit.

Opmerking

Het symmetrisch verschil A\div B van correspondeert met de exclusieve of.

x\in A\div B\Leftrightarrow x\in A\oplus x\in B.

Opmerking

Voor het verschil A\setminus B van twee verzamelingen is er geen corresponderende logisch connectief. Maar je kunt het verschil eenvoudig uitdrukken met behulp van het complement en de doorsnede: A\setminus B=A\cap\overline{B}. Dus

x\in A\setminus B\Leftrightarrow x\in A\wedge\neg(x\in B).

Opmerking

Als je aantoont dat x\in B volgt uit x\in A, dan heb je slechts de inclusie A\subset B bewezen. Om aan te tonen dat A en B gelijk zijn moet je dus twee implicaties bewijzen, namelijk x\in A\rightarrow x\in B en x\in B\rightarrow x\in A.

Voorbeeld

De regel van De Morgan zegt dat \overline{A\cap B}=\overline{A}\cap\overline{B}. Dit kun je eenvoudig bewijzen met behulp van de logsiche wet \neg(p\wedge q)\Leftrightarrow\neg p\vee\neg q:

\begin{array}{lll} x\in\overline{A\cap B} & \displaystyle\mathop{\Leftrightarrow}_{} & \neg(x\in A\cap B) \\ & \displaystyle\mathop{\Leftrightarrow}_{} & \neg(x\in A\wedge x\in B) \\ & \displaystyle\mathop{\Leftrightarrow}_{} & \neg(x\in A)\vee\neg(x\in B) \\ & \displaystyle\mathop{\Leftrightarrow}_{} & x\in\overline{A}\vee x\in\overline{B} \\ & \displaystyle\mathop{\Leftrightarrow}_{} & x\in\overline{A}\cup\overline{B}. \end{array}

Voorbeeld

In het algemen bestaan gelijkheidsbewijzen van verzamelingen uit twee inclusies. In sommige gevallen zijn deze bewijzen ondoenlijk ingewikkeld. Een typisch voorbeeld is het symmetrisch verschil. Directe bewijzen met het symmetrisch verschil zijn niet prettig om te lezen, laat staan om ze te leveren. Door over te gaan op propositielogica gaat alles een stuk vlotter.

Stel je wilt de volgende gelijkheid bewijzen:

(A\div B)\div C=A\div(B\div C).
We gaan over op propositielogica, en bewijzen
(x\in A\oplus x\in B)\oplus x\in C=x\in A\oplus(x\in B\oplus x\in C).
Om de formules wat meer leesbaar te maken voeren we de volgende notaties in: p\Leftrightarrow(x\in A), q\Leftrightarrow(x\in B) en r\Leftrightarrow(x\in C). Maak nu een waarheidstabel:
(1) (2) (3) (4) (5) (6) (7) \\
p q r p\oplus q (p\oplus q)\oplus r q\oplus r p\oplus(q \oplus r)
0 0 0 0 0 0 0
0 0 1 0 1 1 1
0 1 0 1 1 1 1
0 1 1 1 0 0 0
1 0 0 1 1 0 1
1 0 1 1 0 1 0
1 1 0 0 0 1 0
1 1 1 0 1 0 1
Uit de gelijkheid van kolom (5) en (7) volgt (p\oplus q)\oplus r\Leftrightarrow p\oplus(q \oplus r).