slide

Logica voor Informatica
Mehdi Dastani
Introductie predicatenlogica
Semantiek van Predicatenlogica
Gottlob Frege
Semantiek

Tot nu toe hebben we het alleen gehad over
de syntax van een predikatenlogische taal T.
Nu gaan we over naar de semantiek.

Een model voor een predicatenlogische taal
T is M=<D,I> waar:
 Een niet-leeg domein D van objecten
 Een interpretatie-functie I
Interpretaties

Given a domain D, een interpretatie(functie)
I interpreteert

Constante c
I(c) = d∈D

Functiesymbool fn
I(fn) = hin : Dn → D

Predicaatsymbool Pn
I(Pn) = Rn ⊆ Dn
Voorbeeld

D=

Gegeven I met




(verz. natuurlijke getallen)
I(0) = 0
I(S) = Succ
I(+) = +
zdd
zdd
I( +( S(0) , S(0) ) ) =
=
=
=
Succ(0)=1 ,…
+(1,1)=2 ,…
I(+)( I(S(0)) , I(S(0)) )
+( I(S)(I(0)) , I(S)(I(0)) )
+(Succ(0), Succ(0))
+(1, 1) = 2
Bedelingen (Assignments)


Een bedeling is een functie b : VAR → D die de
variabelen afbeeldt op objecten in het domein D.
Voorbeeld: VAR = {x,y,z,…} en D = {Jan, Piet, Auto,…}




b1(x)=Jan,
b2(x)=Piet,
b3(x)=Auto,
…
b1(y)=Piet,
b2(y)=Jan,
b3(y)=Piet,
b1(z)=auto
b2(z)=auto
b3(z)=Piet
Dezelfde object
…
…
…
Waardering van Termen

Een interpretatie I beeldt CON, FUN en PRE van
predikatenlogische taal T af op objecten, functies
en relaties in het domein D.

Een bedelingen b beeldt VAR van T af op
objecten in het domain D.

Given een interpretatie I en een bedeling b, een
waardering is een functie WI,b: TER → D die
termen afbeeldt op objecten in D.
Waardering van Termen

Given een interpretatie I en een bedeling b, een
waardering is een functie WI,b: TER → D die
termen afbeeldt op objecten in D.

WI,b(t) = I(t)
als t een constante is

WI,b(t) = b(t)
als t een variabele is, dus iedere
variabele heeft een waarde in D

WI,b(fn(t1,…, tn))
=
I(fn)(WI,b(t1),…, WI,b(tn))
Varianten van bedelingen

We definieren een relatie =x op bedelingen
b’ =x b
“b’ is een x-variant van b”, of
“b’ is gelijk aan b, evt. op x na”
b’ =x b ⇔ voor alle variabelen y ≠ x: b’(y) = b(y)
(en voor alle constanten, functie- en predicatensymbolen
zijn b en b’ ook gelijk)

M.a.w. b’ en b kunnen alleen in hun waarde voor x
verschillen, dus niet noodzakelijk b(x) = b’(x)
Valuatie


Wat betekent het dat “formule ϕ van
predikatenlogische taal T waar is in M=<D,I>” ?
Gegeven een model M en een bedeling b, een
valuatie is een functie VM,b:FOR→{true,false} zdd






VM,b(Pn(t1,…, tn)) = true
VM,b(¬ ϕ) = true
VM,b(ϕ∧ψ) = true
VM,b(ϕ∨ψ) = true
VM,b(ϕ→ψ) = true
VM,b(ϕ↔ψ) = true
⇔
⇔
⇔
⇔
⇔
⇔
< VM,b(t1) ,…, VM,b(tn) > ∈ I(Pn)
VM,b(ϕ) = false
VM,b(ϕ)=true en VM,b(ψ)=true
VM,b(ϕ)=true of VM,b(ψ)=true
als VM,b(ϕ)=true dan VM,b(ψ)=true
VM,b(ϕ)=true desda VM,b(ψ)=true
Valuatie (kwantoren)

Gegeven een model M en een bedeling b, een
valuatie is een functie VM,b:FOR→{true,false} zdd

VM,b(∃x ϕ) = true
⇔
VM,b’ (ϕ)=true voor een b’=x b

VM,b(∀x ϕ) = true
⇔
VM,b’ (ϕ)=true voor alle b’=x b
Vervulbaarheid (Satisfactie) ⊨


Zij M=<D,I> een model van de predikatenlogische
taal T, b een bedeling, en ϕ een formule uit T.
We zeggen dat M en b de formule ϕ vervullen als
VM,b(ϕ) = true

Notatie: M,b ⊨ ϕ

Dus:
M,b ⊨ ϕ
⇔
VM,b(ϕ) = true
Voorbeeld: Er is een even
natuurlijk getal ∃x Even(x)


Zij D= , M=<D, I > een model met
I(Even) = Even = {2,4,6,…}, en bedeling b
M,b ⊨ ∃x Even(x)
⇔ VM,b(∃x Even(x)) = true
⇔ VM,b(Even(x)) = true voor een b’ met b’ =x b
⇔ er is b’ en n∈D : VM,b’(Even(x)) = true en
b’(x)=n en b’(y) = b(y) voor alle y ≠ x
⇔ er is b’ en n∈D : VM,b’(x)∈ I(Even)
⇔ er is n∈D : n ∈ Even = {2,4,6,…}
⇔ true
Waarheid en Contingentie

Een formule ϕ is waar in een model M



Een formule ϕ is onwaar in een model M



Notatie: M ⊨ ϕ
Als voor alle bedeling b geldt: M,b ⊨ ϕ
Notatie: M ⊭ ϕ
Als voor alle bedeling b geldt: M,b ⊭ ϕ
Een formule ϕ is contingent in een model M

Als ϕ waar noch onwaar is in M
Logisch gevolg

Een predikatenlogische formule ψ is een logisch
gevolg van predikatenlogische formules ϕ1,…,ϕn


Notatie: ϕ1,…,ϕn ⊨ ψ
Als voor elk model M geldt dat
M ⊨ ϕ1∧…∧ϕn implies M ⊨ ψ

Download Report