Uebung 02 Aufgaben - SoSe PDF

Preview

Summary

Aussagenlogikund Prädikatenlogik (FGdI II)2. ÜbungsblattFachbereich Mathematik SoSe 2021Prof. Dr. Martin Otto Übung: 5./7. Mai 2021Dr. Ulrik Buchholtz, Jonathan Weinberger Abgabe bis: 12. Mai 2021, 18 UhrGruppenübungAufgabe G2 (Kompaktheit) Der Kompaktheitssatz (der Aussagenlogik) besagt: Ist jede e...

Description

Aussagenlogik und Prädikatenlogik (FGdI II) 2. Übungsblatt Fachbereich Mathematik Prof. Dr. Martin Otto Dr. Ulrik Buchholtz, Jonathan Weinberger

SoSe 2021 Übung: 5./7. Mai 2021 Abgabe bis: 12. Mai 2021, 18 Uhr

Gruppenübung Aufgabe G2.1 (Kompaktheit) Der Kompaktheitssatz (der Aussagenlogik) besagt: Ist jede endliche Teilmenge einer Formelmenge Φerfüllbar, so ist auch Φals Ganzes erfüllbar. (a) Zeigen Sie, dass Kompaktheit äquivalent ist zu der folgenden Aussage: Gilt Φ ψ, so gibt es eine endliche Teilmenge Φ mit Φ 0 ⊆Φ 0  ψ. (b) Zeigen Sie, dass die Existenz eines vollständigen und korrekten Beweiskalküls den Kompaktheitssatz impliziert. Aufgabe G2.2 (Kompaktheit und unendliche Bit-Sequenzen) Eine Interpretation I : V = {p1 , p2 , . . . } → B kann als unendliche Bit-Sequenz I(p1 )I(p2 )I(p3 ) . . . aufgefasst werden. Sei P eine Menge solcher Sequenzen und sei P das Komplement von P . Wir nehmen an, dass sowohl P als auch P durch (unendliche) Mengen aussagenlogischer Formeln spezifiziert werden können, dass für geeignete Φ , Ψ ⊆ AL(V ) also

P

=

{I : I |= Φ },

P

=

{I : I |= Ψ}

gilt. Zeigen Sie, dass P und P dann sogar schon durch endliche Formelmengen Φ 0 ⊆ Φund Ψ0 ⊆ Ψ spezifiziert werden können. Folgern Sie, dass man nur endlich viele Bits aus I betrachten muss, um zu entscheiden, ob I ∈ P gilt. Aufgabe G2.3 (Resolutionsverfahren) (a) Beweisen Sie die Folgerungsbeziehung {p, p → q, (p → q) → (q → r)} |= r , indem Sie die leere Klausel  aus der Klauselmenge

{{ p}, {¬ p, q}, {p, ¬q, r}, {¬q, r}, {¬ r }}. mittels Resolution ableiten. (b) Für jede aussagenlogische Formel ϕ sei Kϕ eine Klauselmenge mit ϕ ≡

ϕ ist unerfüllbar

⇔

V

Kϕ . Laut Vorlesung gilt die Äquivalenz

 ∈ Res∗ (Kϕ ).

Charakterisieren Sie die folgenden Aussagen durch ähnliche Äquivalenzen: i. ϕ ist erfüllbar, ii. ϕ ist allgemeingültig, iii. ϕ |= ψ, iv. Φ 0 ist unerfüllbar, wobei Φ 0 eine endliche Menge von aussagenlogischen Formeln ist. Aufgabe G2.4 (Extra: Endlichkeitssatz für Parkettierungen) Ein Parkettierungs-System D = (D, H, V ) ist gegeben durch eine endliche Menge D von Kacheltypen und zwei Relationen H, V ⊆ D × D, die beschreiben, wann zwei Kacheltypen horizontal bzw. vertikal nebeneinander passen, d.h. (d, e) ∈ H gdw. e rechts neben d passt und (d, e) ∈ V gdw. e über d passt. Eine gegebene Teilmenge von Z × Z besitzt eine Pakettierung, wenn sie korrekt mit Kacheln belegt werden kann, d.h., wenn benachbarte Kacheln in ihrem Typ gemäß H und V zusammen passen. (Wir gehen davon aus, dass wir unbegrenzt viele Kacheln jedes Typs haben) Weisen Sie nach, dass für ein endliches Parkettierungs-System D = (D, H, V ) stets äquivalent sind:

1

(a) Es existiert eine Parkettierung auf Z × Z. (b) Es existiert eine Parkettierung auf N × N. (c) Es existieren Parkettierungen auf (n × n)-Quadraten für beliebig große n ∈ N. Hinweis: Benutzen Sie AL-Variablen pd i j für d ∈ D, i, j ∈ Z, die besagen, dass in Position (i, j) eine Kachel vom Typ d liegt. Die Bedingungen an D-Parkettierungen lassen sich dann in geeigneter Weise als AL-Formelmengen beschreiben. Sie können auch ganz anders argumentieren, z.B. mit dem Lemma von K˝ onig.

