wetten van de Morgan

© h.hofstede (h.hofstede@hogeland.nl)

De wetten van de Morgan.

Misschien is het je in de vorige lessen al opgevallen; de tekens ∧ en ∨ werken een beetje als elkaars omgekeerde.
Zo was een bijvoorbeeld (p₁ ∧ ¬ p₁) een contradictie, maar daarentegen was (p₁ ∨ ¬ p₁) nou juist een tautologie.
Dat omgekeerde effect komen we ook weer tegen als we de distributiviteit gaan bekijken.

En dat gaan we nu doen.

Bij gewone getallen gaf de distributieve eigenschap aan, hoe een getal dat voor haakjes staat, verdeeld moet worden over de getallen binnen die haakjes. Dingen als 2 • (x + 4) = 2 • x + 2 • 4. Die 2 verdeel je over de x en de 4.
Hoe werkt dat bij onze tekens?

NIET.
Laten we beginnen met NIET met haakjes.

Neem de formule ¬ ( p₁ ∨ p₂). Kunnen we de haakjes wegwerken, en hoe verdeelt ¬ die zich dan?

Laten we een voorbeeld nemen.
Stel p₁ = "ik heb een hond" en p₂ = "ik heb een kat".
Dan is dus ( p₁ ∨ p₂) de bewering "ik heb een hond of ik heb een kat".
Dan is ¬ ( p₁ ∨ p₂) de bewering: NIET(ik heb een hond of ik heb een kat) ofwel in iets normaler Nederlands: "Het is NIET zo dat ik een hond of een kat heb"
Nou, dat kan alleen maar kloppen als je geen van beiden hebt. Dus deze bewering is gelijk met "Ik heb geen hond en ik heb geen kat".
conclusie:

¬ (p₁ ∨ p₂) ⇔ ¬ p₁ ∧ ¬ p₂

Ik vermoed al wel wat er gebeurt als we EN in OF veranderen, maar laten we toch nog even kijken.

Stel p₁ = "ik heb een moord gepleegd" en p₂ = "ik heb een bank beroofd "
Dan is dus ( p₁ ∧ p₂) de bewering "ik heb een moord gepleegd en ik heb een bank beroofd".
Dan is ¬ ( p₁ ∧ p₂) de bewering: NIET(ik heb een moord gepleegd en ik heb een bank beroofd) ofwel in iets normaler Nederlands: "Het is NIET zo dat ik een moord gepleegd heb en een bank heb beroofd".
Nou, dat klopt zodra ik één van beiden niet heb gedaan. Dus deze bewering is gelijk met "Ik heb geen moord gepleegd of geen bank beroofd". (Gelukkig kan deze OF ook betekenen dat ik beiden niet heb gedaan).
conclusie:

¬ (p₁ ∧ p₂) ⇔ ¬ p₁ ∨ ¬ p₂

Natuurlijk kunnen we deze beide regels makkelijk met waarheidstabellen controleren. Dat laat ik daarom maar over aan opgave 1. Deze twee regels heten trouwens ook wel de wetten van de Morgan.
Ze leveren een manier om ∧ en ∨ in elkaar te veranderen, mocht je dat willen, kijk maar:

(p₁ ∧ p₂) = ¬ ¬ (p₁ ∧ p₂ ) = ¬ (¬ p₁ ∨ ¬ p₂)
(p₁ ∨ p₂) = ¬ ¬ (p₁ ∨ p₂ ) = ¬ (¬ p₁ ∧ ¬ p₂)

EN/OF

Hoe is het als er ∧ of ∨ voor haakjes staat?
We bekijken de twee eenvoudigste voorbeelden.

(p₁ ∧ (p₂ ∨ p₃))
eerst maar weer een voorbeeldje.
p₁ = "Jan gaat morgen boodschappen bij Albert Hein doen"
p₂ = "Jan gaat morgen brood kopen"
p₃ = "Jan gaat morgen bier kopen"
Dan zegt de hele bewering

"Jan gaat morgen boodschappen doen bij Albert Hein en hij gaat daar brood of bier kopen"

Kortom dan zijn er voor Jan twee mogelijkheden:
• Hij gaat boodschappen doen bij Albert Hein en hij gaat brood kopen (p₁ ∧ p₂)
• Hij gaat boodschappen doen bij Albert Hein en hij gaat bier kopen (p₁ ∧ p₃)
Jan moet één van deze beiden doen (beiden mag ook), dus de eerste OF de tweede.
Dus ((p₁ ∧ p₂) ∨ (p₁ ∧ p₃))
Conclusie:

p₁ ∧ (p₂ ∨ p₃) ⇔ (p₁ ∧ p₂) ∨ (p₁ ∧ p₃)

Ik geef het tweede eenvoudige voorbeeld direct zonder aannemelijkmakerij. In opgave 2 bewijzen we netjes met een waarheidstabel dat dit allemaal klopt.

p₁ ∨ (p₂ ∧ p₃) ⇔ (p₁ ∨ p₂) ∧ (p₁ ∨ p₃)

Denk hierbij aan een bewering als: "Ik ga vanavond vroeg naar bed, of ik ga uit eten en naar de film".


OPGAVEN.

1.	Toon met behulp van waarheidstabellen aan dat geldt:

	a.	¬ (p₁ ∨ p₂) ⇔ ¬ p₁ ∧ ¬ p₂
	b.	¬ (p₁ ∧ p₂) ⇔ ¬ p₁ ∨ ¬ p₂

2.	Toon met behulp van waarheidstabellen aan dat geldt:

	a.	p₁ ∧ (p₂ ∨ p₃) ⇔ (p₁ ∧ p₂) ∨ (p₁ ∧ p₃)
	b.	p₁ ∨ (p₂ ∧ p₃) ⇔ (p₁ ∨ p₂) ∧ (p₁ ∨ p₃)