47
Vorlesung Logik für Informatiker 13. Prädikatenlogik – Der Satz von Herbrand – Bernhard Beckert Universität Koblenz-Landau Sommersemester 2006 Logik für Informatiker, SS ’06 – p.1

Logik für Informatiker - KITbeckert/teaching/Logik-SS06/13Praedika... · Vorlesung Logik für Informatiker 13. Prädikatenlogik Œ Der Satz von Herbrand Œ Bernhard Beckert Universität

  • Upload
    dodiep

  • View
    232

  • Download
    0

Embed Size (px)

Citation preview

Page 1: Logik für Informatiker - KITbeckert/teaching/Logik-SS06/13Praedika... · Vorlesung Logik für Informatiker 13. Prädikatenlogik Œ Der Satz von Herbrand Œ Bernhard Beckert Universität

Vorlesung

Logik für Informatiker13. Prädikatenlogik

– Der Satz von Herbrand –

Bernhard Beckert

Universität Koblenz-Landau

Sommersemester 2006 Logik für Informatiker, SS ’06 – p.1

Page 2: Logik für Informatiker - KITbeckert/teaching/Logik-SS06/13Praedika... · Vorlesung Logik für Informatiker 13. Prädikatenlogik Œ Der Satz von Herbrand Œ Bernhard Beckert Universität

Semantische Bäume

Eine klassische Beweistechnik

Semantische Bäume

Logik für Informatiker, SS ’06 – p.2

Page 3: Logik für Informatiker - KITbeckert/teaching/Logik-SS06/13Praedika... · Vorlesung Logik für Informatiker 13. Prädikatenlogik Œ Der Satz von Herbrand Œ Bernhard Beckert Universität

Semantische Bäume

Definition: Semantischer Baum

Gegeben:〈p0, p1, . . .〉 beliebige Aufzählung einer aussagenl. Signatur Σ

Ein semantischer Baum über Σ ist markierter, binärer Baum mit:

1. Wurzel ist unmarkiert

2. Nachfolgerknoten der Wurzel mit p0 und ¬p0 markiert

3. Ist Knoten mit pi oder ¬pi markiert,sind Nachfolgerknoten mit pi+1 und ¬pi+1 markiert

Bemerkung

Semantische Bäume repräsentieren alle möglichen Σ-Interpretationen

Logik für Informatiker, SS ’06 – p.3

Page 4: Logik für Informatiker - KITbeckert/teaching/Logik-SS06/13Praedika... · Vorlesung Logik für Informatiker 13. Prädikatenlogik Œ Der Satz von Herbrand Œ Bernhard Beckert Universität

Semantische Bäume

Definition: Semantischer Baum

Gegeben:〈p0, p1, . . .〉 beliebige Aufzählung einer aussagenl. Signatur Σ

Ein semantischer Baum über Σ ist markierter, binärer Baum mit:

1. Wurzel ist unmarkiert

2. Nachfolgerknoten der Wurzel mit p0 und ¬p0 markiert

3. Ist Knoten mit pi oder ¬pi markiert,sind Nachfolgerknoten mit pi+1 und ¬pi+1 markiert

Bemerkung

Semantische Bäume repräsentieren alle möglichen Σ-Interpretationen

Logik für Informatiker, SS ’06 – p.3

Page 5: Logik für Informatiker - KITbeckert/teaching/Logik-SS06/13Praedika... · Vorlesung Logik für Informatiker 13. Prädikatenlogik Œ Der Satz von Herbrand Œ Bernhard Beckert Universität

Semantische Bäume

Definition: Semantischer Baum

Gegeben:〈p0, p1, . . .〉 beliebige Aufzählung einer aussagenl. Signatur Σ

Ein semantischer Baum über Σ ist markierter, binärer Baum mit:

1. Wurzel ist unmarkiert

2. Nachfolgerknoten der Wurzel mit p0 und ¬p0 markiert

3. Ist Knoten mit pi oder ¬pi markiert,sind Nachfolgerknoten mit pi+1 und ¬pi+1 markiert

Bemerkung

Semantische Bäume repräsentieren alle möglichen Σ-InterpretationenLogik für Informatiker, SS ’06 – p.3

