Naar inhoud springen

Verzamelingen/Wetten van de Morgan

Uit Wikibooks

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[bewerken]

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:

en

Bewijs[bewerken]

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

p q pq
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 pq Waar, dus is Onwaar. Etc.

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

p q p 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 en dezelfde waarde, de uitdrukkingen zijn dus identiek.

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

Wetten van de Morgan voor verzamelingen[bewerken]

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

  • (A ∩ B)c=Ac ∪ Bc
  • (A ∪ B)c=Ac ∩ Bc

Bewijs[bewerken]

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 aC - (A∪B). Volgens de definitie van de verzameling X-Y geldt dan dus dat aC en aA∪B. Dat laatste betekent dat aA en dat aB. Kortom (aC en aA) en (aC en aB), oftewel aC-A en aC-B. ==> C - (A∪B) ⊆ (C-A)∩(C-B).(resultaat (i))

Dan moeten we nog de andere kant uit bewijzen:
Laat a(C-A)∩(C-B). ==> aC-A en aC-B.
aC-A ==> aC en aA
aC-B ==> aC en aB
Uit aA en aB ==> aA∪B
==> aA en aA∪B ==> a 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(C - (A∩B)) ==>
aC a(A∩B) ==>
aC (aA aB) ==>
(Noem aA even p en noem aB even q. Dan kunnen we (p q) volgens de 2e wet van Morgan voor logica herschrijven als p q)
aC ( a A a B) ==>
aC ( a A a B) (gebruik eigenschap 6.3) ==>
(a(C-A) (a(C-B)).
Oftewel C - (A∩B) ⊆ (C-A)∪(C-B)

Dan hebben we nog de andere kant uit te bewijzen, dus (C-A)∪(C-B) ⊆ C - (A∩B). Dit bewijs geven we als opgave.

Engels[bewerken]

(geen)

Opgaven[bewerken]

VII.1 Toon aan dat .
VII.2 Toon aan dat (C-A)∪(C-B) ⊆ C - (A∩B)


Samenvatting: In dit hoofdstuk heb je geleerd wat de wetten van de Morgan zijn.

← Inleiding in de booleaanse logica Wetten van de Morgan Oplossingen opgaven →
Informatie afkomstig van https://nl.wikibooks.org Wikibooks NL.
Wikibooks NL is onderdeel van de wikimediafoundation.