aussagenlogik

Satz dem wahr oder falsch zugeordnet werden kann

Aussagenlogische Formeln sind abgeschlossen gegenüber Konjunktion, Disjunktion, Implikation und Negation.

Atomare Formeln sind Formeln

Interpretation (Bewertung) ist eine Abbildung der atomaren Aussage auf die Wahrheitswerte 1 (wahr) und 0 (falsch)

• im Kontext der Wissensverarbeitung ist die logische Implikation insbesondere von Bedeutung

• ex falso quodlibet

Negation

vor

Konjunktion

vor

Disjunktion

Interpretation durch sukzessives Auswerten der Teilformeln unter Berücksichtigung der Vorrangsregeln

Interpretation I, für die Formel F den Wahrheitswert 1 annimmt

(Interpretation erfüllt die Formel F)

Formel F erfüllbar, wenn mindestens ein Modell existiert

Formel, die für von jeder Interpretation erfüllt wird

(allgemeingültig)

(charakterisiert Gesetzmäßigkeit)

Formel ohne Modell

(auch Kontradiktion)

Formel ist genau dann Tautologie, wenn ihre Negation unerfüllbar ist

Übergang von F zu nicht F kann durch Spiegelungsprinzip veranschaulicht werden

• eine allgemeingültige Formel wird zu unerfüllbaren Formel und umgekehrt

• erfüllbare aber nicht allgemeingültige Formel wird wieder zu erfüllbarer aber nicht allgemeingültiger Formel

Zwei Formeln F,G semantisch äquivalent, wenn I(F)=I(G) für alle Interpretationen I

F und G äquivalent, wenn alle Modelle von F auch Modelle von G sind und umgekehrt

• syntaktisch unterschiedliche Formeln, die identische Wahrheitswerte haben

• bei jeder Bewertung/Interpretation der Formeln ergibt sich derselbe Wahrweitswert

  
  

Bedeutung

• standartisierte, möglichst einfache Darstellung von Formeln wichtig

  • Wissensverarbeitung, Schaltkreisminimierung

• In diese Form muss jede Formel überführbar sein

• z.B. DNF, KNF

Literal: atomare Formel oder die Negation einer atomaren Formel

KNF: Konjunktive Normalform

Konjunktion von Disjunktionen von Literalen

DNF: Disjunktive Normalform

Disjunktion von Konjunktion von Literalen

1. Implikation ersetzen und doppelte Negationen

2. DeMorgan

3. KNF oder DNF

Formel G heist semantische Folgerung der Formelmenge M, wenn jedes Modell von M auch ein Modell von G ist

M |= G

• Aus A und A -> B folgt B

• 
  

• NAND, NOR besonders wichtig für Schaltungsentwurf

  • reicht NOR-Operation elektronisch zu realisieren, alle anderen logischen Operationen auf NOR zurückführbar

• minimal vollständig:

  • {NICHT, UND}, {NICHT, ODER}, {nand}, {nor}

• vollständig, aber nicht minimal:

  • {NICHT, UND, ODER}

Zusammenhang von semantischer Folgerung und der Unerfüllbarkeit

Formelmenge M={ F1, … , Fn },

FM = F1 ^ … ^ Fn und F Formeln,

dann ist äquivalent:

1. M |= F

2. M = M u {F} bzw. (FM = FM ^ F)

3. (FM ^ -F) ist unerfüllbar

4. (FM => F) ist Tautologie

Äquivalenz:

• Folgerbarkeit aus Modelluntersuchung

• Unerfüllbarkeitstest

• Tautologietest

Formel F ist Hornformel, falls F in KNF und jedes Disjunktionsglied höchstens ein positives Literal enthält

sehr effizienter Unerfüllbarkeitstest für Hornformeln

Stoppt nach n Markierungsschritten, wobei n die Anzahl der atomaren Formeln in F sind

Menge von Literalen, die deren Disjunktion entspricht

{} ist die leere Klausel - Wahrheitswert 0

K1 und K2 Klauseln und A Atom, das in der einen positiv und in der anderen negativ enthalten ist

Resolvente ist Klausel aus der Vereinigung von K1 und K2 ohne das Atom

M Klauselmenge

K1 und K2 Klauseln aus M

R Resolvente von K1 und K2

Dann gilt:

M |= R

M genau dann erfüllbar, wenn M vereinigt mit R erfüllbar ist

Klauselmenge M ist unerfüllbar genau dann, wenn die leere Klausel mit einer endlichen Anzahl von Resolutionsschritten aus M abgeleitet werden kann.