TU/e
Mike Boldy en Hans Cuypers

Vereniging, doorsnede en complement

Definitie

De vereniging, doorsnede en het complement kunnen worden gedefinieerd met behulp van de logische operaties \vee (of), \wedge (en) en \neg (niet). Zie ook het hoofdstuk over logica.

Let op bij de definitie van het complement. ``Alles dat niet in A zit'' is te veel van het goede. Alleen die elementen die in het universum U zitten doen mee in het complement. Dit betekent dat je vooraf moet weten wat het universum is. Overigens schrijft men vaak \overline{A}=\{x\in U|x\not\in A\}

Zonder bewijs vermelden we hier de meest gebruikte rekenregels. De regels komen voor in paren. Dit noemt men het dualiteitsprincipe. Het houdt in dat als je in een regel \cap vervangt door \cup en omgekeerd, en je doet hetzelfde met \emptyset en U, dan krijg je weer een rekenregel. Als in een regel de inclusie \subset voorkomt, vervang deze dan door \supset (en omgekeerd).

Vereniging en doorsnede
1 A\cup B=B\cup A A\cap B=B\cap A
2 (A\cup B)\cup C=A\cup(B\cup C) (A\cap B)\cap C=A\cap(B\cap C)
3 A\cup(B\cap C)=(A\cup B)\cap(A\cup C) A\cap(B\cup C)=(A\cap B)\cup(A\cap C)
4 A\cup\emptyset=A A\cap U=A
5 A\cup U=U A\cap\emptyset=\emptyset
6 A\cup A=A A\cap A=A
7 A\cup(A\cap B)=A A\cap(A\cup B)=A

Complement
8 \overline{\emptyset}=U \overline{U}=\emptyset
9 \multicolumn{2}{l}{\overline{\overline{A}}=A}
10 A\cup\overline{A}=U A\cap\overline{A}=\emptyset
11 \overline{A\cup B}=\overline{A}\cap\overline{B} \overline{A\cap B}=\overline{A}\cup\overline{B}

Inclusie
12 A\subset A\cup B en B\subset A\cup B A\cap B\subset A en A\cap B\subset B
13 Als A\subset C en B\subset C, dan A\cup B\subset C Als A\subset B en A\subset C, dan A\subset B\cap C
14 A\subset B dan en slechts dan als A\cup B=B A\subset B dan en slechts dan als A\cap B=A

Complement en inclusie
A\subset B dan en slechts dan als \overline{B}\subset\overline{A}

Regel 1 noemt men wel de commutativiteit van de vereniging en doorsnede. Varianten die met behulp van de commutativiteit zijn af te leiden zijn niet in de lijst met regels opgenomen. Bijvoorbeeld bij regel 4 zou zou je verwachten: \emptyset\cup A=A. Maar deze regel kun je eenvoudig als volgt afleiden:

\emptyset\cup A\mathop{=}_{1}A\cup\emptyset\mathop{=}_{4}A.

Vanwege regel 2 is het toegestaan om A\cup B\cup C te schrijven in plaats van (A\cup B)\cup C of A\cup(B\cup C). Hetzelfde geldt voor de doorsnede.

Regel 11 staat ook bekend als de regel van de Morgan.

Regels 9 en 14 hebben zichzelf als duale regel. Vandaar dat er maar één regel op de betreffende rij vermeld staat.

Let op: `disjunct' wil niet zeggen `verschillend'. Er geldt namelijk \emptyset\cap\emptyset=\emptyset, dus \emptyset en \emptyset zijn disjunct! Dit is ook het enige voorbeeld. Als A en B disjunct zijn en A=B, dan geldt A=B=\emptyset. Dit volgt uit regel 6:

A\mathop{=}_{6}A\cap A=A\cap B=\emptyset.

Voorbeeld

Stel A=\{1,2,3\} en B=\{2,3,4,5,6\}. Kies als universum U=\mathbb N=\{0,1,2,3,\ldots\}, dan
A\cup B=\{1,2,3,4,5,6\},
A\cap B=\{2,3\},
\overline{A}=\{0,4,5,6,\ldots\}
en
\overline{B}=\{0,1,7,8,9,\ldots\}.

Voorbeeld

Regel 7 kun je met behulp van het vorige voorbeeld verifiëren:

A\cup(A\cap B)=\{1,2,3\}\cup\{2,3\}=\{1,2,3\}=A
en
A\cap(A\cup B)=\{1,2,3\}\cap\{1,2,3,4,5,6\}=\{1,2,3\}=A.

