Übungen zur Vorlesung Logik für Informatiker WS 2008/09, Blatt 3

Abgabe: Mittwoch, 19. November 2008, vor der Vorlesung

Aufgabe 1. Geben Sie zu den folgenden Formeln jeweils eine äquivalente Formel in Negationsnormalform an.

a) ¬(A_{1} ∧ ¬(A_{2} ∨ (A_{3} → A_{4})))

b) (((A_{4} → A_{1}) → (A_{2} → A_{3})) → A_{1})

Dabei heißt eine aussagenlogische Formel in Negationsnormalform, wenn in ihr Negationszeichen nur unmittelbar vor Variablen vorkommen.

Aufgabe 2. Geben Sie zu den folgenden aussagenlogischen Formeln jeweils äquivalente Formeln in KNF und in DNF an.

\begin{matrix}a) & ((A_{1} ∧ (A_{2} ∨ A_{3})) ∨ A_{4}) \\ b) & (A_{1} ∨ (¬A_{2} ∧ (A_{3} ∨ ¬(A_{4} → A_{5})))) \end{matrix}

Aufgabe 3. a) (P, ≤) sei eine partielle Ordnung, in der je zwei Elemente ein Supremum und ein Infimum besitzen. Zeigen Sie, daß dann (P, inf, sup) ein Verband ist.

b) Sei nun umgekehrt (V, ⊓, ⊔) ein Verband. Für Elemente a, b ∈ V definieren wir a ≤ b gdw. a ⊓ b = a. Zeigen sie, daß (V, ≤) eine partielle Ordnung ist, in welcher a ⊓ b das Infimum und a ⊔ b das Supremum von a und b ist.

Aufgabe 4. Schreiben Sie ein Programm in Python, welches Formeln der Aussagenlogik parst. Das Programm soll zum Beispiel der Formel ((A ∧ ¬B) ∨ C) den Parse [∨, [∧, A, [¬, B]], C] zuordnen.

Die Eingabe soll nur die folgenden Zeichen enthalten: (,), n, u, o, A, B, C, . . .. Dabei sollen ( und ) die Klammern in Formeln, n, u und o die Junktoren ¬, ∧ und ∨, die einzelnen Großbuchstaben A, B, C, … die Aussagenlogischen Variablen kodieren. Ihr Programm soll also zum Beispiel die obige Formel in der Kodierung ((AunB)oC) akzeptieren.

Schicken Sie Ihr Pythonskript an: uebungen-lfi@math.uni-freiburg.de.

Hinweis: Aufgabe 4 auf Blatt 2.