Next: Prädikatenlogik Up: Logik Previous: Syntax der Aussagenlogik

Semantik der Aussagenlogik

Chronologisch	Alphabetisch
Semantik Aussagenlogik  Wahrheitswerte  Belegung  Interpretation  Folgerbarkeit  Kalkül  Logische Axiome  Ableitbarkeit  Modus Ponens  Korrektheit  Vollständigkeit  Resolution  Resolutionslemma  Resolvent  Resolutionssatz Aussagenlogik  Konsistenz  Vollständigkeit  Modell  Minimales Modell  Modell-Lemma  Erfüllbarkeit  Tautologie	Ableitbarkeit Belegung  Erfüllbarkeit Folgerbarkeit  Interpretation Kalkül  Konsistenz Korrektheit  Logische Axiome Minimales Modell Modell  Modell-Lemma  Modus Ponens Resolution  Resolutionslemma  Resolutionssatz Aussagenlogik  Resolvent  Semantik Aussagenlogik Tautologie Vollständigkeit Vollständigkeit Wahrheitswerte

Definition 1.8: Semantik der Aussagenlogik

Die Elemente der Menge {0,1} heißen Wahrheitswerte. Eine Belegung oder Interpretation ist eine Funktion

. Man erweitert  zu einer Funktion  wie folgt:

1. Für jede atomare Formel  ist  .
2. 
3. 
4. 

Definition 1.9: Folgerbarkeit

Sei S eine Signatur, A eine Formelmenge und F eine Formel, also  und  . Aus A folgt F, kurz  , falls für alle Interpretationen oder Belegungen  gilt: Falls  , dann  .

Kalkül

Ein Kalkül ist eine Sammlung rein ``mechanisch`` anzuwendender syntaktischer Umformungsregeln.

Der Begriff der Ableitbarkeit steht hier im Vordergrund. Die Ableitbarkeit stützt sich auf die Syntax, die Folgerbarkeit nimmt Bezug zur Semantik der Aussagenlogik. Eine Formel F ist aus einer Formelmenge A ableitbar, falls man F aus A sowie gewissen logischen Axiomen mittels einer Schlußfolgerungsregel, dem sog. Modus Ponens, erhalten kann.

Definition 1.10: Logische Axiome

Sei S eine Signatur und  .



heißt Menge der logischen Axiome zur Signatur S.

Definition 1.11: Ableitbarkeit

Sei S eine Signatur,  und  . F ist aus A ableitbar, kurz  , falls es eine Folge  in  gibt mit folgenden Eigenschaften:

1. 
2. Für alle i = 1,...n gilt:  oder es gibt j < i und k < i mit  .

Eine solche Folge  heißt Ableitung von F aus A.

Wie kommt eine Ableitung von F aus A zustande?

• Man darf eine schon erzeugte Ableitungsfolge um ein logisches Axiom sowie um eine Formel aus A verlängern.
• Kommt in einer schon erzeugten Ableitungsfolge eine Formel G und eine Formel  vor, so darf die Folge um die Formel H verlängert werden. Diese Art des Verlängerns heißt Modus Ponens.

Mit dem Begriff der Ableitbarkeit hat man den Gehalt des Begriffs der Folgerbarkeit vollständig erfaßt:

Satz 1.2: Korrektheit

Sei S eine Signatur,  . Dann gilt: Wenn  , dann  .

Satz 1.3: Vollständigkeit

Sei S eine Signatur,  . Dann gilt: Wenn  , dann  .

Resolution

Die Resolution ist eine einfach anzuwendende syntaktische Umformungsregel. Hierbei wird in einem Schritt aus zwei Formeln, sofern sie die Voraussetzungen für die Anwendung der Resolutionsregel erfüllen, eine dritte Formel generiert, die dann als Eingabe in weitere Resolutionsschritte dienen kann.

Definition 1.12: Resolution

Seien ,  und R Klauseln. Dann heißt R Resolvent von  und  , falls es ein Literal L gibt mit  und  und R die Form hat:

Hierbei ist  definiert als

Man kann diesen Sachverhalt in folgendem Diagramm darstellen:

...

Satz 1.4: Resolutionslemma

Sei F eine Formel in KNF, dargestellt als Klauselmenge. Ferner sei R ein Resolvent zweier Klauseln  und  in F. Dann sind F und  äquivalent.

Definition 1.13: Resolvent

Sei F eine Klauselmenge. Dann ist Res(F) definiert als

Außerdem setze:

und schließlich sei

Satz 1.5: Resolutionssatz der Aussagenlogik

Eine Klauselmenge F ist unerfüllbar, genau dann, wenn 

Definition 1.14: Konsistenz

Sei S eine Signatur und  . A heißt konsistent, falls es keine Formel  gibt mit  und  .

Definition 1.15: Vollständigkeit

Sei S eine Signatur und  . A heißt vollständig, falls für jedes  gilt:  oder  .

Definition 1.16: Modell

Eine Interpretation heißt ein Modell von A, wenn  , d.h. jede Formel  gilt unter der Belegung bzw. Interpretation  . Man schreibt auch:  ,  ist ein Modell von A.

Falls  für eine Formel  , so schreibt man:  , d.h.  ist kein Modell für G.

Definition 1.17: Minimales Modell

Eine Interpretation heißt ein minimales Modell von A, wenn  ein Modell von A ist und es keine Interpretation  gibt, die auch ein Modell von A ist und  . Man schreibt für das minimale Modell  .

Satz 1.6: Modell-Lemma

Sei S eine Signatur. Dann gilt: Zu jeder konsistenten Formelmenge A gibt es ein Modell von A.

Definition 1.18: Erfüllbarkeit

Eine Formel F heißt erfüllbar, falls F mindestens ein Modell besitzt, andernfalls heißt F unerfüllbar.

Eine Menge von Formeln A heißt erfüllbar, falls es eine Belegung  gibt, die für jede Formel in A ein Modell ist.

Definition 1.19: Tautologie

Eine Formel F heißt gültig (oder Tautologie), falls jede zu F passende Belegung ein Modell für F ist.

Schreibweise:  , falls F eine Tautologie ist und  , falls F keine Tautologie ist.

  
Next: Prädikatenlogik Up: Logik Previous: Syntax der Aussagenlogik
Uschi Robers