Page 6: Logik für Informatiker - KITbeckert/teaching/Logik-SS06/13Praedika... · Vorlesung Logik für Informatiker 13. Prädikatenlogik Œ Der Satz von Herbrand Œ Bernhard Beckert Universität

Semantische Bäume

Beispiel

Σ = {p, q, r, s}

p

q

r

s ¬s

¬r

s ¬s

¬q

r

s ¬s

¬r

s ¬s

¬p

q

r

s ¬s

¬r

s ¬s

¬q

r

s ¬s

¬r

s ¬s

Logik für Informatiker, SS ’06 – p.4

Page 7: Logik für Informatiker - KITbeckert/teaching/Logik-SS06/13Praedika... · Vorlesung Logik für Informatiker 13. Prädikatenlogik Œ Der Satz von Herbrand Œ Bernhard Beckert Universität

Semantische Bäume

Beispiel

Σ = {p, q, r, s}

p

q

r

s ¬s

¬r

s ¬s

¬q

r

s ¬s

¬r

s ¬s

¬p

q

r

s ¬s

¬r

s ¬s

¬q

r

s ¬s

¬r

s ¬s

Logik für Informatiker, SS ’06 – p.4

Page 8: Logik für Informatiker - KITbeckert/teaching/Logik-SS06/13Praedika... · Vorlesung Logik für Informatiker 13. Prädikatenlogik Œ Der Satz von Herbrand Œ Bernhard Beckert Universität

Semantische Bäume

Definition: Widerlegungsmenge

Widerlegungsmenge eines Knotens ν eines semantischen Baums:

Alle Markierungen oberhalb und einschließlich von ν

Definition: Fehlschlagsknoten

Eine Klausel C schlägt fehl bei ν , falls für alle Literale L ∈ CMarkierung L in Widerlegungsmenge von ν

ν ist Fehlschlagsknoten für (aussagenlogische) Klauselmenge S, falls

1. ein C ∈ S bei ν fehlschlägt

2. kein C ∈ S oberhalb von ν fehlschlägt

Logik für Informatiker, SS ’06 – p.5

Page 9: Logik für Informatiker - KITbeckert/teaching/Logik-SS06/13Praedika... · Vorlesung Logik für Informatiker 13. Prädikatenlogik Œ Der Satz von Herbrand Œ Bernhard Beckert Universität

Semantische Bäume

Definition: Widerlegungsmenge

Widerlegungsmenge eines Knotens ν eines semantischen Baums:

Alle Markierungen oberhalb und einschließlich von ν

Definition: Fehlschlagsknoten

Eine Klausel C schlägt fehl bei ν , falls für alle Literale L ∈ CMarkierung L in Widerlegungsmenge von ν

ν ist Fehlschlagsknoten für (aussagenlogische) Klauselmenge S, falls

1. ein C ∈ S bei ν fehlschlägt

2. kein C ∈ S oberhalb von ν fehlschlägt

Logik für Informatiker, SS ’06 – p.5

Page 10: Logik für Informatiker - KITbeckert/teaching/Logik-SS06/13Praedika... · Vorlesung Logik für Informatiker 13. Prädikatenlogik Œ Der Satz von Herbrand Œ Bernhard Beckert Universität

Semantische Bäume

Definition: Inferenzknoten

Ein Inferenzknoten ist ein Knoten, dessen beide NachfolgerFehlschlagsknoten sind.

Definition: geschlossener semantischer Baum

Ein semantischer Baum ist geschlossen für S, fallsjeder Pfad Fehlschlagsknoten für S enthält

Logik für Informatiker, SS ’06 – p.6

Page 11: Logik für Informatiker - KITbeckert/teaching/Logik-SS06/13Praedika... · Vorlesung Logik für Informatiker 13. Prädikatenlogik Œ Der Satz von Herbrand Œ Bernhard Beckert Universität

Semantische Bäume

Definition: Inferenzknoten

Ein Inferenzknoten ist ein Knoten, dessen beide NachfolgerFehlschlagsknoten sind.

Definition: geschlossener semantischer Baum

Ein semantischer Baum ist geschlossen für S, fallsjeder Pfad Fehlschlagsknoten für S enthält

Logik für Informatiker, SS ’06 – p.6

