Predikatenrekenen

Hoofdstuk 5
Predikatenrekenen
5.1
Inleiding
Om het gedrag van digitale schakelingen te beschrijven, hebben we proposities gebruikt zoals
(s ≡ (a 6≡ b)) ∧ (c ≡ a ∧ b)
s ≡ (a 6≡ b) en c ≡ a ∧ b zijn daarbij proposities die in de tweewaardige semantiek de
waarheidswaarde 0 of 1 kunnen aannemen. Tenzij we het uitdrukkelijk anders vermelden,
zullen we vanaf nu aannemen dat we werken binnen die tweewaardige semantiek en dat we
de 15 axioma’s en de afleidingsregels uit het vorige hoofdstuk ter beschikking hebben voor
het propositierekenen. Er is een gelijkenis tussen bovenvermelde proposities en formules zoals
x = x + a en iszero a uit hoofdstuk 2. We willen nu ook over die formules formeel kunnen
redeneren met expressies zoals
x = x + a ⇒ iszero a
Daarom maken we in dit hoofdstuk de stap naar predikatenrekenen. Een predikaat is een
functie die enkel de waarden 0 en 1 kan aannemen. Operatoren als ≡, = en iszero kunnen
opgevat worden als predikaten. We zullen in dit hoofdstuk vooral veel aandacht besteden aan
de predikaten ∀ en ∃ (de zogenaamde kwantoren).
In dit hoofdstuk wordt zeer duidelijk dat we naast de calculationele stijl ook kiezen voor
een functionele stijl waarbij wiskundige objecten zoveel mogelijk als functies gezien worden.
Dat predikaten, en in het bijzonder kwantoren, functies zijn is daar een tekenend voorbeeld
van. We zullen dan ook in eerste instantie de nodige aandacht besteden aan het concept
“functie”. Een functie wordt volledig gekenmerkt door haar definitieverzameling en haar
voorschrift (d.w.z. dat als je definitieverzameling en voorschrift kent, dat je dan de functie kent, en omgekeerd). Zoals de benaming laat vermoeden, is de definitieverzameling de
verzameling van waarden waarvoor de functie gedefinieerd is. Daarom zullen we ook eerst
het begrip “verzameling” van naderbij bekijken. We maken daarbij gebruik van propositierekenen; dat verklaart waarom we nu pas toekomen aan het rekenen met verzamelingen en
functies. Anderzijds zullen we, eens we ook predikatenrekenen ter beschikking hebben, onze
batterij rekenregels voor functies nog verder kunnen uitbreiden.
Tot nu toe hebben we steeds gewerkt binnen het veilige kader van ´e´en taal waar de zinnen (eenvoudige wiskundige uitdrukkingen, lambdatermen, proposities) slechts een beperkt
aantal gedaantes konden aannemen. We hebben elk van deze formele systemen apart behandeld en zijn tot de vaststelling gekomen dat ze elk op zich reeds zeer expressief zijn (denk
73
74
HOOFDSTUK 5. PREDIKATENREKENEN
b.v. aan de programmeertaal die we gebouwd hebben in de lambdacalculus). Zoals uit het
voorbeeld hierboven al blijkt, zullen we nu verschillende (deel)talen samen gaan gebruiken
(in het voorbeeld: wiskundige uitdrukkingen en propositierekenen). Een ander voorbeeld
kennen we uit de programmeertaal Haskell, waar we mogen schrijven (\x -> 4+x)3 wat in
de ons vertrouwdere notatie staat voor (λx.4 + x)3, m.a.w. een combinatie van wiskundige
uitdrukkingen en lambdarekenen. In de overkoepelende taal die op die manier ontstaat zijn
er zoveel verschillende mogelijkheden dat het opstellen van een BNF–syntax geen eenvoudige
klus meer is. Gelukkig is dit ook niet nodig om in de praktijk te kunnen werken met zinnen
uit die taal. We houden de gebruikelijke afspraken aan m.b.t. weglaten van haakjes.
Afspraak 12 (Reductie van haakjes)
• De buitenste haakjes rond een uitdrukking die op zichzelf staat, mogen weggelaten
worden.
• 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 prioriteiten zijn als volgt geregeld:
– Substitutie heeft de hoogste prioriteit.
– Unaire operatoren hebben een hogere prioriteit dan binaire operatoren.
– De binaire operatoren worden als volgt gerangschikt van hoogste naar laagste prioriteit (op dezelfde lijn betekent dezelfde prioriteit):
+−∪∩\
=<>≤≥∈⊆
∨∧
⇒⇐
≡ 6≡
Wanneer we in het vervolg spreken over een expressie, dan bedoelen we een zin uit de overkoepelende taal. Eenvoudige wiskundige uitdrukkingen, lambdatermen en proposities zijn dus
allemaal expressies. Ook zinnen uit nieuwe (deel)talen die we verder nog zullen invoeren,
zijn expressies. Als notatie voor een willekeurige expressie gebruiken we vaak d of e. De
afleidingsregel instantiatie van een stelling blijft algemeen gelden. Voor gelijkheid = en ≡
hebben we bovendien de afleidingsregel van Leibniz (gelijken vervangen door gelijken) en
transitiviteit. Voor = hebben we de afleidingsregel voor symmetrie; voor ≡ maken we wat
dat betreft gebruik van axioma 2 (x ≡ y ≡ y ≡ x). Ook reflexiviteit van =, m.a.w. e = e voor
een willekeurige uitdrukking e is een beschikbare stelling.
5.2
Rekenen met Verzamelingen
De taal van de verzamelingen wordt gekenmerkt door de volgende BNF–syntax:
verzameling
applicatie
veranderlijke
constante
cop 2
::=
::=
::=
::=
::=
veranderlijke | constante | applicatie .
(verzameling cop 2 verzameling).
X | Y | Z.
∅ | B | N | Z | Q | R | C.
∪|∩|\.
75
5.2. REKENEN MET VERZAMELINGEN
De buitenste haakjes rond een applicatie mogen zoals gebruikelijk weggelaten worden. ∪,
∩ en \ hebben dezelfde prioriteit. Om willekeurige verzamelingen aan te duiden, gebruiken
we als notatie vaak S en T . Om formeel te kunnen rekenen met verzamelingen, grijpen we
terug naar het propositierekenen. De sleutel hiertoe is de lidmaatschapsoperator ∈. Voor een
willekeurige expressie e en een willekeurige verzameling S, kunnen we schrijven
e∈S
We lezen dit als “e behoort tot S”, “e is van het type S” of nog “e is een element van S”.
Voorbeeld 42
(x ∧ y) ∈ B
π∈R
(x ∧ π ∈ R) ∈ B
De lidmaatschapsoperator laat ons toe om een aantal definities in te voeren m.b.t. de operatoren uit de verzamelingenleer. We doen dit a.d.h.v. axioma’s.
Axioma
Axioma
Axioma
Axioma
Axioma
Axioma
V1
V2
V3
V4
V5
V6
unie
doorsnede
niet–lidmaatschap
verschil
lege verzameling
singleton
x∈X ∪Y
x∈X ∩Y
x∈
/X
x ∈ X\Y
x∈
/∅
x ∈ ιy
≡
≡
≡
≡
x∈X ∨x∈Y
x∈X ∧x∈Y
¬(x ∈ X)
x∈X ∧x∈
/Y
≡
x=y
Heel wat gekende stellingen uit de verzamelingenleer kunnen bewezen worden a.d.h.v. deze
axioma’s. We geven een voorbeeld en verwijzen naar de opgaven voor andere voorbeelden.
Voorbeeld 43 Bewijs van stelling x ∈ X ∩ Y ≡ x ∈ Y ∩ X
x∈X ∩Y
≡
≡
≡
haxV2, x ∈ X ∩ Y ≡ x ∈ X ∧ x ∈ Y i
hst18, x ∧ y ≡ y ∧ xi
haxV2, x ∈ X ∩ Y ≡ x ∈ X ∧ x ∈ Y i
x∈ X ∧x ∈Y
x∈Y ∧x∈X
x∈Y ∩X
Merk op dat in de tweede stap uit bovenstaand bewijs de volgende concrete invulling van de
afleidingsregel voor instantiatie van een stelling gebruikt werd:
x∧y ≡ y∧x
(x ∧ y ≡ y ∧ x)[x, y := x ∈ X, x ∈ Y ]
We willen nu nog een stap verder gaan en bewijzen dat X ∩ Y = Y ∩ X. Daarvoor hebben
we gelijkheid van verzamelingen nodig. We voeren dit in a.d.h.v. een axioma en een strikte
afleidingsregel.
Axioma V7 (Gelijkheid van verzamelingen)
X = Y ⇒ (x ∈ X ≡ x ∈ Y )
76
HOOFDSTUK 5. PREDIKATENREKENEN
Afleidingsregel (Extensionaliteit voor verzamelingen)
q ⇒ (v ∈ S ≡ v ∈ T )
q⇒S=T
met q ⇒ (v ∈ S ≡ v ∈ T ) een stelling en x niet vrij in q, S en T .
Op het eerste zicht lijkt het vreemd om ´en een axioma ´en een afleidingsregel in te voeren.
Leg voor jezelf uit waarom de expressie X = Y ≡ (x ∈ X ≡ x ∈ Y ) geen goede keuze zou
zijn als axioma om de gelijkheid van verzamelingen te defini¨eren. Uit de afleidingsregel van
extensionaliteit volgt onmiddellijk een bewijsmethode voor de gelijkheid van verzamelingen.
Bewijsmethode 3 Als bewijs voor S = T volstaat een bewijs voor
v∈S ≡ v∈T
met v niet vrij in S en T .
Verklaring
Merk op dat
v∈S ≡ v∈T
≡
hst50, 1 ⇒ x ≡ xi
1⇒v∈S ≡ v∈T
m.a.w. 1 ⇒ v ∈ S ≡ v ∈ T is een stelling, waaruit we met de afleidingsregel voor extensionaliteit kunnen afleiden dat
1 ⇒ (S = T )
een stelling is. Bovendien
1 ⇒ (S = T )
≡
hst50, 1 ⇒ x ≡ xi
S=T
waaruit het gestelde.
Uit het in Voorbeeld (43) gegeven bewijs voor x ∈ X ∩Y ≡ x ∈ Y ∩X kunnen we dus besluiten
dat X ∪ Y = Y ∪ X. A.d.h.v. een achtste axioma voeren we inclusie van verzamelingen in.
Axioma V8 (Inclusie)
X ⊆Y ≡ Y =X ∪Y
X ⊆ Y wordt gelezen als “X is bevat in Y ” of “X is een deelverzameling van Y ”.
Voor een v die niet vrij voorkomt in S kunnen we schrijven e ∈ {v : S |p} met de gebruikelijke
betekenis
e ∈ {v : S | p} ≡ e ∈ S ∧ p[v := e]
Voorbeeld 44
m ∈ {n : Z | n > 2006} ≡ m ∈ Z ∧ m > 2006
77
5.3. REKENEN MET FUNCTIES
5.3
Rekenen met functies
Een functie is een wiskundig object dat volledig gekenmerkt wordt door haar definitieverzameling of domein en haar voorschrift. Een manier om een functie f te defini¨eren is dan ook
door het geven van 2 axioma’s:
• een definitieverzamelingaxioma van de vorm D f = S of van de vorm x ∈ D f ≡ p
• een voorschriftaxioma van de vorm x ∈ D f ⇒ q
Daarbij is S een verzameling en zijn p en q proposities. x komt typisch vrij voor in p en
q, terwijl f typisch enkel vrij voorkomt in q. We maken verder gebruik van f en g om
willekeurige functies aan te duiden. Indien niet uitdrukkelijk anders opgegeven, gebruiken
we de zogenaamde prefixnotatie waarbij de waarde van f in x geschreven wordt als f x.
Wanneer de waarheidswaarde van het antecedent in het voorschriftaxioma 0 is, dan is de
waarheidswaarde van het volledige axioma 1. Het consequent wordt daarom enkel ge¨evalueerd
(d.w.z. de waarde ervan wordt bepaald) wanneer de waarde van het antecedent 1 is. Wanneer de q uit het voorschriftaxioma begint met “f x =,” dan spreekt men van een expliciet
voorschrift; in het andere geval van een impliciet voorschrift. Onderstaande voorbeelden
illustreren respectievelijk een impliciet en een expliciet voorschrift.
Voorbeeld 45 De functie wrtl wordt gedefinieerd door de volgende axioma’s:
D wrtl
x ∈ D wrtl
=
⇒
N
wrtl x · wrtl x = x
Een alternatief definitieverzamelingaxioma is x ∈ D wrtl ≡ x ∈ Z ∧ x ≥ 0.
Voorbeeld 46 De functie id die alle elementen uit X afbeeldt op zichzelf wordt gedefinieerd
door de volgende axioma’s:
D id = X
x ∈ D id ⇒ id x = x
Wanneer een expliciet voorschrift voorhanden is, dan kan de functie kortweg genoteerd worden
m.b.v. een functie–abstractie die sterk gelijk op de manier waarop functies voorgesteld worden
bij lambdarekenen.
Definitie 26 (Functie–abstractie) Een functie–abstractie is een expressie van de vorm
v : S ∧. p . e
waarbij S een verzameling, p een propositie, e een expressie en v een veranderlijke is die
niet vrij voorkomt in S. Alle voorkomens van v in e zijn gebonden en dus niet vrij. Deze
functie–abstractie is een beknopte notatie voor de volgende axioma’s:
x ∈ D (v : S ∧. p . e)
x ∈ D (v : S ∧. p . e)
≡
⇒
x ∈ S ∧ p[v := x]
(v : S ∧. p . e)x = e[v := x]
Bovendien korten we v : S ∧. 1 . e af tot
v:S .e
78
HOOFDSTUK 5. PREDIKATENREKENEN
Het hierboven gegeven voorschriftaxioma is expliciet. Het definitieverzamelingaxioma kan
ook geschreven worden als (zie opgave 6)
D (v : S ∧. p . e) = {v : S | p}
Men noemt dit een puntvrije stijl omdat er geen veranderlijke x meer in optreedt.
Voorbeeld 47 Gegeven is de functie f gedefinieerd door een functie–abstractie als
f = n : Z ∧. n ≥ 0 . 2 · n
Men gaat na dat
m ∈ Df
≡
≡
≡
≡
hdef. f i
hdef. functie–abstractiei
hsubstitutiei
hdef. Ni
m ∈ D (n : Z ∧. n ≥ 0 . 2 · n)
m ∈ Z ∧ (n ≥ 0)[n := m]
m∈Z∧m≥0
m∈N
Met de afleidingsregel voor extensionaliteit leiden we hieruit af dat D f = N. Op gelijkaardige
wijze bekomt men (ga dit na)
m ∈ Df ⇒ f m = 2·m
Voorbeeld 48 De functie uit voorbeeld 46 kan kortweg gedefinieerd worden door de volgende
functie–abstractie
x:X .x
Het voorschriftaxioma van een functie wordt vaak gebruikt om in elementen van de definitieverzamelingen de functiewaarde te evalueren. In voorbeeld 47 kan het voorschriftaxioma
m ∈ D f ⇒ f m = 2 · m gebruikt worden om voor een element m uit de definitieverzameling
f m te vervangen door 2 · m. Om dit vlot en correct te doen maken we een afspraak die een
nieuwe mogelijkheid introduceert in onze bewijzen in calculationele stijl. We beginnen met
de bewijsmethode die aan de basis ligt van deze afspraak.
Bewijsmethode 4 (Leibniz onder aanname) Als bewijs voor
(p ∧ q) ⇒ r[v := d] ≡ (p ∧ q) ⇒ r[v := d′ ]
volstaat een bewijs voor
p ⇒ d = d′
We noteren dit in een calculationeel bewijs als
(p ∧ q) ⇒ r[v := d]
≡
hp ⇒ d = d′ i
(p ∧ q) ⇒ r[v := d′ ]
79
5.3. REKENEN MET FUNCTIES
Verklaring We verklaren deze methode door gebruik te maken van de bewijsmethode van
aanname van het antecedent. Om
p ⇒ (r[v := d] ≡ r[v := d′ ])
te bewijzen nemen we eerst p aan en bewijzen dat onder deze aanname
r[v := d] ≡ r[v := d′ ]
Dit verloopt als volgt
1
≡
⇒
haannames p en p ⇒ d = d′ i
hst54i
p ∧ (p ⇒ d = d′ )
d = d′
Uit stelling 50 volgt dat bovenstaande een bewijs is voor d = d′ onder de aanname p. Met de
afleidingsregel van Leibniz leiden we af dat
r[v := d] ≡ r[v := d′ ]
onder aanname p. We gebruiken dit in de volgende ketting
p∧q
⇒
⇒
hst53bi
hzie bovenstaandei
p
r[v := d] ≡ r[v := d′ ]
Uit stelling 40 volgt het gestelde.
Merk op dat het hier louter gaat om een bewijsmethode en een bijhorende notatie–afspraak
die elegante bewijzen toelaat, en dus niet om de introductie van een nieuw axioma of een
nieuwe afleidingsregel!
Voorbeeld 49 Zij f zoals in voorbeeld 47.
m ∈ D f ∧ m > 0 ⇒ ff m
m =1
≡ hm ∈ D f ⇒ f m = 2 · mi m ∈ D f ∧ m > 0 ⇒
2·m
2·m
=1
In voorbeeld 47 hebben we het gelijkheidsteken gebruikt om gelijkheid van functies aan te
geven, namelijk f en n : Z ∧. n ≥ 0 . 2·n. We hebben die gelijkheid verder enkel gebruikt om het
principe van Leibniz te kunnen toepassen, d.w.z. om f te vervangen door n : Z ∧. n ≥ 0 . 2 · n
en omgekeerd. De betekenis die we willen geven aan gelijkheid van functies is dat 2 functies
gelijk zijn indien ze dezelfde definitieverzameling hebben en ze dezelfde waarde toekennen aan
dezelfde elementen uit hun definitieverzameling. Net als bij verzamelingen introduceren we
gelijkheid van functies a.d.h.v. een axioma en een strikte afleidingsregel.
Axioma (Gelijkheid van functies)
(f = g) ⇒ (D f = D g ∧ (x ∈ D f ∩ D g ⇒ f x = g x))
80
HOOFDSTUK 5. PREDIKATENREKENEN
Afleidingsregel (Extensionaliteit voor functies)
q ⇒ D f = D g ∧ (x ∈ D f ∩ D g ⇒ f x = g x)
q⇒f =g
met q ⇒ D f = D g ∧ (x ∈ D f ∩ D g ⇒ f x = g x) een stelling en x niet vrij in q, f en g.
Een bekendere vorm van gelijkheid van functies kan als stelling bewezen worden eens we de
kwantor ∀ ter beschikking hebben (zie opgave 13).
Bewijsmethode 5 Als bewijs voor f = g volstaat een bewijs voor
Df = Dg
gevolgd door
• of een bewijs voor x ∈ D f ∩ D g ⇒ f x = g x
• of een bewijs voor x ∈ D f ⇒ f x = g x
• of een bewijs voor x ∈ D g ⇒ f x = g x
Het tweede stuk wordt bovendien vaak bewezen door aanname van het antecedent. Leg voor
jezelf uit waarom dit een correcte bewijsmethode is.
We geven nog een aantal voorbeelden van functies gedefinieerd a.d.h.v. een functie–abstractie.
Definitieverzameling– en voorschriftaxioma zijn er als illustratie bij vermeld. We zullen in
het vervolg nog veelvuldig gebruik maken van deze functies.
Definitie 27 (Constante functie)
X •y = x:X .y
Bijhorende definitieverzameling– en voorschriftaxioma’s zijn
D (X • y)
x ∈ D (X • y)
=
⇒
X
(X • y) x = y
Definitie 28 (Samenstelling)
f ◦ g = x : D g ∧. g x ∈ D f . f (g x)
Bijhorende definitieverzameling– en voorschriftaxioma’s zijn
x ∈ D (f ◦ g)
x ∈ D (f ◦ g)
≡
⇒
x ∈ Dg ∧gx ∈ Df
(f ◦ g) x = f (g x)
Definitie 29 (Puntsgewijze uitbreiding van een unaire operator)
g f =g◦f
Bijhorende definitieverzameling– en voorschriftaxioma’s zijn
x ∈ D (g f )
x ∈ D (g f )
≡
⇒
x ∈ Df ∧f x ∈ Dg
(g f ) x = g(f x)
81
5.4. KWANTOREN
Definitie 30 (Puntsgewijze uitbreiding van een binaire operator)
fb
⋆ g = x : D f ∩ D g ∧. (f x, g x) ∈ D ⋆ . (f x) ⋆ (g x)
Bijhorende definitieverzameling– en voorschriftaxioma’s zijn
x ∈ D (f b
⋆ g)
x ∈ D (f b
⋆ g)
≡
⇒
x ∈ D f ∩ D g ∧ (f x, g x) ∈ D ⋆
(f b
⋆ g) x = (f x) ⋆ (g x)
Definitie 31 (Beperking)
f ⌉X = x:Df ∩ X .f x
Bijhorende definitieverzameling– en voorschriftaxioma’s zijn
x ∈ D (f ⌉ X)
x ∈ D (f ⌉ X)
5.4
5.4.1
≡
⇒
x ∈ Df ∩X
(f ⌉ X) x = f x
Kwantoren
Definitie en bewijstechnieken
Definitie 32 (Predikaat) Een predikaat is een functie die enkel de waarden 0 en 1 aanneemt.
We gebruiken P en Q om willekeurige predikaten aan te duiden.
Definitie 33 (Kwantoren) De kwantoren ∀ (overal) en ∃ (ergens) zijn gedefinieerd als
∀P
∃P
≡
≡
P = DP •1
¬(P = D P • 0)
Door de bijzondere keuze P = x : X . p bekomen we puntsgewijze gedaante zoals we die het
vaakst tegenkomen in wiskundige werken. ∀P en ∃P dienen gelezen te worden als “overal
P ” en “ergens P ” respectievelijk, terwijl ∀(x : X . p) vaak gelezen wordt als “voor alle x in X
geldt p” en ∃(x : X . p) als “er bestaat een x in X waarvoor geldt p”. ∀ wordt ook wel eens
de universele kwantor genoemd en ∃ de existenti¨ele kwantor.
De volgende stelling kan bewezen worden door op ∀P eerst de definitie van ∀P toe te passen
en vervolgens het axioma van gelijkheid van functies (ga dit na).
Stelling (Invulling)
∀P ⇒ x ∈ D P ⇒ P x
met x niet vrij in q en P .
In deze stelling hebben we enkel een implicatie en geen equivalentie. Dit komt omdat in het
gebruikte axioma voor gelijkheid van functies ook enkel een implicatie optreedt. Voor de
omgekeerde richting geeft de afleidingsregel m.b.t. gelijkheid van functies aanleiding tot de
volgende bewijsmethode (leg voor jezelf uit waarom):
82
HOOFDSTUK 5. PREDIKATENREKENEN
Bewijsmethode (Veralgemening) Als bewijs voor q ⇒ ∀P volstaat een bewijs voor q ⇒
x ∈ D P ⇒ P x (met x niet vrij in q en P ). We noteren dit in een calculationeel bewijs als
⇒
⇒
q
hverantwoordingi
hveralgemeningi
x ∈ DP ⇒ P x
∀P
Uiteraard kan ook hier weer 1 gekozen worden voor q. Het fundamenteel verschil tussen
invulling en veralgemening is dat invulling zegt dat
∀P ⇒ x ∈ D P ⇒ P x
een stelling is, terwijl veralgemening zegt dat als
x ∈ D P ⇒ Px
een stelling is, dat dan ook
∀P
een stelling is.
We kunnen gebruik maken van de stelling “invulling” en de bewijsmethode “veralgemening”
om stellingen over ∀ te bewijzen, en vervolgens onderstaande stelling “dualiteit” gebruiken
om daaruit de corresponderende stellingen voor ∃ te halen.
Stelling (Dualiteit) Voor een willekeurig predikaat P geldt
∀(¬P ) ≡ ¬(∃P )
∃(¬P ) ≡ ¬(∀P )
We schetsen de hoofdlijn van het bewijs van de eerste equivalentie. Hierbij maken we gebruik
van 3 lemma’s die uiteraard op zich ook moeten bewezen worden. We verwijzen hiervoor naar
opgave 8.
Bewijs van ∀(¬P ) ≡ ¬(∃P )
∀(¬P )
≡
≡
≡
≡
≡
≡
≡
hdef ∀i
hD (¬P ) = D P i
h¬ P = Q ≡ P = ¬ Qi
h¬ (D P • 1) = D P • (¬1)i
hax4, 0 ≡ ¬1i
hst6, ¬¬x ≡ xi
hdef ∃i
¬P = D (¬P ) • 1
¬P = D P • 1
P = ¬(D P • 1)
P = D P • (¬1)
P = DP •0
¬¬(P = D P • 0)
¬(∃P )
Voor het bewijs van de tweede equivalentie verwijzen we naar opgave 9. Door toepassing van
stelling 5 uit propositierekenen, namelijk ¬x ≡ y ≡ x ≡ ¬y hebben we hieruit ook meteen
de volgende stellingen als rekenregels ter beschikking:
∃P ≡ ¬(∀(¬P ))
83
5.4. KWANTOREN
∀P ≡ ¬(∃(¬P ))
Die komen in de praktijk goed van pas wanneer we de ∃ kwantor willen “omzetten” in de
∀ kwantor, b.v. omdat we een stelling bewezen hebben voor ∀ en de duale stelling voor ∃
daaruit willen afleiden. Dit is de bewijstechniek die we het meest zullen aanwenden.
Soms zullen we echter ook “rechtstreekse” bewijzen leveren voor stellingen met ∃ door
gebruik te maken van de stelling “getuige” en de bewijsmethode “vrijwilliger” die we op
dezelfde manier bekomen als “invulling” en “veralgemening”, namelijk door het gebruiken
van het axioma en de afleidingsregel van functiegelijkheid in de definitie van ∃.
Stelling (Getuige)
x ∈ D P ∧ P x ⇒ ∃P
Bewijs van getuige
(∃P ⇒ 0)
≡
≡
≡
⇒
≡
hdef ∃i
hst38, x ⇒ y ≡ ¬y ⇒ ¬xi
hst7, ¬0 ≡ 1, st50, 1 ⇒ x ≡ x, st6, ¬¬x ≡ xi
hax gelijkheid functies; def • i
hax4, 0 ≡ ¬1; st5, ¬x ≡ y ≡ x ≡ ¬yi
¬(P = D P • 0) ⇒ 0
¬0 ⇒ ¬¬(P = D P • 0)
P = DP •0
x ∈ D P ⇒ Px ≡ 0
x ∈ D P ⇒ ¬(P x)
Verder hebben we
(∃P ⇒ 0) ⇒ (x ∈ D P ⇒ ¬(P x))
≡
≡
≡
≡
hst51, x ⇒ 0 ≡ ¬xi
hst38, x ⇒ y ≡ ¬y ⇒ ¬xi
hst36, x ⇒ y ≡ ¬x ∨ y, st6, ¬¬x ≡ xi
hst29b, ¬(x ∨ y) ≡ ¬x ∧ ¬y, st6, ¬¬x ≡ xi
¬(∃P ) ⇒ (x ∈ D P ⇒ ¬(P x))
¬(x ∈ D P ⇒ ¬(P x)) ⇒ ¬¬(∃P )
¬(x ∈
/ D P ∨ ¬(P x)) ⇒ ∃P
(x ∈ D P ∧ P x) ⇒ ∃P
Merk op dat m.b.v. aftakking bovenstaande stelling ook kan geschreven worden als
x ∈ D P ⇒ P x ⇒ ∃P
In de omgekeerde richting bekomen we door toepassen van de afleidingsregel voor gelijkheid
van functies de volgende bewijsmethode (ga dit zelf na).
Bewijsmethode (Vrijwilliger) Als bewijs voor ∃P ⇒ q volstaat een bewijs voor
x ∈ D P ∧ Px ⇒ q
(met x niet vrij in P en q).
Bemerk ook hier weer het fundamenteel verschil: getuige zegt dat
x ∈ D P ⇒ P x ⇒ ∃P
84
HOOFDSTUK 5. PREDIKATENREKENEN
een stelling is, terwijl vrijwilliger zegt dat als
x ∈ D P ∧ Px ⇒ q
een stelling is, dat dan ook
∃P ⇒ q
een stelling is.
5.4.2
Rekenregels voor kwantoren
Stelling (Interacties) Voor predikaten P en Q met D P = D Q geldt
b Q) ≡ ∀P ∧ ∀Q (interactie tussen ∀ en ∧ )
∀(P ∧
b Q) ⇐ ∀P ∨ ∀Q (interactie tussen ∀ en ∨ )
∀(P ∨
b Q) ⇒ ∃P ∧ ∃Q (interactie tussen ∃ en ∧ )
∃(P ∧
b Q) ≡ ∃P ∨ ∃Q (interactie tussen ∃ en ∨ )
∃(P ∨
De eerste interactie kan bewezen worden met de methode van wederzijdse implicatie. Voor
de rest is de werkwijze analoog aan het bewijs voor de tweede interactie dat we hieronder als
voorbeeld geven.
b Q) ⇐ ∀P ∨ ∀Q
Bewijs van ∀(P ∨
∀P ∨ ∀Q
⇒
≡
≡
≡
≡
≡
≡
⇒
hinvullingi
hst36, x ⇒ y ≡ ¬x ∨ yi
hD P = D Q; ax9, x ∨ x ≡ xi
hst36, x ⇒ y ≡ ¬x ∨ yi
hD P = D Q; X ∩ X = Xi
hP en Q zijn predi
hdef b i
hveralgemeningi
(x ∈ D P ⇒ P x) ∨ (x ∈ D Q ⇒ Q x)
¬(x ∈ D P ) ∨ P x ∨ ¬(x ∈ D Q) ∨ Q x
¬(x ∈ D P ) ∨ P x ∨ Q x
x ∈ DP ⇒ P x ∨ Qx
x ∈ DP ∩DQ ⇒ P x ∨ Qx
x ∈ D P ∩ D Q ∧ (P x, Qx) ∈ D ∨ ⇒ P x ∨ Q x
b Q) ⇒ (P ∨
b Q)x
x ∈ D (P ∨
b
∀(P ∨ Q)
De derde interactie kan afgeleid worden uit de tweede interactie gebruik makend van de stelling
omtrent dualiteit. We hebben bovendien een lemma nodig waarvan we het bewijs overlaten
als oefening (zie opgave 10).
b Q) ⇒ ∃P ∧ ∃Q
Bewijs van ∃(P ∧
b Q)
∃(P ∧
≡
≡
⇒
≡
≡
hdualiteiti
b Q) = ¬ P ∨
b ¬ Qi
h¬ (P ∧
hinteractie tussen ∀ en ∨; st38, x ⇒ y ≡ ¬y ⇒ ¬xi
hst29b, ¬(x ∨ y) ≡ ¬x ∧ ¬yi
hdualiteiti
b Q))
¬∀(¬ (P ∧
b ¬ Q))
¬(∀(¬ P ∨
¬(∀(¬ P ) ∨ ∀(¬ Q))
¬(∀(¬ P )) ∧ ¬(∀(¬ Q))
∃P ∧ ∃Q
85
5.4. KWANTOREN
Het bewijs van de vierde interactie verloopt analoog.
Om de wisselwerking met ⇒ te kunnen beschrijven, hebben we eerst het begrip “filter” nodig.
Definitie 34 (Filter)
f ↓ P = x : D f ∩ D P ∧. P x . f x
Bijhorende definitieverzameling– en voorschriftaxioma’s zijn
x ∈ D (f ↓ P )
x ∈ D (f ↓ P )
≡
⇒
x ∈ Df ∩DP ∧P x
(f ↓ P ) x = f x
Stelling (Ruilen) Voor willekeurig predikaten P en Q geldt
∀(P ↓ Q) ≡ ∀(Q c
⇒ P)
b P)
∃(P ↓ Q) ≡ ∃(Q ∧
Bewijs van ∀(P ↓ Q) ≡ ∀(Q c
⇒ P ) met de methode van wederzijdse implicatie
∀(P ↓ Q)
⇒
≡
≡
≡
≡
⇒
hinvullingi
hdef. ↓i
hst42, x ⇒ y ⇒ z ≡ x ∧ y ⇒ zi
hP en Q zijn predi
hX ∩ Y = Y ∩ X; def. b i
hveralgemeningi
x ∈ D (P ↓ Q) ⇒ (P ↓ Q)x
x ∈ DP ∩ DQ ∧ Qx ⇒ P x
x ∈ DP ∩ DQ ⇒ Qx ⇒ P x
x ∈ D P ∩ D Q ∧ (Q x, P x) ∈ D (⇒) ⇒ Q x ⇒ P x
x ∈ D (Q c
⇒ P ) ⇒ (Q c
⇒ P )x
∀(Q c
⇒ P)
Het bewijs van de andere implicatie verloopt volledig analoog.
b P ) kan aangetoond worden gebruik
De andere equivalentie, namelijk ∃(P ↓ Q) ≡ ∃(Q ∧
makend van de stelling “dualiteit” en 3 lemma’s waarvan we het bewijs laten als oefening (zie
opgaven 10 en 11).
Voor een volgende paar rekenregels maken we gebruik van transpositie (het omkeren van de
volgorde van argumenten).
Definitie 35 (Transpositie) Zij f een functie die 2 argumenten neemt, dan is f T gedefinieerd
door volgend definitieverzameling– en voorschriftaxioma:
y ∈ D fT
y ∈ D fT
≡
⇒
∀(x : D f . y ∈ D (f x))
D (f T y) = D f ∧ (x ∈ D (f T y) ⇒ f T y x = f x y)
86
HOOFDSTUK 5. PREDIKATENREKENEN
Volgend lemma blijkt goed van pas te komen bij het bewijzen van de rekenregels voor dummy
wissel:
Hulpstelling (Domeinovergang)
x ∈ D f ∧ y ∈ D (f x) ≡ y ∈ D f T ∧ x ∈ D (f T y)
Voor een bewijs van deze hulpstelling kan gebruik gemaakt worden van stelling 34, namelijk
x ∧ y ≡ x ∧ (x ⇒ y).
Stelling (Dummy wissel) Voor een willekeurige functie R met domein X zo dat R x een
predikaat is voor elke x in X, geldt
∀(∀ ◦ R) ≡ ∀(∀ ◦ RT )
∃(∃ ◦ R) ≡ ∃(∃ ◦ RT )
∀(∃ ◦ R) ⇐ ∃(∀ ◦ RT )
Een bewijs voor de eerste wissel kan geleverd worden met de methode van wederzijdse implicatie, gebruik makend van de stelling “invulling” en de bewijsmethode “veralgemening”.
Met onderstaand bewijs van de tweede wissel illustreren we het gebruik van “vrijwilliger” en
“getuige”. De derde wissel kan bewezen worden door gebruik te maken van invulling, veralgemening, vrijwilliger en getuige samen.
Bewijs van ∃(∃ ◦ RT ) ≡ ∃(∃ ◦ R) met de methode van wederzijdse implicatie
Als bewijs voor ∃(∃ ◦ RT ) ⇒ ∃(∃ ◦ R) volstaat (wegens bewijsmethode vrijwilliger) een bewijs
voor
y ∈ D (∃ ◦ RT ) ∧ (∃ ◦ RT )y ⇒ ∃(∃ ◦ R)
y ∈ D (∃ ◦ RT ) ∧ (∃ ◦ RT )y ⇒ ∃(∃ ◦ R)
≡
≡
≡
hdef ◦i
hRT y is predi
hst42, x ⇒ y ⇒ z ≡ x ∧ y ⇒ zi
y ∈ D RT ∧ RT y ∈ D ∃ ∧ ∃(RT y) ⇒ ∃(∃ ◦ R)
y ∈ D RT ∧ RT y ∈ D ∃ ⇒ ∃(∃ ◦ R)
∃(RT y) ⇒ (y ∈ D RT ⇒ ∃(∃ ◦ R))
Als bewijs voor ∃(RT y) ⇒ (y ∈ D RT ⇒ ∃(∃◦R)) volstaat (wegens bewijsmethode vrijwilliger)
een bewijs voor
x ∈ D (RT y) ∧ (RT y)x ⇒ y ∈ D RT ⇒ ∃(∃ ◦ R)
x ∈ D (RT y) ∧ (RT y)x ∧ y ∈ D RT
≡
⇒
⇒
⇒
hdef T ; domeinovergang i
hgetuige; Rx is pred i
hdef ◦i
hgetuigei
x ∈ D R ∧ y ∈ D (Rx) ∧ Rxy
x ∈ D R ∧ Rx ∈ D ∃ ∧ ∃(Rx)
x ∈ D (∃ ◦ R) ∧ (∃ ◦ R)x
∃(∃ ◦ R)
Het bewijs van de andere implicatie verloopt volledig analoog.
87
5.4. KWANTOREN
5.4.3
Puntvrij en puntsgewijs
Tabel 5.1 geeft een overzicht van de rekenregels voor kwantoren (we gaan ervan uit dat D P =
D Q). De notatie uit de tweede kolom wordt puntvrij genoemd omdat er geen veranderlijken
in optreden. Door de bijzondere keuze P = x : X . p, Q = x : X . q en R = x : X . (y : Y . r)
bekomen we puntsgewijze gedaantes van de rekenregels zoals we ze het vaakst tegenkomen
in wiskundige werken (zie de derde kolom). We illustreren de overgang van puntvrij naar
puntsgewijs voor de derde rekenregel. We moeten aantonen dat
b (x : X . q)) ≡ ∀(x : X . p ∧ q)
∀((x : X . p) ∧
We doen dit door aan te tonen dat de functies die optreden na de kwantoren gelijk zijn.
b (x : X . q))
y ∈ D ((x : X . p) ∧
≡
≡
≡
h def b ; x : X . p en x : X . q zijn predi
hfunctie–abstractiei
hfunctie–abstractiei
y ∈ Dx:X .p ∧ y ∈ Dx:X .q
y∈X
y ∈ D (x : X . p ∧ q)
Met de afleidingsregel voor extensionaliteit m.b.t. verzamelingen volgt daaruit de gelijkheid
van de definitieverzamelingen. Neem nu y ∈ D (x : X . p ∧ q) dan
b (x : X . q))y
((x : X . p) ∧
≡
≡
≡
≡
h def b i
hfunctie–abstractiei
hsubstitutiei
hfunctie–abstractiei
(x : X . p)y ∧ (x : X . q)y
p[x := y] ∧ q[x := y]
(p ∧ q)[x := y]
(x : X . p ∧ q)y
88
HOOFDSTUK 5. PREDIKATENREKENEN
∀(¬P ) ≡ ¬(∃P )
∃(¬P ) ≡ ¬(∀P )
dualiteit
interactie
interactie
interactie
interactie
tussen
tussen
tussen
tussen
∀
∀
∃
∃
en
en
en
en
∧
∨
∧
∨
∀(P
∀(P
∃(P
∃(P
b Q)
∧
b Q)
∨
b Q)
∧
b Q)
∨
≡ ∀P ∧ ∀Q
⇐ ∀P ∨ ∀Q
⇒ ∃P ∧ ∃Q
≡ ∃P ∨ ∃Q
∀(x : X . ¬p) ≡ ¬(∃(x : X . p))
∃(x : X . ¬p) ≡ ¬(∀(x : X . p))
∀(x : X . p ∧ q)
∀(x : X . p ∨ q)
∃(x : X . p ∧ q)
∃(x : X . p ∨ q)
≡ ∀(x : X . p) ∧ ∀(x : X . q)
⇐ ∀(x : X . p) ∨ ∀(x : X . q)
⇒ ∃(x : X . p) ∧ ∃(x : X . q)
≡ ∃(x : X . p) ∨ ∃(x : X . q)
ruilen
∀(P ↓ Q) ≡ ∀(Q c
⇒ P)
b P)
∃(P ↓ Q) ≡ ∃(Q ∧
∀(x : X ∧. q . p) ≡ ∀(x : X . q ⇒ p)
∃(x : X ∧. q . p) ≡ ∃(x : X . q ∧ p)
dummy wissel
∀(∀ ◦ R) ≡ ∀(∀ ◦ RT )
∃(∃ ◦ R) ≡ ∃(∃ ◦ RT )
∀(∃ ◦ R) ⇐ ∃(∀ ◦ RT )
∀(x : X . ∀(y : Y.r)) ≡ ∀(y : Y . ∀(x : X . r))
∃(x : X . ∃(y : Y.r)) ≡ ∃(y : Y . ∃(x : X . r))
∀(x : X . ∃(y : Y.r)) ⇐ ∃(y : Y . ∀(x : X . r))
Tabel 5.1: Rekenregels kwantoren — puntvrij en puntsgewijs
89
5.4. KWANTOREN
Oefeningen
1. Bewijs de volgende stellingen.
(a) X ∪ Y = Y ∪ X
(b) (X ∪ Y ) ∪ Z = X ∪ (Y ∪ Z)
(c) X ∪ X = X
(d) X = X
(e) X ∩ Y = Y ∩ X
(f) (X ∩ Y ) ∩ Z = X ∩ (Y ∩ Z)
(g) X ∩ X = X
(h) X ∪ ∅ = X
(i) X ∩ ∅ = ∅
(j) X ∩ (X ∪ Y ) = X
(k) X ∩ (Y ∪ Z) = (X ∩ Y ) ∪ (X ∩ Z)
(l) X ∪ (Y ∩ Z) = (X ∪ Y ) ∩ (X ∪ Z)
2. Bewijs de volgende stellingen.
(a) x ∈ X ∨ x ∈
/X
(b) ¬(x ∈ X ∧ x ∈
/ X)
(c) x ∈ X ∨ Y ≡ x ∈ X ∨ (x ∈
/ X ∧x∈Y)
(d) x ∈
/ X\Y ≡ x ∈
/ X ∨x∈Y
3. Bewijs de volgende stellingen.
(a) X ⊆ X
(b) X ∩ Y ⊆ X
(c) X ⊆ X ∪ Y
(d) X ∩ Y ⊆ X ∪ Y
(e) ∅ ≡ X
4. (a) Bewijs dat a ∧ b ⇒ c ≡ (a ⇒ c) ∨ (b ⇒ c).
(b) Instantieer deze stelling met a, b, c := x ∈ A, x ∈ B, x ∈ C
(c) Zij ⊆ gedefinieerd a.d.h.v. het alternatieve axioma
X⊆Y ≡ x∈X⇒x∈Y
Bewijs A ∩ B ⊆ C ≡ A ⊆ C ∨ B ⊆ C
(d) Kan je deze laatste stelling ook bekomen als je voor ⊆ axioma V8 gebruikt? Geef
een bewijs of een tegenvoorbeeld.
(e) Waar zit het addertje onder het gras?
90
HOOFDSTUK 5. PREDIKATENREKENEN
5. Als T het universum is van alle verzamelingen, bewijs dan dat
R = {X : T |X ∈
/ X}
geen verzameling is, m.a.w. R ∈
/ T . Er bestaat dus niet zoiets als “de verzameling van
verzamelingen die zichzelf niet bevatten”.
6. Bewijs dat het definitieverzamelingaxioma van een functie–abstractie ook kan geschreven
worden als
D (v : S ∧. p | e) = {v : S|p}
7. Bewijs onderstaande lemma’s.
(a) ∀(X • 1) ≡ 1
(b) ∃(X • 0) ≡ 0
8. Bewijs onderstaande lemma’s.
(a) D (¬P ) = D P
(b) ¬ P = Q ≡ P = ¬ Q
(c) ¬ (D P • 1) = D P • (¬1)
9. Bewijs
∃(¬P ) ≡ ¬(∀P )
10. Bewijs onderstaande lemma’s.
b Q) = ¬ P ∨
b ¬Q
(a) ¬ (P ∧
b Q) = ¬ P ∧
b ¬Q
(b) ¬ (P ∨
bQ
(c) P c
⇒ Q = ¬P ∨
(d) ¬ ¬ P = P
11. Bewijs
¬ (P ↓ Q) = (¬ P ) ↓ Q
12. Bewijs
X = Y ≡ ∀(x : X.x ∈ Y ) ∧ ∀(x : Y.x ∈ X)
X en Y zijn verzamelingen.
13. Bewijs onderstaande stellingen. f en g zijn functies.
(a) f = g ≡ D f = D g ∧ ∀(x : D f ∩ D g.f x = g x)
(b) f = g ≡ D f = D g ∧ ∀(f =
b g)
14. (a) Toon aan dat x ∈ N ⇒ (x ∈ N ⇒ x = x)
(b) Hierna wordt “bewezen” dat alle natuurlijke getallen gelijk zijn. Leg uit wat er
mis is met dit “bewijs”.
Als bewijs voor ∀(x : N . ∀(y : N . x = y)) volstaat, wegens veralgemening,
een bewijs voor x ∈ N ⇒ ∀(y : N . x = y). Voor dit laatste volstaat, wegens
veralgemening, een bewijs voor x ∈ N ⇒ (x ∈ N ⇒ x = x).

Download Report