Verzamelingen/Wetten van de Morgan

Na het bestuderen van dit hoofdstuk:

Weet je wat de wetten van de Morgan voor verzamelingen zijn

Kun je deze twee wetten gebruiken

August de Morgan was een wiskundige en logicus die leefde van 1806 tot 1871.

Wetten van de Morgan voor logische beweringen

In de inleiding noemden we al dat er een stevig verband ligt tussen de logica en de leer van de verzamelingen. In het vorige hoofdstuk gaven we een introductie in de booleaanse en propositie logica.

De wetten van de Morgan voor de propositielogica zijn:

\neg (p\lor q)\iff (\neg p)\land (\neg q),

en

\neg (p\land q)\iff (\neg p)\lor (\neg q)

Bewijs

Voor het bewijs maken we gebruik van waarheidstabellen: we schrijven de verschillende combinaties van de waarden van p en q uit:

p	q	p $\lor$ q	$\lnot (p\lor q)$
W	W	W	O
W	O	W	O
O	W	W	O
O	O	O	W

Als P waar is, en q waar is, dan is p $\lor$ q Waar, dus $\lnot (p\lor q)$ is Onwaar. Etc.

Hiermee hebben we de linkerhelft van de eerste wet van Morgan uitgewerkt. Dan blijft de rechter helft over:

p	q	$\lnot$ p	$\lnot$ q	$(\lnot p)\land (\lnot q)$
W	W	O	O	O
W	O	O	W	O
O	W	W	O	O
O	O	W	W	W

Bij elke zelfde combinatie van de waarden van p en q krijgen we voor $\lnot (p\lor q)$ en $(\lnot p)\land (\lnot q)$ dezelfde waarde, de uitdrukkingen zijn dus identiek.

Het bewijs van de tweede stelling is een van de opgaven.

Wetten van de Morgan voor verzamelingen

Laten A, B en C willekeurige verzamelingen zijn. Dan zijn de twee wetten van de Morgan voor verzamelingen:

(A ∩ B)^c=A^c ∪ B^c
(A ∪ B)^c=A^c ∩ B^c

Bewijs

Bekijk de iets krachtiger beweringen:

C - (A∪B) = (C-A)∩(C-B)
C - (A∩B) = (C-A)∪(C-B)

Deze zijn iets krachtiger, want door C=U=de universele verzameling te kiezen, hebben we de wetten van de Morgan.

We beginnen met:

C - (A∪B) = (C-A)∩(C-B)

Laat a $\in$ C - (A∪B). Volgens de definitie van de verzameling X-Y geldt dan dus dat a $\in$ C en a $\notin$ A∪B. Dat laatste betekent dat a $\notin$ A en dat a $\notin$ B. Kortom (a $\in$ C en a $\notin$ A) en (a $\in$ C en a $\notin$ B), oftewel a $\in$ C-A en a $\in$ C-B. ==> C - (A∪B) ⊆ (C-A)∩(C-B).(resultaat (i))

Dan moeten we nog de andere kant uit bewijzen:
Laat a $\in$ (C-A)∩(C-B). ==> a $\in$ C-A en a $\in$ C-B.
a $\in$ C-A ==> a $\in$ C en a $\notin$ A
a $\in$ C-B ==> a $\in$ C en a $\notin$ B
Uit a $\notin$ A en a $\notin$ B ==> a $\notin$ A∪B
==> a $\in$ A en a $\notin$ A∪B ==> a $\in$ C - (A∪B) ==> (C-A)∩(C-B) ⊆ C - (A∪B) (resultaat (ii))
We kunnen resultaat (i) en resultaat(ii) combineren tot C - (A∪B) = (C-A)∩(C-B).

Dan moeten we natuurlijk nog de tweede wet bewijzen. Ook deze doen we in twee stappen, eerste bewijzen we dat de linkerhelft een deelverzameling is van de rechterkant, en vervolgens bewijzen we dat de rechterkant een deelverzameling is van de linkerkant:

C - (A∩B) = (C-A)∪(C-B)

Laat a $\in$ (C - (A∩B)) ==>
a $\in$ C $\land$ a $\notin$ (A∩B) ==>
a $\in$ C $\land$ $\lnot$ (a $\in$ A $\land$ a $\in$ B) ==>
(Noem a $\in$ A even p en noem a $\in$ B even q. Dan kunnen we $\lnot$ (p $\land$ q) volgens de 2e wet van Morgan voor logica herschrijven als $\lnot$ p $\lor$ $\lnot$ q)
a $\in$ C $\land$ ( $\lnot$ a $\in$ A $\lor$ $\lnot$ a $\in$ B) ==>
a $\in$ C $\land$ ( a $\notin$ A $\lor$ a $\notin$ B) (gebruik eigenschap 6.3) ==>
(a $\in$ (C-A) $\lor$ (a $\in$ (C-B)).
Oftewel C - (A∩B) ⊆ (C-A)∪(C-B)