Page 12: Logik für Informatiker - KITbeckert/teaching/Logik-SS06/13Praedika... · Vorlesung Logik für Informatiker 13. Prädikatenlogik Œ Der Satz von Herbrand Œ Bernhard Beckert Universität

Semantische Bäume

Beispiel

Σ = {p, q, r, s}

S = {{p}, {r,¬p, q}, {s,¬q},{¬q,¬s}, {¬q,¬r}, {¬r, q}}

p

q

r

s ¬s

¬r

s ¬s

¬q

r

s ¬s

¬r

s ¬s

¬p

q

r

s ¬s

¬r

s ¬s

¬q

r

s ¬s

¬r

s ¬s

Fehlschlagsknoten gerahmt Inferenzknoten unterstrichen

Logik für Informatiker, SS ’06 – p.7

Page 13: Logik für Informatiker - KITbeckert/teaching/Logik-SS06/13Praedika... · Vorlesung Logik für Informatiker 13. Prädikatenlogik Œ Der Satz von Herbrand Œ Bernhard Beckert Universität

Semantische Bäume

Beispiel

Σ = {p, q, r, s}

S = {{p}, {r,¬p, q}, {s,¬q},{¬q,¬s}, {¬q,¬r}, {¬r, q}}

p

q

r

s ¬s

¬r

s ¬s

¬q

r

s ¬s

¬r

s ¬s

¬p

q

r

s ¬s

¬r

s ¬s

¬q

r

s ¬s

¬r

s ¬s

Fehlschlagsknoten gerahmt Inferenzknoten unterstrichenLogik für Informatiker, SS ’06 – p.7

Page 14: Logik für Informatiker - KITbeckert/teaching/Logik-SS06/13Praedika... · Vorlesung Logik für Informatiker 13. Prädikatenlogik Œ Der Satz von Herbrand Œ Bernhard Beckert Universität

Semantische Bäume

Bemerkung

Die Pfade ohne Fehlschlagsknoten repräsentieren die Modelle von S

Lemma

Ist Klauselmenge S über Σ unerfüllbar,

so ist jeder semantische Baum über Σ geschlossen für S

Logik für Informatiker, SS ’06 – p.8

Page 15: Logik für Informatiker - KITbeckert/teaching/Logik-SS06/13Praedika... · Vorlesung Logik für Informatiker 13. Prädikatenlogik Œ Der Satz von Herbrand Œ Bernhard Beckert Universität

Semantische Bäume

Beweis

Annahme: Es gibt semantischen Baum, der nicht für S geschlossen ist

Sei π beliebiger Pfad ohne Fehlschlagsknoten für S

Jedes p ∈ Σ genau einmal entweder positiv oder negativunter den Markierungen M von π

M induziert Modell I von S vermittels

I(p) =

W p ∈ M

F sonst

Widerspruch zur Unerfüllbarkeit

Logik für Informatiker, SS ’06 – p.9

Page 16: Logik für Informatiker - KITbeckert/teaching/Logik-SS06/13Praedika... · Vorlesung Logik für Informatiker 13. Prädikatenlogik Œ Der Satz von Herbrand Œ Bernhard Beckert Universität

Semantische Bäume

Theorem (Vollständigkeit aussagenlogischer Rosolution)

Ist S eine unerfüllbare AL Klauselmenge,

