Logica voor AI eserved@d = *@let@token

Logica voor AI
Kripke
Semantiek
Geldigheid
Frame eigenschappen en correspondentie
De bereikbaarheidsrelatie
Frame
eigenschappen
Correspondentie
Albert Visser
[email protected]
14 november 2014
1
Kripke Semantiek
Kripke
Semantiek
De taal Lm van de modale propositielogica
ϕ ::= p | ⊥ | > | ¬ϕ | ϕ ∨ ϕ | ϕ ∧ ϕ | ϕ → ϕ | ϕ ↔ ϕ | ϕ | ♦ϕ
Geldigheid
De bereikbaarheidsrelatie
Frame
eigenschappen
Correspondentie
Blokje en ruitje
I
ϕ: het is noodzakelijk dat ϕ
I
♦ϕ: het is mogelijk dat ϕ
2
Kripke Semantiek
Modelstructuur (of frame)
Een modelstructuur (of frame) is een geordend paar
F = hW, Ri, waarbij
I
W=
6 ∅ een verzameling mogelijke werelden en
I
R ⊆ W × W een bereikbaarheidsrelatie is.
Kripke
Semantiek
Geldigheid
De bereikbaarheidsrelatie
Frame
eigenschappen
Correspondentie
w
v
u
t
s
r
3
Kripke Semantiek
Kripke Model
Een Kripke model is een geordend drietal M = hW, R, Vi,
waarbij
Kripke
Semantiek
Geldigheid
I
hW, Ri een modelstructuur en
De bereikbaarheidsrelatie
I
V : W → Pow (VAR) een interpretatiefunctie is.
Een propositie p is waar in een wereld w desda p ∈ V(w ).
Frame
eigenschappen
(p, q)
(p)
(q)
w
v
u
t
s
r
(q)
(p)
(q)
Correspondentie
4
Kripke Semantiek
De semantische regels voor en ♦
I
M, w ϕ
desda
voor iedere v met wRv geldt M, v ϕ
I
M, w ♦ϕ
desda
Kripke
Semantiek
Geldigheid
De bereikbaarheidsrelatie
Frame
eigenschappen
Correspondentie
voor tenminste ´e´en v met wRv geldt M, v ϕ
Dualiteit
I
ϕ ↔ ¬♦¬ϕ
I
♦ϕ ↔ ¬¬ϕ
5
Kripke Semantiek
(p, q)
(p)
(q)
w
v
u
Kripke
Semantiek
Geldigheid
t
s
r
(q)
(p)
(q)
De bereikbaarheidsrelatie
Frame
eigenschappen
Correspondentie
I
M, w ♦p
want wRv en M, v p
I
M, w ¬p
want wRt en M, t 6 p
I
M, w ♦p
want wRt en M, t p, omdat tRv ,
M, v p en v is de enige wereld x
met tRx
I
M, w ♦⊥
want wRv en M, v ⊥, omdat v
een blinde wereld is
6
Geldigheid
Geldigheid in een model: M ϕ
Een formule ϕ is geldig in een Kripke model M = hW, R, Vi,
notatie: M ϕ, desda
Kripke
Semantiek
voor alle werelden w ∈ W geldt M, w ϕ
De bereikbaarheidsrelatie
Geldigheid in een modelstructuur: F ϕ
Frame
eigenschappen
Een formule ϕ is geldig in een modelstructuur F = hW, Ri,
notatie: F ϕ, desda
Correspondentie
Geldigheid
voor alle modellen M = hW, R, Vi geldt M ϕ
Algemene modaallogische geldigheid: ϕ
Een formule ϕ is algemeen modaallogisch geldig,
notatie: ϕ, desda
voor alle modelstructuren F = hW, Ri geldt F ϕ
7
Geldigheid
Algemene modaallogische geldigheid
Kripke
Semantiek
ϕ is algemeen modaallogisch geldig
desda
ϕ is in alle modelstructuren F geldig
desda
Geldigheid
De bereikbaarheidsrelatie
Frame
eigenschappen
Correspondentie
ϕ is in alle modellen M geldig
desda
ϕ is in alle modellen M in alle werelden w waar
Voorbeeld:
I
ϕ ∨ ¬ϕ
I
(ϕ ∨ ¬ϕ)
8
Geldigheid
Algemene modaallogische geldigheid
Kripke
Semantiek
Hoe laat je zien dat een formule ϕ niet algemeen modaallogisch
geldig is?
Je geeft een model M = hW, R, Vi zodanig dat in tenminste
´e´en wereld w ∈ W geldt M, w 6 ϕ.
Geldigheid
De bereikbaarheidsrelatie
Frame
eigenschappen
Correspondentie
Voorbeeld: 6 ♦♦ϕ → ♦ϕ
(p) w
I
6 ♦♦p → ♦p
v()
omdat M, w ♦♦p en M, w 6 ♦p
9
Geldigheid
Kripke
Semantiek
Geldige gevolgtrekking: Γ ϕ
Een formule ϕ ∈ Lm is een geldige gevolgtrekking uit een
verzameling van formules Γ ⊆ Lm , notatie: Γ ϕ, desda
voor alle modellen M = hW, R, Vi en alle werelden w ∈ W
geldt: Als voor alle ψ ∈ Γ, M, w ψ, dan M, w ϕ.
I
∅ϕ
I
{ψ} ϕ
desda
desda
Geldigheid
De bereikbaarheidsrelatie
Frame
eigenschappen
Correspondentie
ϕ
ψ→ϕ
10
Geldigheid
Kripke
Semantiek
Geldige gevolgtrekking
Hoe laat je zien dat een formule ϕ een geldige gevolgtrekking
uit een verzameling Γ is?
Geldigheid
De bereikbaarheidsrelatie
Frame
eigenschappen
Correspondentie
Je neemt een willekeurige Kripke model M = hW, R, Vi en een
willekeurige wereld w ∈ W waarin de formules uit Γ allemaal
waar zijn (d.w.z. M, w ψ voor alle ψ ∈ Γ) en laat zien dat de
formule ϕ vervolgens ook waar is in w (d.w.z. M, w ϕ).
11
Geldigheid
Geldige gevolgtrekking
Kripke
Semantiek
Geldigheid
Voorbeeld: {(ϕ → ψ), ϕ} ψ
Zij M = hW, R, Vi een willekeurige Kripke model en w ∈ W
een willekeurige wereld zodanig dat M, w (ϕ → ψ) en
M, w ϕ.
De bereikbaarheidsrelatie
Frame
eigenschappen
Correspondentie
Zij v een willekeurige wereld met wRv .
Aangezien M, w (ϕ → ψ) geldt M, v ϕ → ψ.
Aangezien M, w ϕ geldt M, v ϕ.
Daaruit volgt: M, v ψ.
Daar dit voor alle v met wRv geldt, volgt: M, w ψ.
12
Geldigheid
Geldige gevolgtrekking
Hoe laat je zien dat een formule ϕ geen geldige gevolgtrekking
uit een verzameling Γ is?
Kripke
Semantiek
Je geeft een model M = hW, R, Vi zodanig dat er in tenminste
´e´en wereld w ∈ W alle formules uit Γ waar zijn (d.w.z.
M, w ψ voor alle ψ ∈ Γ) en ϕ onwaar is (d.w.z. M, w 6 ϕ).
De bereikbaarheidsrelatie
Geldigheid
Frame
eigenschappen
Correspondentie
Voorbeeld: {(ϕ ∨ ψ)} 6 ϕ ∨ ψ
v (p)
(p, q) w
I
M, w (p ∨ q)
I
M, w 6 p ∨ q
u (q)
13
Geldigheid
Geldigheid van Necessitatie
Kripke
Semantiek
Als ϕ, dan ϕ
Geldigheid
Bewijs:
De bereikbaarheidsrelatie
Stel dat ϕ.
Frame
eigenschappen
Zij M = hW, R, Vi een willekeurige Kripke model en w ∈ W
een willekeurige wereld.
Correspondentie
Zij v een willekeurige wereld met wRv .
Aangezien ϕ geldt M, v ϕ.
Daar dit voor alle v met wRv geldt, volgt M, w ϕ.
Omdat dit weer voor elke w ∈ W geldt, volgt M ϕ
En aangezien M willekeurig gekozen was, volgt ϕ.
14
Geldigheid
Geldigheid van Necessitatie: Als ϕ, dan ϕ
I
Kripke
Semantiek
Als ϕ, dan ϕ:
∀M ∀w : M, w ϕ ⇒ ∀M ∀w : M, w ϕ
I
Geldigheid
De bereikbaarheidsrelatie
{ϕ} ϕ:
∀M ∀w (M, w ϕ ⇒ M, w ϕ)
Frame
eigenschappen
Correspondentie
Let op: ϕ 6 ϕ
v (p)
(p) w
I
M, w p
I
M, w 6 p
t ()
15
Geldigheid
Geldigheid van vervanging van equivalenten
Zij θ[ϕ/p] diegene formule die uit θ ontstaat als elk voorkomen
van p in θ door ϕ wordt vervangen.
Voorbeeld:
Als θ = (p ∨ q) en ϕ = p, dan θ[ϕ/p] = (p ∨ q).
Kripke
Semantiek
Geldigheid
De bereikbaarheidsrelatie
Frame
eigenschappen
Correspondentie
Als ϕ ↔ ψ, dan θ[ϕ/p] ↔ θ[ψ/p].
Let op: ϕ ↔ ψ 6 θ[ϕ/p] ↔ θ[ψ/p]
I
θ = p, ϕ = p, ψ = p ∨ q
I
M, w p ↔ (p ∨ q)
I
M, w 6 p ↔ (p ∨ q)
v (p)
(p) w
t (q)
16
De bereikbaarheidsrelatie
I
Zij F = hW, R, Vi een reflexieve modelstructuur.
Dan: F ϕ → ♦ϕ voor alle ϕ ∈ Lm
I
Zij F = hW, R, Vi een niet-reflexieve modelstructuur.
Bijvoorbeeld:
v (p)
Kripke
Semantiek
Geldigheid
De bereikbaarheidsrelatie
Frame
eigenschappen
Correspondentie
(p) w
F 6 ϕ → ♦ϕ
t (q)
want M, w 6 p → ♦p, omdat M, w p en M, w 6 ♦p
17
De bereikbaarheidsrelatie
I
Zij F = hW, R, Vi een reflexieve modelstructuur.
Dan: F ϕ → ♦ϕ voor alle ϕ ∈ Lm
I
Zij F = hW, R, Vi een niet-reflexieve modelstructuur.
Kripke
Semantiek
Geldigheid
De bereikbaarheidsrelatie
Frame
eigenschappen
Bijvoorbeeld:
v (q)
Correspondentie
(p) w
F 6 ϕ → ♦ϕ
t (q)
want M, w 6 p → ♦p,
omdat M, w p en M, w 6 ♦p
18
De bereikbaarheidsrelatie
v (geen schoenen)
Kripke
Semantiek
Geldigheid
(schoenen) w
De bereikbaarheidsrelatie
t (geen schoenen)
Frame
eigenschappen
Correspondentie
I
M, w Ik draag schoenen, en het is niet mogelijk dat ik
schoenen draag. (???)
I
M, w Ik weet dat ik geen schoenen draag, en ik draag
schoenen. (???)
19
De bereikbaarheidsrelatie
v (geen schoenen)
Kripke
Semantiek
Geldigheid
(schoenen) w
De bereikbaarheidsrelatie
t (geen schoenen)
Frame
eigenschappen
Correspondentie
I
M, w Ik geloof dat ik geen schoenen draag, en ik draag
schoenen.
I
M, w Het is verplicht dat ik geen schoenen draag, en
ik draag schoenen.
20
De bereikbaarheidsrelatie
Kripke
Semantiek
w
(schoenen)
v
(geen schoenen)
t
(schoenen)
Geldigheid
De bereikbaarheidsrelatie
Frame
eigenschappen
I
M, w Ik weet dat ik schoenen draag, en ik houd het
niet voor mogelijk dat ik schoenen draag. (???)
I
M, w Het is verplicht dat ik schoenen draag, en het is
niet toegestaan dat ik schoenen draag.(???)
Correspondentie
21
De bereikbaarheidsrelatie
Verschillende modaliteiten
I
alethisch
I
epistemisch
I
doxastisch
I
deontisch
I
temporeel
Kripke
Semantiek
Geldigheid
De bereikbaarheidsrelatie
Frame
eigenschappen
Correspondentie
Verschillende eisen aan de bereikbaarheidsrelatie
I
In epistemische modellen moet elke wereld vanuit zichzelf
bereikbaar zijn.
I
In deontische modellen moet er voor elke wereld tenminste
´e´en bereikbare wereld zijn.
22
Frame eigenschappen
Zij R ⊆ W × W een bereikbaarheidsrelatie.
I
R is reflexief desda ∀w (wRw ).
I
R is symmetrisch desda ∀w ∀v (wRv → vRw ). w
I
R is transitief desda ∀w ∀v ∀z((wRv ∧ vRz) → wRz).
v
w
I
Geldigheid
v
De bereikbaarheidsrelatie
Frame
eigenschappen
Correspondentie
z
R is euclidisch desda ∀w ∀v ∀z((wRv ∧ wRz) → vRz).
v
w
I
Kripke
Semantiek
w
z
R is voortzettend (of serieel) desda ∀w ∃v (wRv ).
23
Frame eigenschappen
R is reflexief
R is irreflexief
R is symmetrisch
R is asymmetrisch
R is anti-symmetrisch
R is transitief
R is euclidisch
R is dicht
R is deterministisch
R is voortzettend
R is disconnected
R is universeel
⇔
⇔
⇔
⇔
⇔
⇔
⇔
⇔
⇔
⇔
⇔
⇔
∀w (wRw )
∀w ¬(wRw )
∀w ∀v (wRv → vRw )
∀w ∀v (wRv → ¬vRw )
∀w ∀v ((wRv ∧ w 6= v ) → ¬vRw )
∀w ∀v ∀z((wRv ∧ vRz) → wRz)
∀w ∀v ∀z((wRv ∧ wRz) → vRz)
∀w ∀v (wRv → ∃z(wRz ∧ zRv ))
∀w ∀v ∀z((wRv ∧ wRz) → v = z)
∀w ∃v (wRv )
∀w ∀v (¬vRw )
∀w ∀v (wRv )
Kripke
Semantiek
Geldigheid
De bereikbaarheidsrelatie
Frame
eigenschappen
Correspondentie
24
Frame eigenschappen
Kripke
Semantiek
Geldigheid
I
Een modelstructuur F = hW, Ri heet reflexief
(symmetrisch, transitief, etc.) desda R reflexief
(symmetrisch, transitief, etc.) is.
De bereikbaarheidsrelatie
Frame
eigenschappen
Correspondentie
I
Een model M = hW, R, Vi heet reflexief (symmetrisch,
transitief, etc.) desda F = hW, Ri reflexief (symmetrisch,
transitief, etc.) is.
25
Correspondentie
Kripke
Semantiek
Geldigheid
Geldigheid in een klasse van modelstructuren: C ϕ
Zij ϕ ∈ Lm een formule en C een klasse van modelstructuren.
ϕ is geldig in C , notatie: C ϕ,
De bereikbaarheidsrelatie
Frame
eigenschappen
Correspondentie
desda
voor alle modelstructuren F = hW, R, i ∈ C geldt F ϕ.
26
Correspondentie
Karakteriseerbaarheid
Een verzameling formules Γ ⊆ Lm karakteriseert een klasse C
van modelstructuren desda
voor alle modelstructuren F geldt:
F ∈C
desda
F ψ voor alle ψ ∈ Γ.
Kripke
Semantiek
Geldigheid
De bereikbaarheidsrelatie
Frame
eigenschappen
Correspondentie
Modale definieerbaarheid
Een klasse C van modelstructuren is modaal definieerbaar
desda
er is een verzameling modale formules Γ ⊆ Lm die deze klasse
karakteriseert.
27
Correspondentie
Kripke
Semantiek
Reflexiviteit
Geldigheid
De klasse van alle reflexieve modelstructuren is modaal
definieerbaar.
De bereikbaarheidsrelatie
De formule ϕ → ϕ karakteriseert de klasse van alle reflexieve
modelstructuren.
Correspondentie
Frame
eigenschappen
Zij F = hW, Ri een modelstructuur.
F ϕ → ϕ desda
F is reflexief.
28
Correspondentie
Reflexiviteit
Zij F = hW, Ri een modelstructuur.
Kripke
Semantiek
Geldigheid
F is reflexief
desda F ϕ → ϕ.
Bewijs:
“⇒” Stel dat F = hW, Ri reflexief is.
De bereikbaarheidsrelatie
Frame
eigenschappen
Correspondentie
Zij M = hW, R, Vi een willekeurige model dat op F
gebaseerd is en w ∈ W een willekeurige wereld.
Stel dat M, w ϕ.
Omdat F reflexief is, geldt: wRw
Aangezien M, w ϕ, volgt: M, w ϕ
Daaruit volgt: M, w ϕ → ϕ
Daar dit voor alle w ∈ W geldt, volgt: M ϕ → ϕ
Aangezien M willekeurig gekozen was, geldt: F ϕ → ϕ
29
Correspondentie
Reflexiviteit
Kripke
Semantiek
Zij F = hW, Ri een modelstructuur.
F is reflexief
desda F ϕ → ϕ.
Bewijs:
“⇐” Stel dat F = hW, Ri niet reflexief is.
Geldigheid
De bereikbaarheidsrelatie
Frame
eigenschappen
Correspondentie
Dan is er een wereld w ∈ W zodanig dat ¬wRw .
Beschouw M = hW, R, Vi met p ∈ V (x) desda wRx.
Dan: M, w p en M, w 6 p
Daaruit volgt: M, w 6 p → p
Dus: F 6 ϕ → ϕ
30
Correspondentie
Reflexiviteit
Let op:
Bekijk de volgende niet-reflexieve modelstructuur.
Kripke
Semantiek
Geldigheid
w
v
Er is een valuatie V op deze modelstructuur zodanig dat in het
resulterende model M geldt: M p → p.
(p) w
De bereikbaarheidsrelatie
Frame
eigenschappen
Correspondentie
v (p)
Maar er is ook een valuatie V 0 zodanig dat in het resulterende
model M0 geldt: M0 6 p → p.
(p) w
v ()
31
Correspondentie
Disconnected
Zij F = hW, Ri een modelstructuur.
F is disconnected
desda F ϕ.
Bewijs:
“⇒” Stel dat F = hW, Ri disconnected is.
Kripke
Semantiek
Geldigheid
De bereikbaarheidsrelatie
Frame
eigenschappen
Correspondentie
Zij M = hW, R, Vi een willekeurige model dat op F
gebaseerd is en w ∈ W een willekeurige wereld.
Omdat F disconnected is, geldt: er is geen v met wRv .
Aangezien w een blinde wereld is, geldt M, w ϕ.
Daar dit voor alle w ∈ W geldt, volgt: M ϕ.
Aangezien M willekeurig gekozen was, geldt: F ϕ
32
Correspondentie
Disconnected
Kripke
Semantiek
Zij F = hW, Ri een modelstructuur.
F is disconnected
desda F ϕ.
Bewijs:
“⇐” Stel dat F = hW, Ri niet disconnected is.
Geldigheid
De bereikbaarheidsrelatie
Frame
eigenschappen
Correspondentie
Dan is er een wereld w ∈ W zodanig dat er een wereld v
is met wRv .
Beschouw M = hW, R, Vi met p ∈
/ V (x) desda wRx.
Dan geldt: M, w 6 p.
Dus: F 6 ϕ
33
Correspondentie
I
I
ϕ → ϕ karakteriseert de klasse van alle reflexieve
modelstructuren.
♦ϕ → ϕ karakteriseert de klasse van alle symmetrische
modelstructuren.
I
ϕ → ϕ karakteriseert de klasse van alle transitieve
modelstructuren.
I
♦ϕ → ♦ϕ karakteriseert de klasse van alle euclidische
modelstructuren.
I
ϕ → ϕ karakteriseert de klasse van alle dichte
modelstructuren.
I
♦ϕ → ϕ karakteriseert de klasse van alle deterministische
modelstructuren.
I
ϕ → ♦ϕ karakteriseert de klasse van alle voortzettende
modelstructuren.
Kripke
Semantiek
Geldigheid
De bereikbaarheidsrelatie
Frame
eigenschappen
Correspondentie
34
Correspondentie
Kripke
Semantiek
Als Γ de klasse C van modelstructuren karakteriseert en Γ0 de
klasse C 0 van modelstructuren karakteriseert, dan karakteriseert
Γ ∪ Γ0 de klasse C ∩ C 0 van modelstructuren.
Geldigheid
De bereikbaarheidsrelatie
Frame
eigenschappen
Correspondentie
Voorbeeld:
{ϕ → ϕ, ♦ϕ → ϕ, ϕ → ϕ} karakteriseert de klasse van
alle modelstructuren die reflexief, symmetrisch en transitief zijn.
35

Download Report