Hoofdstuk 7: Predikaatlogica: semantiek

Inleiding
Structuren
Waarheidsdefinitie
Geldig gevolg
Modellen en axiomatieken
Hoofdstuk 7: Predikaatlogica: semantiek
L. Storme
Toepassingsgerichte formele logica II
academiejaar 2006-2007
L. Storme
Hoofdstuk 7: Predikaatlogica: semantiek
Inleiding
Structuren
Waarheidsdefinitie
Geldig gevolg
Modellen en axiomatieken
Betekenis in propositielogica en predikaatlogica
I
Betekenis formule in propositielogica: (1) via verloop van de
waarheidswaarde van die formule door alle waarderingen heen,
(2) is bepaald door waarheidswaarden van de atomen in die
formule.
I
Predikaatlogische taal veel uitgebreider: ook betekenis geven
aan predikaatletters, functieletters, en formules waarin
kwantoren voorkomen.
Bovendien kan formule vrije variabelen en constanten
bevatten; ook zij moeten een betekenis krijgen.
L. Storme
Hoofdstuk 7: Predikaatlogica: semantiek
Inleiding
Structuren
Waarheidsdefinitie
Geldig gevolg
Modellen en axiomatieken
Bij predikaatlogica hoort altijd een interpretatie
I
Syntactische objecten uit een formele taal (zoals termen en
formules) betekenen op zichzelf niks. Ze moeten van geval tot
geval ge¨ınterpreteerd worden.
I
Voorbeeld: ∀x ∃y (Rxy ∧ Ay ) betekent:
I
I
I
als R staat voor kleiner dan en A voor is een even getal, dat:
elk getal is kleiner dan een even getal.
als R staat voor is de moeder van en A voor is een vrouw,
dat: ieder mens is moeder van een dochter.
Voorbeeld: ∀x (x ≥ 0) is waar in N en vals in R.
L. Storme
Hoofdstuk 7: Predikaatlogica: semantiek
Inleiding
Structuren
Waarheidsdefinitie
Geldig gevolg
Modellen en axiomatieken
Interpretatiefunctie
I
I
I
I
I
Formele taal: beschreven in Hoofdstuk 6.
Formele taal dient om te spreken over structuren.
Interpretatiefunctie: geeft betekenis aan onderdelen van de
taal, zoals predikaatletters, functieletters, . . .
Compositionele semantiek: betekenis van een geheel wordt
bepaald door de betekenis van zijn delen (inductie).
Uiteindelijk: betekenis van termen en formules: via hun
waarheidswaarde in een structuur onder een interpretatie.
L. Storme
Hoofdstuk 7: Predikaatlogica: semantiek
Inleiding
Structuren
Waarheidsdefinitie
Geldig gevolg
Modellen en axiomatieken
Drie aspecten alle essentieel
I
Syntactische tekst en interpretatiefunctie gekend: zonder de
situatie te kennen, niet mogelijk te bepalen of gezegde waar is.
Voorbeeld: ∀x (x ≥ 0) is waar in structuur N, maar vals in
structuur R.
I
Syntactische tekst en situatie gekend (bv. foto met bericht in
Turkse krant): zonder betekenis taal te leren, niet mogelijk te
bepalen of gezegde waar is.
I
Interpretatiefunctie en situatie gekend: zonder kennis van de
tekst, kun je het bericht meestal niet reconstrueren, dus kan
waarheid gezegde niet bepaald worden.
L. Storme
Hoofdstuk 7: Predikaatlogica: semantiek
Inleiding
Structuren
Waarheidsdefinitie
Geldig gevolg
Modellen en axiomatieken
Structuur
Structuur:
I
Domein D: niet-ledige verzameling!
I
Relaties tussen objecten uit het domein = beweringen die wel
of niet het geval (waar/niet waar) zijn.
I
Operaties (functies) op objecten die andere objecten
opleveren. Zij drukken geen beweringen uit.
L. Storme
Hoofdstuk 7: Predikaatlogica: semantiek
Inleiding
Structuren
Waarheidsdefinitie
Geldig gevolg
Modellen en axiomatieken
Voorbeelden
I
I
Relaties op R: ≤, <, ≥, >.
Functies op R: sin, cos, f : R → R : x 7→ x 2 .
I
Relatie binnen bedrijf: de hi¨erarchie-relatie: is ondergeschikt
aan.
I
Functie binnen bedrijf: de functie die de lonen berekent die
horen bij de werknemers.
L. Storme
Hoofdstuk 7: Predikaatlogica: semantiek
Inleiding
Structuren
Waarheidsdefinitie
Geldig gevolg
Modellen en axiomatieken
Relationele structuur
I
I
Relationele structuur: domein met objecten waartussen
relaties gelden.
Voorbeelden:
I
I
I
(R, ≤),
R3 opgevat als de 3-dimensionale Euclidische ruimte, met de
3-plaatsige relatie Txyz (y ligt tussen x en z),
een relationele databank.
L. Storme
Hoofdstuk 7: Predikaatlogica: semantiek
Inleiding
Structuren
Waarheidsdefinitie
Geldig gevolg
Modellen en axiomatieken
Operationele structuur
I
I
Operationele structuur: domein met objecten waarop
operaties (functies) inwerken.
Voorbeelden:
I
I
N met operaties · en +,
{0, 1} met operaties ∧, ∨, ¬, →, ↔.
L. Storme
Hoofdstuk 7: Predikaatlogica: semantiek
Inleiding
Structuren
Waarheidsdefinitie
Geldig gevolg
Modellen en axiomatieken
Structuur
I
Structuur D = drietal hD, R, Oi bestaande uit niet-ledige
verzameling D (het domein), een verzameling R van relaties
op D, en een verzameling O van operaties op D.
I
Voorbeeld: hN, R = {<, =}, O = {+, ·}i.
I
R en O afhankelijk van verzameling D: kunnen ledig zijn.
L. Storme
Hoofdstuk 7: Predikaatlogica: semantiek
Inleiding
Structuren
Waarheidsdefinitie
Geldig gevolg
Modellen en axiomatieken
Inleiding
term
predikaat(letter)
functie(letter)
constante
object
relatie
operatie
uitverkoren object
L. Storme
Hoofdstuk 7: Predikaatlogica: semantiek
Inleiding
Structuren
Waarheidsdefinitie
Geldig gevolg
Modellen en axiomatieken
Interpretatiefunctie
Interpretatiefunctie
I
I
Zij D = drietal hD, R, Oi een structuur.
Interpretatiefunctie
taal
constante c
predikaatletter P
functieletter f
I:
→
→
→
structuur
I (c) ∈ O (nulplaatsige operatie)
I (P) ∈ R (relatie)
I (f ) ∈ O (operatie)
L. Storme
Hoofdstuk 7: Predikaatlogica: semantiek
Inleiding
Structuren
Waarheidsdefinitie
Geldig gevolg
Modellen en axiomatieken
Model in de predikaatlogica
I
Model = paar (D, I )
I
D = hN, {≥}, {0}i, met
I (c1 ) = 0,
I (R) =≥,
I (∀x R(x, c1 )) = ∀x (x ≥ 0).
I
In dit model is de zin ∀x R(x, c1 ) waar.
L. Storme
Hoofdstuk 7: Predikaatlogica: semantiek
Inleiding
Structuren
Waarheidsdefinitie
Geldig gevolg
Modellen en axiomatieken
Bedeling
I
I
Bedeling b = functie die aan elke variabele x een object
b(x) ∈ D toekent.
Voorbeeld: Model M = (D, I ) = (hD, R, Oi, I ) met
D = N, R = {<}, O = {0, +, ·},
I : I (P) =0 <0 , I (f ) =0 +0 , I (g ) =0 ·0 , I (a) = 0,
b : b(xi ) = i (i = 1, 2, 3, . . .).
b,I
Px1 x2 ∧ Pf (a, x9 )g (x5 , x9 ) → 1 < 2 en 9 < 45.
L. Storme
Hoofdstuk 7: Predikaatlogica: semantiek
Inleiding
Structuren
Waarheidsdefinitie
Geldig gevolg
Modellen en axiomatieken
Ander voorbeeld van model voor Boolealgebra
I
I
D = {1, 2, 3, 5, 6, 10, 15, 30}
I (0) = 1 ∈ D en I (1) = 30 ∈ D
I
I (¬p) = de functie 30/b(p).
I
I (∨) = KGV en I (∧) = GGD.
L. Storme
Hoofdstuk 7: Predikaatlogica: semantiek
Inleiding
Structuren
Waarheidsdefinitie
Geldig gevolg
Modellen en axiomatieken
Ander voorbeeld van model voor Boolealgebra
I
D = P(U): D is de verzameling van alle deelverzamelingen
van de verzameling U.
I
I (0) = ∅ ∈ D en I (1) = U ∈ D.
I
I (¬) = de functie complement binnen U (deelverzameling in
U wordt afgebeeld op zijn complement in U).
I
I (∨) = ∪ en I (∧) = ∩.
L. Storme
Hoofdstuk 7: Predikaatlogica: semantiek
Inleiding
Structuren
Waarheidsdefinitie
Geldig gevolg
Modellen en axiomatieken
Notaties
I
Notatie: hN, {<, =}, {0, 1, +, ·}i wordt ook voorgesteld als
hN, <, =, 0, 1, +, ·i.
Zo ook: P ipv. I (P) en f ipv. I (f ).
I
b[x 7→ d] = bedeling b waarbij d aan de variabele x wordt
toebedeeld, ongeacht wat b(x) voordien ook was.
I
Voorbeeld: b : b(xi ) = i (i = 1, 2, 3, . . .)
b[x1 7→ 10](x2 ) = 2,
b[x1 7→ 10](x1 ) = 10.
L. Storme
Hoofdstuk 7: Predikaatlogica: semantiek
Inleiding
Structuren
Waarheidsdefinitie
Geldig gevolg
Modellen en axiomatieken
Waardering van termen
Waardering van termen:
I
I
Intu¨ıtief voorbeeld: als x = 5 en y = 7, dan x · y = 5 · 7 = 35.
Zij M = (D, I ) een model en b een bedeling.
De semantische waardering VM,b van termen is als volgt
inductief gedefinieerd:
(a) VM,b (x) = b(x) voor variabelen x,
(b) VM,b (a) = I (a) voor constanten a,
(c) VM,b (f (t1 , . . . , tk )) = I (f )(VM,b (t1 ), . . . , VM,b (tk )).
L. Storme
Hoofdstuk 7: Predikaatlogica: semantiek
Inleiding
Structuren
Waarheidsdefinitie
Geldig gevolg
Modellen en axiomatieken
Voorbeeld waardering van termen
Zij M een model met D = hN, 0, +i en I (f ) =0 +0 , I (a) = 0.
Zij verder b een bedeling met b(x) = 1.
Dan geldt:
VM,b (f (a, x)) = I (f )(VM,b (a), VM,b (x))
= I (f )(I (a), b(x)) = +(0, 1) = 1.
L. Storme
Hoofdstuk 7: Predikaatlogica: semantiek
Inleiding
Structuren
Waarheidsdefinitie
Geldig gevolg
Modellen en axiomatieken
Waardering van formules
Formule: waar of vals.
I
VM,b (ϕ) = 1: ϕ is waar in M onder de bedeling b.
I
V (ϕ) ipv. VM,b (ϕ) als de context duidelijk is.
I
VM,b (ϕ) = 1: M, b |= ϕ.
I
VM,b (ϕ) = 0: M, b 6|= ϕ.
L. Storme
Hoofdstuk 7: Predikaatlogica: semantiek
Inleiding
Structuren
Waarheidsdefinitie
Geldig gevolg
Modellen en axiomatieken
Inductieve bepaling waardering van formules
Zij M = hD, I i een model en b een bedeling. De waarheidswaarden
(0 of 1) van formules worden op de volgende inductieve manier
bepaald:
(a) M, b |= P(t1 , . . . , tm ) ⇔ I (P)(VM,b (t1 ), . . . , VM,b (tm )) is
waar.
(b) M, b |= ¬ϕ ⇔ M, b 6|= ϕ (overige connectieven op dezelfde
manier, via hun waarheidstabellen).
(c) M, b |= ∃x ϕ ⇔ er is een d ∈ D zodat M, b[x 7→ d] |= ϕ.
(d) M, b |= ∀x ϕ ⇔ voor alle d ∈ D geldt M, b[x 7→ d] |= ϕ.
L. Storme
Hoofdstuk 7: Predikaatlogica: semantiek
Inleiding
Structuren
Waarheidsdefinitie
Geldig gevolg
Modellen en axiomatieken
Voorbeeld
Zij M = hD, I i met D = hQ, <i en I (R) =0 <0 . Zij b bedeling met
b(x1 ) = 4.
I
I
I
I
M, b |= ∀y (Rx1 y → ∃z (Rx1 z ∧ Rzy ))
⇔ voor alle q ∈ Q:
M, b[y 7→ q] |= (Rx1 y → ∃z (Rx1 z ∧ Rzy ))
⇔ voor alle q ∈ Q: als M, b[y 7→ q] |= Rx1 y , dan
M, b[y 7→ q] |= ∃z (Rx1 z ∧ Rzy )
⇔ voor alle q ∈ Q: als 4 < q, dan is er een q 0 ∈ Q met
M, b[y 7→ q][z 7→ q 0 ] |= (Rx1 z ∧ Rzy )
L. Storme
Hoofdstuk 7: Predikaatlogica: semantiek
Inleiding
Structuren
Waarheidsdefinitie
Geldig gevolg
Modellen en axiomatieken
Vervolg voorbeeld
I
I
I
⇔ voor alle q ∈ Q: als 4 < q, dan is er een q 0 ∈ Q met
M, b[y 7→ q][z 7→ q 0 ] |= (Rx1 z ∧ Rzy )
⇔ voor alle q ∈ Q: als 4 < q, dan is er een q 0 ∈ Q met
M, b[y 7→ q][z 7→ q 0 ] |= Rx1 z en M, b[y 7→ q][z 7→ q 0 ] |= Rzy
⇔ voor alle q ∈ Q: als 4 < q, dan is er een q 0 ∈ Q met
4 < q 0 en q 0 < q.
Dit betekent: als q een rationaal getal groter dan 4 is, dan is er
een rationaal getal q 0 groter dan 4 en kleiner dan q, dus er ligt
tussen 4 en q een ander rationaal getal q 0 .
L. Storme
Hoofdstuk 7: Predikaatlogica: semantiek
Inleiding
Structuren
Waarheidsdefinitie
Geldig gevolg
Modellen en axiomatieken
Waardering in propositielogica en predikaatlogica
I
In propositielogica: een waardering V is model van een
formule ϕ als V (ϕ) = 1.
I
Een paar (D, I ) is model van een formule ϕ als voor iedere
bedeling b geldt: V(D,I ),b (ϕ) = 1.
L. Storme
Hoofdstuk 7: Predikaatlogica: semantiek
Inleiding
Structuren
Waarheidsdefinitie
Geldig gevolg
Modellen en axiomatieken
Opmerkingen en voorbeelden
I
Atomaire formule is waar in een structuur als het feit
uitgedrukt door die atomaire formule inderdaad het geval is in
die structuur.
Voorbeeld: I (P) =0 <0 , b(x) = 2, en b(y ) = 7.
Dan is de atomaire formule Pxy waar in hN, <i als in die
structuur inderdaad geldt dat 2 < 7.
I
Speciale rol van bedelingen op variabelen: in het volgende
programma verandert telkens de bedeling voor variabele n:
L. Storme
Hoofdstuk 7: Predikaatlogica: semantiek
Inleiding
Structuren
Waarheidsdefinitie
Geldig gevolg
Modellen en axiomatieken
Opmerkingen en voorbeelden 2
I
0
1
2
3
4
5
BEGIN;
n = 0;
n = n + 1;
IF n > 0 THEN n = n + 1;
IF n < 10 THEN GOTO 3 ELSE GOTO 5;
END.
I
Imperatief programmeren = ’sturen’ van steeds veranderende
bedelingen, opgevat als momentane geheugentoestanden van
de computer.
L. Storme
Hoofdstuk 7: Predikaatlogica: semantiek
Inleiding
Structuren
Waarheidsdefinitie
Geldig gevolg
Modellen en axiomatieken
Opmerkingen en voorbeelden 3
I
Formule ϕ kan in verschillende structuren heel verschillende
beweringen uitdrukken. Zelfs bij gegeven ϕ en structuur D
kunnen nog verschillende interpretatiefuncties de formule ϕ
waar maken.
I
Voorbeeld: ∀x ∀y (f (x, y ) = f (y , x)) is waar op Z en N zowel
met I (f ) =0 +0 als met I (f ) =0 ·0 , en onwaar met I (f ) =0 −0 .
L. Storme
Hoofdstuk 7: Predikaatlogica: semantiek
Inleiding
Structuren
Waarheidsdefinitie
Geldig gevolg
Modellen en axiomatieken
Gelijkheid tussen termen
Gelijkheid tussen termen:
I
Er moet expliciet gezegd worden of het gelijkheidsteken wel of
niet gebruikt kan worden in termen.
I
Gelijkheid tussen termen:
M, b |= t1 = t2 ⇔ VM,b (t1 ) = VM,b (t2 ).
I
Uit definitie volgt: gelijkheid van twee termen hangt af van
gekozen model en bedeling!
L. Storme
Hoofdstuk 7: Predikaatlogica: semantiek
Inleiding
Structuren
Waarheidsdefinitie
Geldig gevolg
Modellen en axiomatieken
Voorbeeld gelijkheid tussen termen
I
I
Voorbeeld: f (x, g (y , z)) = g (f (x, y ), f (x, z)) is waar onder
elke bedeling in N met I (f ) =0 ·0 en I (g ) =0 +0 . De gelijkheid
luidt dan: x · (y + z) = x · y + x · z.
Dit is niet het geval onder elke bedeling in N met I (f ) =0 +0
en I (g ) =0 ·0 . De gelijkheid zou dan namelijk betekenen:
x + (y · z) = (x + y ) · (x + z).
Deze laatste gelijkheid is wel waar onder elke bedeling die aan
x het getal 0 toekent.
L. Storme
Hoofdstuk 7: Predikaatlogica: semantiek
Inleiding
Structuren
Waarheidsdefinitie
Geldig gevolg
Modellen en axiomatieken
Eigenschappen van waarheidsdefinitie: eindigheid
Eindigheid
I
Waarheidswaarde van een formule hangt af van de structuur,
de interpretatiefunctie en van het effect van de bedeling b op
de vrije variabelen in die formule.
I
Eindigheid: Zij x1 , . . . , xk de vrije variabelen van ϕ, en b1 en
b2 twee bedelingen met b1 (xi ) = b2 (xi ), voor i = 1, . . . , k.
Dan geldt: M, b1 |= ϕ ⇔ M, b2 |= ϕ.
I
Voorbeeld: in N: ϕ = ∀x(x ≥ y ).
Als b1 (y ) = b2 (y ) = 0, dan M, b1 |= ϕ en M, b2 |= ϕ.
L. Storme
Hoofdstuk 7: Predikaatlogica: semantiek
Inleiding
Structuren
Waarheidsdefinitie
Geldig gevolg
Modellen en axiomatieken
Gevolg van eindigheid
I
Zinnen (gesloten formules) hebben geen vrije variabelen;
bedeling doet er niet toe.
I
Zinnen: waarheid in een model.
I
Voorbeeld: in N: ϕ = ∀x(x ≥ 0).
L. Storme
Hoofdstuk 7: Predikaatlogica: semantiek
Inleiding
Structuren
Waarheidsdefinitie
Geldig gevolg
Modellen en axiomatieken
Eigenschappen van waarheidsdefinitie: substitutie
Substitutie
Theorem
Voor alle termen t, t 0 geldt:
VM,b ([t/x]t 0 ) = VM,b[x7→VM,b (t)] (t 0 ).
Bewijs.
Zie Hoofdstuk 8.
L. Storme
Hoofdstuk 7: Predikaatlogica: semantiek
Inleiding
Structuren
Waarheidsdefinitie
Geldig gevolg
Modellen en axiomatieken
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 7: Predikaatlogica: semantiek
Inleiding
Structuren
Waarheidsdefinitie
Geldig gevolg
Modellen en axiomatieken
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 7: Predikaatlogica: semantiek
Inleiding
Structuren
Waarheidsdefinitie
Geldig gevolg
Modellen en axiomatieken
Geldig gevolg
Geldig gevolg:
I
Zij Σ een verzameling formules en ψ een formule.
Σ |= ψ (ψ volgt uit Σ) ⇔ voor elk model M en elke bedeling
b geldt: als M, b |= ϕ voor elke ϕ ∈ Σ, dan M, b |= ψ.
I
Oneindig veel mogelijkheden voor M en b.
I
M, b |= Σ: alle formules uit Σ zijn waar in model M onder
bedeling b.
L. Storme
Hoofdstuk 7: Predikaatlogica: semantiek
Inleiding
Structuren
Waarheidsdefinitie
Geldig gevolg
Modellen en axiomatieken
Opmerking: verschil in betekenis van notaties
I
M, b |= Σ: alle formules uit Σ zijn waar in model M onder
bedeling b. (links staat een model M en een bedeling b)
I
Bij semantische tableaus: Φ |= Σ: uit Φ volgt minstens ´e´en
van de formules uit Σ (dus niet noodzakelijk alle). (links
staat een verzameling/lijst formules, links mag ledig zijn)
I
Bijzonder geval: |= Ψ. Toepassing op Φ ◦ Ψ met Φ ledige
lijst. De formule Ψ heet dan universeel geldig.
L. Storme
Hoofdstuk 7: Predikaatlogica: semantiek
Inleiding
Structuren
Waarheidsdefinitie
Geldig gevolg
Modellen en axiomatieken
Opmerking: verschil in betekenis van notaties
I
|= Σ: Onder elke waardering is minstens ´e´en formule in Σ
waar. (deze formule mag vari¨eren van waardering tot
waardering).
I
Opgelet: formulering boek blz. 113: een van de formules in Σ
is universeel geldig: niet correct!
L. Storme
Hoofdstuk 7: Predikaatlogica: semantiek
Inleiding
Structuren
Waarheidsdefinitie
Geldig gevolg
Modellen en axiomatieken
Voorbeeld
I
I
|= ∃x ∀y ϕ → ∀y ∃x ϕ
6|= ∀y ∃x ϕ → ∃x ∀y ϕ
√
√
Tegenvoorbeeld: D = hR+ , =, i, I : I (P) =0 =0 , I (f ) =0 0 ,
√
ϕ = P(x, f (y )) → x = y .
(elk positief re¨eel getal heeft een vierkantswortel, maar er is
geen re¨eel getal dat van alle positieve re¨ele getallen de
vierkantswortel is)
L. Storme
Hoofdstuk 7: Predikaatlogica: semantiek
Inleiding
Structuren
Waarheidsdefinitie
Geldig gevolg
Modellen en axiomatieken
Opmerking
I
Zin ϕ = formule zonder vrije variabelen.
I
Voor bedelingen b1 en b2 : M, b1 |= ϕ ⇔ M, b2 |= ϕ
I
Gevolg: eenvoudiger beschrijving geldig gevolg van zinnen:
Σ |= ϕ als elk model van Σ ook model van ϕ is.
L. Storme
Hoofdstuk 7: Predikaatlogica: semantiek
Inleiding
Structuren
Waarheidsdefinitie
Geldig gevolg
Modellen en axiomatieken
Theorie van model
Theorie van model
Th(M) = {ϕ ϕ is een zin en M |= ϕ}
Voorbeeld: in Tarski’s world: ´e´en configuratie, en we zoeken alle
zinnen die waar zijn voor die welbepaalde configuratie.
L. Storme
Hoofdstuk 7: Predikaatlogica: semantiek
Inleiding
Structuren
Waarheidsdefinitie
Geldig gevolg
Modellen en axiomatieken
Axiomaverzameling
Formuleverzameling Σ axiomatiseert Th(M) als voor alle zinnen ϕ
geldt: ϕ ∈ Th(M) ⇔ Σ |= ϕ.
Voorbeeld: Axiomaverzameling voor model (hZ, <i, I ) met
I (R) =0 <0 :
I
I
I
I
I
∀x ¬Rxx (irreflexiviteit)
∀x∀y (x = y ∨ Rxy ∨ Ryx) (lineariteit)
∀x∀y ∀z ((Rxy ∧ Ryz) → Rxz) (transitiviteit)
∀x∃y (Rxy ∧ ¬∃z (Rxz ∧ Rzy )) (onmiddellijke opvolger)
∀x∃y (Ryx ∧ ¬∃z (Ryz ∧ Rzx)) (onmiddellijke voorganger)
L. Storme
Hoofdstuk 7: Predikaatlogica: semantiek
Inleiding
Structuren
Waarheidsdefinitie
Geldig gevolg
Modellen en axiomatieken
Enkele axioma’s voor Tarski’s world
Tarski’s World kan ook geaxiomatiseerd worden. Hier volgen de
axioma’s voor de vorm van de objecten (Basic Shape Axioms) (blz.
285)
I
I
I
I
¬∃x (Cube(x) ∧ Tet(x))
¬∃x (Tet(x) ∧ Dodec(x))
¬∃x (Dodec(x) ∧ Cube(x))
∀x (Tet(x) ∨ Dodec(x) ∨ Cube(x))
L. Storme
Hoofdstuk 7: Predikaatlogica: semantiek
Inleiding
Structuren
Waarheidsdefinitie
Geldig gevolg
Modellen en axiomatieken
Van zinnen naar modellen
Welke modellen horen bij een zin of verzameling zinnen?
Modelverzameling voor zin ϕ:
Mod(ϕ) = {M M |= ϕ}.
Modelverzameling voor verzameling zinnen Σ:
Mod(Σ) = {M M |= ϕ voor alle ϕ ∈ Σ}.
Voorbeeld: drie modellen voor Boolealgebra.
L. Storme
Hoofdstuk 7: Predikaatlogica: semantiek
Inleiding
Structuren
Waarheidsdefinitie
Geldig gevolg
Modellen en axiomatieken
Zinnen zonder modellen
I
Russell-formule
∃x∀y (Rxy ↔ ¬Ryy )
I
Geen model!
L. Storme
Hoofdstuk 7: Predikaatlogica: semantiek

Download Report