Aussagenlogik: Syntax

Aussagenlogik: Syntax
A ::= X | (A ∧ A) | (A ∨ A) | (¬ A) | (A ⇒ A) | (A ⇔ A) | 0 | 1
Prioritätsreihenfolge : ¬, ∧, ∨, ⇒, ⇔.
A ∧ B:
A ∨ B:
A ⇒ B:
A ⇔ B:
¬A:
A
A
KI, SS
Konjunktion (Verundung).
Disjunktion (Veroderung).
Implikation .
Äquivalenz.
negierte Formel.
Atom, falls A eine Variable ist.
Literal, falls A Atom oder negiertes Atom.
06, F olien 3(1), Seite 1
Aussagenlogik: Semantik
Zunächst pro Operation ¬, ∧, ∨, ⇒, ⇔
eine Funktion fop gemäß folgender Tabelle.
1
1
0
0
KI, SS
06, F olien 3(1), Seite 2
1
0
1
0
∧
1
0
0
0
∨
1
1
1
0
⇒
1
0
1
1
N OR
0
0
0
1
N AN D
0
1
1
1
⇔
1
0
0
1
XOR
0
1
1
0
Interpretation
Definition
Eine Interpretation I ist
eine Funktion I : {aussagenlogische Variablen} → {0, 1}.
Eine Interpretation I liefert Wahrheitswert von Aussagen:
• I(0) := 0, I(1) := 1
• I(¬A) := f¬(I(A))
• I(A op B) := fop(I(A), I(B)), wobei op ∈ {∧, ∨, ⇒, ⇔ . . .}
I(F ) = 1 wird notiert als I |= F .
Sprechweisen für I |= F :
I ist ein Modell für F ,
KI, SS
06, F olien 3(1), Seite 3
F gilt in I,
I macht F wahr
Definition: Tautologie usw.
• A ist eine Tautologie (Satz, allgemeingültig) gdw. für alle Interpretationen I gilt: I |= A.
• A ist ein Widerspruch (widersprüchlich, unerfüllbar) gdw. für alle
Interpretationen I gilt: I(A) = 0.
• A ist erfüllbar (konsistent) gdw. es eine Interpretationen I gibt mit:
I |= A.
• ein Modell für eine Formel A ist eine Interpretation I mit I(A) = 1.
KI, SS
06, F olien 3(1), Seite 4
Beispiele für Tautologie usw.
• X ∨ ¬X ist eine Tautologie.
• (X ⇒ Y ) ⇒ ((Y ⇒ Z) ⇒ (X ⇒ Z)) ist eine Tautologie.
• X ∧ ¬X ist ein Widerspruch.
• X ∨ Y ist erfüllbar.
• I mit I(X) = 1, I(Y ) = 0 ist ein Modell für X ∧ ¬Y
KI, SS
06, F olien 3(1), Seite 5
Äquivalenzen von Aussagen
F, G sind äquivalent (F ∼ G),
gdw.
F ⇔ G ist eine Tautologie ist.
KI, SS
06, F olien 3(1), Seite 6
Tautologien/ Widersprüche: Komplexität
Satz
• Die Frage “Ist A Tautologie“ ist entscheidbar
• Die Frage “Ist A erfüllbar?“ ist N P-vollständig.
• Die Frage “Ist A Tautologie (Widerspruch)?“ ist
co-N P-vollständig.
Für N P-vollständig und co-N P-vollständig:
Es sind nur worst-case exponentielle Algorithmen bekannt
N P-vollst.
co-N P-vollst.
KI, SS
06, F olien 3(1), Seite 7
Algorithmen sind gutartig und optimierbar
Algorithmen sind nicht gutartig und wenig optimierbar
Folgerungsbegriffe
Zwei verschiedene Begriffe der Folgerungen für Logik:
• semantische Folgerung
Basis-Begriff; definiert über Modelle
• syntaktische Folgerung (Herleitung, Ableitung)
Algorithmus
meist ein nicht-deterministischer Kalkül, auf Formeln / Formelmengen
mögliche Ziele:
Erkennung von Tautologien
Erkennung von Folgerungsbeziehungen
KI, SS
06, F olien 3(1), Seite 8
Folgerungsbegriffe in der Aussagenlogik
Definition Sei F eine Menge von (aussagenlogischen) Formeln und G
eine weitere Formel.
G folgt semantisch aus F
Notation: F |= G
gdw.
∀ Interpretationen I : ∀F ∈ F : I(F ) = 1 impliziert I(G) = 1.
KI, SS
06, F olien 3(1), Seite 9
Deduktionstheorem in der Aussagenlogik
Satz (Deduktionstheorem)
{F1, . . . , Fn} |= G
gdw.
F1 ∧ . . . ∧ Fn ⇒ G ist Tautologie.
Beachte: F und G sind äquivalent
gdw.
∀I : I |= F gdw. I |= G
KI, SS
06, F olien 3(1), Seite 10
Aussagenlogische Sätze
∧ und ∨ sind kommutativ, assoziativ, und idempotent:
F ∧G
F ∧F
F ∧ (G ∧ H)
F ∨G
F ∨ (G ∨ H)
F ∨F
KI, SS
06, F olien 3(1), Seite 11
⇔
G∧F
⇔
F
⇔ (F ∧ G) ∧ H
⇔
G∨F
⇔ (F ∨ G) ∨ H
⇔
F
Äquivalenzen:
¬(¬A))
(A ⇒ B)
(A ⇔ B)
¬(A ∧ B)
¬(A ∨ B)
A ∧ (B ∨ C)
A ∨ (B ∧ C)
(A ⇒ B)
A ∨ (A ∧ B)
A ∧ (A ∨ B)
KI, SS
06, F olien 3(1), Seite 12
⇔
⇔
⇔
⇔
⇔
⇔
⇔
⇔
⇔
⇔
A
(¬A ∨ B)
((A ⇒ B) ∧ (B ⇒ A))
¬A ∨ ¬B
(DeMorgansche Gesetze)
¬A ∧ ¬B
(A ∧ B) ∨ (A ∧ C)
Distributivität
(A ∨ B) ∧ (A ∨ C)
Distributivität
(¬B ⇒ ¬A)
Kontraposition
A
Absorption
A
Absorption
Normalformen
disjunktive Normalform (DNF).
Disjunktion von Konjunktionen von Literalen.
(L1,1 ∧ . . . ∧ L1,n1 ) ∨ . . . ∨ (Lm,1 ∧ . . . ∧ Lm,nm )
konjunktive Normalform (CNF).
Konjunktion von Disjunktionen von Literalen.
(L1,1 ∨ . . . ∨ L1,n1 ) ∧ . . . ∧ (Lm,1 ∨ . . . ∨ Lm,nm )
KI, SS
06, F olien 3(1), Seite 13
Transformation in Klauselnormalform
Prozedur:
1.
2.
Elimination von ⇔ und ⇒:
F ⇔ G → F ⇒ G ∧ G ⇒ F und
F ⇒ G → ¬F ∨ G
Negation ganz nach innen schieben:
¬¬F
¬(F ∧ G)
¬(F ∨ G)
3.
KI, SS
→
→
→
F
¬F ∨ ¬G
¬F ∧ ¬G
Distributivität (und Assoziativität, Kommutativität) iterativ
anwenden, um ∧ nach außen zu schieben (“Ausmultiplikation“).
F ∨ (G ∧ H) → (F ∨ G) ∧ (F ∨ H)
06, F olien 3(1), Seite 14
Transformation in Klauselnormalform
Resultat: Konjunktion von Disjunktionen von Literalen
D.h. eine CNF
Eigenschaften
• Die Resultat- CNF ist äquivalent zur eingegebenen Formel
• Der Algorithmus ist worst-case exponentiell (Zeit und Platz)
• Die Anzahl der Literale in der CNF kann exponentiell sein.
KI, SS
06, F olien 3(1), Seite 15
Transformation in Klauselnormalform
Gründe für die Explosion:
Verdoppelung von Unterformeln bei den Transformationsschritten:
•
•
die Elimination von ⇔:
Ausmultiplikation mittels Distributivgesetz:
Beispiele:
(A1 ⇔ A2) ⇔ (A3 ⇔ A4)
;
(A1 ⇒ A2 ∧ A2 ⇒ A1) ⇔ (A3 ⇒ A4 ∧ A4 ⇒ A3)
(A1 ∧ . . . ∧ An) ∨ B2 ∨ . . . ∨ Bm ; ((A1 ∨ B2) ∧ . . . ∧ (An ∨ B2)) ∨ B3 . . . ∨ Bn
KI, SS
06, F olien 3(1), Seite 16
CNF-Algorithmus: Beispiel
((A ∧ B) ⇒ C) ⇒ C
KI, SS
06, F olien 3(1), Seite 17
→
¬(¬(A ∧ B) ∨ C) ∨ C
→
(A ∧ B) ∨ ¬C ∨ C
→
(A ∨ ¬C ∨ C) ∧ (B ∨ ¬C ∨ C)
Schneller CNF-Algorithmus
CNF-Herstellung kann man beschleunigen zu polynomiell: fast O(n).
Trick: komplexe Subformeln iterativ durch neue Variablen abkürzen.
ABER: Formel F ist nicht äquivalent zur berechnten CNF(F ).
Es gilt aber:
F erfüllbar
gdw.
CNF(F ) erfüllbar.
Das reicht aus für Beweisverfahren und semantische Herleitungen
KI, SS
06, F olien 3(1), Seite 18
Schneller CNF-Algorithmus
Wesentlicher Schritt:
Gegeben H1 ∧ . . . ∧ Hn wobei Hj eine Tiefe ≥ 4 hat:
Ersetze in Hj alle Subformeln G1, . . . , Gm von Hj in Tiefe 3 durch neue
Variablen Ai:
D.h. Hj [G1, . . . , Gm] ; (G1 ⇔ A1) ∧ . . . ∧ (Gm ⇔ Am) ∧ Hj [A1, . . . , Am]
Iteriere diesen Schritt, bis er nicht mehr durchführbar ist.
KI, SS
06, F olien 3(1), Seite 19
Schnelle CNF-Herstellung
Hj [G1, . . . , Gm] ; (G1 ⇔ A1) ∧ . . . ∧ (Gm ⇔ Am) ∧ Hj [A1, . . . , Am]
Man sieht, dass Erfüllbarkeit erhalten bleibt.
Gegen-Beispiel zur Äquivalenz:
(A ∨ ¬A) ; (X ⇔ (A ∨ ¬A) ∧ X
Die rechte Formel ist keine Tautologie:
X = 0 ist eine erlaubte Interpretation, die die rechte Formel falsch
macht.
KI, SS
06, F olien 3(1), Seite 20
Resolution für Aussagenlogik
Resolutionsverfahren: Erkennt Widersprüchlichkeit
statt Ist F Tautologie“: Ist ¬F Widerspruch“
”
”
Lemma Eine Formel A1 ∧ . . . ∧ An ⇒ F ist allgemeingültig gdw.
A1 ∧ . . . ∧ An ∧ ¬F widersprüchlich ist.
semantisch formuliert:
{A1, . . . , An} |= F gdw. es keine Interpretation I gibt, so dass
I |= {A1, . . . , An, ¬F }
KI, SS
06, F olien 3(1), Seite 21
Resolutionsverfahren für Aussagenlogik
Gegeben eine Menge M von Klauseln
Iteriere folgende Operation:
Wähle (nichtdeterministisch) 2 Klauseln K, L aus M .
Falls es eine Resolvente R von K, L gibt, füge R zu M hinzu
Stoppe erfolgreich, wenn die leere Klausel erzeugt wurde.
Stoppe nicht widersprüchlich, wenn alle Resolventen schon in M sind,
aber die leere Klausel nicht in M ist.
Klauseln werden als Mengen dargestellt!
KI, SS
06, F olien 3(1), Seite 22
Resolution für Aussagenlogik
Resolutions-Regel:
A
∨B1 ∨ . . . ∨ Bn
¬A ∨C1 ∨ . . . ∨ Cm
B 1 ∨ . . . ∨ B n ∨ C1 ∨ . . . ∨ Cm
zwei Eingabe- Klauseln sind die Elternklauseln
die neu hergeleitete Klausel ist die Resolvente.
KI, SS
06, F olien 3(1), Seite 23
Resolution: Eigenschaften
Aussage
Wenn C → C 0 mit Resolution, dann ist C äquivalent zu C 0.
Aussage
Resolution terminiert
Grund:
Es gibt nur endlich viele mögliche Klauseln, da Resolution keine neuen
Variablen einführt.
KI, SS
06, F olien 3(1), Seite 24
Resolution: Eigenschaften
Resolution ist nicht gut geeignet um Modelle von Formeln zu berechnen:
{{A, B}, {A, ¬A}, {B, ¬B}, {¬A, ¬B}}
Die Formelmenge ist erfüllbar und abgeschlossen bzgl Resolution.
besser Methoden zur Modellberechnung:
Davis-Putnam-Prozedur oder Tableaukalkül
KI, SS
06, F olien 3(1), Seite 25
Resolution: Eigenschaften
Satz In der Aussagenlogik gilt:
Für eine unerfüllbare Klauselmenge findet Resolution nach endlich vielen Schritten die leere Klausel.
Beweis geht mit Induktion nach
(Anzahl der Literale) - (Anzahl der Klauseln)
Satz In der Aussagenlogik gilt:
Resolution erkennt unerfüllbare Klauselmengen.
D.h. Resolution ist vollständig.
KI, SS
06, F olien 3(1), Seite 26
Resolution: Eigenschaften, Bemerkungen
Optimierung der Resolution durch
Elimination von Redundanzen:
•
•
KI, SS
Löschung von Tautologien
Löschen von redundanten Klauseln:
solche mit isolierte Literalen (kein Resolutionsgegenpart)
Subsumtion: Klauseln sind redundant,
die Obermengen von anderen Klauseln sind
06, F olien 3(1), Seite 27
Resolution: Komplexität
Untere Abschätzung der Komplexität im schlimmsten Fall
von ( A. Haken 1985):
Herleitungen können exponentiell lang dauern:
Es gibt Folge von Formeln
(die sogenannten Taubenschlag-formeln (pigeon hole formula,
Schubfach-formeln),
mit exponentiell langen Resolutionsherleitungen
KI, SS
06, F olien 3(1), Seite 28
Davis-Putnam Algorithmus DP (·)
Ist ein Resolutionsverfahren, algorithmisiert
mit Fallunterscheidungen für Literale (A gilt oder A gilt nicht)
und Erkennung isolierter Literale
KI, SS
06, F olien 3(1), Seite 29
Davis-Putnam Algorithmus DP (·)
1
1
2.
a.
b.
a
b
3.
4
KI, SS
Wenn leere Klausel in C: RETURN true.
Wenn C leere Klauselmenge: RETURN false.
wenn 1-Klausel {P } (bzw. {¬P }) ex:
Lösche Klauseln in denen P (bzw. ¬P ) vorkommt.
Lösche Literale ¬P (bzw. P ) in Klauseln
ergibt Klauselmenge C 0. RETURN DP (C 0)
Wenn isolierte Literale existieren:
Lösche Klauseln, in denen isolierte Literale vorkommen.
resultierende Klauselmenge: C 0. RETURN DP (C 0)
Sonst: wähle eine ex. Variable P aus.
RETURN DP (C ∪ {{P }}) ∧ DP (C ∪ {{¬P {{)
06, F olien 3(1), Seite 30
Beispiel für DP
P,
¬P,
P,
¬P,
P,
¬P,
P,
¬P,
Q
Q
¬Q,
¬Q,
Q,
Q,
¬Q,
¬Q,
R
R
R
¬R
¬R
¬R
¬R
Fall 1: Addiere die Klausel {P }. nach einigen Schritten:
Q,
¬Q,
Q,
¬Q,
KI, SS
06, F olien 3(1), Seite 31
R
R
¬R
¬R
Fall 1.1: Addiere {Q}: ergibt die leere Klausel.
Fall 1.2: Addiere {¬Q}: ergibt die leere Klausel.
Fall 2: Addiere die Klausel {¬P }. Nach einigen Schritten:
Q
¬Q R
Q
¬R
¬Q ¬R
Weitere Schritte für Q ergeben
R
¬R
ergibt leere Klausel.
Smullyan: Wer ist der Pfefferdieb?
Rätsel von Raymond Smullyan vor:
Es gibt drei Verdächtige: Den Hutmacher, den Schnapphasen und die
(Hasel-)Maus. Folgendes ist bekannt:
• Genau einer von ihnen ist der Dieb.
• Unschuldige sagen immer die Wahrheit
• Schnapphase: der Hutmacher ist unschuldig.
• Hutmacher: die Hasel-Maus ist unschuldig
KI, SS
06, F olien 3(1), Seite 33
Kodierung: H, S, M
1.
2.
3.
4.
5.
6.
H ∨S∨M
H ⇒ ¬(S ∨ M )
S ⇒ ¬(H ∨ M )
M ⇒ ¬(H ∨ S)
¬S ⇒ ¬H
¬H ⇒ ¬M
Klauselmenge:
{{H, S, M }, {¬H, ¬S}, {¬H, ¬M }, {¬S, ¬M }, {S, ¬H}, {H, ¬M }}
KI, SS
06, F olien 3(1), Seite 34
Kodierung: H, S, M : Resultat
pfefferdieb =
"((H \\/
/\\ (S =>
/\\(-S =>
dp
S \\/ M) /\\ (H => -(S \\/ M))
-(H \\/ M)) /\\ (M => -(H \\/ S))
-H) /\\ (-H => -M))"
Modell: S, -M, -H"
KI, SS
06, F olien 3(1), Seite 35
Eine Logelei aus der Zeit
Abianer sagen die Wahrheit, Bebianer Lügen. Aussagen:
1.
2.
3.
4.
5.
6.
7.
Knasi: Knisi ist Abianer.
Knesi: Wenn Knösi Bebianer, dann ist auch Knusi ein Abianer.
Knisi: Wenn Knusi Abianer, dann ist Knesi Bebianer.
Knosi: Knesi und Knüsi sind beide Abianer.
Knusi: Wenn Knüsi Abianer ist, dann ist auch Knisi Abianer.
Knösi: Entweder ist Knasi oder Knisi Abianer.
Knüsi: Knosi ist Abianer.
A <=> I
E <=> (-OE => U)
I <=> (U => -E)
O <=> (E /\ UE)
U <=> (UE => I)
OE <=> (A XOR I)
UE <=> O
KI, SS
06, F olien 3(1), Seite 36
Logelei: Lösung
Die Eingabe in den Davis-Putnam-Algorithmus ergibt:
abianer1Expr = "((A <=> I) /\\ (E <=> (-OE => U)) /\\ (I <=> (U => -E))
/\\ (O <=> (E /\\ UE)) /\\ (U <=> (UE => I))
/\\ (OE <=> -(A <=> I)) /\\ (UE <=> O))"
Resultat:
"Modell: -OE, -O, -UE, E, U, -I, -A"
Damit sind Knesi und Knusi Abianer, die anderen sind Bebianer.
KI, SS
06, F olien 3(1), Seite 37
Ein weiteres Rätsel von Raymond Smullyan:
Hier geht es um den Diebstahl von Salz.
Die Verdächtigen sind:
Lakai mit dem Froschgesicht, Lakai mit dem Fischgesicht, Herzbube.
Die Aussagen und die bekannten Tatsachen sind:
• Frosch: der Fisch wars
• Fisch: ich wars nicht
• Herzbube: ich wars
• Genau einer ist der Dieb
• höchstens einer hat gelogen
KI, SS
06, F olien 3(1), Seite 38
Kodierung des Problems
Wir verwenden Variablen mit folgenden Namen und Bedeutung:
FRW
FIW
HBW
FID
FRD
HBD
KI, SS
Frosch sagt die Wahrheit
Fisch sagt die Wahrheit
Herzbube sagt die Wahrheit
der Fisch ist der Dieb
der Frosch ist der Dieb
der Herzbube ist der Dieb
06, F olien 3(1), Seite 39
Kodierung des Frosch-Fisch-Problems
höchstens einer sagt die Wahrheit:
¬F RW ⇒ F IW ∧ HBW
¬F IW ⇒ F RW ∧ HBW
¬HBW ⇒ F RW ∧ HIW
genau einer ist der Dieb:
F ID ∨ F RD ∨ HBD
F ID
⇒ ¬F RD ∧ ¬HBD
F RD
⇒ ¬F ID ∧ ¬HBD
HBD
⇒ ¬F ID ∧ ¬F RD
Die Aussagen:
F RW
⇒ F ID
F IW
⇒ ¬F ID
HBW
⇒ HBD
KI, SS
06, F olien 3(1), Seite 40
Frosch-Fisch: DP-Algorithmus:
dp "((-FRW => FIW /\\ HBW) /\\ (-FIW => FRW /\\ HBW)
/\\ (-HBW => FRW /\\ HIW)
/\\ (FID => -FRD /\\ -HBD) /\\ (FRD => -FID /\\ -HBD)
/\\ (HBD => -FID /\\ -FRD) /\\ (FRW => FID)
/\\ (FIW => -FID) /\\ (HBW => HBD))"
Die berechnete Lösung ist:
HBD, −F ID, HBW, F IW, −F RW, −F RD
D.h FRW ist falsch, d.h. der Fisch hat gelogen und der Herzbube war
der Dieb.
KI, SS
06, F olien 3(1), Seite 41
Das n-Damen Problem aussagenlogisch
Funktion zum Erzeugen der aussagenlogischen Bedingungen:
Ausgabe im Fall n = 4:
[[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12],
[13, 14, 15, 16], [1, 5, 9, 13],
[2, 6, 10, 14], [3, 7, 11, 15], [4, 8, 12, 16],
[-1, -5], [-1, -9], [-1, -13],
[-1, -2], [-1, -6], [-1, -3], [-1, -11], [-1, -4], [-1, -16],
[-5, -9], [-5, -13],
[-5, -2], [-5, -6], [-5, -10], [-5, -7], [-5, -15], [-5, -8],
[-9, -13],
[-9, -6], [-9, -10], [-9, -14], [-9, -3], [-9, -11], [-9, -12],
[-13, -10], [-13, -14],
[-13, -7], [-13, -15], [-13, -4], [-13, -16], [-2, -6], [-2, -10],
KI, SS
06, F olien 3(1), Seite 42
[-2, -14],[-2, -3], [-2, -7], [-2, -4], [-2, -12], [-6, -10],
[-6, -14], [-6, -3],
[-6, -7], [-6, -11], [-6, -8], [-6, -16], [-10, -14], [-10, -7],
[-10, -11], [-10, -15],[-10, -4], [-10, -12], [-14, -11],
[-14, -15], [-14, -8], [-14, -16], [-3, -7],
[-3, -11], [-3, -15], [-3, -4], [-3, -8], [-7, -11], [-7, -15],
[-7, -4], [-7,-8],
[-7, -12], [-11, -15], [-11, -8], [-11, -12], [-11, -16], [-15, -12],
[-15, -16], [-4, -8], [-4, -12], [-4, -16], [-8, -12],
[-8, -16], [-12, -16]]
Das n-Damen Problem aussagenlogisch
Das Ergebnis der DP-Prozedur sind zwei Interpretationen:
[[-4, -8, -15, 5, -13, 14, -6, -2, 12, -9, -1, 3, -16, -10, -7, -11],
[-4, 2, 8, -6, -1, 9, -12, -14, -13, -5, 15, -3, -16, -10, -7, -11]]
Zwei möglichen Platzierungen im Fall n = 4.
KI, SS
06, F olien 3(1), Seite 44
Das n-Damen Problem aussagenlogisch
Der Aufruf dpqueens 8 ergibt nach kurzer Zeit:
D
-
D
-
KI, SS
D
-
D
-
D
-
D
D
-
06, F olien 3(1), Seite 45
D
-