Hausübung

Hinweise zur Hausübung Bitte geben Sie Ihre Lösungen zu dieser Hausübung bis Mittwoch, 12. Mai, 18 Uhr, online in Moodle ab. Die Abgabe erfolgt als einzelne Datei im PDF-Format (max. 20 MB). Wir unterstützen ausdrücklich das gemeinsame Arbeiten und Diskutieren in Gruppen. Die Hausübungen können in Gruppen von bis zu drei Personen abgegeben werden (auch von Teilnehmern unterschiedlicher Übungsgruppen). Bitte geben Sie in jedem Fall auf den Abgaben die Namen und die Nummern der Übungsgruppe an. Antworten sind grundsätzlich zu begründen.

onig und Kompaktheitssatz) (12 Punkte) Aufgabe H2.1 (Lemma von K˝ Das Lemma von K˝onig besagt: Jeder unendliche, endlich verzweigte Baum hat einen unendlichen Pfad (vgl. AL-Skript, Lemma 4.4). Im AL-Skript wird das Lemma von K˝ onig mithilfe des Kompaktheitssatzes bewiesen. Tatsächlich sind beide Sätze äquivalent. Hier soll nun die umgekehrte Implikation bewiesen werden. (a) Sei T = (V, E, λ) ein Baum. Die Tiefe (engl. depth) dep(v ) eines Knotens v 6= λ ist die Länge des (eindeutigen) Pfades λ → . . . → v . Die Höhe von λ ist dep(λ) = 0. Die n-te Stufe (engl. level) eines Baums T ist gegeben durch lv T (n) := {v ∈ V : dep(v ) = n} für n ≥ 0. Zeigen Sie: Ein unendlicher Baum T ist genau dann endlich verzweigt, wenn l n := |lv T (n)| für alle n ≥ 0 endlich ist. (b) Benutzen Sie das Lemma von K˝ onig um den Kompaktheitssatz zu zeigen. (Hinweis: Sei Φeine endlich erfüllbare Formelmenge, d.h. jede endliche Teilmenge Φ sei erfüllbar. Definieren Sie einen Baum TΦ , dessen Knoten aus 0 ⊆Φ geeigneten (partiellen) Belegungen bestehen. Benutzen Sie (a), um zu zeigen, dass TΦ die Voraussetzungen des onig erfüllt.) Lemmas von K˝ Aufgabe H2.2 (Hornklauseln) (12 Punkte) Wir betrachten die Menge H = {{¬p, ¬t, s}, {p }, {¬p, ¬q, r}, {t}, {¬ p , ¬s, q}, {¬s, ¬r, t}, {¬p, ¬u, r}, {¬u}, {¬q}} von Hornklauseln. (a) Bestimmen Sie die minimale erfüllende Interpretation der nicht-negativen Klauseln aus H . Entscheiden Sie, ob H erfüllbar ist. (b) Geben Sie einen Ableitungsbaum im Resolutionskalkül an, welcher  aus der Klauselmenge H herleitet. (c) Bei der Einheitsresolution darf die Resolvente zweier Klauseln nur gebildet werden, wenn eine der Klauseln aus einem einzelnen Literal besteht. Zeigen Sie: Die Einheitsresolution ist im Allgemeinen nicht vollständig, für Hornklauseln aber schon. Aufgabe H2.3 (Endliche boolesche Algebren) (12 Punkte) In dieser Aufgabe sehen wir, dass sich jede endliche boolesche Algebra als Potenzmengenalgebra realisieren lässt. Sei im folgenden B = (B, ·, +,′ , 0, 1) eine endliche boolesche Algebra, d.h. B eine endliche Menge. Auf B betrachten wir die partielle Ordnung ≤ mit x ≤ y : ⇐⇒ x · y = x (vgl. H1.3). Sei AB die Menge der Atome in B . (a) Zeigen Sie, dass für alle x ∈ B gilt x · 0 = 0. Folgern Sie damit, dass x ≤ y genau dann gilt, wenn x · y ′ = 0. (3 Punkte) (b) Zeigen Sie: Für jedes Element x ∈ B mit x 6= 0 gibt es ein Atom b ∈ B mit b ≤ x .

(1 Punkt)

(c) Sei x ∈ B . Zeigen Sie, dass x die kleinste obere Schranke (Supremum) der Menge A x := {a ∈ AB : a ≤ x} ist, d.h. es ist a ≤ x für alle a ∈ A x und für alle y ∈ B mit a ≤ y für alle a ∈ A x gilt x ≤ y . (Hinweis: Benutzen Sie (a) und (b).) (2 Punkte)

2

(d) Zeigen Sie, dass die Abbildung

ϕ : B → P (AB ),

x 7→ A x

ein Isomorphismus ist. (Hinweis: Zur Surjektivität betrachten Sie für U ⊆ AB das Element x := Σu∈U u. Für die leere Summe wird Σu∈; u := 0 gesetzt.) (6 Punkte)

3...