Kapitel 13: Prädikatenlogik erster Stufe Thomas...

Grundbegri�e der InformatikKapitel 13: Prädikatenlogik erster Stufe

Thomas Worsch

KIT, Institut für Theoretische Informatik

Wintersemester 2015/2016

GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 1 / 63

Überblick

Syntax prädikatenlogischer Formeln

Semantik prädikatenenlogischer Formeln

Freie und gebundene Variablenvorkommen und Substitutionen

Beweisbarkeit

Wo sind wir?

Beweisbarkeit

Prädikatenlogische Formelnkomplizierter aufgebaut als aussagenlogische

drei Schri�eTerme

Variablensymbole, Konstantensymbole, Funktionssymboleatomare Formeln

aus Termenmi�els Relationssymbolen

prädikatenlogische Formelnaus atomaren Formelnmi�els aussagenlogischer Konnektive undsogenannter �antoren

nicht nur die Syntax ist aufwändiger . . .

Prädikatenlogische Formeln — der Aufwand lohnt sichkompliziertere Syntax

aufwändigere Definitionen

aber (deswegen) viele benutztbeim „alltäglichen Formulieren“

Definitionen, Aussagen, Beweise

bei der Verifikation von Algorithmen

großzügige Benutzungnach Abschluss dieses Kapitels

Terme — benötigte AlphabeteVariablensymbole: Alphabet VarPL

xi (für endliche viele i ∈ N0)kurz x, y, z

Konstantensymbole: Alphabet ConstPLci (für endliche viele i ∈ N0)kurz c, d

Funktionsymbole: Alphabet FunPLfi (für endliche viele i ∈ N0)kurz f, g, hjedes fi ∈ FunPL hat Stelligkeit ar(fi ) ∈ N+

ATer = {(, ,, )} ∪ VarPL ∪ ConstPL ∪ FunPL

Terme — SyntaxGrammatik (NTer ,ATer ,T, PTer )

m maximale Stelligkeit von Funktions- bzw. Relationssymbolen

m + 1 Nich�erminalsymboleNTer = { T } ∪ { Li | i ∈ N+ und i ≤ m }

Produktionen

Li+1 → Li,T für jedes i ∈ N+ mit i < m

L1 → TT→ ci für jedes ci ∈ ConstPLT→ xi für jedes xi ∈ VarPLT→ fi(Lar(fi )) für jedes fi ∈ FunPL

Terme — BeispielBestandteile

VarPL = {x, y}ConstPL = {c}FunPL = {f, g} mit ar(f) = 2 und ar(g) = 1

DannNTer = {T,L1,L2}PTer = {L2 → L1,T , L1 → T

T→ c | x | y

T→ g(L1) | f(L2)}

BeispielableitungenL1 ⇒∗ c und T⇒∗ g(c)L2 ⇒∗ x,g(c)und T⇒∗ f(x,g(c))

Terme — BeispielBestandteile

VarPL = {x, y}ConstPL = {c}FunPL = {f, g} mit ar(f) = 2 und ar(g) = 1

DannNTer = {T,L1,L2}PTer = {L2 → L1,T , L1 → T

T→ c | x | y

T→ g(L1) | f(L2)}

