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

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

Aufgabe 1. Übertragen Sie folgende Sätze in die Aussagenlogik:

1. Wenn es regnet oder wenn ich faul bin, nehme ich die Straßenbahn oder bleibe zu Hause.

2. Wenn ich nicht zu Hause bleibe, obwohl es regnet, nehme ich die Straßenbahn; und wenn ich faul bin und die Straßenbahn nicht nehme, bleibe ich zu Hause.

Sagen diese Sätze das gleiche aus?

Aufgabe 2. Welche der folgenden Formeln sind Tautologien, welche sind erfüllbar? Begründen Sie jeweils Ihre Antwort.

\begin{matrix}(((A_{1} ∧ A_{2}) → A_{3}) ↔ (A_{1} → (A_{2} → A_{3}))) \\ (((A_{3} → A_{1}) → A_{3}) ∧ ¬A_{3}) \end{matrix}

Aufgabe 3. a) Gilt ((A_{1} ∨ A_{2}) → A_{3}) ≡ ((A_{1} → A_{3}) ∨ (A_{2} → A_{3}))? Begründen Sie Ihre Antwort.

b) Geben Sie für die Formel (¬A_{1} → ((A_{3} → A_{2}) ∨ A_{1})) sowohl eine erfüllende als auch eine nicht-erfüllende Belegung an.

Aufgabe 4. Schreiben Sie ein Programm in Python, welches bei Eingabe einer Zeichenreihe ξ dasjenige Anfangsstück von ξ ausgibt, welches eine aussagenlogische Formel ist. Ist kein Anfangsstück von ξ eine aussagenlogische Formel, so soll die leere Zeichenreihe ausgegeben werden.

Dabei sollen die Buchstaben n, u und o die Junktoren ¬, ∧ und ∨ darstellen, ( und ) die Klammern in Formeln und einzelne Großbuchstaben A, B, C, … die aussagenlogischen Variablen. Schicken Sie den kompilierbaren Quelltext Ihres Programms an folgende Emailadresse:

uebungen-lfi@math.uni-freiburg.de.