Übung 4 - (Dr. Kord Eickmeyer) ohne Hausaufgabenlösungen PDF

Preview

Summary

(Dr. Kord Eickmeyer) nur Gruppenlösungen ohne Hausaufgabenlösungen...

Description

Aussagenlogik und Prädikatenlogik (FGdI II) 4. Übungsblatt Fachbereich Mathematik Dr. Kord Eickmeyer Dr. Ulrik Buchholtz, Jonathan Weinberger

SoSe 2020 10./12. Juni 2020

Gruppenübung Aufgabe G4.1 (Quiz) (a) Seien ϕ und ψ AL-Formeln und Φ ⊆ AL. Wie kann man den Sequenzenkalkül nutzen, um zu überprüfen, ob i. ϕ erfüllbar ist? ii. ϕ allgemeingültig ist?

iv. Φ unerfüllbar ist (für endliches Φ)? v. Φ unerfüllbar ist (für unendliches Φ)?

iii. ϕ |= ψ? (b) Zeigen Sie durch Gegenbeispiele dass folgende Behauptungen falsch sind: i. Jede erfüllbare Klauselmenge besitzt eine eindeutige minimale erfüllende Belegung. (Was gilt stattdessen?) ii. Für eine Resolvente C zweier Klauseln C1 , C2 gilt stets {C} ≡ {C1 , C2 }. (Was gilt stattdessen?) iii. Für alle Klauselmengen K und Klauseln C gilt K |= C genau dann, wenn C ∈ Res∗ (K). (Was gilt stattdessen?) Lösung: (a) Mit Hilfe des Sequenzenkalküls kann durch Rückwärtsuche algorithmisch geprüft werden, ob eine Sequenz Γ ⊢ ∆ allgemeingültig ist oder nicht. i. ϕ ist erfüllbar gdw. ϕ ⊢ ; nicht allgemeingültig ist ii. ϕ ist allgemeingültig gdw. ⊢ ϕ allgemeingültig ist iii. ϕ |= ψ gdw. ϕ ⊢ ψ allgemeingültig ist iv. Φ is unerfüllbar gdw. Φ ⊢ ; allgemeingültig ist v. Φ is unerfüllbar gdw. Φ0 ⊢ ; allgemeingültig ist für ein endliches Φ0 ⊆ Φ (b)

i. K = {{p, q}} ist eine erfüllbare Klauselmenge ohne eindeutige minimale erfüllende Belegung, weil sowohl {p 7→ 1, q 7→ 0} |= K als auch {p 7→ 0, q 7→ 1} |= K gilt. Stattdessen besitzt jede erfüllbare Hornklauselmenge eine eindeutige minimale erfüllende Belegung. ii. Seien C1 = {p, q}, C2 = {¬p, r} Klauseln und C = {q, r} eine Resolvente von C1 und C2 . Dann gilt {C} ≡ {C1 , C2 } nicht. Stattdessen gilt {C1 , C2 , C} ≡ {C1 , C2 } für alle Resolventen C zweier beliebiger Klauseln C1 und C2 . iii. Sei K = {{p}} und C = {p, q}. Dann gilt K |= C , allerdings nicht C ∈ Res∗ (K) = K . Stattdessen gilt K |=  genau dann, wenn  ∈ Res∗ (K) für alle Klauselmengen K .

Aufgabe G4.2 (FO-Formalisierung und Graphen) Sei S = {E}, wobei E ein zweistelliges Relationssymbol sei. Formalisieren Sie die folgenden Sätze über ungerichtete Graphen in FO(S): (a) Je zwei verschiedene Knoten sind miteinander verbunden. (b) Es gibt drei Knoten, die keinen Kreis bilden. (c) Der Graph enthält keine Kante, aber mindestens zwei Knoten. (d) Der Graph besteht aus nur einem Knoten. Lösung:

1

(a) ∀x∀ y (¬x = y → E x y)   (b) ∃x∃ y∃z ¬x = y ∧ ¬x = z ∧ ¬ y = z ∧ ¬(E x y ∧ E yz ∧ E xz)   (c) ∃x∃ y ¬x = y ∧ ∀x∀ y ¬E x y (d) ∀x∀ y (x = y)

Aufgabe G4.3 (Wörter und Sprachen) Wir wollen Sprachen über dem Alphabet Σ := {a, b} mit Hilfe der Prädikatenlogik definieren. Wie im Skript, S. 3, definieren wir zu einem nichtleeren Wort w = w 1 . . . w n ∈ Σ+ := Σ∗ \ {ǫ} eine Wortstruktur

wobei

  W (w) = {1, . . . , n},...