Propositierekenen

Hoofdstuk 4
Propositierekenen
4.1
Inleiding
In dit hoofdstuk maken we kennis met propositierekenen of propositiecalculus. Na het introduceren van de taal (alfabet en syntax) en 4 afleidingsregels, stellen we een lijst van axioma’s
voorop. Uit die axioma’s zullen we a.d.h.v. formeel redeneren stellingen brouwen. Behalve
in die stellingen zelf, zijn we vooral ge¨ınteresseerd in technieken om afleidingen of bewijzen
van stellingen te bekomen (opnieuw in calculationele stijl). Deze manipulatie van symbolen
verloopt volledig op syntactisch niveau. Pas daarna zullen we betekenis hechten aan de taal.
Tenslotte illustreren we het gebruik van propositierekenen voor het ontwerpen van digitale
schakelingen.
4.1.1
Alfabet en syntax
Net als bij de eenvoudige wiskundige uitdrukkingen is het alfabet van de propositiecalculus
samengesteld uit veranderlijken, constanten, unaire en binaire operatoren. Ook de syntax is
analoog.
Definitie 22 (Taal van het propositierekenen) De syntax wordt vastgelegd door de volgende herschrijfregels:
propositie
applicatie
veranderlijke
constante
cop 1
cop 2
::=
::=
::=
::=
::=
::=
veranderlijke | constante | applicatie .
(cop 1 propositie )|(propositie cop 2 propositie ).
x | y | z.
0 | 1.
¬.
≡ | 6≡ | ∨ | ∧ | ⇒ | ⇐ .
Een zin voortgebracht door het startsymbool propositie noemen we een propositie. De verzameling van alle proposities noteren we als P , en met V bedoelen we zoals gewoonlijk de
verzameling van veranderlijken.
I.p.v. propositie spreekt men soms ook over een goed gevormde formule (Engels: well–formed
formula, kortweg wff). Opnieuw zullen we een aantal afspraken maken om het gebruik van
haakjes binnen de perken te houden.
37
38
HOOFDSTUK 4. PROPOSITIEREKENEN
Afspraak 3 (Reductie van haakjes)
• Zoals gebruikelijk mogen we de buitenste haakjes probleemloos weglaten (probleemloos
omdat we ze op ondubbelzinnige wijze terug kunnen plaatsen).
• Haakjes rond de applicatie van een operator mogen weggelaten worden indien die applicatie optreedt als ´e´en van de argumenten van een binaire operator met lagere prioriteit.
De prioriteit is als volgt geregeld:
– De unaire operator ¬ heeft een hogere prioriteit dan de binaire operatoren.
– De binaire operatoren worden als volgt gerangschikt van hoogste naar laagste prioriteit: ∨ en ∧, ⇒ en ⇐, ≡ en 6≡. ∧ en ∨ zitten dus op hetzelfde niveau, dat hoger
is dan dat van ⇒ en ⇐. ≡ en 6≡ zitten op het laagste niveau.
• Haakjes rond een applicatie van ¬ mogen weggelaten worden.
• ⇒ is rechtsassociatief. x ⇒ y ⇒ z staat dus voor x ⇒ (y ⇒ z)
• ⇐ is linksassociatief. x ⇐ y ⇐ z staat dus voor (x ⇐ y) ⇐ z
Voorbeeld 29 Voorbeelden van proposities zijn
x
1
¬¬x x ⇒ y
¬x ∨ 0
(x ⇒ y) ∧ (y ⇒ x) ≡ (x ≡ y)
Voorbeeld 30 Wanneer we schrijven
x ⇒ y ⇒ (x ∧ z)
dan bedoelen we x ⇒ (y ⇒ (x ∧ z)) en dus niet (x ⇒ y) ⇒ (x ∧ z). Anderzijds, wanneer we
schrijven
x ⇐ y ⇐ (x ∧ z)
dan bedoelen we (x ⇐ y) ⇐ (x ∧ z) en dus niet x ⇐ (y ⇐ (x ∧ z)).
Afspraken omtrent het weglaten van haakjes m.b.t. associativiteit van de andere binaire operatoren zullen we maken bij het introduceren van de axioma’s (omdat die een verantwoording
geven voor die afspraken).
De operatoren uit de propositiecalculus hebben allemaal een eigen naam die nauw samenhangt met de gebruikelijke semantiek die eraan gehecht wordt. We zullen deze semantiek pas
op het einde van dit hoofdstuk bespreken, maar in onderstaande tabel vermelden we alvast de
gebruikelijke benamingen om vlotter over proposities te kunnen spreken in natuurlijke taal.
symbool
¬
≡
omschrijving
negatie (ontkenning)
equivalentie
¬x
x≡y
∨
∧
⇒
inequivalentie
exclusieve of
disjunctie
conjunctie
implicatie
x∨y
x∧y
x⇒y
⇐
gevolg
x⇐y
6≡
x 6≡ y
lees als
niet x
x is equivalent met y
x is nodig en voldoende voor y
x is niet equivalent met y
x xor y
x of y
x en y
x impliceert y, als x dan y
x is voldoende voor y
x volgt uit y
x is nodig voor y
39
4.1. INLEIDING
Binnen het propositierekenen vervult ≡ de rol van gelijkheid. In x∨y worden x en y disjuncten
genoemd. In x ∧ y worden x en y conjuncten genoemd. In x ⇒ y is x het antecedent en y
het consequent.
Substitutie van een (lijst van) veranderlijke(n) v door een (lijst van) propositie(s) q in een
propositie p, d.w.z.
p[v := q] of p[vq
verloopt volledig analoog als bij de eenvoudige wiskundige uitdrukkingen. We zullen verder
p, q, r en s gebruiken om willekeurige proposities aan te duiden, en v voor een willekeurige
veranderlijke.
4.1.2
Formeel redeneren
Een afleidingsregel in de propositiecalculus is een tabel van de vorm Pq met P een collectie
van proposities (de premissen) en q een propositie (het consequent). We maken gebruik van
4 afleidingsregels waarvan we er reeds 3 kennen, namelijk
Afleidingsregel 1 (Transitiviteit)
p ≡ q, q ≡ r
p≡r
voor alle proposities p, q en r.
Afleidingsregel 2 (Principe van Leibniz)
p≡q
r[v := p] ≡ r[v := q]
voor alle proposities p, q en r en elke veranderlijke v.
Afleidingsregel 3 (Instantiatie van een stelling)
p
p[v := q]
voor elke stelling p, (lijst van) veranderlijke(n) v en (lijst van) propositie(s) q.
We herinneren eraan dat een stelling de conclusie is van een afleiding waarvan de aannames
axioma’s zijn. Een propositie q is een conclusie van aannames H indien
• ofwel q tot H behoort
• ofwel q het consequent is van een afleidingsregel waarvan de premissen conclusies zijn
van de aannames uit H
Om de propositiecalculus krachtig genoeg te maken, voegen we nog een vierde afleidingsregel
toe.
Afleidingsregel 4 (Gelijkgestemdheid)
p, p ≡ q
q
voor alle proposities p en q.
Een afleiding of bewijs van een stelling is een georganiseerde weergave van hoe die stelling
wordt afgeleid uit axioma’s. We gebruiken hiervoor de calculationele stijl.
40
HOOFDSTUK 4. PROPOSITIEREKENEN
Axioma
Axioma
Axioma
Axioma
Axioma
Axioma
Axioma
Axioma
Axioma
Axioma
Axioma
Axioma
Axioma
Axioma
1
2
3
4
5
6
7
8
9
10
11
12
13
14
Associativiteit van ≡
Symmetrie van ≡
Definitie van 1
Definitie van 0
Semi–distributiviteit van ¬ t.o.v. ≡
Definitie van 6≡
Symmetrie van ∨
Associativiteit van ∨
Idempotentie van ∨
Distributiviteit van ∨ t.o.v. ≡
Uitgesloten derde
Gouden regel
Definitie van implicatie
Gevolg
((x ≡ y) ≡ z) ≡ (x ≡ (y ≡ z))
x≡y≡y≡x
1≡y≡y
0 ≡ ¬1
¬(x ≡ y) ≡ ¬x ≡ y
(x 6≡ y) ≡ ¬(x ≡ y)
x∨y ≡y∨x
(x ∨ y) ∨ z ≡ x ∨ (y ∨ z)
x∨x ≡ x
x ∨ (y ≡ z) ≡ x ∨ y ≡ x ∨ z
x ∨ ¬x ≡ 1
x∧y ≡x ≡ y ≡ x∨y
x ⇒y ≡x∨y ≡y
x⇐y≡y⇒x
Tabel 4.1: Axioma’s van de propositiecalculus
4.2
Axioma’s
Verschillende keuzes van axioma’s kunnen toch leiden tot dezelfde verzameling van stellingen.
Er bestaan heel wat mogelijkheden die nauw verband houden met de volgorde waarin axioma’s
over de verschillende symbolen uit de taal ge¨ıntroduceerd worden. Wat bij de ene aanpak een
axioma is, zal dan bij de andere aanpak opduiken als stelling (ook al is het daar geen axioma),
en omgekeerd. Tabel 4.1 bevat de 14 axioma’s die wij zullen gebruiken. Associativiteit doelt
op het plaatsen, verplaatsen en weglaten van haakjes. Dankzij axioma 1 (associativiteit van
≡) kunnen we schrijven
p≡q≡r
of we nu (p ≡ q) ≡ r of p ≡ (q ≡ r) bedoelen. In het tweede axioma is die afspraak omtrent
het weglaten van haakjes meteen toegepast. Haakjes kunnen daarin op verschillende manieren
teruggeplaatst worden die alle correct zijn, zoals ((x ≡ y) ≡ y) ≡ x of x ≡ (y ≡ (y ≡ x)).
Waarom bovenstaand axioma symmetrie wordt genoemd, wordt echter duidelijk wanneer we
de haakjes terugplaatsen als volgt
(x ≡ y) ≡ (y ≡ x)
Dankzij axioma 8 kunnen we schrijven
p∨q∨r
of we nu (p ∨ q) ∨ r of p ∨ (q ∨ r) bedoelen. Er zijn geen axioma’s omtrent associativiteit van 6≡
en ∧ opgenomen in Tabel 4.1 maar zoals we later zullen zien, zullen we die kunnen bewijzen
als stellingen (stellingen 11 en 19 uit Tabel 4.2). Het derde axioma definieert de constante 1.
Het vierde en vijfde axioma defini¨eren negatie ¬. Het zesde axioma definieert inequivalentie
6≡. Symmetrie van ∨ is opgenomen als axioma 7, terwijl de symmetrie van 6≡ en van ∧ ook
weer later zal opduiken als stelling (stellingen 10 en 18). ∨ wordt idempotent genoemd omdat,
bij axioma 9, x ∨ x even machtig is als x. Uit een latere stelling 20 zal blijken dat ∧ ook
4.3. STELLINGEN EN BEWIJZEN
41
idempotent is. Om de naam van axioma 10 beter te begrijpen, kan men vergelijken met de
distributiviteit van vermenigvuldiging t.o.v. optelling van getallen, b.v. 2 · (3 + 1) = 2 · 3 + 2 · 1.
Merk op dat men wegens de afspraken omtrent prioriteit axioma 10 moet lezen als
(x ∨ (y ≡ z)) ≡ (x ∨ y) ≡ (x ∨ z)
x ∨ ¬x uit axioma 11 kan men lezen als “x of niet x”; er wordt m.a.w. geen derde mogelijkheid
opengelaten. Axioma’s 12, 13 en 14 defini¨eren respectievelijk ∧, ⇒ en ⇐ in termen van eerder
in de axioma’s ingevoerde operatoren. De axioma’s dienen stuk voor stuk in hun geheel gelezen
te worden. Zo b.v. is het stukje x∧ y ≡ x van de gouden regel op zich geen axioma of stelling!
4.3
Stellingen en bewijzen
Tabellen 4.2 en 4.3 geven een overzicht van belangrijke stellingen uit de propositiecalculus die
kunnen afgeleid worden uit de hierboven gegeven axioma’s. We gaan nu dieper in op hoe deze
stellingen kunnen bewezen worden. We herinneren er nogmaals aan dat een bewijs van een
stelling een georganiseerde weergave is van hoe een stelling kan afgeleid worden uit axioma’s.
Een stelling kan meerdere bewijzen hebben. De georganiseerde weergave die wij gebruiken is
de calculationele stijl.
Het opstellen van een bewijs kan men doen op verschillende manieren, te vergelijken met
het schrijven van een computerprogramma. Zo kan men een “quick en dirty” stijl hanteren
waarbij men zo snel mogelijk iets wil hebben dat werkt (een werkend programma of bewijs)
en zich niets aantrekt van hoe het programma of het bewijs geschreven wordt. Deze handelswijze kan bruikbaar zijn wanneer de programmacode of het bewijs zelf achteraf niet meer
hoeft bekeken te worden. Dikwijls moet men achteraf echter wel teruggrijpen naar de code,
b.v. omdat er iets moet aan gewijzigd worden zodat het programma ook werkt voor een
verwant probleem, of omdat men de correctheid wil nagaan. Dit geldt net zozeer voor bewijzen
als voor computerprogramma’s, b.v. wanneer men een bewijs moet leveren voor een stelling die
goed lijkt op een stelling die reeds bewezen is, of wanneer men bij het afleiden van stellingen
een tegenstrijdigheid uitkomt en moet opzoeken in welk bewijs de fout zit (a.h.w. het debuggen
van bewijzen).
Net zoals een programmeerstijl is een mooie bewijsstijl een vrij persoonlijke aangelegenheid die men gaandeweg ontwikkelt. Er zijn uiteraard wel een aantal vuistregels die kunnen
bijdragen tot een goed leesbare stijl. Behalve aan de stellingen zelf van de propositiecalculus, zullen we in dit hoofdstuk dan ook veel aandacht besteden aan dergelijke vuistregels en
bewijsmethoden. Een eerste dergelijke vuistregel is: onderscheid hoofdzaken van bijzaken in
een bewijs. Zorg er m.a.w. voor dat de stappen die cruciaal zijn in het bewijs uitdrukkelijk
vermeld worden en niet overschaduwd worden door bijzaken. E´en van die typische bijzaken is
het plaatsen, verplaatsen en weglaten van haakjes. We maken daarom de volgende afspraak.
Afspraak 4 (Stilzwijgend gebruik van associativiteit van ≡ en ∨) Axioma 1 en axioma 8 mogen steeds zonder uitdrukkelijke vermelding gebruikt worden voor het plaatsen,
verplaatsen en weglaten van haakjes.
Let op: bovenstaande afspraak houdt geen verplichting in maar wel een vrijheid. Wanneer
axioma 1 of 8 cruciaal is in een bewijs (b.v. om de associativiteit van ∧ te bewijzen, zie stelling
19), dan mag er uiteraard wel een uitdrukkelijke vermelding opgenomen worden!
42
4.3.1
HOOFDSTUK 4. PROPOSITIEREKENEN
Stellingen m.b.t. equivalentie
Afspraak 5 (Stap in calculationele stijl) Het gebruik van een afleidingsregel met premisse p en consequent van de vorm q ≡ r noteren we in een bewijs in calculationele stijl
als
q ≡ hpi r
Merk op dat enkel de afleidingsregels “instantiatie van een stelling” en “principe van Leibniz”
hiervoor in aanmerking komen want de andere 2 hebben telkens 2 premissen. Zodadelijk
leggen we uit hoe de afleidingsregels m.b.t. transitiviteit en gelijkgestemdheid in ons plaatje
passen, maar eerst illustreren we bovenstaande afspraak met volgend voorbeeld:
x≡x≡y≡y
≡
h(x ≡ y ≡ y) ≡ xi
x≡x
De concrete invulling van het principe van Leibniz die hier gebruikt is, is
(x≡y≡y) ≡ x
(x≡z)[z:=x≡y≡y] ≡ (x≡z)[z:=x]
of nog
(x≡y≡y)≡x
x≡x≡y≡y ≡ x≡x
Een alternatieve manier om deze stap in een bewijs te schrijven is
x≡x≡y≡y
≡
hax2i
x≡x
waarbij i.p.v. het volledige axioma enkel een afkorting van de naam opgegeven wordt. Om de
leesbaarheid en de controleerbaarheid van een bewijs te verhogen, zullen we ook vaak (zeker
in het begin) beide schrijfwijzen combineren tot
x≡x≡y≡y
≡
hax2, (x ≡ y ≡ y) ≡ xi
x≡x
Afspraak 6 (Ketting in calculationele stijl) De stappen
q1
≡
hp1 i
r1
r1
≡
hp2 i
r2
en
mogen aan elkaar geregen worden tot een ketting
q1
≡
≡
hp1 i
hp2 i
r1
r2
Hierbij zijn p1 , p2 , q1 , r1 en r2 proposities. Dit geldt ook voor kettingen van meer dan 2
stappen.
Bovenstaande afspraak mogen we maken dankzij de afleidingsregel m.b.t. transitiviteit. Met
deze afleidingsregel volgt uit de premissen q1 ≡ r1 en r1 ≡ r2 immers q1 ≡ r2 , wat de schrijfwijze als ketting verantwoordt. We illustreren dit met een voorbeeld.
Bewijs van stelling 1
x≡x≡y≡y
≡
≡
hax2, (x ≡ y ≡ y) ≡ xi
hax2, x ≡ (y ≡ y ≡ x)i
x≡x
x≡y≡y≡x
4.3. STELLINGEN EN BEWIJZEN
43
(Oefening: schrijf de concrete invulling van Leibniz neer voor de 2e schakel.)
Merk op dat we bovenstaand voorbeeld reeds een “bewijs van stelling 1” noemen, ook al
moeten we strikt genomen nog een aantal afleidingsregels toepassen om echt aan stelling
1 uit Tabel 4.2 te geraken. Er zijn echter zoveel bewijzen die eindigen met juist dezelfde
toepassing van bepaalde afleidingsregels dat we liever algemene bewijsmethoden formuleren.
Zo’n bewijsmethode geeft aan waar je mag stoppen in je bewijs. Om te verklaren dat een
bewijsmethode correct is, moeten we eenmalig uitleggen dat je vanaf dat punt steeds het
volledige bewijs kan construeren.
Bewijsmethode 1 Om te bewijzen dat p ≡ q een stelling is, volstaat het om een ketting
neer te schrijven die
• ofwel p omzet in q
• ofwel q omzet in p
gebruik makend van het principe van Leibniz en instantiatie.
Verklaring: Het eerste geval is een aanvaardbaar bewijs dankzij de afleidingsregel m.b.t. transitiviteit. Het tweede geval levert ons op dezelfde manier eigenlijk een bewijs voor q ≡ p maar
m.b.v. de geschikte instantiatie van axioma 2, namelijk q ≡ p ≡ p ≡ q en de vierde afleidingsregel kunnen we daar steeds een bewijs voor p ≡ q uit halen.
De ketting die we gegeven hebben is dus eigenlijk een bewijs voor de stelling
(x ≡ x ≡ y ≡ y) ≡ (x ≡ y ≡ y ≡ x)
of nog
(x ≡ y ≡ y ≡ x) ≡ (x ≡ x ≡ y ≡ y)
waarbij de haakjes niet nodig zijn wegens axioma 1 maar wel mogen geplaatst worden om
de leesbaarheid te verhogen. We kunnen nu verder gebruik maken van het feit dat x ≡ y ≡
y ≡ x een axioma is (namelijk axioma 2) en de vierde afleidingsregel om te besluiten dat ook
x ≡ x ≡ y ≡ y een stelling is. Dit illustreert meteen een volgende bewijsmethode.
Bewijsmethode 2 Om te bewijzen dat p volstaat het te bewijzen dat
• ofwel r ≡ p
• ofwel p ≡ r
voor een stelling r.
Verklaring: Uit de premissen r en r ≡ p kan je immers met de vierde afleidingsregel afleiden
dat p een stelling is. In de praktijk is het dikwijls gemakkelijker te beginnen met p en van daar
uit op zoek te gaan naar een r zo dat p ≡ r een stelling is. Gebruik makend van instantiatie
van een stelling kan je uit axioma 2 (symmetrie van ≡) immers halen dat p ≡ r ≡ r ≡ p.
M.b.v. de vierde afleidingsregel en het feit dat p ≡ r een stelling is, bewijs je dan dat r ≡ p
44
HOOFDSTUK 4. PROPOSITIEREKENEN
een stelling is en dan ben je weer in het eerste geval.
Hieruit blijkt dat bewijsmethode 2 inderdaad kan gebruikt worden om p te bewijzen. Merk
op dat het bewijs van stelling r in theorie deel uitmaakt van het bewijs van p maar in de
praktijk gaan we dat uiteraard niet opnieuw opschrijven. Eens een stelling bewezen is, mogen
we er gebruik van blijven maken zonder telkens opnieuw het bewijs te herhalen. In het bewijs
van een stelling uit tabel 4.2 of 4.3 zullen we naast de axioma’s dan ook volop kunnen gebruik
maken van de reeds bewezen stellingen, d.w.z. stellingen met een lager volgnummer.
De afleidingsregels m.b.t. transitiviteit en gelijkgestemdheid zitten impliciet vervat in de
bovenstaande bewijsmethoden — het is vooral dankzij deze afleidingsregels dat de bewijsmethoden correct zijn. Omdat ze er impliciet in vervat zitten, hoeven we ze in de dagelijkse
praktijk van bewijsvoering echter niet uitdrukkelijk te vermelden.
De tweede stelling uit tabel 4.2 is opmerkelijk kort. Een bewijs dat gebruik maakt van bewijsmethode 2 verloopt als volgt:
Bewijs van stelling 2
1
≡
≡
hax3, 1 ≡ (y ≡ y) met y := 1i
hax3, 1 ≡ (y ≡ y)i
1≡1
1≡y≡y
De tweede stap is een zuivere toepassing van het principe van Leibniz. De eerste stap is een
toepassing van instantiatie van een stelling. Merk op dat we om de leesbaarheid te verhogen
bij de verantwoording hebben aangegeven wat hierbij de veranderlijke v is uit de algemene
formulering van de afleidingsregel voor instantiatie.
We hebben ondertussen al een aantal keer stilzwijgend gebruik gemaakt van axioma 1
om haakjes te plaatsen en weg te laten. Een ander axioma dat zo vaak gebruikt wordt dat
we het gebruik ervan in de toekomst vaak niet uitdrukkelijk zullen aangeven, is axioma 2
m.b.t. symmetrie van ≡ (het 2e geval van bewijsmethoden 1 en 2 bevat trouwens reeds een
impliciet gebruik van axioma 2).
Afspraak 7 (Stilzwijgend gebruik van symmetrie van ≡) Wanneer we als premisse voor
een afleidingsregel r ≡ q nodig hebben, b.v. voor een stap
e
≡
hr ≡ qi
e′
waarbij e en e′ proposities zijn, zullen we ook toelaten
e
≡
hq ≡ ri
e′
Axioma 2 laat immers toe te bewijzen dat r ≡ q een stelling is, gegeven dat q ≡ r een stelling
is. De tweede stap van het volgende bewijs van stelling 3 illustreert dit door combinatie van
Leibniz en symmetrie. Het bewijs volgt bewijsmethode 2.
Bewijs van stelling 3
x≡x
≡
≡
hst1, x ≡ x ≡ y ≡ yi
hax3, 1 ≡ y ≡ yi
y≡y
1
45
4.3. STELLINGEN EN BEWIJZEN
Stelling
Stelling
Stelling
Stelling
Stelling
Stelling
Stelling
Stelling
Stelling
Stelling
Stelling
Stelling
Stelling
Stelling
Stelling
Stelling
Stelling
Stelling
Stelling
Stelling
Stelling
Stelling
Stelling
Stelling
Stelling
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
Reflexiviteit van ≡
Dubbele negatie
Negatie van 0
Symmetrie van 6≡
Associativiteit van 6≡
Onderlinge associativiteit
Onderlinge verwisselbaarheid
Opslorpend element van ∨
Eenheidselement van ∨
Distributiviteit van ∨ t.o.v. ∨
Symmetrie van ∧
Associativiteit van ∧
Idempotentie van ∧
Eenheidselement van ∧
Opslorpend element van ∧
Distributiviteit van ∧ t.o.v. ∧
Contradictie
Absorptie
Stelling 26
Absorptie
Stelling 27
Stelling 28
Stelling 29
Distributiviteit van ∨ t.o.v. ∧
Distributiviteit van ∧ t.o.v. ∨
De Morgan
Stelling
Stelling
Stelling
Stelling
Stelling
Stelling
30
31
32
33
34
35
Vervanging
Exclusieve of
(a)
(b)
(a)
(b)
(a)
(b)
x≡x≡y≡y
1
x≡x
y≡1≡y
¬x ≡ y ≡ x ≡ ¬y
¬¬x ≡ x
¬0 ≡ 1
(x 6≡ y) ≡ ¬x ≡ y
¬x ≡ x ≡ 0
(x 6≡ y) ≡ (y 6≡ x)
((x 6≡ y) 6≡ z) ≡ (x 6≡ (y 6≡ z))
((x 6≡ y) ≡ z) ≡ (x 6≡ (y ≡ z))
x 6≡ y ≡ z ≡ x ≡ y 6≡ z
x∨1≡1
x∨0≡x
x ∨ (y ∨ z) ≡ (x ∨ y) ∨ (x ∨ z)
x ∨ y ≡ x ∨ ¬y ≡ x
x∧y ≡y∧x
(x ∧ y) ∧ z ≡ x ∧ (y ∧ z)
x∧x≡x
x∧1≡x
x∧0≡0
x ∧ (y ∧ z) ≡ (x ∧ y) ∧ (x ∧ z)
x ∧ ¬x ≡ 0
x ∧ (x ∨ y) ≡ x
x ∨ (x ∧ y) ≡ x
x ∧ (¬x ∨ y) ≡ x ∧ y
x ∨ (¬x ∧ y) ≡ x ∨ y
x ∨ (y ∧ z) ≡ (x ∨ y) ∧ (x ∨ z)
x ∧ (y ∨ z) ≡ (x ∧ y) ∨ (x ∧ z)
¬(x ∧ y) ≡ ¬x ∨ ¬y
¬(x ∨ y) ≡ ¬x ∧ ¬y
x ∧ y ≡ x ∧ ¬y ≡ ¬x
x ∧ (y ≡ z) ≡ x ∧ y ≡ x ∧ z ≡ x
x ∧ (y ≡ x) ≡ x ∧ y
(x ≡ y) ∧ (z ≡ x) ≡ (x ≡ y) ∧ (z ≡ y)
x ≡ y ≡ (x ∧ y) ∨ (¬x ∧ ¬y)
x 6≡ y ≡ (¬x ∧ y) ∨ (x ∧ ¬y)
Tabel 4.2: 1e reeks stellingen uit de propositiecalculus
46
HOOFDSTUK 4. PROPOSITIEREKENEN
Stelling
Stelling
Stelling
Stelling
Stelling
Stelling
Stelling
Stelling
Stelling
Stelling
Stelling
Stelling
Stelling
Stelling
Stelling
Stelling
Stelling
Stelling
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
Alternatieve definitie van ⇒
Alternatieve definitie van ⇒
Contrapositie
Stelling
Stelling
Stelling
Stelling
Stelling
Stelling
54
55
56
57
58
59
Modus ponens
Gevallenonderzoek
Gevallenonderzoek
Wederzijdse implicatie
Antisymmetrie
Transitiviteit
Distributiviteit van ⇒ t.o.v. ≡
Aftakking
Reflexiviteit van ⇒
Verzwakken
(a)
(b)
(c)
(d)
(e)
(a)
(b)
(c)
x ⇒ y ≡ ¬x ∨ y
x⇒y ≡ x∧y ≡ x
x ⇒ y ≡ ¬y ⇒ ¬x
x ⇒ (y ≡ z) ≡ x ∧ y ≡ x ∧ z
x ⇒ (y ≡ z) ≡ x ⇒ y ≡ x ⇒ z
x ⇒ (y ⇒ z) ≡ (x ⇒ y) ⇒ (x ⇒ z)
x ∧ y ⇒ z ≡ x ⇒ (y ⇒ z)
x ∧ (x ⇒ y) ≡ x ∧ y
x ∧ (y ⇒ x) ≡ x
x ∨ (x ⇒ y) ≡ 1
x ∨ (y ⇒ x) ≡ y ⇒ x
x∨y ⇒x∧y ≡x≡y
x⇒x≡1
x⇒1≡1
1⇒x≡x
x ⇒ 0 ≡ ¬x
0⇒x≡1
x⇒x∨y
x∧y ⇒x
x∧y ⇒x∨y
x ∨ (y ∧ z) ⇒ x ∨ y
x ∧ y ⇒ x ∧ (y ∨ z)
x ∧ (x ⇒ y) ⇒ y
(x ⇒ z) ∧ (y ⇒ z) ≡ (x ∨ y) ⇒ z
(x ⇒ z) ∧ (¬x ⇒ z) ≡ z
(x ⇒ y) ∧ (y ⇒ x) ≡ x ≡ y
(x ⇒ y) ∧ (y ⇒ x) ⇒ (x ≡ y)
(x ⇒ y) ∧ (y ⇒ z) ⇒ (x ⇒ z)
(x ≡ y) ∧ (y ⇒ z) ⇒ (x ⇒ z)
(x ⇒ y) ∧ (y ≡ z) ⇒ (x ⇒ z)
Tabel 4.3: 2e reeks stellingen uit de propositiecalculus
47
4.3. STELLINGEN EN BEWIJZEN
Om aan bovenstaand bewijs te geraken hebben we de te bewijzen stelling x ≡ x vergeleken
met de axioma’s en de reeds bewezen stellingen 1 en 2, om vast te stellen dat x ≡ x voorkomt
als onderdeel van stelling 1. Vandaar onze keuze om deze stelling 1 te gebruiken. We noemen
deze werkwijze patroonherkenning. Om stelling 4 te bewijzen gaan we op dezelfde manier te
werk. We ontdekken daarbij dat een deel van de te bewijzen stelling 4 terugkomt in axioma
3, namelijk 1 ≡ y.
Bewijs van stelling 4
y≡1≡y
≡
≡
hax3, 1 ≡ y ≡ yi
hax3, 1 ≡ y ≡ yi
y≡y
1
Dankzij stelling 4 kunnen we m.b.v. instantiatie en Leibniz 1 ≡ p evenals p ≡ 1 steeds vervangen door p (voor een willekeurige propositie p). Het 1 ≡ of ≡ 1 gedeelte is dus a.h.w. overbodig. We zullen het dan ook meestal weglaten tenzij het van pas komt in de bewijsvoering.
Anderzijds kunnen we wanneer dat goed uitkomt ook p vervangen door 1 ≡ p of door p ≡ 1.
4.3.2
Stellingen m.b.t. de andere operatoren
Om stelling 5 te bewijzen beginnen we weer met patroonherkenning, d.w.z. het opsporen van
(stukken van) de te bewijzen stelling 5 in de axioma’s en de reeds bewezen stellingen 1 t.e.m. 4.
Merk daarbij op dat het in de loop van het bewijs van stelling 5 geen zin heeft om axioma 6
toe te passen omdat we nog geen enkele stelling bewezen hebben over 6≡; het gebruiken van
axioma 6 leidt in dit stadium dan ook naar een doodlopend straatje. We beginnen met een
bewijs volgens bewijsmethode 2 en we maken daarbij gebruik van de volgende afspraak.
Afspraak 8 (Combinatie van Leibniz en instantiatie) Het principe van Leibniz en instantiatie van een stelling mogen in 1 stap toegepast worden, waarbij de te instanti¨eren stelling
opgegeven wordt als premisse, al dan niet met een hint omtrent de instantiatie.
In de derde stap komen we een gecombineerde toepassing tegen van axioma 2, instantiatie
van een stelling, en zelfs het principe van Leibniz!
Bewijs van stelling 5
¬x ≡ y ≡ x ≡ ¬y
≡
≡
≡
≡
≡
hax5, ¬(x ≡ y) ≡ ¬x ≡ yi
hax2, x ≡ y ≡ y ≡ x met x, y := x, ¬yi
hax5, ¬(x ≡ y) ≡ ¬x ≡ y met x, y := y, xi
hax2, x ≡ y ≡ y ≡ x met x, y := y, xi
hax3, 1 ≡ y ≡ y met y := ¬(x ≡ y)i
¬(x ≡ y) ≡ x ≡ ¬y
¬(x ≡ y) ≡ ¬y ≡ x
¬(x ≡ y) ≡ ¬(y ≡ x)
¬(x ≡ y) ≡ ¬(x ≡ y)
1
We kunnen ook gebruik maken van bewijsmethode 1 om een alternatief bewijs te geven.
48
HOOFDSTUK 4. PROPOSITIEREKENEN
Nog een bewijs van stelling 5
¬x ≡ y
≡
≡
≡
≡
hax5, ¬(x ≡ y) ≡ ¬x ≡ yi
hax2, x ≡ y ≡ y ≡ xi
hax5, ¬(x ≡ y) ≡ ¬x ≡ y met x, y := y, xi
hax2, x ≡ y ≡ y ≡ x met x, y := ¬y, xi
¬(x ≡ y)
¬(y ≡ x)
¬y ≡ x
x ≡ ¬y
Dit bewijs heeft evenveel stappen en de verantwoordingen zijn bijna dezelfde. In het eerste
bewijs wordt dezelfde deeluitdrukking, namelijk ¬(x ≡ y) ≡ overgenomen op elke lijn. Dit
zorgt voor meer schrijfwerk, maakt het bewijs minder overzichtelijk en verhoogt het risico op
fouten maken (door verkeerd overschrijven). Maak er een goede gewoonte van het herhalen
van deeluitdrukkingen te vermijden.
Voor bewijzen van stellingen 6, 7 en 8 verwijzen we naar opgave 2. Voor stelling 9 geven we
2 bewijzen, respectievelijk met bewijsmethode 1 en 2.
Bewijs van stelling 9
¬x ≡ x
≡
≡
≡
hax5, ¬(x ≡ y) ≡ ¬x ≡ y met x, y := x, xi
hax3, 1 ≡ y ≡ y met y := xi
hax4, 0 ≡ ¬1i
¬(x ≡ x)
¬1
0
Nog een bewijs van stelling 9
¬x ≡ x ≡ 0
≡
≡
hax5, ¬(x ≡ y) ≡ ¬x ≡ y met x, y := x, xi
hax3, 1 ≡ y ≡ y met y := xi
¬(x ≡ x) ≡ 0
¬1 ≡ 0
Hoewel het tweede bewijs een stap minder lang is, verkiezen we toch het eerste bewijs omdat
daar de deeluitdrukking ≡ 0 niet steeds moet herhaald worden.
Wanneer we een stelling moeten bewijzen over een operator (zoals 6≡) die gedefinieerd is in
termen van andere operatoren (zoals ¬ en ≡) zullen we vaak eerst de definitie van de originele
operator toepassen, vervolgens de eigenschappen van de andere operatoren uitbuiten om de
propositie om te vormen, en indien nodig en mogelijk op het einde weer proberen terug te
keren naar de originele operator. Volgend bewijs van stelling 10 illustreert dit.
Bewijs van stelling 10
(x 6≡ y)
≡
≡
≡
hax6, (x 6≡ y) ≡ ¬(x ≡ y)i
hax2, x ≡ y ≡ y ≡ xi
hax6, (x 6≡ y) ≡ ¬(x ≡ y) met x, y := y, xi
¬(x ≡ y)
¬(y ≡ x)
(y 6≡ x)
Ook stellingen 11, 12 en 13 kunnen op deze manier bewezen worden. We verwijzen hiervoor
naar opgave 3. Merk op dat stelling 12 toelaat om haakjes weg te laten in proposities met
49
4.3. STELLINGEN EN BEWIJZEN
applicaties van ≡ en 6≡ door elkaar. Net zoals axioma 1 zullen we stelling 12 meestal stilzwijgend toepassen om haakjes te plaatsen en weg te laten. Dit weglaten van haakjes hebben we
meteen toegepast in de formulering van Stelling 13. Hierna volgen 2 bewijzen voor stelling
14 m.b.v. bewijsmethode 1. Welk bewijs verkiest u?
Bewijs van stelling 14
1
≡
≡
≡
hax3, 1 ≡ y ≡ y met y := x ∨ xi
hax10, x ∨ (y ≡ z) ≡ x ∨ y ≡ x ∨ z met x, y, z := x, x, xi
hax3, 1 ≡ y ≡ y met y := xi
x∨x ≡ x∨x
x ∨ (x ≡ x)
x∨1
Nog een bewijs van stelling 14
x∨1
≡
≡
≡
hax3, 1 ≡ y ≡ y met y := xi
hax10, x ∨ (y ≡ z) ≡ x ∨ y ≡ x ∨ z met x, y, z := x, x, xi
hax3, 1 ≡ y ≡ y met y := x ∨ xi
x ∨ (x ≡ x)
x∨x ≡ x∨x
1
Het verloop van het tweede bewijs is vanzelfsprekender, daar waar de eerste stap uit het
eerste bewijs mysterieus overkomt (want waarom precies die stap?). Hoewel beide bewijzen
correct zijn, zullen we streven naar een bewijsstijl die zo leesbaar mogelijk is door dergelijke
tovertruukjes zo veel mogelijk te vermijden. Een hulpmiddel daarbij kan zijn om te vertrekken
van de meest gestructureerde kant van de stelling die we willen bewijzen. x ∨ 1 heeft meer
structuur dan 1 wat de patroonherkenning ook gemakkelijker te volgen maakt. 1 wordt het
opslorpend element van ∨ genoemd omdat x er a.h.w. in opgeslorpt wordt. 0 wordt het
eenheidselement van ∨ genoemd omdat disjunctie met 0 geen effect heeft op x. We laten het
bewijs van stelling 15 als oefening (zie opgave 4). Ook voor een bewijs van stelling 16, 17 en
18 verwijzen we naar opgaven 5, 6 en 7.
Net zoals het bij programmeren soms de moeite loont om een stuk van het programma in
een aparte functie of procedure te stoppen, hebben we er soms alle belang bij om stukken van
een bewijs onder te brengen als aparte hulpstelling of lemma. Dit heeft verschillende belangrijke voordelen: hulpstellingen kunnen de leesbaarheid sterk verhogen en laten hergebruik toe
(wat interessant is indien je dezelfde hulpstelling meer dan eens nodig hebt in een bewijs). Er
is geen strikte regel over wat een stelling te noemen en wat een hulpstelling; dit hangt af van
het aanvoelen van de persoon die het bewijs ontwerpt. We illustreren dit met een bewijs van
stelling 19.
Bewijzen van stellingen m.b.t. ∧ kunnen vaak gevonden worden door m.b.v. axioma 12
(de gouden regel die dienst doet als de definitie van ∧) de applicatie van ∧ te herschrijven
in termen van ≡ en ∨, de bekomen propositie te manipuleren en achteraf indien nodig via
axioma 12 proberen terug te keren naar ∧. Voor stelling 19 is dat niet anders. We passen
bewijsmethode 1 toe en vertrekken van de linkerzijde van stelling 19 (we hadden even goed
van de rechterzijde kunnen vertrekken want ze zijn beide in dezelfde mate gestructureerd).
Bewijs van hulpstelling 1
50
HOOFDSTUK 4. PROPOSITIEREKENEN
(x ∧ y) ∧ z
≡
≡
≡
≡
≡
hax12, x ∧ y ≡ x ≡ y ≡ x ∨ yi
hax12, x ∧ y ≡ x ≡ y ≡ x ∨ yi
hax10, x ∨ (y ≡ z) ≡ x ∨ y ≡ x ∨ zi
hax10, x ∨ (y ≡ z) ≡ x ∨ y ≡ x ∨ zi
hax1, ax2, ax7, ax8i
(x ≡ y ≡ x ∨ y) ∧ z
(x ≡ y ≡ x ∨ y) ≡ z ≡ (x ≡ y ≡ x ∨ y) ∨ z
x ≡ y ≡ x ∨ y ≡ z ≡ (x ≡ y) ∨ z ≡ (x ∨ y) ∨ z
x≡ y ≡ x∨y ≡ z ≡ x∨z ≡ y∨z ≡ x∨y∨z
x≡ y ≡ z ≡ x∨y ≡ y∨z ≡ z∨x≡ x∨y∨z
Merk op dat we in bovenstaand bewijs axioma 7 en 8 omtrent de symmetrie en de associativiteit van ∨ hebben toegepast. Die axioma’s komen net als axioma 1 en 2 in de praktijk zo
vaak voor en zijn zo eenvoudig dat uitdrukkelijke vermelding meestal niet echt nodig is voor
de goede leesbaarheid van het bewijs, of dat we verscheidene van die axioma’s tegelijkertijd in
1 stap kunnen gebruiken. Bovendien hebben we om het schrijfwerk te beperken het “met...”
luik weggelaten uit de verantwoordingen, al mag dat natuurlijk steeds geplaatst worden. Een
alternatief is het niet volledig uitschrijven van de stelling of het axioma maar ons beperken
tot de afkorting en wel het “met...”-gedeelte toevoegen. We illustreren dit zo dadelijk. Bovenstaand bewijs is natuurlijk nog geen bewijs voor stelling 19 maar wel van
Hulpstelling 1
(x ∧ y) ∧ z ≡ x ≡ y ≡ z ≡ x ∨ y ≡ y ∨ z ≡ z ∨ x ≡ x ∨ y ∨ z
We verheffen deze equivalentie die we net bewezen hebben tot de status van hulpstelling omdat
ze een interessante structuur vertoont (namelijk een equivalentie van alle mogelijke disjuncties
van x, y en z). Bovendien hopen we om de rechterzijde van stelling 19 hier ook toe te kunnen
herleiden zodat we 2 maal gebruik kunnen maken van hulpstelling 1 om stelling 19 te bewijzen.
Bewijs van stelling 19
x ∧ (y ∧ z)
≡
≡
≡
≡
hst18, x ∧ y ≡ y ∧ xi
hhst1, met x, y, z := y, z, xi
hax1, ax2, ax7, ax8i
hhst1i
(y ∧ z) ∧ x
y ≡ z ≡ x ≡y∨z ≡ z∨x≡ x∨y ≡ y∨z∨x
x≡ y ≡ z ≡x∨y ≡y∨z ≡ z∨x≡ x∨y∨z
(x ∧ y) ∧ z
Voor het bewijs van stelling 20 verwijzen we naar opgave 8.
De gouden regel (axioma 12) laat zich in veel bochten wringen. Meestal lezen we hem als
(p ∧ q) ≡ (p ≡ q ≡ p ∨ q)
en gebruiken we hem om een conjunctie p ∧ q om te zetten in p ≡ q ≡ (p ∨ q). Dankzij de
associativiteit van ≡ (axioma 1) kunnen we de haakjes ook anders plaatsen, b.v.
(p ∧ q ≡ p) ≡ (q ≡ p ∨ q)
51
4.3. STELLINGEN EN BEWIJZEN
Deze leeswijze komt van pas om met bewijsmethode 2 stelling 21 te bewijzen.
Bewijs van stelling 21
x∧1≡x
≡
hax12, x ∧ y ≡ x ≡ y ≡ x ∨ y met x, y := x, 1i
1≡x∨1
De rechterzijde is stelling 14.
Merk op dat we na de calculationele ketting in ons bewijs nog een zin toegevoegd hebben
om te verduidelijken dat de laatste rechterzijde wel degelijk een stelling is. Naarmate het
aantal reeds bewezen en dus beschikbare stellingen groeit, zijn dergelijke verduidelijkingen
een welkome hint voor wie het bewijs leest.
Stelling 24 is de tegenhanger van axioma 11 (dit is meteen een hint voor het bewijs van
stelling 24 dat we overlaten als oefening). De stellingen m.b.t. absorptie danken hun naam
aan het feit dat een deel van de linkerzijde a.h.w. geabsorbeerd wordt en niet meer voorkomt
aan de rechterzijde. De stelling van De Morgan is genoemd naar de bedenker ervan. Voor
bewijzen van stellingen 22 t.e.m. 30 verwijzen we naar opgaven 9 t.e.m. 19. Het volgende
knap bewijs van stelling 31 is nog eens een voorbeeld van de bochten waarin we de gouden
regel kunnen wringen. I.p.v.
x ∧ (y ≡ z) ≡ x ∧ y ≡ x ∧ z ≡ x
bewijzen we
x ∧ (y ≡ z) ≡ x ≡ x ∧ y ≡ x ∧ z
wat met axioma 2 uiteraard probleemloos kan omgezet worden in stelling 31.
Bewijs van stelling 31
x ∧ (y ≡ z) ≡ x
≡
≡
≡
≡
≡
hax12, x ∧ y ≡ x ≡ y ≡ x ∨ y met x, y := x, y ≡ zi
hax10, x ∨ (y ≡ z) ≡ x ∨ y ≡ x ∨ zi
hax2, x ≡ y ≡ y ≡ x met x, y := z, x ∨ yi
hax12, x ∧ y ≡ x ≡ y ≡ x ∨ yi
hax12, x ∧ y ≡ x ≡ y ≡ x ∨ y met x, y := x, zi
y ≡ z ≡ x ∨ (y ≡ z)
y ≡z ≡x∨y ≡x∨z
y ≡x∨y ≡z ≡x∨z
x∧y ≡x≡z ≡x∨z
x
Voor bewijzen van stellingen 32 t.e.m. 35 verwijzen naar opgaven 20 t.e.m. 23. Stelling 35
maakt duidelijk waarom 6≡ ook wel exclusieve of wordt genoemd: de rechterzijde van stelling
35 omvat a.h.w. het geval waarin x zich niet voordoet maar y wel, en de situatie waarin x
zich voordoet maar y niet. M.a.w. we hebben ofwel x ofwel y. De rechterzijde van stelling 34
kan op analoge manier gelezen worden.
4.3.3
Stellingen m.b.t. implicatie
Tabel 4.3 bevat allerlei stellingen m.b.t. ⇒. Analoge stellingen m.b.t. ⇐ kunnen hier onmiddellijk uit afgeleid worden a.d.h.v. axioma 14. x ⇒ y kan op verschillende manieren
52
HOOFDSTUK 4. PROPOSITIEREKENEN
herschreven worden. Wij hebben gekozen voor
x ⇒y ≡x∨y ≡y
als axioma 13, maar in andere teksten kiest men in plaats daarvan soms voor wat bij ons
opduikt als stelling 36 en 37. Het is belangrijk om te zien dat dit alternatieve definities zijn,
omdat we ze ook kunnen gebruiken bij de bewijsstrategie waarbij men een operator eerst
vervangt door zijn definitie die in termen van andere operatoren is, de bekomen propositie
manipuleert en dan indien nodig weer terugkeert via de oorspronkelijke definitie. Ook stelling
38 kan op die manier gebruikt worden. Voor bewijzen van stellingen 36, 37 en 38 verwijzen
we naar opgave 24, maar we illustreren hier wel de hierboven beschreven bewijsstrategie nog
eens voor stelling 39. We lezen deze stelling als
(x ⇒ (y ≡ z)) ≡ (x ∧ y ≡ x ∧ z)
We beginnen met de linkerzijde, d.w.z. we mikken op bewijsmethode 1. Omdat aan de
rechterzijde conjuncties voorkomen,lijkt stelling 37 de beste kandidaat.
Bewijs van stelling 39
x ⇒ (y ≡ z)
≡
≡
hst37, x ⇒ y ≡ x ∧ y ≡ x met x, y := x, y ≡ zi
hst31, x ∧ (y ≡ z) ≡ x ∧ y ≡ x ∧ z ≡ xi
x ∧ (y ≡ z) ≡ x
x∧y ≡x∧z
Voor bewijzen van stellingen 40 t.e.m. 52 verwijzen we naar opgaven 25 t.e.m. 37. De Engelstalige benaming van stelling 42 is shunting. Dit betekent aftakken, rangeren (m.b.t. spoorwegen). y wordt hierbij uit het antecedent gehaald en naar het consequent geleid. Stellingen
49 t.e.m. 52 beschrijven de interactie tussen ⇒ en de constanten 0 en 1. Merk op dat je uit
stelling 49 t.e.m. 52 kan zien dat ⇒ niet symmetrisch is. In onderstaand bewijs maken we
gebruik van de alternatieve definitie uit stelling 36 om ⇒ te herschrijven.
Bewijs van stelling 53(a)
x ⇒ (x ∨ y)
≡
≡
≡
hst36, x ⇒ y ≡ ¬x ∨ y met x, y := x, x ∨ yi
hax11, x ∨ ¬x ≡ 1i
hst14, x ∨ 1 ≡ 1 met x := yi
¬x ∨ x ∨ y
1∨y
1
We hebben hier axioma 7 en 8 stilzwijgend toegepast. In onderstaande afspraak geven we
een overzicht van axioma’s en stellingen die zeker in aanmerking komen voor een dergelijke stilzwijgende toepassing; een aantal afspraken die we gaandeweg doorheen dit hoofdstuk
ingevoerd hebben, worden er in samengevat.
Afspraak 9 (Stilzwijgend gebruik van axioma’s en stellingen) Volgende axioma’s mogen stilzwijgend toegepast worden:
Axioma
Axioma
Axioma
Axioma
1
2
7
8
Associativiteit van ≡
Symmetrie van ≡
Symmetrie van ∨
Associativiteit van ∨
((x ≡ y) ≡ z) ≡ (x ≡ (y ≡ z))
x≡y≡y≡x
x∨y ≡y∨x
(x ∨ y) ∨ z ≡ x ∨ (y ∨ z)
53
4.3. STELLINGEN EN BEWIJZEN
Nadat het bewijs ervan geleverd is, mogen volgende stellingen stilzwijgend toegepast worden.
Stelling
Stelling
Stelling
Stelling
Stelling
Stelling
4
10
11
12
18
19
Symmetrie van 6≡
Associativiteit van 6≡
Onderlinge associativiteit
Symmetrie van ∧
Associativiteit van ∧
y≡1≡y
(x 6≡ y) ≡ (y 6≡ x)
((x 6≡ y) 6≡ z) ≡ (x 6≡ (y 6≡ z))
((x 6≡ y) ≡ z) ≡ (x 6≡ (y ≡ z))
x∧y ≡y∧x
(x ∧ y) ∧ z ≡ x ∧ (y ∧ z)
Voor een bewijs van stelling 53(b) t.e.m. stelling 53(e) verwijzen we naar opgave 38. Stelling
54 is zeer bekend en de moeite van het onthouden waard. Er bestaat een bewijs dat gebruik
maakt van stelling 43. Stellingen 55 en 56 leggen de fundamenten voor een bewijsmethode
die dezelfde naam draagt, namelijk gevallenonderzoek. We komen hier later nog op terug.
Voor bewijzen verwijzen we naar opgave 39. Dit brengt ons reeds bij stelling 57.
Bewijs van stelling 57
(x ⇒ y) ∧ (y ⇒ x)
≡
≡
≡
≡
≡
hst36, 2
hst28, 3
hst24, 2
hst15, 2
hst34 i
maal
maal
maal
maal
i
i
i
i
(¬x ∨ y) ∧ (¬y ∨ x)
(¬x ∧ ¬y) ∨ (y ∧ ¬y) ∨ (¬x ∧ x) ∨ (y ∧ x)
(¬x ∧ ¬y) ∨ 0 ∨ 0 ∨ (y ∧ x)
(¬x ∧ ¬y) ∨ (y ∧ x)
x≡y
Voor bewijzen van stelling 58 en 59 verwijzen we naar opgaven 40 t.e.m. 42.
Tot nu toe hebben we de schakels in onze calculationele bewijzen aan elkaar gebonden
d.m.v. ≡. Dit kon dankzij de afleidingsregel voor transitiviteit. Stelling 59 biedt nu een
gelijkaardige kracht om kettingen aan elkaar te hangen m.b.v. ⇒ en zelfs met ≡ en ⇒ door
elkaar.
Afspraak 10 (Stap in calculationele stijl) Het gebruik van een afleidingsregel met premisse p en consequent van de vorm q ⇒ r noteren we in een bewijs in calculationele stijl
als
q ⇒ hpi r
Afspraak 11 De stappen
q1
≡
hp1 i
r1
r1
⇒
hp2 i
r2
en
mogen aan elkaar geregen worden tot een ketting
q1
≡
⇒
hp1 i
hp2 i
r1
r2
Hierbij zijn p1 , p2 , q1 , r1 en r2 proposities. Deze ketting levert een bewijs voor de stelling
q 1 ⇒ r2 .
54
HOOFDSTUK 4. PROPOSITIEREKENEN
Verklaring: We hebben reeds een bewijs voor q1 ≡ r1 dus dat is een stelling. M.b.v. de afleidingsregel voor gelijkgestemdheid hebben we q1 ≡ r1 ≡ 1 (neem q1 ≡ r1 en de instantiatie
van stelling 4 met y := q1 ≡ r1 als premissen). Analoog hebben we r1 ⇒ r2 ≡ 1. Vervolgens
vertrekken we van een instantiatie van stelling 59(b) .
(q1 ≡ r1 ) ∧ (r1 ⇒ r2 ) ⇒ (q1 ⇒ r2 )
≡
≡
≡
hq1 ≡ r1 ≡ 1, r1 ⇒ r2 ≡ 1i
hst21, x ∧ 1 ≡ x met x := 1i
hst50, 1 ⇒ x ≡ x met x := q1 ⇒ r2 i
1 ∧ 1 ⇒ (q1 ⇒ r2 )
1 ⇒ (q1 ⇒ r2 )
q 1 ⇒ r2
waaruit blijkt dat q1 ⇒ r2 inderdaad een stelling is.
Oefening: verklaar waarom onderstaande kettingen eveneens een bewijs leveren voor q1 ⇒ r2 .
q1
⇒
⇒
hp1 i
hp2 i
r1
r2
q1
⇒
≡
hp1 i
hp2 i
r1
r2
We kunnen deze afspraken ook uitbreiden tot kettingen van een willekeurige lengte waarbij
we ≡ en ⇒ door elkaar gebruiken. Let er wel op dat deze afspraken maar tot onze beschikking
zijn na het bewijzen van stelling 59!
Voorbeeld 31 Een mogelijk bewijs voor stelling 53(d) indien we stelling 59 reeds ter beschikking zouden hebben wordt gegeven door:
x ∨ (y ∧ z)
≡
⇒
hst27i
hst53(b)i
(x ∨ y) ∧ (x ∨ z)
x∨y
Het is zeer belangrijk om te onthouden dat de operatoren die gebruikt worden om de schakels
van een calculationeel bewijs aan elkaar te hangen steeds de laagste prioriteit hebben! Zolang
we enkel werkten met ≡ was dit vrij vanzelfsprekend omdat ≡ sowieso de laagste prioriteit
heeft. Voor ⇒ wil dit b.v. zeggen dat
x
⇒
hx ⇒ y ⇒ zi
y⇒z
juist is maar
x⇒y
⇒
hx ⇒ y ⇒ zi
z
niet!!!
4.3.4
Een 15e axioma
Om het verhaal over axioma’s en stellingen van de propositiecalculus af te ronden, introduceren we nog een 15e axioma dat zich onderscheidt van de voorgaande 14 axioma’s omdat het
metaveranderlijken bevat in de formulering.
55
4.3. STELLINGEN EN BEWIJZEN
Stelling 60
Vervang p door q
Stelling 61
Vervang door 1
Stelling 62
Vervang door 0
Stelling 63
Stelling 64
Vervang door 1
Vervang door 0
(a)
(b)
(c)
(a)
(b)
(a)
(b)
(p ≡ q) ∧ r[v := p]
(p ≡ q) ⇒ r[v := p]
s ∧ (p ≡ q) ⇒ r[v := p]
x ⇒ r[v := x]
y ∧ x ⇒ r[v := x]
r[v := x] ⇒ x
r[v := x] ⇒ x ∨ y
x ∧ r[v := x]
x ∨ r[v := x]
≡
≡
≡
≡
≡
≡
≡
≡
≡
(p ≡ q) ∧ r[v := q]
(p ≡ q) ⇒ r[v := q]
s ∧ (p ≡ q) ⇒ r[v := q]
x ⇒ r[v := 1]
y ∧ x ⇒ r[v := 1]
r[v := 0] ⇒ x
r[v := 0] ⇒ x ∨ y
x ∧ r[v := 1]
x ∨ r[v := 0]
Tabel 4.4: 3e reeks stellingen uit de propositiecalculus
Axioma 15
(p ≡ q) ⇒ (r[v := p] ≡ r[v := q])
Eigenlijk is axioma 15 dus een bundeling van een heleboel axioma’s die ontstaan wanneer we
voor p, q en r proposities invullen en voor v een veranderlijke (dus x, y of z). Een voorbeeld
van zo’n concrete invulling is (let op de haakjes)
(x ∧ y ≡ y) ⇒ ((z ⇒ y)[z := x ∧ y] ≡ (z ⇒ y)[z := y])
of na uitwerken van de substitutie
(x ∧ y ≡ y) ⇒ (x ∧ y ⇒ y ≡ y ⇒ y)
Let op het verschil met het principe van Leibniz: die afleidingsregel laat ons toe om uit
x ∧ y ≡ y af te leiden x ∧ y ⇒ y ≡ y ⇒ y. Dus als we weten dat x ∧ y ≡ y een stelling is,
dan weten we m.b.v. het principe van Leibniz ook dat x ∧ y ⇒ y ≡ y ⇒ y een stelling is. Het
15e axioma echter stelt dat (x ∧ y ≡ y) ⇒ (x ∧ y ⇒ y ≡ y ⇒ y) in zijn geheel een stelling
is! Zoals te verwachten is, laat dit axioma ons toe nieuwe stellingen af te leiden, zie Tabel
4.4. Deze stellingen zijn ook geformuleerd a.d.h.v. metaveranderlijken maar de bewijsvoering
verloopt op dezelfde manier die we reeds gewoon zijn. Zie opgave 43.
4.3.5
Bewijsmethoden
Een aantal bewijsmethoden die veelvuldig gebruikt worden doorheen de wiskunde (ook buiten
het kader van propositierekenen) gaan terug op de hierboven bestudeerde stellingen van de
propositiecalculus. Voor elk van die bewijsmethoden bestaat er een verklaring waarom de
methode in kwestie correct is. We zullen ons echter beperken tot een korte algemene schets
van elke bewijsmethode en het verband met het propositierekenen.
Aannemen van het antecedent Tot nu toe hebben we in dit hoofdstuk afleidingen of
bewijzen voor stellingen gegeven, d.w.z. voor
A⊢p
56
HOOFDSTUK 4. PROPOSITIEREKENEN
waarbij A de 15 axioma’s bevat en p de stelling in kwestie is. Een bewijs voor een stelling
p ⇒ q is dus een afleiding voor
A⊢p⇒q
Dit is in principe iets anders dan een afleiding voor
A, p ⊢ q
Het is echter mogelijk om een afleiding voor A ⊢ p ⇒ q om te zetten in een afleiding voor
A, p ⊢ q en ook omgekeerd. Dit maakt “aannemen van het antecedent” tot een correcte (en
veelvuldig gebruikte) bewijstechniek voor het bewijzen van p ⇒ q. Men moet hierbij wel
opletten dat in een afleiding voor A, p ⊢ q de afleidingsregel voor instantiatie van een stelling
niet mag gebruikt worden voor p als p geen stelling is.
Gevallenonderzoek Stelling 55 geeft aan dat x ∨ y ⇒ z kan bewezen worden door de
gevallen x ⇒ z en y ⇒ z apart te bewijzen. Stelling 56 geeft aan hoe een bewijs voor z kan
opgebroken worden in 2 gevallen. In het algemeen zal men bij een bewijs voor een propositie
p met gevallenonderzoek op zoek gaan naar proposities q en r zodat q ∨ r en q ⇒ p en r ⇒ p
alle stellingen zijn.
Gevallenonderzoek maakt dat het bewijs uiteen valt in verschillende stukken, wat de
overzichtelijkheid niet altijd ten goede komt. Bovendien is het vaak langer dan een bewijs
dat gevallenonderzoek vermijdt omdat je niet alleen de afzonderlijke gevallen moet bewijzen
(namelijk q ⇒ p en r ⇒ p), maar ook nog eens dat er daarbuiten geen andere gevallen bestaan
(namelijk q ∨ r). Het is daarom meestal beter om gevallenonderzoek te vermijden, al kan dit
niet altijd.
Methode van de wederzijdse implicatie
stelling 57, namelijk
Een andere bewijstechniek gaat voort op
(x ⇒ y) ∧ (y ⇒ x) ≡ x ≡ y
Deze stelling geeft aan dat om p ≡ q te bewijzen je afzonderlijk kan aantonen dat p ⇒ q en
q ⇒ p.
Methode van de contradictie
51 met x := ¬x, namelijk
Deze bewijstechniek steunt op een instantiatie van stelling
¬x ⇒ 0 ≡ x
Om te bewijzen dat p een stelling is, bewijst men eerst dat ¬p ⇒ 0 een stelling is. Men noemt
dit ook wel eens een bewijs uit het ongerijmde. Om te bewijzen dat ¬p ⇒ 0 een stelling is,
bewijst men soms eerst dat ¬p ⇒ q ∧ ¬q. Dit brengt ons bij stelling 24, namelijk x ∧ ¬x ≡ 0.
Vandaar ook de naamkeuze “methode van de contradictie”.
Methode van de contrapositie Om p ⇒ q te bewijzen, bewijst men ¬q ⇒ ¬p. Deze
bewijsmethode steunt op stelling 38.
57
4.4. SEMANTIEK
4.4
4.4.1
Semantiek
Tweewaardig
We hebben kennis gemaakt met de syntax van de taal van het propositierekenen. We weten
hoe we m.b.v. 4 afleidingsregels proposities kunnen afleiden uit axioma’s (de zogenaamde
stellingen). Tot nu toe zijn dergelijke proposities echter opeenvolgingen van symbolen uit het
alfabet zonder betekenis. Er kan op verschillende wijzen een semantiek gehecht worden aan
proposities. De meest gebruikte aanpak lijkt op de betekenis van zinnen in een natuurlijke
taal. Een zin zoals “er is vandaag oefeningenles” is in principe ook maar een opeenvolging van
symbolen. Stel nu dat er werkelijk oefeningenles is, dan zeggen we dat de zin “er is vandaag
oefeningenles” waar is. Anders is de zin in kwestie niet waar, of nog: vals.
Dit idee van betekenis gaat ook op voor proposities. Net zoals een zin in natuurlijke taal
zeggen we ook dat een propositie waar of vals kan zijn. “waar” en “vals” worden waarheidswaarden of booleaanse waarden genoemd. Er bestaan heel wat notaties en afkortingen voor
deze 2 waarheidswaarden. Denk b.v. aan Tru en Fls die we ontmoet hebben bij het gebruik
van lambdacalculus als programmeertaal, of true en false uit Java, of True and False uit
Haskell. Soms gebruikt men ook T en F, of in een Nederlandse tekst W en V. Wij kiezen
voor 1 en 0 omdat dat gemakkelijk “rekent” waar het ons in wezen om te doen is.
Hoe kunnen we nu de waarheidswaarde van een applicatie bepalen? We hebben aan het
begin van dit hoofdstuk reeds even aangehaald dat p ∧ q, p ∨ q en ¬p kunnen gelezen worden
als “p en q”, “p of q” en “niet p” respectievelijk. Laat ons opnieuw even vergelijken met een
zin in natuurlijke taal, namelijk “er is theorieles en er is oefeningenles”. Deze zin is enkel waar
indien de 2 deelzinnen die door “en” verbonden zijn allebei waar zijn. Op dezelfde manier is
p ∧ q waar indien p waar is en q waar is; in alle andere gevallen is p ∧ q vals. Dit kan beknopt
weergegeven worden in een waarheidstabel.
p
0
0
1
1
q
0
1
0
1
p∧q
0
0
0
1
Ook voor de waarheidswaarde van ¬p en van p ∨ q in functie van de waarheidswaarden van p
en q kunnen we waarheidstabellen opstellen.
p
0
1
¬p
1
0
p
0
0
1
1
q
0
1
0
1
p∨q
0
1
1
1
¬p is waar indien p vals is en omgekeerd. p ∨ q is waar indien p waar is of q waar is of ze
allebei waar zijn. Dit is verschillend met ons gewone taalgebruik: als we bij onze maaltijd
frietjes of gekookte aardappels kunnen nemen, wordt er normaal gezien ´e´en van beide bedoeld
en niet de mogelijkheid om ze allebei samen te nemen. De courante “of” uit ons dagelijks
taalgebruik wordt daarom “exclusief” genoemd (zie verder).
De structuur die gevormd wordt door de verzameling {0, 1} uitgerust met de bewerkingen die vastgelegd worden door bovenstaande waarheidstabellen wordt een binaire algebra
58
HOOFDSTUK 4. PROPOSITIEREKENEN
p
0
1
0
0
0
1
¬
1
0
1
1
Tabel 4.5: Betekenis van monadische operatoren
p
0
0
1
1
q
0
1
0
1
0
0
0
0
−
∨
1
0
0
0
0
1
0
0
1
1
0
0
0
0
1
0
1
0
1
0
6≡
0
1
1
0
−
∧
1
1
1
0
∧
0
0
0
1
≡
1
0
0
1
0
1
0
1
⇒
1
1
0
1
0
0
1
1
⇐
1
0
1
1
∨
0
1
1
1
1
1
1
1
Tabel 4.6: Betekenis van dyadische operatoren
genoemd. De benaming “binair” verwijst naar het feit dat er 2 waarden zijn, namelijk 0 en
1. Deze binaire algebra is bovendien een speciaal geval van een zogenaamde boole–algebra en
wordt daarom ook wel eens initi¨ele booleaanse algebra genoemd. Vanaf nu noteren we {0, 1}
ook als B.
Er kunnen uiteraard nog andere bewerkingen op B gedefinieerd worden; in totaal zijn er 4
verschillende die inwerken op 1 argument en 16 verschillende die inwerken op 2 argumenten.
I.p.v. een afzonderlijke waarheidstabel voor elk van die bewerkingen op te schrijven, bundelen we ze samen in tabellen 4.5 en 4.6. De eerste kolom in tabel 4.5 somt de mogelijke
waarheidswaarden op van een propositie p. De eerste, tweede en vierde kolom na de verticale scheidingslijn leggen betekenissen vast van operatoren die meestal geen specifieke naam
hebben in de propositiecalculus. In de derde kolom herkennen we de reeds eerder vermelde
betekenis van ¬. We gaan nu op dezelfde manier te werk voor de binaire operatoren. De
eerste 2 kolommen van tabel 4.6 beschrijven de mogelijke waarden van proposities p en q.
Een aantal van de kolommen in bovenstaande tabel leggen een betekenis vast van binaire
operatoren die we reeds kennen uit de taal van de propositiecalculus. We herkennen ∧ en ∨
die voor de volledigheid weer zijn opgenomen, maar ook 6≡ die de rol speelt van de hierboven
vermelde exclusieve of. Een equivalentie p ≡ q is waar indien p en q dezelfde waarheidswaarde
hebben. Merk op dat als p vals is dan p ⇒ q sowieso waar is. Vergelijk met een uitspraak
als “Als Pavarotti slank is, dan ben ik een topmodel!”; deze zin is waar omdat Pavarotti niet
slank is.
Op die manier hebben we een betekenis vastgelegd voor elk van de operatoren uit de taal
van de propositiecalculus. Het symbool 1 uit de propositiecalculus krijgt waarheidswaarde 1,
terwijl 0 waarheidswaarde 0 krijgt. De waarheidswaarde van de veranderlijken tenslotte kan
veranderen (vandaar ook de naam). Net als op het einde van hoofdstuk 2 maken we ook hier
weer gebruik van het begrip toestand: dit zijn de (waarheids)waarden van alle veranderlijken
op een gegeven moment.
Voorbeeld 32 In een gegeven toestand worden de waarden van x, y en z respectievelijk
gegeven door 1, 1 en 0. De waarde van x ∨ (y ∧ ¬z) is dan 1, terwijl de waarde van x ∧ y ∧ z
0 is.
We kunnen nu uitgebreide waarheidstabellen gebruiken om de waarheidswaarde van een
propositie in elke mogelijke toestand na te gaan. Daarbij schrijven we de propositie in de
59
4.4. SEMANTIEK
hoofding van de tabel en onder de veranderlijken de mogelijke waarden. Aangezien onze taal
3 verschillende veranderlijken bevat, hebben we te doen met hoogstens 8 verschillende mogelijke toestanden (d.w.z. 8 rijen in de waarheidstabel). Vervolgens vullen we, rekening houdend
met de prioriteiten, de kolommen onder de veranderlijken aan. Onderstaande voorbeelden
illustreren deze werkwijze.
Voorbeeld 33 De waarheidswaarde van propositie x ∨ (y ∧ z) in alle mogelijke toestanden.
We beginnen met het invullen van de mogelijke toestanden.
x
0
0
0
0
1
1
1
1
∨
(y
0
0
1
1
0
0
1
1
∧
z)
0
1
0
1
0
1
0
1
Vervolgens berekenen we de waarheidswaarde van y ∧ z in elke toestand.
x
0
0
0
0
1
1
1
1
∨
(y
0
0
1
1
0
0
1
1
∧
0
0
0
1
0
0
0
1
z)
0
1
0
1
0
1
0
1
Tenslotte kunnen we de waarheidswaarde van de volledige propositie in elke toestand invullen.
x
0
0
0
0
1
1
1
1
∨
0
0
0
1
1
1
1
1
(y
0
0
1
1
0
0
1
1
∧
0
0
0
1
0
0
0
1
z)
0
1
0
1
0
1
0
1
Het eindresultaat is nu af te lezen in de tweede kolom.
Voorbeeld 34 In onderstaande tabel hebben we achtereenvolgens de eerste, de vierde en de
derde kolom ingevuld. In de tweede kolom tenslotte is het eindresultaat af te lezen.
x
0
1
∨
1
1
¬
1
0
x
0
1
60
HOOFDSTUK 4. PROPOSITIEREKENEN
Alle kolommen uit tabellen 4.5 en 4.6 kunnen gereconstrueerd worden enkel gebruik makend
van de kolommen voor p, q, ¬ en ∨. De kolommen na de verticale scheidingslijn in tabel 4.5
bekomen we b.v. als betekenis van
¬(p ∨ ¬p)
p
¬p
p ∨ ¬p
Voor de eerste kolom na de scheidingslijn in tabel 4.6 kunnen we de betekenis van ¬(p ∨ ¬p)
nemen, of van ¬(q ∨ ¬q). Ga als oefening na hoe de andere kolommen op deze wijze kunnen
bekomen worden. Controleer je resultaat a.d.h.v. een uitgebreide waarheidstabel.
Voorbeeld 35 De waarheidstabellen voor (x ≡ y) ≡ (y ≡ x), ((x ≡ y) ≡ y) ≡ x en
x ≡ (y ≡ (y ≡ x)) zijn verschillend maar het resultaat in de laatst in te vullen kolom is wel
gelijk (dit is respectievelijk de vierde, de zesde en de tweede kolom).
(x
0
0
1
1
≡
1
0
0
1
((x
0
0
1
1
x
0
0
1
1
y)
0
1
0
1
≡
1
0
0
1
≡
1
1
1
1
y)
0
1
0
1
(y
0
1
0
1
≡
1
1
1
1
≡
0
0
1
1
≡
0
0
1
1
(y
0
1
0
1
≡
1
0
0
1
y)
0
1
0
1
(y
0
1
0
1
≡
1
1
1
1
≡
1
0
0
1
x)
0
0
1
1
x
0
0
1
1
x))
0
0
1
1
Voorbeeld 36 De waarheidswaarde van propositie x −
∧ y ≡ ¬(x ∧ y) in alle mogelijke toestanden. Eerst vullen we de eerste en de zesde kolom in (die dezelfde waarden bevatten),
vervolgens de derde en de achtste kolom. Dan kunnen we de tweede en de zevende kolom
invullen (of eerst de zevende en dan de tweede kolom, de volgorde speelt geen rol). Dan vullen
we de vijfde kolom in, en het eindresultaat tenslotte staat in de vierde kolom.
x
0
0
1
1
−
∧
1
1
1
0
y
0
1
0
1
≡
1
1
1
1
¬
1
1
1
0
(x
0
0
1
1
∧
0
0
0
1
y)
0
1
0
1
−
∧ is geen symbool uit de taal van de propositiecalculus zoals we die ge¨ıntroduceerd hebben
aan het begin van dit hoofdstuk. x −
∧ y ≡ ¬(x ∧ y) is dus ook geen axioma of stelling. Hadden
we −
∧ wel opgenomen in onze taal van de propositiecalculus, dan hadden we allicht eveneens
x−
∧ y ≡ ¬(x ∧ y)
61
4.4. SEMANTIEK
opgenomen als axioma om −
∧ te defini¨eren. Oefening: construeer de waarheidstabel voor
x−
∨ y ≡ ¬(x ∨ y)
De laatste voorbeelden zijn bijzonder omdat de kolom met het resultaat enkel de waarheidswaarde 1 bevat. Een propositie die waar is in elke toestand geven we een bijzondere naam.
Definitie 23 (Tautologie) Een tautologie is een propositie die waar is in elke toestand.
Een stelling is een gevolg van axioma’s. Een afleiding van een stelling a.d.h.v. afleidingsregels
hebben we een bewijs genoemd, en genoteerd in calculationele stijl. Een stelling is een opeenvolging van symbolen die het resultaat is van symbolische manipulatie. Dit speelt zich af
op het niveau van de syntax en het afleidingsmechanisme en is op zich betekenisloos. Een
tautologie daarentegen is onlosmakelijk verbonden met de semantiek die aan een taal gegeven
wordt. Nagaan of een propositie een tautologie is, doen we door de betekenis ervan in elke
toestand na te gaan (b.v. a.d.h.v. een waarheidstabel). Stelling en tautologie kunnen dus
volstrekt los van elkaar beschouwd worden, maar er bestaat wel een mogelijk verband tussen
beide.
Definitie 24 (Betrouwbaar, Volledig) Indien elke stelling een tautologie is, dan wordt
de formele logica betrouwbaar genoemd. Indien elke tautologie een stelling is, dan wordt de
formele logica volledig genoemd.
Het propositierekenen zoals we dat in dit hoofdstuk hebben ingevoerd is volledig en betrouwbaar m.b.t. de hierboven uiteengezette semantiek. Dit is gerealiseerd dankzij een overwogen
keuze van de axioma’s (die uiteraard allemaal tautologie¨en moeten zijn; leg voor jezelf uit
waarom) en de afleidingsregels. Meer bepaald zijn de afleidingsregels zo gekozen dat wanneer
de premissen tautologie¨en zijn, het consequent ook een tautologie is.
4.4.2
Meerwaardig
Tweewaardige logica met de semantiek zoals hierboven uiteengezet heeft haar wortels in de
tijd van Aristoteles (omstreeks 350 v. Chr.). De voorbije eeuw zijn er heel wat inspanningen
geleverd voor het op poten zetten van meerwaardige logica’s. De bekendste is vaaglogica,
ge¨ıntroduceerd in de jaren 1960 door L. A. Zadeh. Het uitgangspunt hierbij is dat een
uitspraak vaak niet zomaar waar of vals te noemen is, maar wel waar in een bepaalde mate.
Denk b.v. uitspraken als “55 is oud”, “dat restaurant is goedkoop” , “het schilderij is mooi”
enz. Dat iets waar is in een bepaalde mate wordt veroorzaakt door het gebruik van vage
talige uitdrukkingen zoals oud, goedkoop en mooi. De overgang tussen oud en niet oud zijn,
tussen goedkoop en niet goedkoop zijn, tussen mooi en niet mooi zijn, is niet abrupt maar
gradueel.
In de tweewaardige semantiek kan een veranderlijke ofwel 0 ofwel 1 als waarheidswaarde
hebben. Om gradaties in waarheidsgehalte te kunnen weergeven, gebruikt men bij vaaglogica
[0,1] i.p.v. B als verzameling van waarheidswaarden. Zelfs met slechts 3 veranderlijken x, y en z
ontstaan er reeds oneindig veel mogelijke toestanden waardoor waarheidstabellen onbruikbaar
worden. De constanten 0 en 1 uit de taal van het propositierekenen krijgen respectievelijk 0
en 1 als waarheidswaarde. De voorbije decennia is er veel nagedacht over de volgende vraag:
als proposities p en q respectievelijk waarheidswaarden a en b hebben (a in [0,1] en b in [0,1]),
wat is dan de waarheidswaarde van p ∧ q, p ∨ q en ¬p? In onderstaande tabel geven we de
62
HOOFDSTUK 4. PROPOSITIEREKENEN
in de praktijk meest gebruikte antwoorden op deze vraag. Elk van de rijen SEM1, SEM2 en
SEM3 komt overeen met een andere semantiek.
SEM1
SEM2
SEM3
p
a
a
a
q
b
b
b
p∧q
min(a, b)
a·b
max(a + b − 1, 0)
p∨q
max(a, b)
a+b−a·b
min(a + b, 1)
¬p
1−a
1−a
1−a
Men kan nagaan dat x ∨ x enkel in SEM1 steeds dezelfde waarheidswaarde heeft als x. Bovendien heeft x ∨ ¬x enkel in SEM3 steeds de waarheidswaarde 1. Wanneer we de betekenis van
≡ blijven behouden zoals voorheen (namelijk p ≡ q heeft waarheidswaarde 1 indien p en q
dezelfde waarheidswaarde hebben; anders 0) en een tautologie een propositie is die waarheidswaarde 1 heeft in elke mogelijke toestand, dan is axioma 9 een tautologie in SEM1 maar niet
in SEM2 en SEM3. Analoog is axioma 11 een tautologie in SEM3 maar niet in SEM1 en
SEM2.
4.4.3
Verband tussen ≡ en =
We eindigen dit luik over de semantiek met een opmerking over ≡. De waarheidswaarde van
x ≡ y is waar indien de waarheidswaarden van x en y gelijk zijn. Toch hebben we een speciaal
symbool ≡ gebruikt en niet het traditionele =. Beide symbolen zijn dan ook verschillend in
gebruik. Een duidelijk verschil komt tot uiting in een propositie als
0≡0≡1
Bewijs dat dit een stelling is (syntactisch niveau) en ga na dat het een tautologie is (semantisch
niveau), m.a.w. waar in elke toestand. Wanneer we echter schrijven 0 = 0 = 1 dan bedoelen
we eigenlijk
(0 ≡ 0) ∧ (0 ≡ 1)
Ga na dat dit geen tautologie is. = is dus niet associatief maar ≡ wel.
4.5
Digitale schakelingen
Specificatie en implementatie Een poort is een kleine elektronische eenheid die opgebouwd is uit ´e´en of meerdere transistoren. Dergelijke poorten kunnen 2 soorten ingangssignalen krijgen en uitgangssignalen voortbrengen: een laag signaal tussen 0 en 1 volt, en een
hoog signaal tussen 2 en 5 volt. De uitvoer van de ene poort kan gebruikt worden als invoer
voor een andere poort. Door op die manier poorten aan elkaar te hangen, bekomt men digitale
schakelingen of circuits. Dit zijn de elementaire bouwstenen van de hardware van hedendaagse
computers. Hier beschouwen we digitale schakelingen waar de uitvoer louter afhankelijk is
van de huidige invoer; er komen dus b.v. geen poorten in voor waarvan de uitgang verbonden
is met de ingang.
Een schakeling kan beschreven worden door een schema dat een aantal poorten en hun
onderlinge connecties weergeeft. Er bestaan vaste symbolen voor de verschillende types van
poorten. Een NOT–poort zet een hoog signaal om in een laag signaal en omgekeerd. Een
AND–poort brengt een hoog signaal voort indien alle invoersignalen hoog zijn, anders een
laag signaal. Een OR–poort brengt een laag signaal voort indien alle invoersignalen laag
63
4.5. DIGITALE SCHAKELINGEN
zijn, anders een hoog signaal. Een beschrijving van een circuit HA met 3 AND–poorten, 1
OR–poort en 2 NOT–poorten ziet er b.v. uit als volgt:
c = AND(a, b); d = NOT(b); e = AND(a, d); f = NOT(a); g = AND(b, f ); s = OR(e, g)
(4.1)
De kleine letters komen daarbij overeen met de in– en uitgangssignalen. Vertrekkend van
deze circuitbeschrijving kunnen we een propositie construeren die het gedrag van het circuit
beschrijft.
(c ≡ a ∧ b) ∧ (d ≡ ¬b) ∧ (e ≡ a ∧ d) ∧ (f ≡ ¬a) ∧ (g ≡ b ∧ f ) ∧ (s ≡ e ∨ g)
d We gebruiken de tweewaardige semantiek: waarheidswaarde
We noemen deze propositie HA.
1 correspondeert daarbij met een hoog signaal en 0 met een laag signaal. We kunnen dus de
axioma’s en afleidingsregels van het propositierekenen gebruiken om een propositie die het
gedrag weergeeft van een circuit symbolisch te manipuleren. Merk op dat we de ; vervangen hebben door ∧ en dat we eveneens alle kleine letters uit het Nederlandse alfabet gaan
gebruiken als veranderlijken (omdat x, y en z niet volstaan als we digitale schakelingen van
enige omvang willen bestuderen).
In de tweewaardige semantiek zijn er 28 mogelijkheden om waarheidswaarde 0 of 1 toe te
d In een aantal van die toestanden zal HA
d waarheidskennen aan de veranderlijken uit HA.
waarde 1 hebben. Deze toestanden komen overeen met de in de praktijk mogelijke signalen
d 1 is, is b.v.
als in– en uitvoer van de poorten van HA. Een van de toestanden waarin HA
a
0
b
1
c
0
d
0
e
0
f
1
g
1
s
1
Men kan nagaan dat in elke toestand met
a
0
b
0
c
1
d waarheidswaarde 0 heeft (ga ook na waarom deze situatie zich nooit kan voordoen in
HA
d het gedrag ervan
circuit HA). (4.1) beschrijft de structuur van circuit HA, terwijl HA
beschrijft. Verschillende circuits kunnen hetzelfde gedrag vertonen.
Voorbeeld 37 De structuur van circuit C1 is
d = NOT(AND(a, b))
Het gedrag van C1 is dus
d ≡ ¬(a ∧ b)
b1 . De structuur van circuit C2 is
wat we ook noteren als C
d = OR(NOT(a), NOT(b))
Het gedrag van C2 is dus
d ≡ ¬a ∨ ¬b
b2 . Uit stelling 29 (De Morgan) volgt dat C1 en C2 hetzelfde gedrag
wat we ook noteren als C
vertonen. Toch zijn het in de praktijk verschillende circuits want bij C1 gebruiken we 1 NOT–
poort en 1 AND–poort, terwijl we voor C2 2 NOT–poorten en 1 OR–poort nodig hebben.
64
HOOFDSTUK 4. PROPOSITIEREKENEN
Normaal gezien kent men eerst het gewenste gedrag (de specificatie, gegeven als een propositie
S) en ontwerpt men vervolgens een circuit C daarvoor.
b ⇒ S.
Definitie 25 (Implementatie) Circuit C implementeert propositie S indien C
b ⇒ S een stelling is,
Opdat circuit C specificatie S zou implementeren, eisen we dus dat C
of nog, vermits de propositielogica met de tweewaardige semantiek volledig en betrouwbaar
b ⇒ S een tautologie is, d.w.z. waarheidswaarde 1 heeft in elke toestand. Indien C
b
is, dan C
b
b
waarde 0 heeft, dan is de waarde van C ⇒ S steeds 1. Indien C waarde 1 heeft, dan is de
b ⇒ S 1 op voorwaarde dat de waarde van S ook 1 is. C
b is m.a.w. een versterking
waarde van C
of verstrenging van S (want als C 1 is, dan zal S ook 1 zijn). Om te weten of een circuit C een
b van C bepalen en vervolgens
specificatie S implementeert, moeten we dus eerst het gedrag C
b ⇒ S (door te bewijzen dat het een stelling is of door na te gaan dat het een
nagaan dat C
tautologie is).
b1 . Circuit C1 implementeert specifiVoorbeeld 38 Circuit C1 implementeert specificatie C
b
b2 .
b
catie C2 . Circuit C2 implementeert specificatie C1 . Circuit C2 implementeert specificatie C
De bewijzen hiervan worden als oefening gelaten.
Voorbeeld 39 Specificatie
z⇒x
wordt ge¨ımplementeerd door een circuit met structuur
z=0
Immers het gedrag van dit circuit is z ≡ 0 en we hebben (z ≡ 0) ⇒ z ⇒ x want
(z ≡ 0)
≡
≡
⇒
hst21, x ∧ 1 ≡ xi
hst52, 0 ⇒ x ≡ 1i
hst59(b), (x ≡ y) ∧ (y ⇒ z) ⇒ (x ⇒ z)i
(z ≡ 0) ∧ 1
(z ≡ 0) ∧ (0 ⇒ x)
z⇒x
We kunnen dit ook op een alternatieve manier aantonen door na te gaan dat (z ≡ 0) ⇒ z ⇒ x
een tautologie is
(z ≡ 0) ⇒ z ⇒ x
0 1 0
1 0 1 0
0 1 0
1 0 1 1
1 0 0
1 1 0 0
1 0 0
1 1 1 1
Het resultaat staat in de vierde kolom. Een ander circuit dat ook de specificatie z ⇒ x
implementeert heeft als structuur z = x. Ga dit zelf na als oefening.
Voorbeeld 40 De optelling van bits verloopt als volgt
+
1
1
1
0
+
0
1
0
1
+
0
0
1
1
+
0
0
0
0
65
4.5. DIGITALE SCHAKELINGEN
en is dus van de algemene vorm
a
b
s
+
c
waarbij a en b de op te tellen bits zijn, s de minst significante bit van de som en c de
overdrachtsbit. We willen een circuit dat deze optelling realiseert, m.a.w. waarbij a en b
invoersignalen zijn en dat s en c oplevert als uitvoer, dus
a
0
0
1
1
s
0
1
1
0
b
0
1
0
1
c
0
0
0
1
Wanneer we de kolom voor s en voor c vergelijken met de kolommen uit tabel 4.6, komen we
tot de volgende specificatie
(s ≡ (a 6≡ b)) ∧ (c ≡ a ∧ b)
Men kan nagaan dat deze specificatie ge¨ımplementeerd wordt door het eerder vermelde circuit
HA met structuur
c = AND(a, b); d = NOT(b); e = AND(a, d); f = NOT(a); g = AND(b, f ); s = OR(e, g)
We laten dit over als oefening; merk op dat het allicht handiger zal zijn om een calculationeel
bewijs te leveren dan een waarheidstabel met 256 toestanden!
De specificatie (s ≡ (a 6≡ b)) ∧ (c ≡ a ∧ b) is veel beknopter dan het gedrag
(c ≡ a ∧ b) ∧ (d ≡ ¬b) ∧ (e ≡ a ∧ d) ∧ (f ≡ ¬a) ∧ (g ≡ b ∧ f ) ∧ (s ≡ e ∨ g)
zoals we dat rechtstreeks van het circuit afgelezen hebben. De beknoptere specificatie vermeldt
enkel de ingangs– en uitgangssignalen van de volledige schakeling en zegt niets over “interne
draden”. Dit wordt beschouwd als een goede specificatie omdat overbodige details achterwege
gelaten zijn en de vrijheid van de ontwerper van het circuit op die manier niet belemmerd
wordt. Omwille van zijn functionaliteit, namelijk het optellen van bits, wordt circuit HA
een halve opteller genoemd (Engels: half adder). Dergelijke schakelingen worden gebruikt als
bouwstenen voor het optellen van bitgetallen.
Voorbeeld 41 De optelling van 2 getallen van n bits heeft de algemene vorm
+
dn
an−1
bn−1
dn−1
B.v.
+
1
1
1
0
...
...
...
0
1
1
a1
b1
d1
0
0
1
a0
b0
d0
1
1
0
De overdracht naar kolom i (met 0 ≤ i ≤ n) noteren we als ci . We hebben dan
c0 ≡ 0
66
HOOFDSTUK 4. PROPOSITIEREKENEN
dn ≡ cn
De overdracht vanuit kolom i (met 0 ≤ i < n) is 1 als minstens 2 van ai , bi en ci 1 zijn, m.a.w.
ci+1 ≡ (ai ∧ bi ) ∨ (bi ∧ ci ) ∨ (ci ∧ ai )
di (met 0 ≤ i < n) de minst significante bit van de som van ai , bi en ci . di is 1 als een oneven
aantal van ai , bi en ci 1 zijn, m.a.w.
di ≡ (ai ≡ bi ≡ ci )
Gebruik makend van de stellingen uit opgave 57 kunnen we bewijzen dat
(a ≡ b ≡ c) ≡ ((a 6≡ b) 6≡ c)
(a ∧ b) ∨ (b ∧ c) ∨ (c ∧ a) ≡ (a ∧ b) ∨ ((a 6≡ b) ∧ c)
Merk de gelijkenis op tussen de sombit
(a 6≡ b) 6≡ c
en de overdracht
(a ∧ b) ∨ ((a 6≡ b) ∧ c)
die we bij de optelling van a, b en c moeten bepalen. (a 6≡ b) 6≡ c en (a 6≡ b) ∧ c kunnen
bekomen worden als uitvoersignalen van een halve opteller met invoer a 6≡ b en c. a 6≡ b en
a ∧ b kunnen op analoge manier bekomen worden als uitvoer van een halve opteller met invoer
a en b. We kunnen m.a.w. a.d.h.v. 2 halve optellers en een OR–poort een digitale schakeling
maken voor het optellen van 3 bits. Een dergelijke schakeling wordt een volledige opteller
(Engels: full adder) genoemd. Dergelijke optellers kunnen aan elkaar geschakeld worden om
bitgetallen op te tellen.
NAND–poorten De stelling van de Morgan (stelling 29) verzekert ons dat de werking van
een AND–poort kan gesimuleerd worden door gebruik te maken van 3 NOT–poorten en een
OR–poort. Zo vertonen
d = AND(a, b)
en
d = NOT(OR(NOT(a), NOT(b)))
hetzelfde gedrag, namelijk d ≡ a ∧ b. Daarom volstaat het om NOT–poorten en OR–poorten
te maken. De operator −
∧ waarvan de betekenis gegeven is in tabel 4.6 en die we axiomatisch
zouden kunnen invoeren als
x−
∧ y ≡ ¬(x ∧ y)
is wat dat betreft nog krachtiger. Met een zogenaamde NAND–poort die deze operator
implementeert (m.a.w. uitvoersignaal is 0 indien alle invoersignalen 1 zijn; anders is het
uitvoersignaal 1), kan zowel een NOT–poort, een OR–poort als een AND–poort gesimuleerd
worden! Er geldt immers
¬p ≡ p −
∧1
p ∧ q ≡ (p −
∧ q) −
∧1
p ∨ q ≡ (p −
∧ 1) −
∧ (q −
∧ 1)
Bovendien heeft men voor het maken van een NAND–poort slechts 2 transistoren nodig,
terwijl er voor een OR–poort en een AND–poort telkens 3 nodig zijn (en 1 voor een NOT–
poort). In de praktijk bouwt men dan ook meestal digitale schakelingen uitsluitend gebruik
makend van NAND–poorten.
4.5. DIGITALE SCHAKELINGEN
67
Oefeningen
In onderstaande oefeningen mag je voor de bewijzen van stellingen enkel gebruik maken van:
• de axioma’s uit Tabel 4.1 en axioma 15
• de stellingen uit Tabel 4.2, 4.3 en 4.4 met een kleiner volgnummer
1. We hebben reeds 2 bewijzen gegeven voor stelling 5. Geef nog 2 bewijzen, namelijk ´e´en
waarbij je ¬x ≡ y ≡ x omzet in ¬y, en ´e´en waarbij je ¬x omzet in y ≡ x ≡ ¬y. Welk
van de 4 bewijzen vind je zelf het elegantste en/of gemakkelijkste en waarom?
2. Bewijs onderstaande stellingen.
(a) ¬¬x ≡ x (stelling 6, dubbele negatie)
(b) ¬0 ≡ 1 (stelling 7, negatie van 0)
(c) (x 6≡ y) ≡ ¬x ≡ y (stelling 8)
3. Bewijs onderstaande stellingen.
(a) ((x 6≡ y) 6≡ z) ≡ (x 6≡ (y 6≡ z)) (stelling 11, associativiteit van 6≡)
(b) ((x 6≡ y) ≡ z) ≡ (x 6≡ (y ≡ z)) (stelling 12, onderlinge associativiteit)
(c) x 6≡ y ≡ z ≡ x ≡ y 6≡ z (stelling 13, onderlinge verwisselbaarheid)
4. Bewijs dat 0 het eenheidselement is van ∨, d.w.z. x ∨ 0 ≡ x (stelling 15). Vertrek in je
bewijs van de meest gestructureerde kant.
5. Bewijs stelling 16, namelijk x ∨ (y ∨ z) ≡ (x ∨ y) ∨ (x ∨ z). Het is mogelijk een bewijs
te leveren dat enkel gebruik maakt van axioma’s 7, 8 en 9.
6. Bewijs stelling 17, namelijk x ∨ y ≡ x ∨ ¬y ≡ x. Merk op dat x ∨ y ≡ x ∨ ¬y van dezelfde
algemene vorm is als de rechterzijde van axioma 10.
7. Bewijs stelling 18, namelijk x ∧ y ≡ y ∧ x.
8. Bewijs stelling 20, namelijk x ∧ x ≡ x.
9. Bewijs stelling 22, namelijk x ∧ 0 ≡ 0.
10. Bewijs stelling 23, namelijk x ∧ (y ∧ z) ≡ (x ∧ y) ∧ (x ∧ z)
11. Bewijs stelling 24, namelijk x ∧ ¬x ≡ 0
12. Bewijs stelling 25 (a), namelijk x ∧ (x ∨ y) ≡ x
13. Bewijs stelling 25 (b), namelijk x ∨ (x ∧ y) ≡ x
14. Bewijs stelling 26 (b), namelijk x ∨ (¬x ∧ y) ≡ x ∨ y
15. Bewijs stelling 27, namelijk x ∨ (y ∧ z) ≡ (x ∨ y) ∧ (x ∨ z)
16. Bewijs stelling 28, namelijk x ∧ (y ∨ z) ≡ (x ∧ y) ∨ (x ∧ z)
68
HOOFDSTUK 4. PROPOSITIEREKENEN
17. Bewijs stelling 29 (a), namelijk ¬(x ∧ y) ≡ ¬x ∨ ¬y
18. Bewijs stelling 29 (b), namelijk ¬(x ∨ y) ≡ ¬x ∧ ¬y
19. Bewijs stelling 30, namelijk x ∧ y ≡ x ∧ ¬y ≡ ¬x
20. Bewijs stelling 32, namelijk x ∧ (y ≡ x) ≡ x ∧ y
21. Bewijs stelling 33, namelijk (x ≡ y) ∧ (z ≡ x) ≡ (x ≡ y) ∧ (z ≡ y)
22. Bewijs stelling 34, namelijk x ≡ y ≡ (x ∧ y) ∨ (¬x ∧ ¬y)
23. Bewijs stelling 35, namelijk x 6≡ y ≡ (¬x ∧ y) ∨ (x ∧ ¬y)
24. Bewijs onderstaande stellingen die kunnen gebruikt worden om ⇒ te herschrijven in
termen van andere operatoren.
(a) x ⇒ y ≡ ¬x ∨ y (stelling 36)
(b) x ⇒ y ≡ x ∧ y ≡ x (stelling 37)
(c) x ⇒ y ≡ ¬y ⇒ ¬x (stelling 38, contrapositie)
25. Bewijs stelling 40, namelijk x ⇒ (y ≡ z) ≡ x ⇒ y ≡ x ⇒ z
26. Bewijs stelling 41, namelijk x ⇒ (y ⇒ z) ≡ (x ⇒ y) ⇒ (x ⇒ z)
27. Bewijs stelling 42, namelijk x ∧ y ⇒ z ≡ x ⇒ (y ⇒ z)
28. Bewijs stelling 43, namelijk x ∧ (x ⇒ y) ≡ x ∧ y
29. Bewijs stelling 44, namelijk x ∧ (y ⇒ x) ≡ x
30. Bewijs stelling 45, namelijk x ∨ (x ⇒ y) ≡ 1
31. Bewijs stelling 46, namelijk x ∨ (y ⇒ x) ≡ y ⇒ x
32. Bewijs stelling 47, namelijk x ∨ y ⇒ x ∧ y ≡ x ≡ y
33. Bewijs stelling 48, namelijk x ⇒ x ≡ 1
34. Bewijs stelling 49, namelijk x ⇒ 1 ≡ 1
35. Bewijs stelling 50, namelijk 1 ⇒ x ≡ x
36. Bewijs stelling 51, namelijk x ⇒ 0 ≡ ¬x
37. Bewijs stelling 52, namelijk 0 ⇒ x ≡ 1
38. Bewijs onderstaande stellingen.
(a) x ∧ y ⇒ x (stelling 53(b))
(b) x ∧ y ⇒ x ∨ y (stelling 53(c))
(c) x ∨ (y ∧ z) ⇒ x ∨ y (stelling 53(d))
(d) x ∧ y ⇒ x ∧ (y ∨ z) (stelling 53(e))
69
4.5. DIGITALE SCHAKELINGEN
39. Bewijs onderstaande stellingen m.b.t. gevallenonderzoek.
(a) (x ⇒ z) ∧ (y ⇒ z) ≡ (x ∨ y) ⇒ z (stelling 55)
(b) (x ⇒ z) ∧ (¬x ⇒ z) ≡ z (stelling 56)
40. Bewijs stelling 58, namelijk (x ⇒ y) ∧ (y ⇒ x) ⇒ (x ≡ y)
41. Bewijs stelling 59(b), namelijk (x ≡ y) ∧ (y ⇒ z) ⇒ (x ⇒ z)
42. Bewijs stelling 59(c), namelijk (x ⇒ y) ∧ (y ≡ z) ⇒ (x ⇒ z)
43. Bewijs de stellingen uit Tabel 4.4.
In onderstaande oefeningen mag je voor de bewijzen van stellingen gebruik maken
van alle reeds eerder bewezen stellingen. Tenzij uitdrukkelijk anders vermeld,
wordt er uit gegaan van de tweewaardige semantiek uit 4.4.1.
44. Bewijs de volgende stellingen. Een mogelijkheid is om een ketting op te stellen van
x ≡ y naar x ⇒ y (voor de eerste stelling) waarbij je ≡ en ⇒ gebruikt om de schakels
aan elkaar te hangen.
(a) (x ≡ y) ⇒ x ⇒ y
(b) (x ≡ y) ⇒ y ⇒ x
45. Bewijs de stelling van Shannon, namelijk
r[v := x] ≡ (x ∧ r[v := 1]) ∨ (¬x ∧ r[v := 0])
waarbij r een willekeurige propositie is en v een willekeurige veranderlijke.
46. Bewijs de volgende stelling. Je kan gebruik maken van de stellingen uit Tabel 4.4.
x ∧ y ⇒ (x ≡ y)
47. Bewijs
(x ⇒ y) ⇒ (z ⇒ x) ⇒ (z ⇒ y)
door aannemen van het antecedent x ⇒ y
48. Bewijs
x⇒y⇒x
door aannemen van het antecedent x
49. Bewijs
(x ∨ y) ∧ z ≡ (x ∧ z) ∨ (y ∧ z)
door gevallenonderzoek.
50. Bewijs de volgende stellingen (het kan handig zijn ze te bewijzen in de volgorde waarin
ze opgegeven zijn).
70
HOOFDSTUK 4. PROPOSITIEREKENEN
(a) x ⇒ y ⇒ x
(b) x ⇒ y ⇒ z ≡ y ⇒ x ⇒ z
(c) (x ⇒ y) ⇒ (z ⇒ x) ⇒ (z ⇒ y)
(d) (x ⇒ y) ⇒ (y ⇒ z) ⇒ (x ⇒ z)
(e) (x ⇒ y) ⇒ (x ∨ z) ⇒ (y ∨ z)
(f) (x ⇒ y) ⇒ (x ∧ z) ⇒ (y ∧ z)
51. Bewijs de volgende stellingen.
(a) ¬x ⇒ x ≡ x
(b) ¬x ⇒ x ⇒ y
52. Bewijs de volgende stelling. Maak eventueel gebruik van wat je bewezen hebt in de
vorige oefening.
(¬x ⇒ ¬y) ⇒ (¬x ⇒ y) ⇒ x
53. Bepaal de waarheidswaarde van proposities (a) t.e.m. (f) in toestand S1 en S2 .
(a)
(b)
(c)
(d)
(e)
(f)
¬(x ∨ y)
¬x ∨ y
¬(x ∧ y)
¬x ∧ y
(x ∨ y) ⇒ z
x ∨ (y ⇒ z)
toestand S1
x y
z
1 0
1
1 0
1
1 0
1
1 0
1
1 0
1
1 0
1
toestand S2
x y
z
0 1
1
0 1
1
0 1
1
0 1
1
1 1
0
1 1
0
54. Bepaal de waarheidswaarde van de volgende proposities in alle toestanden.
(a) x ∨ (y ∨ z)
(b) x ∧ (y ∧ z)
(c) x ∧ (y ∨ z)
(d) x ∨ (y ∧ z)
(e) ¬x ⇒ (x ∨ z)
(f) ¬x ≡ (x ∨ z)
(g) (¬x ≡ y) ∨ x
(h) (x ≡ y) ≡ (x ⇒ y) ∧ (y ⇒ x)
55. Ga na dat de axioma’s uit Tabel 4.1 tautologie¨en zijn.
56. Welk van onderstaande proposities zijn tautologie¨en? Indien de propositie een tautologie
is, geef dan een calculationeel bewijs waaruit blijkt dat de propositie een stelling is.
Indien de propositie geen tautologie is, geef dan een voorbeeld van een toestand waarin
de propositie niet waar is.
(a) (x ∨ y) ∧ (x ⇒ z) ⇒ z ∨ y
71
4.5. DIGITALE SCHAKELINGEN
(b) (x ∧ y) ∧ (x ⇒ z) ⇒ z ∧ y
(c) ¬x ∧ (x ⇒ z) ⇒ ¬z
57. Bewijs de volgende stellingen:
(a) (x ≡ y ≡ z) ≡ (x 6≡ y 6≡ z)
(b) ¬(x ∧ y) ∧ (x ∨ y) ≡ (x 6≡ y)
58. Welk van onderstaande circuits implementeert specificatie (z ≡ x ∧ y) ∨ (z 6≡ x)?
(a) z = AND(x, y)
(b) z = NOT(x)
59. Toon aan dat
¬x
x∧y
x∨y
≡
≡
≡
x−
∧1
(x −
∧ y) −
∧1
(x −
∧ 1) −
∧ (y −
∧ 1)
60. Een producent van poorten voor digitale schakelingen beslist om de produktie van NOT–
poorten en OR–poorten stop te zetten en in de toekomst enkel nog NOR–poorten te
maken. Een NOR–poort is een poort waarvan het uitvoersignaal 1 is als alle invoersignalen 0 zijn. Anders is het uitvoersignaal 0. Waarom denk je dat hij die beslissing
maakt?
61. Welke circuits implementeren onderstaande specificaties?
(a) (z ≡ x) ∨ (z ≡ ¬x)
(b) (z ≡ x) ∧ (z ≡ ¬x)

Download Report