Hoofdstuk 8: Predikaatlogica: eenvoudige theorie

Substitutie
Prenexvormen
Fragmenten van de predikaatlogica
Hoofdstuk 8: Predikaatlogica: eenvoudige theorie
L. Storme
Toepassingsgerichte formele logica II
academiejaar 2006-2007
L. Storme
Hoofdstuk 8: Predikaatlogica: eenvoudige theorie
Substitutie
Prenexvormen
Fragmenten van de predikaatlogica
Eerste probleemstelling
Bepaling van de semantische waarde van de term [t/x]t 0 .
I
Opmerking: behalve in gevallen waar van variabelen of
kwantoren sprake is, mag substitutie recursief door predikaaten functieletters, en door logische connectieven, heen
doorgevoerd worden.
I
Voorbeeld: V ([t/x]¬ψ) = V (¬[t/x]ψ).
Theorem
Voor alle termen t, t 0 geldt:
VM,b ([t/x]t 0 ) = VM,b[x7→VM,b (t)] (t 0 ).
L. Storme
Hoofdstuk 8: Predikaatlogica: eenvoudige theorie
Substitutie
Prenexvormen
Fragmenten van de predikaatlogica
Voorbeeld
Zij t 0 = f (x, y ) en t = a (a constante), dan
I
VM,b ([a/x]f (x, y )) = VM,b (f (a, y )) =
I (f )(VM,b (a), VM,b (y )) = I (f )(I (a), b(y )), en anderzijds
I
VM,b[x7→VM,b (a)] (f (x, y )) =
I (f )(VM,b[x7→VM,b (a)] (x), VM,b[x7→VM,b (a)] (y )) =
I (f )(VM,b (a), b(y )) = I (f )(I (a), b(y )).
L. Storme
Hoofdstuk 8: Predikaatlogica: eenvoudige theorie
Substitutie
Prenexvormen
Fragmenten van de predikaatlogica
Vervolg voorbeeld
In N : f (x, y ) = x + y = +(x, y ), dus I (f ) =0 +0 . Stel b(y ) = 10
en I (a) = a.
I
VM,b ([a/x]f (x, y )) = VM,b (f (a, y )) =
I (f )(VM,b (a), VM,b (y )) = I (f )(I (a), b(y )) = +(a, b(y )) =
+(a, 10) = a + 10, en anderzijds
I
VM,b[x7→VM,b (a)] (f (x, y )) =
I (f )(VM,b[x7→VM,b (a)] (x), VM,b[x7→VM,b (a)] (y )) =
I (f )(VM,b (a), b(y )) = I (f )(I (a), 10) = +(a, 10) = a + 10.
L. Storme
Hoofdstuk 8: Predikaatlogica: eenvoudige theorie
Substitutie
Prenexvormen
Fragmenten van de predikaatlogica
Bewijs stelling
Bewijs: Inductie op complexiteit van de term.
Notatie: V ipv. VM,b .
Basisstap:
I
Als t 0 = x, dan [t/x]t 0 = t, en V ([t/x]t 0 ) = V (t).
Anderzijds: Vb[x7→V (t)] (t 0 ) = Vb[x7→V (t)] (x) = V (t).
I
Als t 0 = y met y een variabele verschillend van x of een
constante, dan [t/x]t 0 = y , en V ([t/x]t 0 ) = V (y ).
Anderzijds: Vb[x7→V (t)] (t 0 ) = Vb[x7→V (t)] (y ) = V (y ).
L. Storme
Hoofdstuk 8: Predikaatlogica: eenvoudige theorie
Substitutie
Prenexvormen
Fragmenten van de predikaatlogica
Vervolg bewijs
Inductiestap:
I
IH: Stel stelling geldt voor reeks termen t1 , . . . , tn . We
bewijzen dat ze geldt voor t 0 = f n (t1 , . . . , tn ).
I
V ([t/x]t 0 ) = V (f n ([t/x]t1 , . . . , [t/x]tn )) =
I (f n )(V ([t/x]t1 ), . . . , V ([t/x]tn )) = (IH toepassen)
I (f n )(Vb[x7→V (t)] (t1 ), . . . , Vb[x7→V (t)] (tn )).
Anderzijds Vb[x7→V (t)] (t 0 ) = Vb[x7→V (t)] (f n (t1 , . . . , tn )) =
I (f n )(Vb[x7→V (t)] (t1 ), . . . , Vb[x7→V (t)] (tn )).
2
L. Storme
Hoofdstuk 8: Predikaatlogica: eenvoudige theorie
Substitutie
Prenexvormen
Fragmenten van de predikaatlogica
Tweede probleemstelling
Bepaling van de semantische waarde van de formule [t/x]ϕ.
Theorem
Zij ϕ een formule, t een term, x een variabele, en zij t vrij voor x
in ϕ, dan geldt in elk model M voor elke bedeling b:
VM,b ([t/x]ϕ) = VM,b[x7→VM,b (t)] (ϕ).
Bewijs: Inductie op complexiteit van de formule.
Notatie: V ipv. VM,b .
L. Storme
Hoofdstuk 8: Predikaatlogica: eenvoudige theorie
Substitutie
Prenexvormen
Fragmenten van de predikaatlogica
Bewijs stelling
Basisstap: zij ϕ = P(t1 , . . . , tn )
V ([t/x]P(t1 , . . . , tn )) = 1
⇔ V (P([t/x]t1 , . . . , [t/x]tn )) = 1
⇔ I (P)(V ([t/x]t1 ), . . . , V ([t/x]tn )) (waarheidsdefinitie)
⇔ I (P)(Vb[x7→V (t)] (t1 ), . . . , Vb[x7→V (t)] (tn )) (vorige stelling)
⇔ Vb[x7→V (t)] (P(t1 , . . . , tn )) = 1 (waarheidsdefinitie)
L. Storme
Hoofdstuk 8: Predikaatlogica: eenvoudige theorie
Substitutie
Prenexvormen
Fragmenten van de predikaatlogica
Vervolg bewijs
Inductiestap: zij ϕ = ¬ψ:
V ([t/x]¬ψ) = 1
⇔ V (¬[t/x]ψ) = 1
⇔ V ([t/x]ψ) = 0
⇔ VM,b[x7→V (t)] (ψ) = 0 (inductiehypothese IH)
⇔ VM,b[x7→V (t)] (¬ψ) = 1 (waarheidsdefinitie)
(andere connectieven op dezelfde manier)
L. Storme
Hoofdstuk 8: Predikaatlogica: eenvoudige theorie
Substitutie
Prenexvormen
Fragmenten van de predikaatlogica
Vervolg bewijs
zij ϕ = ∀z ψ: twee gevallen te controleren.
Geval 1: stel x is niet vrij in ϕ.
Dan [t/x]ϕ = ϕ en dus V ([t/x]ϕ) = V (ϕ).
Omdat x niet vrij voorkomt in ϕ, geldt VM,b[x7→V (t)] (ϕ) = V (ϕ)
(bewering 7.1: precieze bedeling doet er niet toe).
L. Storme
Hoofdstuk 8: Predikaatlogica: eenvoudige theorie
Substitutie
Prenexvormen
Fragmenten van de predikaatlogica
Vervolg bewijs
Geval 2: stel x is vrij in ϕ.
Dan [t/x]ϕ = ∀z ([t/x]ψ) en dus V ([t/x]ϕ) = V (∀z ([t/x]ψ)).
Dit betekent: V (∀z ([t/x]ψ)) = 1 ⇔ voor alle
d ∈ D : Vb[z7→d] ([t/x]ψ) = 1.
IH zegt dat voor ψ bewering reeds geldt. Dit impliceert:
L. Storme
Hoofdstuk 8: Predikaatlogica: eenvoudige theorie
Substitutie
Prenexvormen
Fragmenten van de predikaatlogica
Vervolg bewijs
Vb[z7→d] ([t/x]ψ) = Vb[z7→d][x7→V 0 (t)] (ψ), met V 0 = Vb[z7→d] .
Maar t is vrij voor x in ϕ, dus z treedt niet op in t, en dus
V 0 (t) = Vb[z7→d] (t) = V (t).
Ook geldt x 6= z daar x vrij is in ϕ.
Daardoor b[z 7→ d][x 7→ V (t)] = b[x 7→ V (t)][z 7→ d].
De gelijkheid wordt: Vb[z7→d] ([t/x]ψ) = Vb[x7→V (t)][z7→d] (ψ).
L. Storme
Hoofdstuk 8: Predikaatlogica: eenvoudige theorie
Substitutie
Prenexvormen
Fragmenten van de predikaatlogica
Einde bewijs
Dit leidt tot:
V ([t/x]∀z ψ) = 1
⇔ V (∀z [t/x]ψ) = 1
⇔ voor alle d ∈ D : Vb[z7→d] ([t/x]ψ) = 1
⇔ voor alle d ∈ D : Vb[x7→V (t)][z7→d] (ψ) = 1 (vorige analyse)
⇔ Vb[x7→V (t)] (∀z ψ) = 1.
(Geval ϕ = ∃z ψ op analoge manier)
L. Storme
Hoofdstuk 8: Predikaatlogica: eenvoudige theorie
2
Substitutie
Prenexvormen
Fragmenten van de predikaatlogica
Prenexvormen
Prenexvormen: zie oefeningenlessen.
L. Storme
Hoofdstuk 8: Predikaatlogica: eenvoudige theorie
Substitutie
Prenexvormen
Fragmenten van de predikaatlogica
Fragmenten/deeltalen
I
Fragmenten of deeltalen: ontstaan door het opleggen van
restricties aan predikaatlogica.
I
Voorbeeld: monadische taal: alleen 1-plaatsige
predikaatletters toegelaten.
I
Monadische predikaatlogica: voldoende om syllogismen te
behandelen.
I
Syllogisme = gevolgtrekking bestaande uit twee aannames en
´e´en conclusie: alle drie van de vorm:
alle/geen/sommige A is/zijn B
L. Storme
Hoofdstuk 8: Predikaatlogica: eenvoudige theorie
Substitutie
Prenexvormen
Fragmenten van de predikaatlogica
Voorbeeld syllogisme
∀x (Kx → Rx)
¬∃x (Rx ∧ Fx)
¬∃x (Kx ∧ Fx)
Alle kaaimannen zijn reptielen.
Geen reptiel kan fluiten.
Geen kaaiman kan fluiten.
L. Storme
Hoofdstuk 8: Predikaatlogica: eenvoudige theorie
Substitutie
Prenexvormen
Fragmenten van de predikaatlogica
Eigenschap van monadische predikaatlogica
I
Monadische predikaatlogica met eindig aantal k aan
predikaten kan beschreven worden met eindige modellen.
I
Enige dat rol speelt is: al dan niet aanwezigheid van
individuen die de 2k mogelijke combinaties van deze k
eigenschappen vertonen.
I
Voorbeeld: K (aaiman), R(eptiel), F (luiten).
k = 3, dus 23 = 8 combinaties van deze drie eigenschappen.
L. Storme
Hoofdstuk 8: Predikaatlogica: eenvoudige theorie

Download Report