dann gilt S `RA 2

Logik für Informatiker, SS ’06 – p.10

Page 17: Logik für Informatiker - KITbeckert/teaching/Logik-SS06/13Praedika... · Vorlesung Logik für Informatiker 13. Prädikatenlogik Œ Der Satz von Herbrand Œ Bernhard Beckert Universität

Semantische Bäume

(Alternativer) Beweis mit semantischen Bäumen

Sei ST geschlossener semantischer Baum für S nach Lemma

Jeder geschlossene semantische Baum hat Inferenzknoten

Sei ν ein Inferenzknoten maximaler Tiefe in ST

Nachfolger von ν sind Fehlschlagsknoten; seien mit p und ¬p markiert

C, D ∈ S die Klauseln, die bei Nachfolgern von ν fehlschlagen

C = {¬p} ∪ C′ und D = {p} ∪ D′

C und D resolvieren zu E = C′ ∪ D′

E schlägt bei ν fehl, da Komplemente aller Literale in C ∪ D außerp und ¬p schon in Widerlegungsmenge von ν

S ∪ {E} hat geschlossenen semantischen Baum mit wenigerFehlschlagsknoten als ST

Logik für Informatiker, SS ’06 – p.11

Page 18: Logik für Informatiker - KITbeckert/teaching/Logik-SS06/13Praedika... · Vorlesung Logik für Informatiker 13. Prädikatenlogik Œ Der Satz von Herbrand Œ Bernhard Beckert Universität

Semantische Bäume

(Alternativer) Beweis mit semantischen Bäumen (Forts.)

Geschlossener semantischer Baum hat endlich vieleFehlschlagsknoten

Also erreicht man nach endlich vielen Schritten eine Klauselmengemit einzigem Fehlschlagsknoten Wurzel

Nur 2 kann für diesen semantischen Baum fehlschlagen

Also 2 in dieser Klauselmenge enthalten

Logik für Informatiker, SS ’06 – p.12

Page 19: Logik für Informatiker - KITbeckert/teaching/Logik-SS06/13Praedika... · Vorlesung Logik für Informatiker 13. Prädikatenlogik Œ Der Satz von Herbrand Œ Bernhard Beckert Universität

Semantische Bäume

Bemerkungen

• Beweis ist konstruktiv

• Resolutionsableitung aus Beweis aber i.a. nicht der kürzeste

• Länge abhängig von gewählter Ordnung auf Σ

• Kann sogar exponentiell länger werden als bei günstiger Ordnung

Logik für Informatiker, SS ’06 – p.13

Page 20: Logik für Informatiker - KITbeckert/teaching/Logik-SS06/13Praedika... · Vorlesung Logik für Informatiker 13. Prädikatenlogik Œ Der Satz von Herbrand Œ Bernhard Beckert Universität

Semantische Bäume

Bemerkungen

• Beweis ist konstruktiv

• Resolutionsableitung aus Beweis aber i.a. nicht der kürzeste

• Länge abhängig von gewählter Ordnung auf Σ

• Kann sogar exponentiell länger werden als bei günstiger Ordnung

Logik für Informatiker, SS ’06 – p.13

Page 21: Logik für Informatiker - KITbeckert/teaching/Logik-SS06/13Praedika... · Vorlesung Logik für Informatiker 13. Prädikatenlogik Œ Der Satz von Herbrand Œ Bernhard Beckert Universität

Semantische Bäume

Bemerkungen

• Beweis ist konstruktiv

• Resolutionsableitung aus Beweis aber i.a. nicht der kürzeste

• Länge abhängig von gewählter Ordnung auf Σ

• Kann sogar exponentiell länger werden als bei günstiger Ordnung

Logik für Informatiker, SS ’06 – p.13

Page 22: Logik für Informatiker - KITbeckert/teaching/Logik-SS06/13Praedika... · Vorlesung Logik für Informatiker 13. Prädikatenlogik Œ Der Satz von Herbrand Œ Bernhard Beckert Universität

Semantische Bäume

Bemerkungen

• Beweis ist konstruktiv

• Resolutionsableitung aus Beweis aber i.a. nicht der kürzeste

• Länge abhängig von gewählter Ordnung auf Σ

• Kann sogar exponentiell länger werden als bei günstiger Ordnung

Logik für Informatiker, SS ’06 – p.13

Page 23: Logik für Informatiker - KITbeckert/teaching/Logik-SS06/13Praedika... · Vorlesung Logik für Informatiker 13. Prädikatenlogik Œ Der Satz von Herbrand Œ Bernhard Beckert Universität

Herbrand-Modelle

Ab jetzt wieder Prädikatenlogik . . .

Annahme

Es gibt mindestens einen variablenfreien Term, d.h.es gibt mindestens eine Konstante

Definition: Herbrand-Modell

Modell

M = 〈U, I〉 mit

U die Menge aller Grundterme (variablenfreie Terme)

I( f )(t1, . . . , tn) = f (t1, . . . , tn)

für alle Funktionssymbole f , Grundterme t1, . . . , tn

Logik für Informatiker, SS ’06 – p.14

Page 24: Logik für Informatiker - KITbeckert/teaching/Logik-SS06/13Praedika... · Vorlesung Logik für Informatiker 13. Prädikatenlogik Œ Der Satz von Herbrand Œ Bernhard Beckert Universität

Herbrand-Modelle

Ab jetzt wieder Prädikatenlogik . . .

Annahme

Es gibt mindestens einen variablenfreien Term, d.h.es gibt mindestens eine Konstante

Definition: Herbrand-Modell

Modell

M = 〈U, I〉 mit

U die Menge aller Grundterme (variablenfreie Terme)

I( f )(t1, . . . , tn) = f (t1, . . . , tn)

für alle Funktionssymbole f , Grundterme t1, . . . , tn

Logik für Informatiker, SS ’06 – p.14

Page 25: Logik für Informatiker - KITbeckert/teaching/Logik-SS06/13Praedika... · Vorlesung Logik für Informatiker 13. Prädikatenlogik Œ Der Satz von Herbrand Œ Bernhard Beckert Universität

Herbrand-Modelle

Ab jetzt wieder Prädikatenlogik . . .

Annahme

Es gibt mindestens einen variablenfreien Term, d.h.es gibt mindestens eine Konstante

Definition: Herbrand-Modell

Modell

M = 〈U, I〉 mit

U die Menge aller Grundterme (variablenfreie Terme)

I( f )(t1, . . . , tn) = f (t1, . . . , tn)

für alle Funktionssymbole f , Grundterme t1, . . . , tn Logik für Informatiker, SS ’06 – p.14

Page 26: Logik für Informatiker - KITbeckert/teaching/Logik-SS06/13Praedika... · Vorlesung Logik für Informatiker 13. Prädikatenlogik Œ Der Satz von Herbrand Œ Bernhard Beckert Universität

Herbrand-Modelle

Bemerkung

Für feste Signatur sind alle Herbrand-Modelle gleich

bis auf Interpretation der Prädikate

Logik für Informatiker, SS ’06 – p.15

Page 27: Logik für Informatiker - KITbeckert/teaching/Logik-SS06/13Praedika... · Vorlesung Logik für Informatiker 13. Prädikatenlogik Œ Der Satz von Herbrand Œ Bernhard Beckert Universität

Herbrand-Modelle

Theorem

Jede erfüllbare Klauselmenge hat ein Herbrand-Modell

Zum Beweis

Konstruiere aus beliebigem Modell ein Herbrand-Modell vermittels

I∗(p)(t) = I(p)(I(t))

Logik für Informatiker, SS ’06 – p.16

Page 28: Logik für Informatiker - KITbeckert/teaching/Logik-SS06/13Praedika... · Vorlesung Logik für Informatiker 13. Prädikatenlogik Œ Der Satz von Herbrand Œ Bernhard Beckert Universität

Herbrand-Modelle

Theorem

Jede erfüllbare Klauselmenge hat ein Herbrand-Modell

Zum Beweis

Konstruiere aus beliebigem Modell ein Herbrand-Modell vermittels

I∗(p)(t) = I(p)(I(t))

Logik für Informatiker, SS ’06 – p.16

Page 29: Logik für Informatiker - KITbeckert/teaching/Logik-SS06/13Praedika... · Vorlesung Logik für Informatiker 13. Prädikatenlogik Œ Der Satz von Herbrand Œ Bernhard Beckert Universität

Prädikatenlogische semantische Bäume

Definition: prädikatenlogischer Semantischer Baum

Semantischer Baum für prädikatenlogische Signatur Σ ist(aussangenlogischer) semantischer Baum über

ΣAL = Menge aller Grund-Atome über Σ

Definition: Fehlschlagsknoten (prädikatenlogisch)

Eine prädikatenlogische Klausel C schlägt fehl bei ν ,

falls es eine Grundinstanz von C gibt,

die (aussagenlogisch) bei ν fehlschlägt

Logik für Informatiker, SS ’06 – p.17

Page 30: Logik für Informatiker - KITbeckert/teaching/Logik-SS06/13Praedika... · Vorlesung Logik für Informatiker 13. Prädikatenlogik Œ Der Satz von Herbrand Œ Bernhard Beckert Universität

Prädikatenlogische semantische Bäume

Definition: prädikatenlogischer Semantischer Baum

Semantischer Baum für prädikatenlogische Signatur Σ ist(aussangenlogischer) semantischer Baum über

ΣAL = Menge aller Grund-Atome über Σ

Definition: Fehlschlagsknoten (prädikatenlogisch)

Eine prädikatenlogische Klausel C schlägt fehl bei ν ,

falls es eine Grundinstanz von C gibt,

die (aussagenlogisch) bei ν fehlschlägt

Logik für Informatiker, SS ’06 – p.17

Page 31: Logik für Informatiker - KITbeckert/teaching/Logik-SS06/13Praedika... · Vorlesung Logik für Informatiker 13. Prädikatenlogik Œ Der Satz von Herbrand Œ Bernhard Beckert Universität

Prädikatenlogische semantische Bäume

Auch dann gilt immer noch(Beweis wie in der aussagenlogischen Variante):

Lemma

Ist Klauselmenge S über Σ unerfüllbar,

so ist jeder semantische Baum über Σ geschlossen für S

Logik für Informatiker, SS ’06 – p.18

Page 32: Logik für Informatiker - KITbeckert/teaching/Logik-SS06/13Praedika... · Vorlesung Logik für Informatiker 13. Prädikatenlogik Œ Der Satz von Herbrand Œ Bernhard Beckert Universität

Prädikatenlogische semantische Bäume

Lemma

Ein geschlossener semantischer Baum hat einen endlichen

geschlossenen Teilbaum

Beweis:

Mit Königs Lemma:

Jeder endlich verzweigende Baum,in dem jeder Ast endliche Länge hat,ist endlich.

Logik für Informatiker, SS ’06 – p.19

Page 33: Logik für Informatiker - KITbeckert/teaching/Logik-SS06/13Praedika... · Vorlesung Logik für Informatiker 13. Prädikatenlogik Œ Der Satz von Herbrand Œ Bernhard Beckert Universität

Prädikatenlogische semantische Bäume

Lemma

Ein geschlossener semantischer Baum hat einen endlichen

geschlossenen Teilbaum

Beweis:

Mit Königs Lemma:

Jeder endlich verzweigende Baum,in dem jeder Ast endliche Länge hat,ist endlich.

Logik für Informatiker, SS ’06 – p.19

Page 34: Logik für Informatiker - KITbeckert/teaching/Logik-SS06/13Praedika... · Vorlesung Logik für Informatiker 13. Prädikatenlogik Œ Der Satz von Herbrand Œ Bernhard Beckert Universität

Satz von Herbrand

Aus den beiden Lemmas folgt:

Satz von Herbrand

Ist C eine unerfüllbare (prädikatenlogische) Klauselmenge, danngibt es eine endliche Menge von Grund-Instanzen von Klauseln in C,die unerfüllbar ist.

Konsequenzen

Unerfüllbarkeit kann in endlich vielen Schritten nachgewiesen werden

Vollständigkeit der prädikatenlogischen Resolution

Kompaktheitssatz für die Prädikatenlogik

Logik für Informatiker, SS ’06 – p.20

Page 35: Logik für Informatiker - KITbeckert/teaching/Logik-SS06/13Praedika... · Vorlesung Logik für Informatiker 13. Prädikatenlogik Œ Der Satz von Herbrand Œ Bernhard Beckert Universität

Satz von Herbrand

Aus den beiden Lemmas folgt:

Satz von Herbrand

Ist C eine unerfüllbare (prädikatenlogische) Klauselmenge, danngibt es eine endliche Menge von Grund-Instanzen von Klauseln in C,die unerfüllbar ist.

Konsequenzen

Unerfüllbarkeit kann in endlich vielen Schritten nachgewiesen werden

Vollständigkeit der prädikatenlogischen Resolution

Kompaktheitssatz für die Prädikatenlogik

Logik für Informatiker, SS ’06 – p.20

Page 36: Logik für Informatiker - KITbeckert/teaching/Logik-SS06/13Praedika... · Vorlesung Logik für Informatiker 13. Prädikatenlogik Œ Der Satz von Herbrand Œ Bernhard Beckert Universität

Satz von Herbrand

Aus den beiden Lemmas folgt:

Satz von Herbrand

Ist C eine unerfüllbare (prädikatenlogische) Klauselmenge, danngibt es eine endliche Menge von Grund-Instanzen von Klauseln in C,die unerfüllbar ist.

Konsequenzen

Unerfüllbarkeit kann in endlich vielen Schritten nachgewiesen werden

Vollständigkeit der prädikatenlogischen Resolution

Kompaktheitssatz für die Prädikatenlogik

Logik für Informatiker, SS ’06 – p.20

Page 37: Logik für Informatiker - KITbeckert/teaching/Logik-SS06/13Praedika... · Vorlesung Logik für Informatiker 13. Prädikatenlogik Œ Der Satz von Herbrand Œ Bernhard Beckert Universität

Satz von Herbrand

Aus den beiden Lemmas folgt:

Satz von Herbrand

Ist C eine unerfüllbare (prädikatenlogische) Klauselmenge, danngibt es eine endliche Menge von Grund-Instanzen von Klauseln in C,die unerfüllbar ist.

Konsequenzen

Unerfüllbarkeit kann in endlich vielen Schritten nachgewiesen werden

Vollständigkeit der prädikatenlogischen Resolution

Kompaktheitssatz für die PrädikatenlogikLogik für Informatiker, SS ’06 – p.20

Page 38: Logik für Informatiker - KITbeckert/teaching/Logik-SS06/13Praedika... · Vorlesung Logik für Informatiker 13. Prädikatenlogik Œ Der Satz von Herbrand Œ Bernhard Beckert Universität

Kompaktheitssatz

Theorem (Kompaktheitssatz)

Eine (unendliche) Menge prädikatenlogischer Formeln

ist genau dann erfüllbar,

wenn jede ihrer endlichen Teilmengen erfüllbar ist

Korollar (beispielsweise)

In Prädikatenlogik ist nicht formalisierbar:

Endlichkeit des (Modell-)Universums

Transitiver Abschluss einer Relation

Logik für Informatiker, SS ’06 – p.21

Page 39: Logik für Informatiker - KITbeckert/teaching/Logik-SS06/13Praedika... · Vorlesung Logik für Informatiker 13. Prädikatenlogik Œ Der Satz von Herbrand Œ Bernhard Beckert Universität

Kompaktheitssatz

Theorem (Kompaktheitssatz)

Eine (unendliche) Menge prädikatenlogischer Formeln

ist genau dann erfüllbar,

wenn jede ihrer endlichen Teilmengen erfüllbar ist

Korollar (beispielsweise)

In Prädikatenlogik ist nicht formalisierbar:

Endlichkeit des (Modell-)Universums

Transitiver Abschluss einer Relation

Logik für Informatiker, SS ’06 – p.21

Page 40: Logik für Informatiker - KITbeckert/teaching/Logik-SS06/13Praedika... · Vorlesung Logik für Informatiker 13. Prädikatenlogik Œ Der Satz von Herbrand Œ Bernhard Beckert Universität

Zusammenfassung: Der Satz von Herbrand

• Aussagenlogischer semantischer Baum

• Widerlegungsmenge, Fehlschlagsknoten, Inferenzknoten

• Geschlossener semantischer Baum

• Alternativer Beweis für Vollständigkeitaussagenlogischer Resolution

• Herbrand-Modelle

• Prädikatenlogischer semantischer Baum

• Satz von Herbrand

• Kompaktheitssatz

Logik für Informatiker, SS ’06 – p.22

Page 41: Logik für Informatiker - KITbeckert/teaching/Logik-SS06/13Praedika... · Vorlesung Logik für Informatiker 13. Prädikatenlogik Œ Der Satz von Herbrand Œ Bernhard Beckert Universität

Zusammenfassung: Der Satz von Herbrand

• Aussagenlogischer semantischer Baum

• Widerlegungsmenge, Fehlschlagsknoten, Inferenzknoten

• Geschlossener semantischer Baum

• Alternativer Beweis für Vollständigkeitaussagenlogischer Resolution

• Herbrand-Modelle

• Prädikatenlogischer semantischer Baum

• Satz von Herbrand

• Kompaktheitssatz

Logik für Informatiker, SS ’06 – p.22

Page 42: Logik für Informatiker - KITbeckert/teaching/Logik-SS06/13Praedika... · Vorlesung Logik für Informatiker 13. Prädikatenlogik Œ Der Satz von Herbrand Œ Bernhard Beckert Universität

Zusammenfassung: Der Satz von Herbrand

• Aussagenlogischer semantischer Baum

• Widerlegungsmenge, Fehlschlagsknoten, Inferenzknoten

• Geschlossener semantischer Baum

• Alternativer Beweis für Vollständigkeitaussagenlogischer Resolution

• Herbrand-Modelle

• Prädikatenlogischer semantischer Baum

• Satz von Herbrand

• Kompaktheitssatz

Logik für Informatiker, SS ’06 – p.22

Page 43: Logik für Informatiker - KITbeckert/teaching/Logik-SS06/13Praedika... · Vorlesung Logik für Informatiker 13. Prädikatenlogik Œ Der Satz von Herbrand Œ Bernhard Beckert Universität

Zusammenfassung: Der Satz von Herbrand

• Aussagenlogischer semantischer Baum

• Widerlegungsmenge, Fehlschlagsknoten, Inferenzknoten

• Geschlossener semantischer Baum

• Alternativer Beweis für Vollständigkeitaussagenlogischer Resolution

• Herbrand-Modelle

• Prädikatenlogischer semantischer Baum

• Satz von Herbrand

• Kompaktheitssatz

Logik für Informatiker, SS ’06 – p.22

Page 44: Logik für Informatiker - KITbeckert/teaching/Logik-SS06/13Praedika... · Vorlesung Logik für Informatiker 13. Prädikatenlogik Œ Der Satz von Herbrand Œ Bernhard Beckert Universität

Zusammenfassung: Der Satz von Herbrand

• Aussagenlogischer semantischer Baum

• Widerlegungsmenge, Fehlschlagsknoten, Inferenzknoten

• Geschlossener semantischer Baum

• Alternativer Beweis für Vollständigkeitaussagenlogischer Resolution

• Herbrand-Modelle

• Prädikatenlogischer semantischer Baum

• Satz von Herbrand

• Kompaktheitssatz

Logik für Informatiker, SS ’06 – p.22

Page 45: Logik für Informatiker - KITbeckert/teaching/Logik-SS06/13Praedika... · Vorlesung Logik für Informatiker 13. Prädikatenlogik Œ Der Satz von Herbrand Œ Bernhard Beckert Universität

Zusammenfassung: Der Satz von Herbrand

• Aussagenlogischer semantischer Baum

• Widerlegungsmenge, Fehlschlagsknoten, Inferenzknoten

• Geschlossener semantischer Baum

• Alternativer Beweis für Vollständigkeitaussagenlogischer Resolution

• Herbrand-Modelle

• Prädikatenlogischer semantischer Baum

• Satz von Herbrand

• Kompaktheitssatz

Logik für Informatiker, SS ’06 – p.22

Page 46: Logik für Informatiker - KITbeckert/teaching/Logik-SS06/13Praedika... · Vorlesung Logik für Informatiker 13. Prädikatenlogik Œ Der Satz von Herbrand Œ Bernhard Beckert Universität

Zusammenfassung: Der Satz von Herbrand

• Aussagenlogischer semantischer Baum

• Widerlegungsmenge, Fehlschlagsknoten, Inferenzknoten

• Geschlossener semantischer Baum

• Alternativer Beweis für Vollständigkeitaussagenlogischer Resolution

• Herbrand-Modelle

• Prädikatenlogischer semantischer Baum

• Satz von Herbrand

• Kompaktheitssatz

Logik für Informatiker, SS ’06 – p.22

Page 47: Logik für Informatiker - KITbeckert/teaching/Logik-SS06/13Praedika... · Vorlesung Logik für Informatiker 13. Prädikatenlogik Œ Der Satz von Herbrand Œ Bernhard Beckert Universität

Zusammenfassung: Der Satz von Herbrand

• Aussagenlogischer semantischer Baum

• Widerlegungsmenge, Fehlschlagsknoten, Inferenzknoten

• Geschlossener semantischer Baum

• Alternativer Beweis für Vollständigkeitaussagenlogischer Resolution

• Herbrand-Modelle

• Prädikatenlogischer semantischer Baum

• Satz von Herbrand

• Kompaktheitssatz

Logik für Informatiker, SS ’06 – p.22