nicht ableitbarxy c(x) f)x,y( g(c,c,c,x)

Atomare Formeln — SyntaxRelationsymbole: Alphabet RelPL=̇ immer dabeiRi (für endliche viele i ∈ N0)kurz als R, Sjedes Ri ∈ RelPL hat Stelligkeit ar(Ri ) ∈ N+

ARel = ATer ∪ RelPL

Grammatik (NRel,ARel,A, PRel )m maximale Stelligkeit von Funktions- bzw. RelationssymbolenNRel = { A,T } ∪ { Li | i ∈ N+ und i ≤ m }PRel = PTer ∪ {A→ Ri(Lar(Ri )) | für jedes Ri ∈ RelPL }

∪ { A→ T =̇T } .

Atomare Formeln — Beispielebei geeigneter Wahl von VarPL , ConstPL , FunPL sowie

RelPL = {R, S}mit ar(R) = 3 und ar(S) = 1

ableitbarg(x)=̇ f(x,g(z))S(c)R(y, c, g(x))

syntaktisch falschx =̇ y =̇ z R =̇ f S(x)=̇ S(x)

R(x,y) f(S(x)) R(S(x),x,x)

(S(S))(x) R)x,y(gRf() x R(zx < y

Prädikatenlogische Formeln — SyntaxAFor = ARel ∪ { , >, <, , , }

AllquantorExistenzquantor

Grammatik (NFor ,AFor ,F, PFor )NFor = { F } ∪ NRelPFor = PRel ∪ { F→ A }

∪ { F→( F), F→(F > F)}∪ { F→(F < F), F→(F F)}∪ { F→( xi F) | xi ∈ VarPL }

∪ { F→( xi F) | xi ∈ VarPL }

Klammereinsparungsregeln wie in Aussagenlogikzusätzlich: �antoren binden noch stärker als alle andere

Prädikatenlogische Formeln — Beispielex R(x,y) > S(x)

Kurzform von( x R(x,y)) > S(x)

( x x =̇ y) ( x x =̇ y)

Was ist wichtigDas sollten Sie mitnehmen:

Termeatomare FormelnFormeln

Das sollten Sie üben:Formeln analysieren

Syntaxfehler suchenFormeln schreiben

Syntaxfehler vermeiden ;-)

Wo sind wir?

Beweisbarkeit

InterpretationenAlphabete ConstPL , FunPL und RelPL gegeben

Interpretation (D, I )

nichtleere Menge D, das UniversumI (ci ) ∈ D für ci ∈ ConstPLI (fi ) : Dar(fi ) → D für fi ∈ FunPLI (Ri ) ⊆ Dar(Ri ) für Ri ∈ RelPL

BeispielD = N0I (c) = 0ar(f) = 2 und I (f) : N2

0 → N0 : (x ,y) 7→ x + yar(R) = 2 und I (R) = {(x ,y) | x ≤ y} ⊆ N2

Variablenbelegung β : VarPL → D

z. B. β (x) = 3 und β (y) = 42

valD,I ,β — ein Wert für jeden Termund ein Wahrheitswert für jede Formel

Alphabete ConstPL , FunPL und RelPL gegeben

Interpretation (D, I )

Variablenbelegung β : VarPL → D

definiere valD, I,β : LTer ∪ LFor → D ∪ Bfür jeden Term t : valD, I,β (t ) ∈ Dfür jede Formel G: valD, I,β (G ) ∈ B

valD,I ,β — ein Wert in D für jeden Term

Interpretation (D, I )Variablenbelegung β : VarPL → D

für Term t ∈ LTer drei MöglichkeitenvalD, I,β (xi ) = β (xi ) für xi ∈ VarPLvalD, I,β (ci ) = I (ci ) für ci ∈ ConstPLvalD, I,β (fi(t1, . . . ,tk)) = I (fi ) (valD, I,β (t1), . . . , valD, I,β (tk ))

erstes BeispielD = N0, I (c) = 0, I (f) Additionβ (x) = 3 und β (y) = 42valD, I,β (f(y,c)) = I (f) (valD, I,β (y), valD, I,β (c))

= I (f) (β (y), I (c))

= I (f) (42, 0)= 42 + 0 = 42

valD,I ,β — ein Wert in D für jeden Term

für Term t ∈ LTer drei MöglichkeitenvalD, I,β (xi ) = β (xi ) für xi ∈ VarPLvalD, I,β (ci ) = I (ci ) für ci ∈ ConstPLvalD, I,β (fi(t1, . . . ,tk)) = I (fi ) (valD, I,β (t1), . . . , valD, I,β (tk ))

zweites BeispielD = {a,b}+, I (c) = bab, I (f) Konkatenationβ (x) = aaa und β (y) = bavalD, I,β (f(y,c)) = I (f) (valD, I,β (y), valD, I,β (c))

= I (f) (β (y), I (c))

= I (f) (ba,bab)= ba · bab = babab

valD,I ,β — ein Wahrheitswert für jede atomare Formel

für atomare Formel A ∈ LRel zwei MöglichkeitenvalD, I,β (Ri(t1, . . . , tk)) =

w, falls (valD, I,β (t1), . . . , valD, I,β (tk )) ∈ I (Ri )

f, falls (valD, I,β (t1), . . . , valD, I,β (tk )) < I (Ri )

valD, I,β (t1 =̇ t2) =

w, falls valD, I,β (t1) = valD, I,β (t2)

f, falls valD, I,β (t1) , valD, I,β (t2)

valD,I ,β — Beispiel für atomare Formeln

valD, I,β (Ri(t1, . . . , tk)) =

w, falls (valD, I,β (t1), . . . , valD, I,β (tk )) ∈ I (Ri )

f, falls (valD, I,β (t1), . . . , valD, I,β (tk )) < I (Ri )

valD, I,β (t1 =̇ t2) =

w, falls valD, I,β (t1) = valD, I,β (t2)

f, falls valD, I,β (t1) , valD, I,β (t2)

BeispielD = N0, I (c) = 0, I (f) Addition, I (R) Kleiner-oder-gleichβ (x) = 3 und β (y) = 42

valD, I,β (R(y,c)) = wgdw. (valD, I,β (y), valD, I,β (c)) ∈ I (R)

gdw. (β (y), I (c)) ∈ I (R)

gdw. (42, 0) ∈ I (R)gdw. 42 ≤ 0 also ist valD, I,β (R(y,c)) = f

valD,I ,β — ein Wahrheitswert für jede Formel

für Formel G ∈ LFor mehrere MöglichkeitenH , H1 > H2, H1 < H2, H1 H2

wie in der Aussagenlogikz. B. valD, I,β (H1 > H2) = b > (valD, I,β (H1), valD, I,β (H2))

xi H , xi Herfordert eine kleine Vorbereitung

für β : VarPL → D, xi ∈ VarPL und d ∈ D sei

βdxi : VarPL → D : xj 7→

β (xj ) falls j , i

d falls j = i

valD,I ,β — ein Wahrheitswert für jede Formel

für Formel G ∈ LFor mehrere MöglichkeitenH , H1 > H2, H1 < H2, H1 H2

wie in der Aussagenlogikz. B. valD, I,β (H1 > H2) = b > (valD, I,β (H1), valD, I,β (H2))

xi H , xi Herfordert eine kleine Vorbereitung

für β : VarPL → D, xi ∈ VarPL und d ∈ D sei

βdxi : VarPL → D : xj 7→

β (xj ) falls j , i

d falls j = i

valD,I ,β — Wahrheitswert für quantifizierte Formeln

valD, I,β ( xi H ) =

w, falls für jedes d ∈ D und β ′ = βdxi gilt:

valD, I,β ′ (H ) = wf, sonst

w, falls für mind. ein d ∈ D und β ′ = βdxi gilt:

valD,I ,β — Beispiel für quantifizierte Formeln

Interpretation (D, I ), Variablenbelegung β : VarPL → D

valD, I,β ( x R(c,x)) = w

gdw. für alle d ∈ D, β ′ = βdx : (valD, I,β ′ (c), valD, I,β ′ (x)) ∈ I (R)

gdw. für alle d ∈ D, β ′ = βdx : (I (c), β ′(x)) ∈ I (R)

gdw. für alle d ∈ D, β ′ = βdx : (0,d ) ∈ I (R)

gdw. für alle d ∈ D, β ′ = βdx : 0 ≤ d also ist valD, I,β ( x R(c,x)) = w

gdw. für alle d ∈ D, β ′ = βdx : 0 ≤ d

also ist valD, I,β ( x R(c,x)) = w

gdw. für alle d ∈ D, β ′ = βdx : 0 ≤ d also ist valD, I,β ( x R(c,x)) = wGBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 22 / 63

Allgemeingültige Formelnprädikatenlogische Formel F allgemeingültig, wenn

für jede passende Interpretation (D, I ) undjede passende Variablenbelegung β gilt:valD, I,β (F ) = w.

einfache Beispiele:aussagenlogischer Tautologie Gfür vorkommende Aussagevariable Pije eine beliebige prädikatenlogische Formel Giersetze in G jedes Pi syntaktisch durch Gi

prädikatenlogische Tautologien

Beispiel

R(x,y) (( x f(y)=̇ c) R(x,y))GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 23 / 63

Allgemeingültige Formeln — aber keine TautologienBeispiele (für t1, t2 ∈ LTer )

(t1 =̇ t2) (t2 =̇ t1)

Beispiele (für G,H ∈ LFor )

( xi (G H)) (( xi G) ( xi H))

Beispiele (für t ∈ LTer )

( x R(x)) R(t)

Modelle(D, I ) Modell für G ∈ LFor , wenn

(D, I ) Interpretation für G undfür jedes β ist valD, I,β (G ) = w.

(D, I ) Modell für Γ ⊆ LFor , wenn(D, I ) Modell für jedes G ∈ Γ

Γ |= G, wennjedes Modell von Γ auch Modell von G

H |= G, wenn {H } |= G

|= G, wenn {} |= G,d. h. wenn G allgemeingültig

Modelle — BeispielFormel: x f(x,c)=̇ x

Modell: D = N0, I (c) = 0, I (f) Additionanschaulich: für jede nichtnegative ganze Zahl x ist x + 0 = xgenauer: prüfe, ob für jedes β gilt: valD, I,β (G ) = wprüfe für d ∈ N0 und β ′ = βdx , obvalD, I,β ′ (f(x,c)=̇ x) = wgdw. valD, I,β ′ (f(x,c)) = valD, I,β ′ (x) ist.linke Seite I (f) (β ′(x), I (c)) = β ′(x) + 0 = β ′(x)gleich rechter Seite

anderes Modell von G:D = {a,b}∗, I (c) = ε , I (f) Konkatenation

kein Modell: D = N0, I (c) = 0, I (f) Multiplikation

Was ist wichtigDas sollten Sie mitnehmen:

InterpretationenWerte in D für jeden TermWahrheitswert für jede Formel

Modelle

Das sollten Sie üben:Terme und Formeln auswertenFormeln auf Allgemeingültigkeit prüfen

Wo sind wir?

Beweisbarkeit

Vorkommen von Variablensymbolen in Formelnnur Vorkommen in Termen

nicht die Symbole unmi�elbar hinter �antoren

gleiche Variable kann an mehreren Stellen vorkommen

unterscheide freie und gebundene Vorkommen

definiereMenge fv(G ) der frei vorkommenden Variablen unddie Menge bv(G ) der gebunden vorkommenden Variablen

freie und gebundene Vorkommen vonVariablensymbolen

atomare Formel Galle Vorkommen von Variablen sind freibv(G ) = {}fv(G ) Menge aller in G an mindestens einer Stellevorkommenden Variablen.

bv(G ) = bv(H ) und fv(G ) = fv(H )freies bzw. gebundenes Vorkommen in Hist ein freies bzw. gebundenes Vorkommen in G.

G ∈ { H1 > H2,H1 < H2,H1 H2}

bv(G ) = bv(H1) ∪ bv(H2) und fv(G ) = fv(H1) ∪ fv(H2)freies bzw. gebundenes Vorkommen in Hiist ein freies bzw. gebundenes Vorkommen in G.

freie und gebundene Vorkommen vonVariablensymbolen (2)

G von der Form( xi H)oder( xi H)

bv(G ) =

bv(H ) ∪ {xi } falls xi ∈ fv(H )

bv(H ) sonstfv(G ) = fv(H ) r {xi }in G alle Vorkommen der Variablen xi gebundenVorkommen anderer Variablen in G frei bzw. gebundenwie in H

Redeweisen: alle in H freien Vorkommen von xibefinden sich im Wirkungsbereich des �antors am Anfangwerden durch den �antor am Anfang von G gebunden

Formel G geschlossen, wenn fv(G ) = {}

Beispiel x( R(x,y) > y R(x,y))sechstes Zeichen

erstes Vorkommen von xVorkommen gebunden durch Allquantor am Anfang

fünfzehntes Zeichenzweites Vorkommen von xVorkommen gebunden durch Allquantor am Anfang

achtes Zeichenerstes Vorkommen von yfreies Vorkommen

siebzehntes Zeichenzweites Vorkommen von yVorkommen gebunden durch Existenzquantor

also bv(G ) = {x, y} und fv(G ) = {y}

SubstitutionenSubstitution: Abbildung σ : VarPL → LTer

falls σ durch Menge S der Paare S = { xi j /σ (xi j ) | 1 ≤ j ≤ k }eindeutig bestimmtalso insbesondere S rechtseindeutigschreibe σS = σ { xij /σ (xij ) | 1≤j≤k }.

Beispiel: σ {x/c,y/f(x)} Abbildung mit

σ (x) = c

σ (y) = f(x)

σ (z) = z für jedes z < {x, y}

Erweiterung auf Terme und Formeln

Substitutionen — erweitert auf Termeerweitere σS zu σ ′S : LTer → LTer ,

σ ′S (t ) =

σS (x ), falls t = x ∈ VarPLc, falls t = c ∈ ConstPLf(σ ′S (t1), . . . ,σ

′S (tk )) falls t = f(t1, . . . , tk)

mit f ∈ FunPL , t1, . . . , tk ∈ LTer

schreibe sta� σ ′S wieder σS

Beispiele: σ {x/c,y/f(x)} (x) = c

σ {x/c,y/f(x)} (y) = f(x)

σ {x/c,y/f(x)} (g(y,x)) = g(f(x),c)

σ {x/c,y/f(x)} (f(z,z)) = f(z,z)

Substitutionen — erweitert auf Termeerweitere σS zu σ ′S : LTer → LTer ,

σ ′S (t ) =

σS (x ), falls t = x ∈ VarPLc, falls t = c ∈ ConstPLf(σ ′S (t1), . . . ,σ

′S (tk )) falls t = f(t1, . . . , tk)

mit f ∈ FunPL , t1, . . . , tk ∈ LTer

schreibe sta� σ ′S wieder σS

Achtung:σ {x/y,y/x} (f(x, y)) = f(σ {x/y,y/x} (x),σ {x/y,y/x} (y))

= f(y, x)

aber σ {x/y} (σ {y/x} (f(x, y)) = f(y, y)

Alle Variablen werden „gleichzeitig substituiert“!GBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 34 / 63

Substitutionen — erweitert auf nicht quantifizierteFormeln

erweitere σS zu σ ′′S : LFor → LFor ,

σ ′′S (G ) =

R(σ ′S (t1), . . . ,σ′S (tk )), falls G = R(t1, . . . , tk)∈ LRel

σ ′S (t1) =̇σ′S (t2), falls G = t1 =̇ t2 mit t1, t2 ∈ LTer

σ ′′S (H ), falls G = H

σ ′′S (H1) > σ ′′S (H2), falls G = H1 > H2

σ ′′S (H1) < σ ′′S (H2), falls G = H1 < H2

σ ′′S (H1) σ ′′S (H2), falls G = H1 H2

schreibe sta� σ ′′S wieder σS

Substitutionen — erweitert auf quantifizierte Formelnzu σS und x ∈ VarPL definiere Substitution σS−x :

σS−x (x ) = x

σS−x (y) = σS (y) für jedes y ∈ VarPL mit y , x

Beispielfür σ = σ {x/c,y/x}ist σ−x = σ {x/c,y/x}−x = σ {y/x}

definiere σ ′′S ( x H ) = x σ ′′S−x (H )

σ ′′S ( x H ) = x σ ′′S−x (H )

gebundene Variablenvorkommen werden nicht substituiert

schreibe sta� σ ′′S wieder σSGBI — Grundbegri�e der Informatik KIT, Institut für Theoretische Informatik 36 / 63

Substitutionen — Beispiel für eine quantifizierte FormelBeispiel G = S(x) > x R(x,y).

für jedes σ ist σ (G ) = σ (S(x) > x R(x,y))

= σ (S(x)) > σ ( x R(x,y))

= S(σ (x)) > x σ−x (R(x,y))

= S(σ (x)) > x R(σ−x (x),σ−x (y))

konkret z. B. σ = σ {x/c,y/f(x)}, also σ−x = σ {y/f(x)}

alsoσ (G ) = S(σ (x)) > x R(σ−x (x),σ−x (y))

= S(σ {x/c,y/f(x)} (x)) > x R(σ {y/f(x)} (x),σ {y/f(x)} (y))

= S(c) > x R(x,f(x))

Kollisionsfreie Substitutionen für FormelnSubstitution σ für Formel G kollisionsfrei, wenn gilt:

wennσ (xi ) , xi undxj in σ (xi ) vorkommt,

dannjedes freie Vorkommen von xi in Gnicht im Wirkungsbereich eines �antors xj oder xj

Logisch äquivalente FormelnFormeln G und H logisch äquivalent, wenn

für jede passende Interpretation (D, I ) undjede passende Variablenbelegung β

gilt:valD, I,β (G ) = valD, I,β (H )

Satz. WennG und H logisch äquivalent,Formel F enthält G als Teilformel undFormel F ′ entsteht aus F durch Ersetzen von G durch H

dannist F logisch äquivalent F ′.

Lemma. Wenn G und H logisch äquivalent sind,dann ist G H allgemeingültig.

Logisch äquivalente Formeln — Beispiele (1)G,H ∈ LFor , xi , xj ∈ VarPL

xi G und xi Gxi G und xi G

xi xj G und xj xi Gxi xj G und xj xi G

xi(G > H)und xi G > xi Hxi(G < H)und xi G < xi H

wenn xj < fv(G ) und σ {xi /xj } kollisionsfrei für G,dann sind äquivalent

xi G und x j σ {xi /xj } (G )

gebundene Umbenennung der Variable

Logisch äquivalente Formeln — Beispiele (2)G,H ∈ LFor , xi , xj ∈ VarPL

wenn xi < fv(G ), dann sind äquivalentG > xi H und xi(G > H)G > xi H und xi(G > H)

G < xi H und xi(G < H)G < xi H und xi(G < H)

G xi H und xi(G H)G xi H und xi(G H)

wenn xi < fv(H ), dann sind äquivalent( xi G) H und xi(G H)( xi G) H und xi(G H)

Weitere allgemeingültige Formeln (1)G,H ∈ LFor , xi , xj ∈ VarPL

wenn Substitution σ {xi /t } kollisionsfrei für G ist, dann

( xi G) σ {xi /t } (G )

allgemeingültig

wenn xi < fv(G ), dann

xi(G H) (G xi H)

allgemeingültig

Weitere allgemeingültige Formeln (2)G,H ∈ LFor

Für xi , xj , xk ∈ VarPL sindxi =̇ xixi =̇ xj xj =̇ xixi =̇ xj (xj =̇ xk xi =̇ xk)

allgemeingültig.

Für jedes k ∈ N+ gilt:Wenn x1, . . . ,xk ∈ VarPL und y1, . . . ,yk ∈ VarPL ,fi ein k-stelliges Funktionssymbol undRi ein k-stelliges Relationssymbol, dann sind

x1 =̇y1 (x2 =̇y2 ( · · ·(xk =̇yk fi(x1, . . . ,xk)=̇ fi(y1, . . . ,yk))· · · ))x1 =̇y1 (x2 =̇y2 ( · · ·(xk =̇yk (Ri(x1, . . . ,xk) Ri(y1, . . . ,yk)))· · · ))

allgemeingültig.

Wo sind wir?

Beweisbarkeit

KalküleFormeln

Axiome

Ableitungsregeln

Theoreme

Hilbert-Kalkül — für Prädikatenlogik erster StufeAlphabet AFor

Variablen-, Konstanten-, Funktions-, Relationssymbole

Formelmenge LFor

Axiomenmenge AxPL ⊆ LFor (kommt gleich)

SchlussregelnModus ponensGeneralisierung (kommt gleich)

Axiome für Hilbert-Kalkül — alle allgemeingültig (1)

AxAL1 ={(G (H G)) �� G,H ∈ LFor

AxAL2 ={(G (H K)) ((G H) (G K))�� G,H ,K ∈ LFor

AxAL3 ={( H G) (( H G) H) �� G,H ∈ LFor

AxPL1 ={( xi G) σ {xi /t } (G ) �� G ∈ LFor , xi ∈ VarPL, t ∈ LTer

und σ {xi /t } kollisionsfrei für G}

AxPL2 ={( xi(G H)) (G xi H)�� G,H ∈ LFor , xi ∈ VarPL, und xi < fv(G )

AxEq 1 ={xi =̇ xi

�� xi ∈ VarPL}

AxEq2 ={xi =̇ xj xj =̇ xi

�� xi , xj ∈ VarPL}

AxEq3 ={xi =̇ xj (xj =̇ xk xi =̇ xk)

�� xi , xj , xk ∈ VarPL}

AxEq4 ={xi1 =̇ xj1 (xi2 =̇ xj2 ( · · ·(xin =̇ xjn

fi(xi1, . . . ,xin)=̇ fi(xj1, . . . ,xjn))· · · ))�� xi1 , · · · , xin , xj1 , · · · , xjn ∈ VarPL, fi ∈ FunPL

AxEq5 ={xi1 =̇ xj1 (xi2 =̇ xj2 ( · · ·(xin =̇ xjn

(Ri(xi1, . . . ,xin) Ri(xj1, . . . ,xjn)))· · · ))�� xi1 , · · · , xin , xj1 , · · · , xjn ∈ VarPL, Ri ∈ RelPL

Schlussregeln für den Hilbert-Kalkül

Modus ponens MP ⊆ L3ForMP = {(G H ,G,H ) | G,H ∈ LFor }

Generalisierung GEN ⊆ L2ForGEN = {(G,( xi G)) | G ∈ LFor und xi ∈ VarPL }

( xi G)

beide Schlussregeln erhalten Allgemeingültigkeit

Ableitungen — formal gefasstAbleitungen nutzen Prämissen, Axiome und Schlussregeln

Γ ⊆ ForAL Hypothesen oder Prämissen undG eine Formel

Ableitung von G aus Γendliche Folge (G1, . . . ,Gn ) von Formeln mitGn = G (oder weiter vorne) undfür jedes Gi tri�t einer der folgenden Fälle zu:

Axiom Gi ∈ AxAL ,Prämisse Gi ∈ Γes gibt Indizes i1 und i2 echt kleiner i , für die gilt:(Gi1 ,Gi2 ,Gi ) ∈ MP .es gibt Index i1 echt kleiner i , für den gilt: (Gi1 ,Gi ) ∈ GEN .

einziger Unterschied zur Aussagenlogik

geschrieben Γ ` G

Ableitungen — formal gefasstAbleitungen nutzen Prämissen, Axiome und Schlussregeln

Γ ⊆ ForAL Hypothesen oder Prämissen undG eine Formel

Ableitung von G aus Γendliche Folge (G1, . . . ,Gn ) von Formeln mitGn = G (oder weiter vorne) undfür jedes Gi tri�t einer der folgenden Fälle zu:

Axiom Gi ∈ AxAL ,Prämisse Gi ∈ Γes gibt Indizes i1 und i2 echt kleiner i , für die gilt:(Gi1 ,Gi2 ,Gi ) ∈ MP .es gibt Index i1 echt kleiner i , für den gilt: (Gi1 ,Gi ) ∈ GEN .

einziger Unterschied zur Aussagenlogik

geschrieben Γ ` G

Beweis — formal gefasstBeweis von G: Ableitung aus Γ = {}

geschrieben ` GG heißt Theorem des Kalküls

Hilbert-Kalkül — korrekt und vollständigSatz.Für jede Formelmenge Γ ⊆ LFor und jedes G ∈ LFor gilt:

wenn Γ ` G, dann auch Γ |= G .

Der Hilbert-Kalkül ist korrekt.

Satz.Für jede Formelmenge Γ ⊆ LFor und jedes G ∈ LFor gilt:

wenn Γ |= G, dann auch Γ ` G .

Der Hilbert-Kalkül ist vollständig.

Deduktionstheorem — aber nur mit EinschränkungenSatz.Für geschlossene Formel G ∈ LFor und jede H ∈ LFor gilt

G ` H genau dann, wenn `(G H)

es gibt schwächere hinreichende Voraussetzungen

aber falsch für beliebige G und G ` H

Skizze eines Beispielses sei

FunPL = {f}ConstPL = {c}Γ = { x(f(c,x)=̇ x > f(x,c)=̇ x) }.

Modell (D, I ) von Γ

besitzt zweistellige Operation I (f) auf Deine Konstante I (c), die neutrales Element bezüglich I (f) ist.

BeispieleD = N0, I (f) : N0 × N0 → N0 : (x ,y) 7→ x + y und I (c) = 0,

D = {a,b}∗,I (f) : {a,b}∗ × {a,b}∗ → {a,b}∗ : (w1,w2) 7→ w1 ·w2 undI (c) = ε .

BeispieleD = N0, I (f) : N0 × N0 → N0 : (x ,y) 7→ x + y und I (c) = 0,

D = {a,b}∗,I (f) : {a,b}∗ × {a,b}∗ → {a,b}∗ : (w1,w2) 7→ w1 ·w2 undI (c) = ε .

BeispieleD = N0, I (f) : N0 × N0 → N0 : (x ,y) 7→ x + y und I (c) = 0,D = {a,b}∗,I (f) : {a,b}∗ × {a,b}∗ → {a,b}∗ : (w1,w2) 7→ w1 ·w2 undI (c) = ε .

Skizze eines Beispiels (2)Ziel: neutrales Element immer eindeutig

in jedem Modell von Γ ist Formel G

y( x(f(y,x)=̇ x > f(x,y)=̇ x) y =̇ c)

Weg:zeige Γ ` Gdann auch Γ |= G (Hilbert-Kalkül korrekt)

Skizze eines Beispiels (3)Kern der Argumentation

y = f (c,y) weil c (links)neutral

= c weil y (rechtbs)neutral

Übertragung in Hilbert-Kalkülprinzipiell möglichsehr mühsambeschränken uns auf Skizze

Skizze eines Beispiels (4)grobe Vorgehensweise in fünf Schri�en

Schri� 0: Ziel: für „beliebiges“ y giltx(f(y,x)=̇ x > f(x,y)=̇ x) y =̇ c

Schri� 1: zeige: y =̇ f(c,y)

Schri� 2: zeige: x(f(y,x)=̇ x > f(x,y)=̇ x) y =̇ f(c,y)

Schri� 3: zeige: x(f(y,x)=̇ x > f(x,y)=̇ x) f(c,y)=̇ c

Schri� 4: zeige x(f(y,x)=̇ x > f(x,y)=̇ x) y =̇ c

Schri� 5: von Schri� 4 durch Generalisierung zu:y( x(f(y,x)=̇ x > f(x,y)=̇ x) y =̇ c)

Skizze eines Beispiels (5)Schri� 1: zeige: y =̇ f(c,y)

Schri� 1.1: wegen x(f(c,x)=̇ x > f(x,c)=̇ x)giltinsbesonderef(c,y)=̇ y > f(y,c)=̇ y

Schri� 1.2: Also gilt f(c,y)=̇ y.Schri� 1.3: Also gilt y =̇ f(c,y).

Skizze eines Beispiels (6)Schri� 2: zeige: x(f(y,x)=̇ x > f(x,y)=̇ x) y =̇ f(c,y)

Schri� 1: y =̇ f(c,y)nutze Tautologieschema G (H G)

Skizze eines Beispiels (7)Schri� 3: zeige:x(f(y,x)=̇ x > f(x,y)=̇ x) f(c,y)=̇ c

Schri� 3.1: zeige x(f(y,x)=̇ x > f(x,y)=̇ x)x(f(y,x)=̇ x) > x(f(x,y)=̇ x)

Schri� 3.2: zeige x(f(y,x)=̇ x) > x(f(x,y)=̇ x)x(f(x,y)=̇ x)

Schri� 3.3: also x(f(y,x)=̇ x > f(x,y)=̇ x) x(f(x,y)=̇ x)

Schri� 3.4: zeige x(f(x,y)=̇ x) f(c,y)=̇ c

Schri� 3.5: also x(f(y,x)=̇ x > f(x,y)=̇ x) f(c,y)=̇ c

Skizze eines Beispiels (8)Schri� 4: zeige x(f(y,x)=̇ x > f(x,y)=̇ x) y =̇ c

Schri� 4.1 mit Ergebnissen von Schri� 2 und Schri� 3 zeige:x(f(y,x)=̇ x > f(x,y)=̇ x) (y =̇ f(c,y) > f(c,y)=̇ c)

Schri� 4.2: zeige(y =̇ f(c,y) > f(c,y)=̇ c) y =̇ c

Schri� 4.3: also x(f(y,x)=̇ x > f(x,y)=̇ x) y =̇ c

ZusammenfassungSyntax prädikatenlogischer Formeln

Terme, atomare Formeln, Formeln

SemantikInterpretationen und VariablenbelegungenModelle von Formel(menge)n oder nichtAllgemeingültigkeit

KalküleBeweisbarkeitHilbert-Kalkül korrekt und vollständig

Kapitel 13: Prädikatenlogik erster Stufe Thomas...

Documents

Logik Teil 2: Prädikatenlogik Grundlagen

Vortrag von Carla De Simoni Seminar: Neurokognition …neurowissenschaft.ch/.../Mehrsprachigkeit/Mehrsprachigkeit-Folien.pdf · Mehrsprachigkeit Vortrag von Carla De Simoni Seminar:

Digitale vs. Analoge Vorkurse Mathematikgraebe/Texte/Wlassak-20-Folien.pdf · Digitale vs. Analoge Brückenkurse Mathematik Mathematisches Institut, Abteilung Didaktik UNTERSTÜTZUNGSMAßNAHMEN

Umweltinformatik in einer vernetzten Welt - Rohrbacher Kreisrohrbacher-kreis.de/Dahlen-12/KFK-Folien.pdf · Soziologie Bioinformatik Wirtschaftsinformatik Proz. Informatik Angewandte

07.02.00GK Prolog: Prolog und Prädikatenlogik I 1 Prolog und Prädikatenlogik I Prolog Grundkurs WS 99/00 Christof Rumpf rumpf@uni-duesseldorf.de

Kryptographie mit Anwendungen - userpage.zedat.fu-berlin.deuserpage.zedat.fu-berlin.de/~ywing/Seminar/Folien.pdf · Kryptographie mit Anwendungen 27 Hashing Geburtstags–Attacke

Bachelor und Master Elektrotechnik - Uni Siegen...2013/07/15 · Anweisungen, erste Grundlagen der Objektorientierung) Aussagen- und Prädikatenlogik Rekursive Algorithmen *Dynamische

Die ersten 5 Schritte für den Start mit PHP auf IBM istatic.zend.com/topics/5steps-PHP-IBMi-DE-Folien.pdf · Qshell 30 57XXss1 System Openness Includes 13 57XXss1 IBM Portable Utilities

TightVNC - public.urz.uni-heidelberg.depublic.urz.uni-heidelberg.de/statistik/kurse/SPSS/folien.pdf · VNC server keller Password spss Einführung in SPSS

Folien.pdf (10121 KB)

Logik für Informatiker Wintersemester 2012/13 · Logik für Informatiker Wintersemester 2012/13 2 Prädikatenlogik In der Prädikatenlogik kann man die in der Aussagenlogik bereits

Algebraische Strukturen - math.uni-tuebingen.dekeilen/download/Lehre/AGSWS07/folien.pdf · Algebraische Strukturen ¨Ubungen ¨Ubungsschein Voraussetzungen Skript Motivation Strichcodes

Wirklichkeitskonstruktion im mediatisierten Wandelgraebe/Texte/Winter-14-Folien.pdf · Konstruktion, Wirklichkeit, Mediatisierung ... Einheit der Realität und Aktualität Wirklichkeit

Was passiert wenn Algorithmen nicht mehr das tun, was sie ...graebe/Texte/Kalloch-13-Folien.pdf · Data Mining * Exploration großer Datenmengen * Automatisierte Extraktion von inhärenten

Deklarative (= fortgeschrittene) Programmierung Vorlesung ...waldmann/edu/ss12/fop/folien/folien.pdf · Deklarative (= fortgeschrittene) Programmierung Vorlesung WS 2009, WS 2010,

Innere Medizin - Mobile Lecture Uni Bremenmlecture.uni-bremen.de/extern/alkohol/20050309_c/folien.pdf · Akute Pankreatitis? Diarrhoe Akut Ethanolwirkung Chronisch Ösophaguskarzinom

05 Aussagenlogik und Prädikatenlogik - Semantic Web Technologien WS 2011/12

Programmieren mit Prädikatenlogik

VO 2 interviews 2 eingnung - Persönliche Webseitena9806297/Files/Folien.pdf · Fakultät für Psychologie Arbeitsbereich Psychologische Diagnostik Test- und Beratungsstelle Interview

Rechnergestützte Beweissystemegumm/Lehre/WS08/RBS/R… · Arithmetik – Logik der Zahlen • Das Induktionsaxiom passt nicht in die Prädikatenlogik erster Stufe. Es wird über