Voorbeeld

De lijst van rekenregels in niet minimaal. Zo kan je regel 7 afleiden uit regels 1, 12 en 14. Uit 12 volgt A\cap B\subset A, dus volgens 14 geldt: (A\cap B)\cup A=A. Gebruik nu regel 1: A\cup(A\cap B)=(A\cap B)\cup A=A.

Voorbeeld

Dat de rechterbewering van regel 14 de duale van de linker is, is niet direct duidelijk. Als je in de linkerregel \cup vervangt door \cap, en \subset door \supset, krijg je niet de rechterregel. Er moet nog wat extra's gedaan worden. Dit gaat als volgt. Begin met de linkerregel (``dan en slechts dan'' is vervangen door \Leftrightarrow):

A\subset B\Leftrightarrow A\cup B=A.
Schrijf de duale regel op:
A\supset B\Leftrightarrow A\cap B=A.
Vervang alle A-s door B-s en vervang alle B-s door A-s:
B\supset A\Leftrightarrow B\cap A=B.
De uitdrukking B\supset A is equivalent met A\subset B:
A\subset B\Leftrightarrow B\cap A=B.
Gebruik tenslotte regel 1:
A\subset B\Leftrightarrow A\cap B=B.

Voorbeeld

De rekenregels kun je gebruiken om nieuwe stellingen te bewijzen. Een voorbeeld is de complementstelling:

Twee verzamelingen A en B zijn elkaars complement dan en slechts dan als het universum de disjuncte vereniging is van A en B.
Twee verzamelingen A en B zijn elkaars complement als \overline{A}=B. Dit is equivalent met A=\overline{B} (dit volgt uit regel 9). Het universum is de disjuncte vereniging van A en B betekent dat A\cap B=\emptyset en dat U=A\cup B. In wiskundige notatie ziet de stelling er dus als volgt uit (het symbool \wedge betekent ``en''):
\overline{A}=B\Leftrightarrow A\cap B=\emptyset\wedge A\cup B=U.
Je moet twee implicaties bewijzen:
  1. \overline{A}=B\Rightarrow A\cap B=\emptyset\wedge A\cup B=U, en
  2. A\cap B=\emptyset\wedge A\cup B=U\Rightarrow\overline{A}=B, en

Het bewijs van implicatie 1 is eenvoudig: Stel \overline{A}=B, dan

A\cap B=A\cap\overline{A}\mathop{=}_{10}\emptyset
en
A\cup B=A\cup\overline{A}\mathop{=}_{10}U.
Het nummer onder het gelijkteken verwijst naar de gebruikte rekenregel.

Het bewijs van implicatie 2 is een stuk lastiger. Je moet het volgende doen: stel A\cap B=\emptyset en A\cup B=U, bewijs dan dat \overline{A}=B. Merk op dat je de gelijkheid van twee verzamelingen moet aantonen. We doen dit met twee inclusies, dus we bewijzen eerst \overline{A}\subset B en dan B\subset\overline{A}. De eerste inclusie gaat als volgt:

\begin{array}{lll} \overline{A} & \displaystyle\mathop{=}_{4} & \overline{A}\cap U \\ & = & \overline{A}\cap(A\cup B) \\ & \displaystyle\mathop{=}_{3} & (\overline{A}\cap A)\cup(\overline{A}\cap B) \\ & \displaystyle\mathop{=}_{5} & \emptyset\cup(\overline{A}\cap B) \\ & \displaystyle\mathop{=}_{4} & \overline{A}\cap B \\ & \displaystyle\mathop{\subset}_{12} & B. \\ \end{array}

De tweede inclusie gaat bijna net zo, maar eerst schrijven we U anders, namelijk

\overline{A}\cup\overline{B}\mathop{=}_{11}\overline{A\cap B}=\overline{\emptyset} \mathop{=}_{8}U.
\begin{array}{lll} B & \displaystyle\mathop{=}_{4} & B\cap U \\ & = & B\cap(\overline{A}\cup\overline{B}) \\ & \displaystyle\mathop{=}_{3} & (B\cap\overline{A})\cup(B\cap\overline{B}) \\ & \displaystyle\mathop{=}_{5} & (B\cap\overline{A})\cup\emptyset \\ & \displaystyle\mathop{=}_{4} & B\cap\overline{A} \\ & \displaystyle\mathop{\subset}_{12} & \overline{A}. \\ \end{array}