Institut für
Theoretische Informatik
ITI
Dr. Jürgen Koslowski
Einführung in die Logik
Aufgabenblatt 3, 2016-05-02
Übungsaufgabe 16
Bestimmen Sie jeweils einen hinsichtlich der Knotenzahl kleinsten Syntaxbaum einer zur gegebenen Formel äquivalenten Formel in FRM :
(a) ¬((F ∨ ¬G) ∨ ¬( F ∨ H)) ∧ (G ∨ H)
(b) (A ∧ ¬¬B) ⇔ (C ⇒ (C ⇒ A) ∨ B)
Lösungsvorschlag:
(a)
¬((F ∨ ¬G) ∨ ¬( F ∨ H)) ∧ (G ∨ H) ≡ ¬F ∧ G ∧ (F ∨ H) ∧ (G ∨ H)
≡ ¬F ∧ G ∧ (F ∨ H)
≡ (¬F ∧ G ∧ F ) ∨ (¬F ∧ G ∧ H)
≡ ⊥ ∨ (¬F ∧ G ∧ H)
≡ ¬F ∧ G ∧ H
Damit ergibt sich folgender Syntaxbaum:
∧
∧
¬
H
G
F
Kleiner kann er bei drei Atomen nur werden, wenn man die Negation eliminiert, was aber
die Syntax entscheident verändert.
(b) Eliminierung der doppelten Negation und der Implikation liefert
(A ∧ ¬¬B) ⇔ (C ⇒ (C ⇒ A) ∨ B) ≡ (A ∧ B) ⇔ ((A ∨ ¬C) ∨ B ∨ ¬C)
≡ (A ∧ B) ⇔ (A ∨ B ∨ ¬C)
Gemäß Proposition 2.3.2(c) kann die Äquivalenz auf (mindestens) zwei verschiedene Weisen eliminiert werden:
F := (A ∧ B) ⇔ (A ∨ B ∨ ¬C)
≡ (A ∧ B ∧ (A ∨ B ∨ ¬C)) ∨ (¬(A ∧ B) ∧ ¬(A ∨ B ∨ ¬C))
≡ ((A ∧ B) ∨ ¬(A ∨ B ∨ ¬C)) ∧ (¬(A ∧ B) ∨ A ∨ B ∨ ¬C)
Im ersten Fall läßt sich die Absorbtionsregel auf die erste Teilformel direkt anwenden,
während sie in der zweiten Teilformel erst nach Anwendung der de Morgan’schen Regeln
zum Einsatz kommen kann:
F := (A ∧ B) ∨ ((¬A ∨ ¬B) ∧ ¬A ∧ ¬B ∧ C)
≡ (A ∧ B) ∨ (¬A ∧ ¬B ∧ C)
Im zweiten Fall reduziert sich das zweite Argument zu >, was neutral bzgl. der Konjunktion
ist, während der erste Teil nach Anwendung der de Morgan’schen Regel dasselbe Ergebnis
wie oben liefert. In Baumform etwa:
∨
∨
∧
∧
¬
B
A
∧
∧
≡
∧
¬
A
∨
∧
B
A
C
B
≡
C
¬
¬
A
B
∧
∧
¬
B
A
C
∨
B
A
wobei die Assoziativität von ∧ und dann die de Morgan’sche Regel genutzt wurden. Aufgrund des zweifachen Auftretens von A und B ist nicht unmittelbar klar, dass der rechte
Baum der Größe 10 schon minimal ist. Diverse Versuche, mit den bisher bekannten Rechenregeln A ∧ B oder A ∨ B zu eliminieren, haben keinen Erfolg. Aber läßt sich vielleicht
die explizite Negation entfernen? Mit Hilfe eines Distributivgesetzes und der Definition von
⇒ erhalten wir
(A ∧ B) ∨ (¬(A ∨ B) ∧ C) ≡ ((A ∧ B) ∨ ¬(A ∨ B)) ∧ ((A ∧ B) ∨ C)
≡ ((A ∨ B) ⇒ (A ∧ B)) ∧ (¬C ⇒ (A ∧ B))
≡ (A ∨ B ∨ ¬C) ⇒ (A ∧ B)
≡ (C ⇒ (A ∨ B)) ⇒ (A ∧ B)
eine Formel der Länge 9. Dabei ist allerdings der vorletzte Schritt durch keine unserer bisherigen Regeln gerechtfertigt, sondern entweder durch mathematisches Hintergundwissen
(Stichwort “cartesische Abgeschlossenheit”), oder durch genauere Analyse der Semantik
der Implikation ⇒: Sind die Wahrheitswerte von F und G höchstens so groß wie der von
H, dann gilt das auch für deren Supremum, also den Wahrheitswert von F ∨ G; die umgekehrte Richtung ist trivial.
Schaut man sich die erste Zeile der obigen Umformung nochmal genauer an, so stellt man
fest, dass sich die Definition von ⇔ darin wiederfinden läßt (alternativ kann man ein
Distributivgesetz auf den mittleren der obigen Bäume anwenden):
(A ∧ B) ∨ (¬(A ∨ B) ∧ C) ≡ (A ⇔ B) ∧ ((A ∧ B) ∨ C)
Diese Formel hat ebenfalls die Länge 9, kann aber weiter verkürzt werden:
(A ⇔ B) ∧ ((A ∧ B) ∨ C) ≡ (A ⇔ B) ∧ (A ∨ C) ≡ (A ⇔ B) ∧ (B ∨ C)
Hier ist keine unserer Rechenregeln zur Anwendunggekommen, aber die Einsicht, dass
bei äquivalenten Formeln F und G ihre Konjunktion F ∧ G sowohl zu F wie auch zu G
äquivalent ist.
∨
∧
∧
∧
A
¬
B
∧
C
⇔
≡
A
∨
∧
B
⇔
A
A
∨
C
∨
A
≡
B
A
C
B
B
Fazit: bei mehrfachem Auftreten von Atomen kann es schwierig sein festzustellen, ob man
bereits die kürzeste Formel (bzw. den kleinsten Baum) gefunden hat.
Aufgabe 17 [9 PUNKTE]
Stellen Sie die Ergebnisse der Sätze 3.1.1–3.2.2 sowie 3.2.5 für n = 2 im Skript als Äquivalenzen
zwischen Syntaxbäumen dar.
Aufgabe 18 [8 PUNKTE]
Zeigen oder widerlegen Sie: zu jeder Formel F ∈ FRM existiert modulo Kommutativität und
Assoziativität genau eine äquivalente Formel G ∈ FRM minimaler inhärenter Länge.
Aufgabe 19 [10 PUNKTE]
In F ∈ FRM {Ai : i < n} mögen alle Variablen vorkommen. Eine Formel F 0 ∈ KNF mit
Klauseln Kj , j < t, heißt kanonische KNF (kKNF) von F , sofern
(a) F 0 ≡ F gilt;
W
(b) jede Klausel hat die Form i<n Li und jede atomare Formel Aj , j < n, genau einmal
vorkommt; also obdA gilt Li ∈ {Ai , ¬Ai };
(c) die Klauseln paarweise verschieden sind.
Zeigen oder widerlegen Sie: jede Formel F ist bis auf die Reihenfolge der Klauseln eindeutig zu
einer Formel in kanonischer KNF äquivalent.
Aufgabe 20 [14 PUNKTE]
(a) Finden Sie einen Algorithmus, der zu einer Formel F eine kanonische KNF F 0 bestimmt.
(b) Zeigen Sie, dass zwei Formeln F und G genau dann äquivalent sind, wenn F mittels ele”
mentarer Äquivalenzumformungen“ (s.u.) in G transformiert werden kann.
Dabei sind elementaren Äquivalenzumformungen“ gegeben durch
”
• den Zusammenhang von >, ⇒, ⇔, ⊕ und ↑ mit den Junktoren ⊥, ¬, ∧ und ∨ gemäß
Proposition 2.3.2 (a)–(d) und Beispiel 3.3.4;
• den Inhalt der Sätze 3.1.1 bis 3.2.2 sowie 3.2.5.
Abgabe bis Montag, 2016-05-09, im Kasten neben IZ 343
© Copyright 2024 ExpyDoc
