Transcript
Logik. Lösungen der Vorlesungs-Aufgaben, Tipps zu Ergänzungsaufgaben, 02.06.2016 Wiederholung Mengenlehre 1. Teilmengen, Mengenoperationen, Abbildungen Seien Teilmengen der natürlichen Zahlen wie folgt definiert: A := {2n | n ∈ IN } , B := {3n | n ∈ IN } , C := {4n | n ∈ IN } D := {6n | n ∈ IN } , E := {8n | n ∈ IN } . a) Welche der folgenden Aussagen sind richtig, welche falsch? i. A ⊆ C ii. E ⊆ C iii. B ⊆ D v. D = {a ⋅ b | a ∈ A, b ∈ B} vi. E ⊆ A ∩ D
Lösung 1a A⊆C D = {a ⋅ b | a ∈ A, b ∈ B}
F W
E⊆C E ⊆ A∩ D
W F
iv. E ⊆ D
vii. A ∪ B = IN \ {1}
B⊆D A ∪ B = IN \ {1}
F F
viii. D C ⊆ AC
E⊆D
F
(Warum ist nicht D = {6n 2 | n ∈ IN } , wo doch 2n ⋅ 3n = 6n 2 ?) b) Bestimmen Sie die folgenden Mengen: i. A ∩ B ii. C ∩ E iii. B ∪ D iv. B \ D
Lösung 1b i. A ∩ B = D ii. C ∩ E = E iv. B \ D = {3 ⋅ (2n − 1) | n ∈ IN }
v. C × D
iii. B ∪ D = B v. C × D = {(4m,6n) | m, n ∈ IN }
2. Relationen, Abbildungen a) Sei f : S → T eine Abbildung. Zeigen Sie, dass ≈ ⊆ S × S mit x ≈ y :⇔ f ( x) = f ( y ) eine Äquivalenzrelation auf S ist. Lösung 2a Seien a, b, c ∈ S . symmetrisch: a ≈ b ⇒ f (a ) = f (b) ⇒ f (b) = f (a ) ⇒ b ≈ a transitiv: a ≈ b und b ≈ c ⇒ f (a ) = f (b) & f (b) = f (c) ⇒ reflexiv: f (a ) = f (a) ⇒ a ≈ a
f ( a ) = f (c ) ⇒ a ≈ c
b) Welche der folgenden Aussagen sind (bezüglich der Abbildungsgraphenmengen) mit A, B, C, D wie in Aufg. 1 richtig, welche falsch? i. C D ⊆ A B
ii. C D ⊆ C A
iii. D C ⊆ AC
Lösung 2b i. F: Eine Abbildung f auf D enthält kein Paar (3,x), eine Abbildung auf B tut das. ii. F: Eine Abbildung f auf D enthält kein Paar (2,x), eine Abbildung auf A tut das. iii. W: Eine linkstotale, rechtseindeutige Teilmenge von C×D ist auch eine linkstotale, rechtseindeutige Teilmenge von C×A. (denn, ausführlich, …)
kein weiterer Tipp zu E1 nötig
Bernd Baumgarten
Hochschule Darmstadt SS 2016
Logik. Lösungen der Vorlesungs-Aufgaben, Tipps zu Ergänzungsaufgaben, 02.06.2016
3. Bildmenge Bildmengen f [ A] werden häufig auch als f ( A) geschrieben. Zeigen Sie anhand einer Abbildung auf { 1, {1}}, dass dies zu inakzeptablen Mehrdeutigkeiten führt. Lösung 3 Sei z.B. f (1) = a , f ({1}) = a . Dann bedeutet f ({1}) (d.h. a) aber gleichzeitig f [{1}] , d.h. { f (1)} , d.h. {a}. Das klappt nur wenn a = {a}. Und das ist in jeder üblichen Art Mengenlehre falsch.
4. Abbildungen a) Geben Sie alle möglichen Abbildungen von {1,2} nach {a,b,c} an. Lösung 4a Wir beschreiben der Kürze wegen jede Funktion f kurz durch das 2-buchstabige Wort f (1) f (2) . Dann gibt es die 9 Abbildungen aa, ab, ac, ba, bb, bc, ca, cb, cc. b) Geben Sie alle möglichen Funktionen von {1,2,3} nach {a,b} an.
Lösung 4b Wir beschreiben der Kürze wegen jede Funktion f kurz durch das 3-buchstabige Wort f (1) f (2) f (3) . Dann gibt es die 8 Abbildungen aaa, aab, aba, abb, baa, bab, bba, bbb c) Welche von ihnen sind i. injektiv? ii. surjektiv? iii. bijektiv?
Lösung 4c (zu a) injektiv: ab, ac, ba, bc, ca, cb. surjektiv: – bijektiv: – (zu b) injektiv: –. surjektiv: aab, aba, abb, baa, bab, bba. bijektiv: –
Tipp zu E2 Schreiben Sie die anderen gegebenen Zahlen geeignet hinein, sowie dann die Zahlen, die Sie daraus folgern können.
Bernd Baumgarten
L9
P 15
V 16
Hochschule Darmstadt SS 2016
Logik. Lösungen der Vorlesungs-Aufgaben, Tipps zu Ergänzungsaufgaben, 02.06.2016 Wiederholung Induktion, Rekursion
5. Induktive Mengendefinition Definieren Sie induktiv über dem Alphabet Alph={a,b} a) die Sprache aller Wörter, die eine ungerade Anzahl von Buchstaben enthalten, b) die Sprache aller Palindrome, d.h. der Wörter, die sich rückwärts wie vorwärts lesen, c) die Sprache aller doppelten Wörter ww. Lösung 5 a) a, b ∈ La , b) ε , a, b ∈ Lb , c) ε ,
w ∈ La ⇒ waa, wab, wba, wbb ∈ La w ∈ Lb ⇒ awa, bwb ∈ Lb ww ∈ Lc ⇒ wawa, wbwb ∈ Lc (Beachte: ε = εε ) Bzw. mit geeigneter Abbildung halb so dass halb(ww)=w: w ∈ Lc ⇒ halb( w) a halb( w) a, halb( w) b halb( w) b ∈ Lc
6. Rekursive Funktionsdefinition und induktiver Beweis n ⋅ (n + 1) a) Beweisen Sie 1 + ... + n = . 2 Lösung 6a Ind.-Basis: Es stimmt für n=0, denn 0=0x1/2. Ind.-Ann.: Es stimme für n. Ind.-Schritt: Dann ist n ⋅ (n + 1) 2n + 2 n ⋅ (n + 1) + 2n + 2 1 + ... + n + (n + 1) = + = 2 2 2 2 n + 3n + 2 (n + 1) ⋅ (n + 2) (n + 1) ⋅ ((n + 1) + 1) = = = 2 2 2 D.h. es stimmt für n+1. b) Wenn wir die Addition noch gar nicht kennen, sondern (für jedes m) m + n als einstellige Funktion „m+(n)“ rekursiv für das Argument n so definieren: m+0 := m, m + succ(n) := succ(m + n), wie können wir dann die Assoziativität l + ( m + n) = (l + m) + n beweisen?
Lösung 6b Basis: Die Aussage „Für alle l,m: l + ( m + n) = (l + m) + n“ gilt für n = 0, denn l + ( m + 0) = l + m = (l + m) + 0. Induktionsschritt: Es gelte für n: „Für alle l,m: l + ( m + n) = (l + m) + n.“ Dann ist l + ( m + succ(n)) = l + succ(m + n) = succ( l + (m + n)) = succ( (l + m) + n) = (l + m) + succ(n)
Bernd Baumgarten
Hochschule Darmstadt SS 2016
Logik. Lösungen der Vorlesungs-Aufgaben, Tipps zu Ergänzungsaufgaben, 02.06.2016 c) Beweisen Sie für die Länge und Verkettung von Wörtern über A: l ( w o w ′) = l ( w) + l ( w ′) .
Lösung 6c Erinnerung an die Definition von l: • l (ε ) := 0 , • w ∈ A*, a ∈ A ⇒ l ( wa ) := l ( w) + 1 Erinnerung an die Definition von ○: • w ∈ A* ⇒ w o ε := w , • w, w′ ∈ A*, a ∈ A ⇒ w o ( w′a ) := ( w o w′)a Damit jetzt: l ( w o w′) = l ( w) + l ( w′) per Induktion über w’ : (Basis) l ( w o ε ) = l ( w) = l ( w) + 0 = l ( w) + l (ε ) Wenn l ( w o w ′) = l ( w) + l ( w ′) (Hyp.), dann l ( w o ( w′a )) = l (( w o w ′)a ) = l ( w o w ′) + 1 = l ( w) + l ( w ′) + 1 = l (w) + l (w′a) (Ind.-Schritt).
7. Grammatiken Geben Sie eine Grammatik für die Palindrome über {a,b} an. Lösung 7 S aSa | bSb | a | b | ε
Tipp zu E3.c „Programmieren“ Sie durch eine Grammatik z.B. einen Mechanismus, der • jeweils zwei gleiche Buchstaben nebeneinander erzeugt, davon aber das zweite Exemplar modifiziert: aA oder bB • alle Großbuchstaben nach rechts und Kleinbuchstaben nach links „sickern“ lässt, ohne große mit großen oder kleine mit kleinen zu vertauschen ( Erhaltung der Buchstabenreihenfolge im „halben Wort“!) Ergänzen Sie die Grammatik so, dass sich noch eine „Verkleinerungsmaschine“ V durch das großgeschriebene Wort fräst, welche • die Buchstaben klein macht, z.B. von rechts nach links (AV Va) • und am Ende verschwindet.
Tipp zu E4.a Zwei Möglichkeiten: Entweder definieren wir die dreistellige Relation Pfad(p,a,b) (p ist Pfad von a nach b) induktiv, oder wir definieren gleichzeitig Pfade induktiv und die Funktionen A und E (Anfangs- und Endknoten) auf Pfaden rekursiv.
Bernd Baumgarten
Hochschule Darmstadt SS 2016
Logik. Lösungen der Vorlesungs-Aufgaben, Tipps zu Ergänzungsaufgaben, 02.06.2016
8. Baumdefinitionen Manche Autoren definieren endlich verzweigte geordnete Bäume als Teilmengen von IN * (Sprache über IN ), indem sie jeden Knoten mit einer Pfadbeschreibung (im Stile von „und jetzt zum wievielten Kind?“) identifizieren. Geben Sie eine Definition der passenden Sprachen an. Lösung 8 Beachten: (a) Der Pfad zur Wurzel ist leer , d.h. ε. (b) Jedes Anfangsstück eines Pfads ist ein Pfad. (c) Hat ein Knoten ein n. Kind, dann auch Kinder Nummer 1 bis n–1. – Reicht! Die Pfadsprachen aller e.v. g. Bäume sind genau die L ⊆ IN * mit folgenden Eigenschaften: (i) L ≠ ∅ ⇒ ε∈L (ii) u , v ∈ IN* , uv ∈ L ⇒ u ∈ L (iii) ub ∈ L, a, b ∈ IN , a < b ⇒ ua ∈ L Wie steht es dabei eigentlich mit unendlichen Pfaden/ unendlichen Bäumen? – Erlaubt? Bereits mit erledigt? Mit einem kleinen Trick erledigbar?
Tipps zu E5 bereits vorhanden AL-Formeln, Wahrheitswerte, Wahrheitstabellen
9. Alternative Schreibweisen Beschreiben Sie, wie sich die (a) Infix-, (b) polnische und (c) umgekehrt polnische Schreibweise einer aussagenlogischen Formel aus der Baumdarstellung ergeben. Lösung 9 a) Infix(Baum): [pseudoprogrammiersprachlich] IF Wurzel(Baum) ist Blatt THEN write(Wurzel(Baum)) ELSE IF Wurzel(Baum) ist ¬ THEN BEGIN write(‚ ¬ ’); Infix(Kindbaum) END ELSE IF Wurzel(Baum) ist 2-stelliger Junktor j THEN BEGIN write(‚(’); Infix(linker Kindbaum); write(j); Infix(rechter Kindbaum); write(‚)’); END; b1) Ab Wurzel linke Hand an den Baum, Hand dranlassen und rund um den Baum laufen, jeden Knoten beim ersten Passieren aufschreiben. b2) Polish(Baum): [pseudoprogrammiersprachlich] IF Wurzel(Baum) ist Blatt THEN write(Wurzel(Baum)) ELSE IF Wurzel(Baum) ist ¬ THEN BEGIN write(‚ ¬ ’); Polish(Kindbaum) END ELSE IF Wurzel(Baum) ist 2-stelliger Junktor j THEN BEGIN write(j); Polish(linker Kindbaum); Polish(rechter Kindbaum); END; Bernd Baumgarten
Hochschule Darmstadt SS 2016
Logik. Lösungen der Vorlesungs-Aufgaben, Tipps zu Ergänzungsaufgaben, 02.06.2016 c1) c2) c3)
Ab Wurzel linke Hand an den Baum, Hand dranlassen und rund um den Baum laufen, jeden Knoten beim letzten Passieren aufschreiben. Ab Wurzel rechte Hand an den Baum, Hand dranlassen, rund um den Baum laufen, jeden Knoten beim ersten Passieren aufschreiben. Am Ende Formel umdrehen. pseudoprogrammiersprachlich?
10. Rekursive Funktionen auf Formeln Definieren Sie „vernünftig“ Sub(ϕ), Grad(ϕ) und Tiefe(ϕ). Lösung 10 Sub : Form → P( Form) Sub( Ai ) := { Ai } Sub(¬ϕ ) := Sub(ϕ ) ∪ {¬ϕ} und für j = ∧, ∨, →, bzw. ↔: Sub(ϕ j ψ ) := Sub(ϕ ) ∪ Sub(ψ ) ∪ {(ϕ j ψ )} Grad : Form → IN 0 Grad ( Ai ) := 0 Grad (¬ϕ ) := Grad (ϕ ) + 1 und für j = ∧, ∨, →, bzw. ↔: Grad (ϕ j ψ ) := Grad (ϕ ) + Grad (ψ ) + 1
Tiefe : Form → IN 0 Tiefe( Ai ) := 0 Tiefe(¬ϕ ) := Tiefe(ϕ ) + 1 und für j = ∧, ∨, →, bzw. ↔: Tiefe(ϕ j ψ ) := max(Tiefe(ϕ ) + Tiefe(ψ )) + 1
11. Wahrheitswert, rekursiv a) Zeichnen Sie den Syntaxbaum der Formel ( A → B ) ∨ ( A ∧ ( B ↔ C )) . b) Schreiben Sie an alle Knoten dieses Syntaxbaumes den zugehörigen Wahrheitswert unter der Belegung A a W , B a F, C a F . Lösung 11 ∨
W
F → W
Bernd Baumgarten
A
∧
B A F W
W ↔W
B F
C F
Hochschule Darmstadt SS 2016
Logik. Lösungen der Vorlesungs-Aufgaben, Tipps zu Ergänzungsaufgaben, 02.06.2016
12. Junktoren in natürlicher Sprache Schreiben Sie die folgenden Sätze jeweils sinn- und möglichst textgetreu als eine AL-„Formel“, in der Sätze natürlicher Sprache mit Junktoren verbunden sind. Ignorieren Sie dabei wertende Beiklänge. Beispiel: Franz und Nadia sind Studenten. a (Franz ist Student) ∧ (Nadia ist Studentin) a) b) c) d) e)
Wenn du fährst, fahre ich auch. Ich fahre nur wenn du auch fährst. Weil du fährst, fahren er und ich auch. Ich fahre nicht, es sei denn, du fährst auch. Es regnet morgen, vielleicht aber auch erst übermorgen.
f) g)
Linda arbeitet, obwohl sie krank ist. Tim ist ein guter Tänzer und Schwimmer. h) Wenn Franz singt, dann nervt er. i) Wenn Franz singt, dann nervt das. Teilsätze sind abgekürzt wiedergegeben:
Lösung 12 a) Df → If b) If → Df (auch If ↔ Df ?) c) Df ∧ (Ef ∧ If)
d) If → Df (auch If ↔ Df ?) g) TigT ∧ TigS e) rm ∨ rüm h) Fs → Fn f) La ∧ Lik i) Fs → F’s Gesang nervt
Bemerkung 1: Beachten Sie die sprachlichen Varianten von → und ∧ . Bemerkung 2: Gelegentlich (vgl. z.B. d) würde man im Alltag evtl. „fairerweise“ ↔ anstatt → als gemeint erwarten Interpretationsdivergenzen! Bemerkung 3: (i) ist verschieden von (h): Es könnte in (h) ja sein, dass sein Gesang OK ist, dass er aber beim Singen übertrieben theatralische Gesten macht etc. Außerdem kann man bei (i) noch diskutieren, ob mit das F’s derzeitiger Gesang gemeint ist, und ob damit die zweite Aussage, wenn F gerade nicht singt, falsch oder sinnlos (keine Aussage) ist.
13. Wahrheitswerteverlauf, Wahrheitstafel Berechnen Sie den Wahrheitswerteverlauf von ( A → B ) ∨ (¬B ∧ A)
Lösung 13 A B W W W F F W F F
A→ B W F W W
(¬B ∧ A) F W F F
∨
→ A
¬B F W F W
Alternativ in modifizierter Tabellenform:
∧
B
¬
A B
W W F F
W F W W
W F W F
( A → B) ∨ (¬B ∧ A) W W W W
W F W F W W W F W W W F W F F W W F F F
Man schreibt von jeder Teilformel nur den „obersten Operator“, dafür aber meist einige Teilformeln mehrfach.
kein Tipp zu E6 Bernd Baumgarten
Hochschule Darmstadt SS 2016
Logik. Lösungen der Vorlesungs-Aufgaben, Tipps zu Ergänzungsaufgaben, 02.06.2016
14. Junktoren und Operatoren a) Geben Sie die 4 einstelligen logischen Operatoren(semantiken) an. b) Gibt es nullstellige? Lösung 14a,b a)
A W F
T W W
⊥ F F
A W F
¬A F W
b) Im T ⊥ -Dialekt die beiden Konstanten. c) Wie viele der n-stelligen Junktoren (Werteverläufe) hängen echt von allen n Argumenten ab (und wie formalisiert man diese Abhängigkeit?) [Beantworten Sie zunächst die Frage in Klammern.] Die allgemeine Anzahl als Funktion von n ist für kleine n zu bestimmen. Eine geschlossene Formel oder induktive Definition für alle n bleibt Ihnen überlassen..
Lösung 14c (Formaliserungsteil) f ( A1 , K , An ) ist „eigentlich unabhängig“ von Ai , wenn für alle Belegungen f ( A1 , K , An ) = f ( A1 , K , Ai −1 , ¬Ai , Ai +1 , K , An ) . Andernfalls (von keinem Argument unabhängig) hängt f echt von allen Argumenten ab. (Anzahl für kleine n) Von den vier 1-stelligen Operatoren (booleschen Funktionen) sind 2 von mindestens einem Argument eigentlich unabhängig. Von den 16 2-stelligen Junktoren sind 6 eigentlich von mindestens einem Argument unabhängig. Semantische Begriffe
15. Semantische Kategorien von Formeln Welche der folgenden Formeln sind ... erfüllbar unerfüllb. konting. allgemeing. widerlegb.? a) ( A ↔ B ) ↔ (( A ∧ B ) ∨ (¬A ∧ ¬B )) b) ( A ∨ B ) → ( A → B ) c) ( A ∧ ¬B ) ∧ ( A → B ) Sie müssen nicht unbedingt die Wahrheitstafel aufschreiben, wenn ihnen jeweils Modelle oder Gegenbeispiele einfallen – bzw. warum es keine geben kann. Lösung 15 erfüllbar unerfüllb. konting. allgemeing. widerlegb.? a) ( A ↔ B ) ↔ (( A ∧ B ) ∨ (¬A ∧ ¬B )) x – – x – b) ( A ∨ B ) → ( A → B ) x – x – x c) ( A ∧ ¬B ) ∧ ( A → B ) – x – – x Verbale Begründungen: a) ( A ↔ B ) ist W ⇔ A und B sind W, oder A und B sind F. (( A ∧ B ) ∨ (¬A ∧ ¬B )) ist W ⇔ A und B sind W, oder A und B sind F. ( A ↔ B ) ↔ (( A ∧ B ) ∨ (¬A ∧ ¬B )) ist W, sobald beide Seiten den gleichen Wert haben, also (s.o.) immer. b) Modell z.B. A,B sind W. Gegenbeispiel? Dann müsste ( A ∨ B ) W und ( A → B ) F sein. Wegen letzterem müsste A W und B F sein. Dies klappt als Gegenbeispiel. Bernd Baumgarten
Hochschule Darmstadt SS 2016
Logik. Lösungen der Vorlesungs-Aufgaben, Tipps zu Ergänzungsaufgaben, 02.06.2016 c) In einem Modell dürfte wegen ( A → B ) nicht gleichzeitig A W und B F sein und muss wegen ( A ∧ ¬B ) gleichzeitig A W und B F sein. Das geht also nicht. Schreiben Sie einfach eine Wahrheitstafel, wenn Ihnen die Begründung unklar ist.
16. Kombinatorische Aufgaben a) Anne sagt: Bea und Chris werden als Nächstes lügen. Bea sagt dann: Anne hat gerade gelogen. Chris sagt dann: Anne hat gerade die Wahrheit gesagt. Wer hat gelogen, wer nicht? Lösung 16a A, B, C : Anne, Bea, Chris sagt in ihrer obigen Aussage die Wahrheit. ¬A , ¬B , ¬C : Anne, Bea, Chris lügt in ihrer obigen Aussage. Die drei Fakten bedeuten dann ( A ↔ (¬B ∧ ¬C )) , B ↔ ¬A und C ↔ A . Gesucht ist die (hoffentlich einzige) Belegung von A, B, C, die alle drei Fakten wahr macht. Mit Wahrheitstafel ergibt sich: Bea sagt die Wahrheit; Anne und Chris lügen. A W W W W F F F F b)
B W W F F W W F F
C W F W F W F W F
¬B F F W W F F W W
¬C F W F W F W F W
¬B ∧ ¬ C F F F W F F F W
A↔K F F F W W W W F
¬A F F F F W W W W
B ↔ ¬A F F W W W W F F
C↔A W F W F F W F W
Anne sagt: Bea wird als Nächstes lügen. Bea sagt dann: Chris wird als Nächstes lügen. Chris sagt dann: Anna hat gerade gelogen. Wer hat gelogen, wer nicht? Was geht jetzt schief? Ist es nicht so, dass jeder jeweils entweder gelogen oder die Wahrheit gesagt haben muss?
Lösung 16b Mit der obigen Methode stellt sich heraus, dass keine Belegung die Wissensbasis – A ↔ ¬B , B ↔ ¬C und C ↔ ¬A – erfüllt. Man kann auch nicht sagen, dann hätten halt alle gelogen, denn selbst dann müsste die Belegung A, B, C a F die Wissensbasis erfüllen. Mindestens einige der Aussagen sind also weder wahr noch gelogen, sondern unsinnig! Das bekannteste Beispiel dieser Art ist das Lügnerparadoxon „Ich lüge immer“ (oder „Ich lüge eben gerade“, oder ein Kreter sagt: „Alle Kreter lügen immer,“ usw.). Sagt eine Person „Ich sage gerade die Wahrheit“ (IW), dann kann IW sowohl wahr als auch gelogen sein. Die Wissensbasis IW ↔ IW ist mit beiden möglichen Belegungen von IW erfüllt. Solche Probleme treten immer dann auf, wenn sich Aussagen zyklisch auf sich selbst beziehen, sei es direkt oder über andere Aussagen als Zwischenstationen. Sie treten nicht auf, wenn wir stets nur über früher gemachte Aussagen sprechen (aber nicht über gegenwärtige oder zukünftige). Der Aufgabenteil (a) ist nichts als ein Glücksfall, bei dem es gerade mal hinhaut. Zusatzaufgabe: Beurteilen Sie nun den Nutzen von Aussagen wie „Diese Erklärung gebe ich im Vollbesitz meiner geistigen Kräfte, freiwillig und ohne Zwang ab.“ Bernd Baumgarten
Hochschule Darmstadt SS 2016
Logik. Lösungen der Vorlesungs-Aufgaben, Tipps zu Ergänzungsaufgaben, 02.06.2016
kein Tipp zu E7 Syntax/Semantik
17. Boolesche Schaltwerke a) Berechnen Sie mit Formeldarstellung und Wahrheitstafel alle SchalterstellungsKombinationen, bei denen das folgende Schaltwerk leitend verbindet: a
b c b c a b) Können Sie die Schaltung darauf hin vereinfachen?
Lösung 17 a) Entsprechende Formel (vgl.u.): a ∨ b ∨ ¬c ∨ (¬a ∧ c ∧ b) . Wahrheitstafel: a b c ¬c a ∨ b ∨ ¬c ¬a ¬a ∧ c ∧ b (a ∨ b ∨ ¬c) ∨ (¬a ∧ c ∧ b) (vgl.u.) W W W F W F F W W W F W W F F W W F W F W F F W W F F W W F F W F W W F W W W W F W F W W W F W F F W F F W F F F F F W W W F W Also alle Schalterstellungen leiten bis auf: a aus, b aus, c an Erläuterungen und Lösungsweg-Alternativen: Wir haben oben dreifache Kon- und Disjunktionen (UND- bzw. ODER-Ketten) auf einen Schlag (wie dreistellige Junktoren) berechnet. Wenn Ihnen das zu gewagt ist, können Sie die Formel zur gewohnten schematischen Anwendung der Wahrheitstafel noch weiter klammern, so dass Sie beispielsweise mit ((a ∨ b) ∨ ¬c) ∨ ((¬a ∧ c) ∧ b) rechnen. Sie könnten aber auch ein 4-stelliges ODER wagen. Sie erhalten je nach Vorgehen mehr oder weniger Spalten in der Tafel, aber dasselbe Ergebnis. b) Durch Vergleich der fünften mit der letzten Tabellenspalte sehen wir wir, dass a ∨ b ∨ ¬c zur ganzen Formel äquivalent ist. Also können die untere Reihenschaltung komplett weglassen.
Bernd Baumgarten
Hochschule Darmstadt SS 2016
Logik. Lösungen der Vorlesungs-Aufgaben, Tipps zu Ergänzungsaufgaben, 02.06.2016
18. Substitution – Gegenbeispiele & Hintereinanderausführung a) Geben Sie eine passende widerlegbare AL-Formel und eine Substitution an, so dass die Formel durch die Substitution in eine Tautologie überführt wird. Lösung 18 a Beispiel: A∨¬B ist kontingent, insbesondere widerlegbar, keine Tautologie; Substitution [A/B] ergibt die Tautologie B∨¬B. b) Geben Sie eine AL-Formel und eine Substitution für A und eine Substitution für B an, derart dass beide Hintereinanderausführungen der Substitutionen und deren gleichzeitige Ausführung drei Formeln ergeben, von denen keine zwei äquivalent sind.
Lösung 18 b Beispiel: Aus der Formel A∧B wird unter den Substitutionen [A/B] [B/A] die Formel A∧A, unter den Substitutionen [B/A] [A/B] B∧B und unter der gleichzeitigen Substitution [A,B /B,A] die Formel A∧B. Keine zwei dieser drei Formeln sind äquivalent. c) Zeigen Sie: Jede gleichzeitige Substitution an einer Formel ist eine Hintereinanderausführung von Einzelsubstitutionen [ Ai / ϕi ]. Vorsicht: Man kann dazu nicht einfach die gleichzeitigen Ersetzungen der einzelnen Aussagevariablen hintereinanderschalten (Warum?). Tipp: Wie vertauscht man in einem Programm die Werte von a und b?
Lösung 18 c Vorsicht-Antwort (Beispiel): ( A ∨ B )[ A,B / B , A] ⇔ / ( A ∨ B )[ A / B ][ B / A]
Tipp-Antwort: Man verwendet dazwischen eine „neutrale“ Variable, z.B. c: c:=a; a:=b; b:=c. Zeige-Antwort: Es sei ϕ eine AL-Formel, und es seien die Aussagevariablen Q1 , K , Qn verschieden • voneinander, • von allen P1 , K , Pn , • von allen Aussagevariablen in ϕ und ψ 1 , K , ψ n . Dann ist ϕ [ P1 ,K, Pn / ψ 1 ,K,ψ n ] ⇔ ϕ [ P1 / Q1 ]K[ Pn / Qn ] [Q1 / ψ 1 ]K[Qn / ψ n ] . „Leider“ hängt die Aufspaltung in Einzelsubstitutionen mit von der bearbeiteten Formel ϕ ab.
Bernd Baumgarten
Hochschule Darmstadt SS 2016
Logik. Lösungen der Vorlesungs-Aufgaben, Tipps zu Ergänzungsaufgaben, 02.06.2016 d) Die Hintereinanderausführung zweier Substitutionen ist wieder eine (gleichzeitige) Substitution – welche? Lösung 18 d Welche Substitution ρ leistet das Gleiche wie die (Hintereinanderausführung der) Substitution σ = [ P1,K , Pm / ψ 1, K ,ψ m ] , gefolgt von der Substitution τ = [Q1, K, Qn / π1, K , π n ] ,
so dass für alle AL-Formeln ϕ gilt: (ϕσ )τ = ϕ ρ ? Zunächst brauchen wir die Qi , die bei σ nicht ersetzt werden; sagen wir es seien k von diesen mit 0 ≤ k ≤ n . Sei also {Qi1 , K , Qik } := {Q1, K , Qn } \ {P1, K , Pm } . Diese bleiben aus ϕ erhalten und werden erst in ϕσ gemäß τ ersetzt. Dann ist ρ = [ P1,K, Pm , Qi1 ,K, Qik /(ψ 1 )τ ,K, (ψ m )τ , π i1 ,K, π ik ] , denn die eingesetzten ψ i sind gemäß τ weiter zu verändern, und die Q j unter den Pi sind bereits von σ durch ihre ψ j ersetzt worden. Beispiel: ( A ∧ ( B ∧ C ))[ A, B / A∨ C ,C → B ][ B ,C / C → A, D ] =
( ( A ∨ C ) ∧ ((C → B ) ∧ C )[ B ,C / C → A, D ]
= =
( (( A ∨ D ) ∧ (( D → (C → A)) ∧ D ) ( A ∧ ( B ∧ C ))[ A, B ,C / A∨ D, D →(C → A), D ]
=
( A ∧ ( B ∧ C ))[ A, B ,C /( A∨C )[ B ,C / C → A, D ] ,(C → B )[ B ,C / C → A, D ] , D ]
Bernd Baumgarten
Hochschule Darmstadt SS 2016
Logik. Lösungen der Vorlesungs-Aufgaben, Tipps zu Ergänzungsaufgaben, 02.06.2016 19. Junktorenbasen a) Suchen Sie über den Basen {¬, ∧, ∨} und {¬, ∧} jeweils eine möglichst einfache Formel für P → (¬Q → ¬P ) . b) Suchen Sie über der Basis {¬, →} eine möglichst einfache Formel für P ∧ Q und für P ∨ Q. Lösung 19
a) Die Wahrheitstafel liefert P Q W W W F F W F F
P → (¬ Q → ¬ P ) W F W W
usw.
Über die W-Zeilen erhalten wir ( P ∧ Q ) ∨ (¬P ∧ Q ) ∨ (¬P ∧ ¬Q ). Mit ODER-Ersetzung A ∨ B ≡ ¬(¬A ∧ ¬B ) könnten wir diese Formel in eine längere über {¬, ∧} äquivalent umformen (üben!). Aus der F-Zeile erhalten wir übrigens schneller und kürzer: ¬( P ∧ ¬Q ). Mit syntaktischer Umformung nach KNF können wir wiederum zu ¬P ∨ Q gelangen. b) P ∨ Q ¬P → Q bzw. ¬Q → P Wie kommt man drauf? Z.B. über P → Q ¬P ∨ Q ! P ∧ Q ¬( P → ¬Q ) Wie kommt man drauf? Z.B. über P ∧ Q ¬(¬P ∨ ¬Q ) und das erste Ergebnis! Beide Antworten überprüft man z.B. per Wahrheitstafel. kein Tipp zu E8 20. ITE-Form erzeugen Bestimmen Sie durch Shannon-Expansionen – und zwar ganz schematisch zuerst nach A und dann nach B – eine ITE-Form von ( B → A) ∧ ( A ∨ B ) . Lösung 20
Expansion nach A: ( B → A) ∧ ( A ∨ B ) ≡ A → (( B → T ) ∧ (T ∨ B )) /(( B →⊥) ∧ (⊥ ∨ B )) weitere Expansion nach B:
≡ B → [ A → ((T → T ) ∧ (T ∨ T)) / ((T → ⊥) ∧ (⊥ ∨ T))] /
[ A → ((⊥ → T ) ∧ (T ∨ ⊥)) / (( ⊥ → ⊥) ∧ (⊥ ∨ ⊥))]
Nach Auswertung der konstanten Teilformeln: ≡ B → [ A → T / ⊥] / [ A → T / ⊥] Ergänzungsfrage: Fällt Ihnen dazu eine kürzere äqivalente ITE-Form ein?
Bernd Baumgarten
Hochschule Darmstadt SS 2016
Logik. Lösungen der Vorlesungs-Aufgaben, Tipps zu Ergänzungsaufgaben, 02.06.2016 21. Folgerungen aus Formelmengen Welche der folgenden Folgerungen sind korrekt? Belegen Sie Ihre Antwort mit Wahrheitstafeln. a) { A ∨ B, B → A} |= A Lösung 21a
A B W W W F F W F F
B→A W W F W
A∨ B W W W F
Wo |= Formelmenge? hier hier
und dort |= A? ja ja
Folgerung korrekt b) {( A ∨ B ) → A, A → ( A ∨ B )} |= ¬( A ∧ ¬B ) Lösung 21b
A W W F F
B A ∨ B ( A ∨ B ) → A A → ( A ∨ B ) Wo |= FM? ¬B A ∧ ¬B ¬( A ∧ ¬B) W W hier F F W W W F W hier W W W W F W W F W F F W F F hier W F W W W
keine Folgerung KNF und Resolution 22. Konjunktive Normalform verwenden Welche der folgenden KNF-Formeln sind allgemeingültig? a) ( B ∨ C ∨ ¬C ) ∧ ( A ∨ B ∨ A) ∧ (¬A ∨ C ∨ A) b) {{ A, B, ¬A}, {}}KNF
c) {{ A, B, ¬A}, {¬C , C}, {¬B, B, C}}KNF Lösung 22:
Enthält jede Klausel eine Aussagevariable und ihre Negation? (a) nein (2. Klausel ist F unter Belegung „A:=B:=F“) (b) nein (Leere Klausel ist sogar stets F) (c) ja
Bernd Baumgarten
Hochschule Darmstadt SS 2016
Logik. Lösungen der Vorlesungs-Aufgaben, Tipps zu Ergänzungsaufgaben, 02.06.2016 23. Konjunktive Normalform erzeugen Bringen Sie ¬( A → ( B ∨ C )) in KNF-Form mittels a) Synthese aus Wahrheitstafel (KNF1) Lösung 23a:
A W W W W F F F F
B W W F F W W F F
C W F W F W F W F
Die Lösung gemäß KNF1 umfasst 21 Literale (7 Zeilen à 3, s.u.). Mit einer guten Idee (s. Pfeilbox unten) geht es hier sogar mit nur 3! B∨C W W W F W W W F
A → (B ∨ C) W W W F W W W W
¬( A → ( B ∨ C )) F F F W F F F F
( ¬A ∨ ¬ B ∨ ¬C ) ∧ ( ¬A ∨ ¬ B ∨ C ) ∧ M
A ∧ ¬B ∧ ¬C (kürzer: M M M ( A ∨ B ∨ C)
Dualkl. ist KNF + DNF!)
b) Formel-Umbau (KNF2): Lösung 23b
Ausgangsformel Elimination von Äquivalenz und Implikation Negation näher zu den AV’n Doppelnegation beseitigen Negation näher zu den AV’n Klammern weglassen
Bernd Baumgarten
¬( A → ( B ∨ C )) ¬(¬A ∨ ( B ∨ C )) ¬¬A ∧ ¬( B ∨ C ) A ∧ ¬( B ∨ C ) A ∧ (¬B ∧ ¬C ) A ∧ ¬B ∧ ¬C
Hochschule Darmstadt SS 2016
Logik. Lösungen der Vorlesungs-Aufgaben, Tipps zu Ergänzungsaufgaben, 02.06.2016 24. KNF-Umformung und Resolution anwenden a) Formen Sie ¬(( A → B) → ((C → A) → (C → B)) ) in KNF um. Lösung 24a Wir formen hier im Wesentlichen nach den „syntaktischen Umformungsegeln“ um, verwenden aber auch als „Makro“ eine andere Tautologie, die uns rascher voranbringt: Das Makro „Wann ist eine Implikation falsch?“ besteht aus drei Schritten hintereinander: ¬( P → Q) Ausgangsformel Implikationen eliminieren ¬(¬P ∨ Q) Negation näher zu den AV’n ¬¬P ∧ ¬Q P ∧ ¬Q Doppelnegation beseitigen
Ausgangsformel Wann ist eine Implikation falsch? … und nochmal … und nochmal Implikationen eliminieren entbehrliche Klammern weg ist KNF, anders geschrieben auch:
¬(( A → B) → ((C → A) → (C → B)) ) ( A → B) ∧ ¬((C → A) → (C → B )) ( A → B) ∧ ((C → A) ∧ ¬(C → B )) ( A → B) ∧ ((C → A) ∧ (C ∧ ¬B )) (¬A ∨ B ) ∧ ((¬C ∨ A) ∧ (C ∧ ¬B)) (¬A ∨ B ) ∧ (¬C ∨ A) ∧ C ∧ ¬B {{¬A, B}, {¬C , A}, {C}, {¬B}}KNF
Umformungs-Makros müssen natürlich nicht sein; es geht auch „normal“ mit KNF2 (das wurde in der Vorlesung vorgeführt) bzw. mit Wahrheitstafel (KNF1).
Bernd Baumgarten
Hochschule Darmstadt SS 2016
Logik. Lösungen der Vorlesungs-Aufgaben, Tipps zu Ergänzungsaufgaben, 02.06.2016 b) Entscheiden Sie mittels Resolution, ob ( A → B ) → ((C → A) → (C → B )) allgemeingültig ist. Verwenden Sie Teil (a). Lösung 24b ( A → B ) → ((C → A) → (C → B )) ist genau dann allgemeingültig, wenn die Negation unerfüllbar ist. ¬(( A → B) → ((C → A) → (C → B)) ) ist genau dann unerfüllbar, wenn aus einer seiner KNF-Formen (z.B. nach (a) {{¬A, B}, {¬C , A}, {C}, {¬B}}KNF ) per Resolution die leere Klausel erzeugbar ist. Resolution: {¬B} {¬A, B} {¬C , A} {C}
{¬A} {¬C} {} Also ist {{¬A, B}, {¬C , A}, {C}, {¬B}}KNF unerfüllbar und ( A → B ) → ((C → A) → (C → B )) tatsächlich Tautologie. Bemerkung: Natürlich können Sie auch ( A → B ) → ((C → A) → (C → B )) in eine äquivalente KNFFormel verwandeln (nicht ganz ohne Mühe), an der sie die Allgemeingültigkeit dann unmittelbar ablesen können (siehe P-¬P-Paare in allen Klauseln). ( A → B ) → ((C → A) → (C → B )) z.B. alle Implikationen auf einmal auflösen ¬(¬A ∨ B) ∨ (¬(¬C ∨ A) ∨ (¬C ∨ B) ) ¬(...∨...) auflösen, ¬¬ weg (A ∧ ¬B) ∨ ( (C ∧ ¬A) ∨ (¬C ∨ B) ) Distributivität von rechts (A ∨ [ (C ∧ ¬A) ∨ (¬C ∨ B) ] ) ∧ ( ¬B ∨ [ (C ∧ ¬A) ∨ (¬C v B) ] ) … und noch 2x (A ∨ [ (C∨ (¬C∨B)) ∧ (¬Av(¬C∨B)) ] ∧ ¬B ∨ [ (C∨ (¬C∨B)) ∧ (¬A∨ (¬C∨B)) ] … und noch 2x von links (A∨C∨¬C∨B) ∧ (A∨¬A∨¬C∨B) ∧ (¬B∨C∨¬C∨B) ∧ (¬B∨¬A∨¬C∨B)
25. Disjunktive Normalform verwenden Welche der folgenden DNF-Formeln sind erfüllbar, welche sind unerfüllbar, welche allgemeingültig? a) ( B ∧ C ∧ ¬C ) ∨ ( A ∧ B ∧ ¬A) ∨ (¬A ∧ C ∧ A) b) {{ A, B, ¬A}, {}}DNF
c) {{ A, B, ¬A}, {¬C , C}, {¬B, C}}DNF Lösung 25:
Enthält jede Dualklausel eine Aussagevariable und ihre Negation? (a) ja (also unerfüllbar) (b) nein(also erfüllbar). Leere Dualklausel ist stets W: allgemeingültig (c) nein (also erfüllbar)
Bernd Baumgarten
Hochschule Darmstadt SS 2016
Logik. Lösungen der Vorlesungs-Aufgaben, Tipps zu Ergänzungsaufgaben, 02.06.2016 26. Tableaux a) Zeichnen Sie einen Tableau-Baum für A → (C ∨ ¬A) , geben Sie eine äquivalente DNF-Formel und alle Modelle (über A und C) an. Wo hätten Sie aufhören können, wenn Sie nur die Erfüllbarkeit hätten prüfen wollen? b) Zeichnen Sie einen Tableau-Baum für ( A ∧ ¬B ) → ( B → ( A ∨ C )) . c) Zeichnen Sie einen Tableau-Baum für ( A ∧ ¬B ) ↔ ( B → ( A ∨ C )) . Lösung 26a
A → (C ∨ ¬A)) ¬A ○
C ∨ ¬A ¬A
C
Die Erfüllbarkeit ist klar bei ○ (erstes offenes Blatt). DNF (nach Rezept): ¬A ∨ C ∨ ¬A bzw. {{¬A}, {C}} DNF . 3 Modelle: A C (+ alle Oberbelegungen, d.h. mit weiteren Variablen) W W F W F F 26b ( A ∧ ¬B ) → ( B → ( A ∨ C )) ¬( A ∧ ¬B ) ¬A
¬¬B
B → ( A ∨ C) ¬B
A∨ C
B A C (also äquivalent zu ¬A ∨ B ∨ ¬B ∨ A ∨ C , erfüllbar, sogar allgemeingültig) 26c Beispiellösung, leicht abgekürztes Tableau: Erkennung von Widersprüchen bereits zwischen Formeln (1) ( A ∧ ¬B ) ↔ ( B → ( A ∨ C )) (2) [von 1] ( B → ( A ∨ C )) → ( A ∧ ¬B ) (3) [1] ( A ∧ ¬B ) → ( B → ( A ∨ C )) (4) [3] ¬( A ∧ ¬B )
(5) [3] B → ( A ∨ C )
(6) ¬( B → ( A ∨ C )) (7) A ∧ ¬B (8) ¬( B → ( A ∨ C )) (9) A ∧ ¬B [ alle von 2] B [6] A [9] (10) ¬( A ∨ C ) [6] ¬B [9] ¬A [10] ¬C [10] ¬B (11)[5] A ∨ C ¬A [4]
¬¬B [4] A [11] C [11] B (also – nach Streichung doppelter Literale in Dualklauseln sowie doppelter Dualklauseln – äquivalent zu (¬A ∧ B ∧ ¬C ) ∨ ( A ∧ ¬B ) ∨ ( A ∧ ¬B ∧ C ) , somit erfüllbar, widerlegbar und kontingent. (¬A ∧ B ∧ ¬C ) ∨ ( A ∧ ¬B ) reicht sogar. (Warum?) Bernd Baumgarten
Hochschule Darmstadt SS 2016
Logik. Lösungen der Vorlesungs-Aufgaben, Tipps zu Ergänzungsaufgaben, 02.06.2016 27. Tableaux a) Verwenden Sie das Tableauverfahren, um die Erfüllbarkeit der Formelmenge { A → B, ¬C → ¬B, ¬C ∨ A} zu beweisen. b) „Verallgemeinern“ Sie das Tableauverfahren auf endliche Formelmengen anstelle einer Formel so, dass Sie gegenüber (a) eine Ebene im Baum einsparen. Lösung 27a { A → B, ¬C → ¬B, ¬C ∨ A} ist erfüllbar ⇔ ( A → B ) ∧ (¬C → ¬B ) ∧ (¬C ∨ A) ist erfüllbar.
( A → B) ∧ ((¬C → ¬B ) ∧ (¬C ∨ A)) A→ B (¬C → ¬B ) ∧ (¬C ∨ A) ¬C → ¬B ¬C ∨ A
(1) (2) (3) (4) (5)
(6) ¬A (8) ¬¬C (12) C
(9) ¬B
(7) B (10) ¬¬C
(von 1) (von 1) (von 3) (von 3) (von 2)
(11) ¬B
(von 4) (von 8)
etc. (13) ¬C
(14) A
(15) ¬C
(16) A
(von 5)
Lösung 27b Formeln der Menge direkt als Wurzel, deren einziges Kind, einziger Enkel etc. hinschreiben (s.o.: 2, 4, 5). (1) und (3) entfallen dann. Einzelne Formel ist „Spezialfall“ als einelementige Menge.
Tipps zu E9 Wählen Sie anstelle von 12 Aussagevariablen wie z.B. • Db = David wohnt in Berlin. wegen der binären Alternative Berlin/Kiel einfach nur 6 Aussagevariablen wie z.B. • D = David wohnt in Berlin (ergo: ¬D = David wohnt in Kiel). Damit entfällt auch die explizite Angabe der 6 strikten Alternativen (z.B. „entweder Db oder Dk“) in der Wissensbasis. Schreiben Sie die Wissensbasis im Tableau-Stil, d.h. untereinander, also mit UND verknüpft. Vorschlag (Geschmackssache!): Machen Sie dann etwa wie im Tableauverfahren weiter, nur dröseln Sie nicht alle ODERAlternativen auf bis unter großer Verzweigung nur noch Literale „übrig bleiben“. Sondern verarbeiten Sie mit möglichst wenigen ODER-Verzweigungen unter Ausnutzung einfacher Folgerungsmuster jeweils ein Literal mit einer Aussage, um ein weiteres Literal (oder zumindest eine kürzere Formel) abzuleiten, das Sie mit UND anhängen. Sobald Sie auf einem Zweig eine ausreichende Belegung ohne offensichtlichen Widerspruch (X UND ¬X ) erzielt haben, machen Sie die Probe: • •
Ist die Belegung ein Modell für die Wissensbasis? Dann ist sie eine Lösung. Ist sie kein Modell? Dann können Sie aus der Belegung und der Wissensbasis auch einen offensichtlichen Widerspruch herleiten, und diese Belegung ist keine Lösung.
Bernd Baumgarten
Hochschule Darmstadt SS 2016
Logik. Lösungen der Vorlesungs-Aufgaben, Tipps zu Ergänzungsaufgaben, 02.06.2016 28. Markierungsalgorithmus Beweisen Sie mit dem Markierungsalgorithmus die Gültigkeit der Aussage „Wenn ich Zeit habe, gehe ich einen Kaffee trinken.“ unter der Annahme der folgenden Wissensbasis: Wenn ich Sicherheit bekomme, schreibe ich eine gute Klausur. Wenn ich mir Mühe gebe, dann bearbeite ich die Aufgaben und lese im Skript. Wenn ich Zeit habe, gebe ich mir Mühe. Wenn ich im Skript lese, kann ich die Aufgaben lösen. Wenn ich eine gute Klausur schreibe, gehe ich einen Kaffee trinken. Wenn ich die Aufgaben bearbeite und sie lösen kann, bekomme ich Sicherheit. Tipp: Regeln s.o. – Fakt: Ich habe Zeit – Ziel: Ich gehe Kaffee trinken Lösung 28 Markieren Sie in der gezeigten Reihenfolge.
Zeit 1
leSkript
Mühe 1
2
3
2
3
beAufg
Kaffee 4
3
7
löAufg 5
7
4
Sicher
guKlau 6
5
6
29. Binary Decision Diagram Bestimmen Sie über (z.B. eine ITE-Form und) eine OBDD-Darstellung und anschließende Reduktion einen ROBDD für ( B → A) ∧ ( A ∨ B ) . Lesen Sie aus dem ROBDD eine zu der ursprünglichen Formel äquivalente aber kürzere Formel heraus. Lösung 29 Eine ITE-Umwandlung ergibt B → ( A → T / ⊥) /( A → T / ⊥) , vgl. Übung 16.
B OBDD:
B
A
A
W
F
Verschm.
Überspr.
A W
= ROBDD v. A .
A
F
W
F
Eine andere ITE-Umwandlung ergibt z.B. A → ( B → T / T ) /( B →⊥ / ⊥) . A OBDD:
A
B
B
W
F
Bernd Baumgarten
2× Überspringen
= W
s.o.
F Hochschule Darmstadt SS 2016
Logik. Lösungen der Vorlesungs-Aufgaben, Tipps zu Ergänzungsaufgaben, 02.06.2016
30. AL-Kalküle Ergänzen Sie im folgenden Beweis (im Mendelson-Kalkül) von { A → B, B → C} |− A → C die „Begründungen“, d.h. • „Gegeben “ oder • „Axiom“ oder • Regel (MP) oder Substitution + Formel-Nummern ihrer Prämissen. 1. A → B ....................... 2. B → C ....................... 3. ( A → ( B → C )) → (( A → B ) → ( A → C )) ....................... 4. A → ( B → A) ....................... (4), ................ 5. ( B → C ) → ( A → ( B → C )) 6. A → ( B → C ) ....................... ....................... 7. ( A → B ) → ( A → C ) 8. A → C ....................... Lösung 30 1. A → B 2. B → C 3. ( A → ( B → C )) → (( A → B ) → ( A → C )) 4. A → ( B → A) 5. ( B → C ) → ( A → ( B → C )) 6. A → ( B → C ) 7. ( A → B ) → ( A → C ) 8. A → C
Gegeben Gegeben Axiom Axiom (4), [A,B/ B → C ,A] (2,5) MP (3,6) MP (1,7) MP
„Eigentlich“ bilden 4.+ 5. zusammen einen Schritt. Er ist zwecks Nachvollziehbarkeit in zwei Teilschritte zerlegt. Substitution ist nur bei Axiomen und Regeln (und Tautologien, aber das gehört nicht zum Kalkül) erlaubt, nicht aber bei beliebigen aus einer Prämissenmenge hergeleiteten Formeln. Wie in (5) ist sie also OK. Auf andere dürften wir sie nicht anwenden. Wir dürften „notfalls“ in Tautologie (5) substituieren, was aber nicht zum eigentlichen Kalkül gehört.
Bernd Baumgarten
Hochschule Darmstadt SS 2016
Logik. Lösungen der Vorlesungs-Aufgaben, Tipps zu Ergänzungsaufgaben, 02.06.2016 31. Werkzeugkasten Leiten Sie Nr. (a) und (i) der folgenden „Kleene-Axiome“ als Tautologien her.
a)
A → ( B → A)
( A → B ) → (( A → ¬B ) → ¬A)
i)
Lösung 31
1. 2. 3. 4. 5.
1. 2. 3. 4. 5. 6. 7. 8. 9.
Zeige ( A → ( B → A)) | A | Zeige B → A | | B | | A | B→A ( A → ( B → A)) Zeige ( A → B ) → (( A → ¬B ) → ¬A) | A→B | Zeige ( A → ¬B ) → ¬A | | A → ¬B | | Zeige ¬A | | | A ¬B | | | | | | B | | | ⊥ | | ¬A | (( A → ¬B ) → ¬A) ( A → B ) → (( A → ¬B ) → ¬A)
Bernd Baumgarten
Ann Ann Wdh BB BB
Ann Ann Ann MP,2,3 MP,1,3 WE,4,5 IB2 BB BB
Hochschule Darmstadt SS 2016
Logik. Lösungen der Vorlesungs-Aufgaben, Tipps zu Ergänzungsaufgaben, 02.06.2016 32. Werkzeugkasten Leiten Sie Nr. (c) der folgenden Folgerungen ab.
c) { ¬A ∨ B, ¬B, A ∨ C } |= C Lösung 32
¬A ∨ B ¬B A∨C Zeige C 4. | ¬A 5. | C 6. C 1. 2. 3.
Kurzversion: 1. ¬A ∨ B 2. ¬B 3. A ∨ C Zeige C 4. | ¬A 5. C
Geg. Geg. Geg. OB1,1,2 OB1,3,4 DB
Geg. Geg. Geg. OB1,1,2 OB1,3,4 DB
33. Craigs Interpolationssatz (evtl. später) Es seien ϕ = ¬( A ∧ B ) → (¬C ∧ B ) und ψ = ( D → A) ∨ ( D → ¬C ) . a) Verwenden Sie ¬P → Q ≡ P ∨ Q und ein Distributivgesetz, um eine möglichst kurze KNF für ϕ zu finden. b) Verwenden Sie (a) und ( P ∨ Q) ∧ S |= ( R → P) ∨ ( R → Q) , um ϕ |= ψ zu beweisen. c) Identifizieren Sie ein interpolierendes π für die Folgerung ϕ |= ψ . Lösung 33a Subst. [ P, Q / A ∧ B, ¬C ∧ B ] ¬( A ∧ B ) → (¬C ∧ B ) ≡ ( A ∧ B ) ∨ (¬C ∧ B ) ≡ ( A ∨ ¬C ) ∧ B KNF! Lösung 33b Subst. [ P, Q, R, S / A, ¬C , D, B ]
ϕ |= ψ
Lösung 33c π↓ ¬( A ∧ B ) → (¬C ∧ B ) |= A ∨ ¬C |= ( D → A) ∨ ( D → ¬C )
Bernd Baumgarten
Hochschule Darmstadt SS 2016
Logik. Lösungen der Vorlesungs-Aufgaben, Tipps zu Ergänzungsaufgaben, 02.06.2016 34. Gültigkeit von ML-Formeln in Kripke-Strukturen
Im Kripke-Rahmen und der Belegung wie rechts, mit welchen Welten als Anfangssituation gilt die Formel A∧
1
2
A
A,B
A,C
C
(A ∧¬C) ?
Tipp: gehen Sie ähnlich wie bei der Wahrheitstafel vor!
3
4
Lösung 34 Um nicht bei der Auswertung der Modaloperatoren und immer wieder auf den Graphen sehen zu müssen, tragen wir zu den Knotennummern des Graphen in Klammern die Nummern der unmittelbaren Nachfolgeknoten ein:
A C ¬C A ∧¬C A A (A ∧¬C) (A ∧¬C) A∧ (A ∧¬C) Wert von
1 (2,3) 1 0 1 1 1 0 1 0 0
2 (4) 1 0 1 1 0 1 0 1 1
3 (4) 1 1 0 0 0 1 0 1 1
4 (1,3) 0 1 0 0 1 1 1 0 0
: erfordert Suche in den Folgeknoten, z.B. A in Spalte k: Gilt in allen Nachfolgerwelten von k die Aussage A?
Bernd Baumgarten
Hochschule Darmstadt SS 2016
Logik. Lösungen der Vorlesungs-Aufgaben, Tipps zu Ergänzungsaufgaben, 02.06.2016 35. ML-Formeln und Modelle In einer Tic-Tac-Toe-Variante TTTV werden abwechselnd von SpielerIn U Kreuze und von SpielerIn I Kreise in die noch freien Felder eines anfangs leeren 3x3-Spielfeldes gesetzt. U beginnt. Das Spiel ist beendet, • sobald I oder U sein/ihr Zeichen in drei Felder auf einer Geraden (also Zeile, Spalte oder Diagonale) gesetzt (und dadurch gewonnen) hat, oder • wenn kein Feld mehr frei ist. Verloren hat, wer nicht mehr ziehen darf bzw. kann.
a) Stellen Sie folgende Teile einer Kripke-Interpretation (mit Anf.) für das Spiel TTTV graphisch dar: • die Anfangssituation plus alle in einem Zug sowie fünf in zwei Zügen erreichbare Situationen, • eine Endsituation mangels freier Felder plus alle (um 1 Zug) vorangehenden Situationen, • eine Endsituation wegen erreichter geradliniger Gewinnkonstellation plus alle (um 1 Zug) vorangehenden Situationen. (jeweils einschließlich Erreichbarkeitspfeilen für Züge zwischen diesen Situationen) Identifizieren Sie dabei Stellungen, die sich nur um Drehung oder Spiegelung voneinander unterscheiden, und stellen Sie jeweils nur eine davon dar: =
=
Lösung 35a Anfang
ein Ende da voll
ein Ende durch Gewinnreihe
Bernd Baumgarten
Hochschule Darmstadt SS 2016
Logik. Lösungen der Vorlesungs-Aufgaben, Tipps zu Ergänzungsaufgaben, 02.06.2016 b) Schreiben Sie je eine ML-Formel – und jeweils 1 TTTV-Situation, für die die Formel gilt – für … • Dies ist eine Endsituation. • Der Spieler am Zug muss mit diesem nächsten Zug gewinnen. • Der Spieler am Zug kann, muss aber nicht, mit diesem nächsten Zug gewinnen. • Der Spieler am Zug kann diesen nächsten Zug so setzen, dass er mit seinem übernächsten Zug gewinnen kann, egal wie der Gegner dazwischen zieht. Tipps: Verwenden Sie den Top-Bottom-Dialekt der AL. Was bedeutet ⊥ (bzw. ⊥, T , T)? Lösung 35b Tipp:
⊥ : Es gibt keine Nachfolger. ⊥≡ ⊥ T≡ T T: Es gibt mind. 1 Nachfolger.
Endsituation:
Formel: ⊥,
Muss gewinnen:
Formel:
⊥∧ T ,
Kann, muss nicht gewinnen
Formel:
⊥∧
Kann so setzen, dass mit übern. Zug gewinnt:
Formel:
Situation: 2 Ende-Bsp. s.o.
⊥∧
Situation: 3 Bsp. s.o. (vor Voll-Ende) T,
Situation:
T, Situation:
Die Teilformeln hinter „und“ sorgen dafür, dass die nächste Box nicht deswegen erfüllt ist, weil es keine Nachfolger gibt.
Bernd Baumgarten
Hochschule Darmstadt SS 2016
Logik. Lösungen der Vorlesungs-Aufgaben, Tipps zu Ergänzungsaufgaben, 02.06.2016 36. ML-Rahmeneigenschaften und Axiome
a) Welche Rahmen werden durch das ML-Axiom
A→
A gekennzeichnet?
Lösung 36a unverzweigt/rechtseindeutig, d.h. ∀u , v, w ∈ K : (( wRu ∧ wRv) → u = v) Annahme: A → A gilt. Hätte ein Knoten mehrere Nachfolger, könnte man genau einen mit A belegen, und dann wäre A richtig und A falsch. Also rechtseindeutig. Annahme rechtseindeutig. Dann natürlich A → A („Kennste einen, kennste alle.“)
b) Wir nennen einen ML-Rahmen Rah=(K,R) euklidisch, wenn ∀u , v, w ∈ K : ((wRu ∧ wRv) → uRv) . Geben sie eine ML-Formel ϕ an, für die gilt: Genau dann ist ein ML-Rahmen euklidisch, wenn ϕ Axiom ist, d.h. wenn für jeden Anfangsknoten Anf und jede K-Belegung Bel jede Substitution von ϕ in (Rah,Bel,Anf) gilt. Lösung 36b A→ A Annahme A → A gilt. Hätte ein Knoten k Nachfolger, die nicht alle in Relation R stehen, dann gäbe es zwei davon, l und m, mit ¬lRm. Wir könnten m mit A belegen und alle Nachfolger von l nicht. Dann wäre in k A richtig (da m |= A) und A falsch (da nicht l |= A). Annahme euklidisch. Gilt A, so erfüllt ein Nachfolger l des aktuellen Knotens k A und ist Nachfolger aller Nachfolger von k, so dass in k gilt: A.
c) Welche Rahmen werden durch das ML-Axiom ¬( A∧ ¬A) gekennzeichnet? Lösung 36c ¬( A∧ ¬A) ist äquivalent zu
¬( A ∧
¬A) ≡ ¬
A → A, denn A∨¬
¬ A ∨ ¬ ¬A ≡ ¬ A ∨ ¬
A∨
A
≡
A→
¬A A
A
– also siehe (a)!
Bernd Baumgarten
Hochschule Darmstadt SS 2016
Logik. Lösungen der Vorlesungs-Aufgaben, Tipps zu Ergänzungsaufgaben, 02.06.2016 37. Zusammenhänge zwischen Temporaloperatoren
Drücken Sie die zusätzlichen Temporaloperatoren R,W, Op1, Op2, Op3 möglichst einfach (mittels AL-Junktoren) durch die Standardoperatoren aus – und umgekehrt die Standardoperatoren (außer X) durch die zusätzlichen. Lösung 37 • φWψ • φRψ
= (φUψ) ∨ Gφ = (ψU(φ∧ψ)) ∨ Gψ = ¬(¬φU¬ψ)
• Op1φ
= GFφ
• Op2φ • Op3φ
= GF¬φ = ¬FGφ = G¬φ = ¬Fφ
• Gφ
= ⊥Rφ
• Fφ • φUψ
= ¬(⊥R¬φ) = Fψ ∧ (φWψ) = ¬(¬φR¬ψ)
klar klar (Begründung etwas langwierig, gut für lange Winterabende) endl. viele ⇒ nach dem letzten Knoten mit φ wird Fφ falsch dito mit ¬φ; Dualismus nie = für immer nicht; Dualismus ⊥ kann nie kommen, also darf φ nie „abgelöst“ (unwahr) werden da Fφ =¬G¬φ klar (folgt leicht aus dem Winterabendergebnis)
38. PLTL-Formeln, Büchi-Automaten und ω-reguläre Ausdrücke
a) Bestimmen Sie zu folgendem Büchi-Automaten a
b b a
(i) eine PLTL-Formel (ii) einen ω-regulären Ausdruck „mit denselben Sprachen“ – beide jeweils möglichst kurz. Lösung 38a: informell: immer wieder mal b (denn nur mit b kommt man immer wieder in den Zielzustand) (i) GFb (und stets aXORb, d.h. z.B. G(a↔¬b)) (ii) (a*b)ω
Bernd Baumgarten
Hochschule Darmstadt SS 2016
Logik. Lösungen der Vorlesungs-Aufgaben, Tipps zu Ergänzungsaufgaben, 02.06.2016 ω
b) Bestimmen Sie zu dem ω-regulären Ausdruck a*b(a|b) (i) einen Büchi-Automaten (ii) eine PLTL-Formel „mit denselben Sprachen“ – beide jeweils möglichst kurz/einfach. Lösung 38b: informell: mindestens einmal b (denn nur mit b kommt man erstmals in den Zielzustand, wo man dann bleibt) (i) a a,b
b
(ii)
Fb (und stets aXORb)
c) Bestimmen Sie zu der PLTL-Formel B ∧ G[A ∧ (B→X¬B) ∧ (¬B→XB)] ∧ FC über den AL-Variablen A,B, C (i) einen Büchi-Automaten (ii) einen ω-regulären Ausdruck „mit denselben Sprachen“ – beide jeweils möglichst kurz/einfach. Lösung 38c: (i)
informell: ABC
AB
A, AC
A AC
(ii)
AB, ABC
• • • •
A immer. B und nicht B wechseln ab. Irgendwann soll man (mit C) in einen der rechten Zustände; ab dann ist C oder nicht C egal. Alternativ oder zusätzlich könnte rechts oben Zielzustand sein.
[Wir schreiben kurz AB°ABC für {A,B}{A,B,C} (und ähnlich)] ω (AB°A)* ° [ABC | AB°AC° (AB|ABC)] ° [(A|AC) ° (AB|ABC)]
Bernd Baumgarten
Hochschule Darmstadt SS 2016
Logik. Lösungen der Vorlesungs-Aufgaben, Tipps zu Ergänzungsaufgaben, 02.06.2016
39. Freie und gebundene Variablen + Lösung • Unterstreichen Sie sämtliche freien Variablenvorkommen. • Zeichen Sie von jedem gebundenen Variablenvorkommen aus einen Pfeil zu der Quantifizierung, die es bindet.
∀x∃y ( R ( x, y ) → ( P ( x) ∨ Q( y, x)))
∀x( P ( x) → ∀yQ( x, y ))
∀x ∃y ( R ( x, y )) → ( P ( x) ∨ Q( y, x))
∀x P ( x) → ∀yQ( x, y )
∀x( P ( x) → Q( x, y ))
∀x( P ( x) → ∀x Q( x, y ))
40. Auswertung von konstanten PL1-Termen und -Formeln Werten Sie in der Struktur ABsp aus:
a) die Terme c, f (c) und f ( f ( f (c))) ; b) die Formeln P ( f (c), f (c)) , P (c, f (c)) und P ( f (c), c) → P (c, c) . Lösung 40 a) l, m, n; b) Pfad m
m? – W, Pfad l
m? – F,
(⊥→T)? – W.
41. Auswertung von PL1-Termen und –Formeln mit Variablen Werten Sie in der Interpretation (ABsp,IV) mit IV(x) = IV(y) = l aus:
a) P ( x, y ) ; b) ∃yP ( x, y ) d) ∀xP ( x, y )
c) ∀x∃yP ( x, y ) ; e) ∃y∀xP( x, y ) ;
Lösung 41
a) P ( x, y ) : Leerer Kantenzug von l nach l, daher: b) ∃yP ( x, y ) : Da für IV(x) = l ∃yP ( x, y ) wahr mit IV(y) = l: c) ∀x∃yP ( x, y ) : ∃yP ( x, y ) stimmt wegen P(x,x) nicht nur für IV(x) = l , sondern auch IV(x) = k, m, n, also: d) ∀xP ( x, y ) : Kein Kantenzug von m oder n nach l, also e) ∃y∀xP( x, y ) : Aber mit IV(y) = n ex. für IV(x) = k, l, m, n ein Kantenzug von IV(x) nach IV(y), also
W W W F W
Wir können auch wegen des endlichen Universums eine Tabelle der Paare ab erstellen, für die P ( x, y ) gilt und die Ergebnisse durch endliche und/oder-Ketten darstellen und systematisch und vollständig abprüfen.
Bernd Baumgarten
Hochschule Darmstadt SS 2016
Logik. Lösungen der Vorlesungs-Aufgaben, Tipps zu Ergänzungsaufgaben, 02.06.2016
42. Auswertung von geschlossenen Formeln in einer Struktur, Lösung Werten Sie folgende geschlossene Formeln (z.B. „durch bloßes Hinsehen“) in der Struktur ABsp aus:
a) ∃x¬P ( x, f ( x)) b) ∀y ((∀xP( x, y )) → y = f ( y )) (in PL1=),
W W
(x:=l) (y= k,l,m Prämisse F, y=n Konklusion W) c) ∀x P ( x, f ( x)) F (x:=l) W (x:=k) d) ∃x∀yP ( x, y ) zu d: Wie lautet ein Term in der Struktur ABsp für solch ein x? Für k gibt es keinen konst. Term in ABsp!
43. Anwendung erster PL-Theoreme in natürlicher Sprache
a) Sometimes it don’t always work. (Casey Stengel, Baseballmanager, 1890-1975) b) Immer putzt Du Dir nie die Füße ab! (zahlreiche Mütter, seit Erfindung der Fußmatte) (i) (ii) (iii) (iv)
Formalisieren Sie jeweils die Aussage als PL1_Formel über einem Universum der entsprechenden „Gelegenheiten“, evtl. auch Personen und Körperteilen. Was ist dabei eine geeignete potentielle Eigenschaft der Objekte? Wie lässt sich die Formel bzw. die Aussage äquivalent abkürzen? Woraus ergibt sich die Äquivalenz?
Lösung 43
a) (i) ∃x¬∀yItWorks ( y ) bzw. ∃x¬∀yWorks (it , y ) bzw. mit y anstelle von x (ii) Es funktioniert bei Gelegenheit x: ItWorks (x) , bzw. Works ⊆ Geschehnisse × Gelegenheiten, z funktioniert bei x: Works ( z , x) . (iii) ¬∀xItWorks (x) bzw. ¬∀xWorks (it , x) (iv) Quantorbeseitigung (Quantorvariable kommt nicht im Scope vor) & gebundene Umbenennung b) (i) ∀x¬∃y DpDdFa( y ) bzw. ∃x¬∀y Putzt_ab( Du , Deine_Füße, y ) (bzw. komplizierter mit Ist_Fuß (u ) ∧ Gehört (u , Du ) ) (ii) Du putzt Dir die Füße ab bei Gelegenheit x: DpDdFa (x) , bzw. Putzt_ab ⊆ Personen × Dinge × Gelegenheiten (iii) ¬∃x DpDdFa (x) bzw. ¬∀x Putzt_ab( Du , Deine_Füße, x) (iv) Quantorbeseitigung (Quantorvariable kommt nicht im Scope vor) & gebundene Umbenennung Anmerkung: Das Universum umfasst ggf. „Objekte“ wie Gelegenheiten, Geschehnisse, Personen, … Aber die Relationen treffen dann höchstens auf bestimmte Objektarten zu. So brauchen wir noch kein PL1 mit Typen.
Bernd Baumgarten
Hochschule Darmstadt SS 2016
