ITIInstitut fürTheoretische Informatik

Prof. Dr. J. Adámek · Dipl.-Math. Dipl.-Inf. H. Urbat

Einführung in die LogikAufgabenblatt 1

Allgemeine Hinweise

• Bitte melden Sie sich für eine Übungsgruppe an, indem Sie sich in die vor Raum IZ 342(Informatikzentrum, 3. Etage) ausgehängten Listen eintragen.

• Ein neues Aufgabenblatt wird jeden Freitag auf der Webseite zur Vorlesung bereitgestellt.Sie haben jeweils eine Woche Zeit zur Bearbeitung. Zur Abgabe verwenden Sie bitte dieentsprechend beschrifteten Briefkästen vor Raum IZ 343.

• Die Hausaufgaben sind in Zweiergruppen zu bearbeiten; dabei sollten beide Personenfür dieselbe Übungsgruppe angemeldet sein. Schreiben Sie stets beide Namen und Matri-kelnummern sowie die Nummer Ihrer Übungsgruppe auf die abgegebenen Lösungen.

• Die Theoretische Informatik ist eine mathematische Disziplin – daher wird bei der Bewer-tung der Hausaufgaben gleichermaßen auf inhaltliche und formale Korrektheit geachtet.Orientieren Sie sich bei der Formulierung Ihrer Lösungen an der mathematischen Termi-nologie und Notation der Vorlesung/Übung.

Übungsaufgabe 1Schreiben Sie ein JAVA-Programm, das seinen eigenen Quellcode auf dem Bildschirm ausgibt.

Übungsaufgabe 2

(a) Ist die Sprache der Aussagenlogik abzählbar?

(b) Ist die Menge aller Formeln der Aussagenlogik abzählbar?

(c) Ist die Menge aller Variablenbelegungen abzählbar?

Übungsaufgabe 3Stellen Sie die Wahrheitstabelle für die Formel F = A∨ (¬(B ∧ (C → B))) auf. Ist F erfüllbar?Ist F allgemeingültig?

Übungsaufgabe 4Definieren Sie die formale Semantik einer erweiterten Aussagenlogik, bei der Atome neben denWahrheitswerten 1 ("wahr") und 0 ("falsch") auch den Wahrheitswert 0.5 ("vielleicht") erhaltenkönnen.

Abgabe bis Freitag, 24.4., 14:00 Uhr, in den Briefkästen vor Raum IZ 343

Hausaufgabe 0 [1 PUNKTE]Lernen Sie die tödlichen Gefahren der logischen Implikation kennen:

https://www.youtube.com/watch?v=k3jt5ibfRzw

Hausaufgabe 1 [11 PUNKTE]Donald Duck hat seine Neffen Tick, Trick und Track zu Besuch. Da Tick am nächsten TagGeburtstag hat, backt er eine Torte und stellt sie in den Kühlschrank. Doch am nächstenMorgen findet er dort zu seinem Schrecken nur noch ein paar übriggebliebene Krümel einesnächtlichen Schmauses vor. Weil es wie üblich keiner gewesen sein will, überlegt sich Donaldfolgendes:

1. Da er die Haustür abgeschlossen hatte, konnte niemand außer Tick, Trick und Track vonder Torte gegessen haben.

2. Track traut sich nur so etwas anzustellen, falls auch Tick mitmacht.

3. Trick ist zu klein, um an den Kühlschrank heranzukommen und ihn zu öffnen.

(a) [6 PUNKTE] Übersetzen Sie die drei Aussagen in aussagenlogische Formeln. Legen Siedazu passende Variablen für atomare Aussagen fest.

(b) [5 PUNKTE] Hat das Geburtstagskind von der Torte gegessen? Argumentieren Sie miteiner Wahrheitstabelle.

Hausaufgabe 2 [8 PUNKTE]Sind die folgenden Aussagen wahr oder falsch?

(a) [2 PUNKTE] Wenn 1 + 1 = 2 ist, dann gibt es ein viereckiges Dreieck.

(b) [2 PUNKTE] Wenn es ein viereckiges Dreieck gibt, dann ist 1 + 1 = 2.

(c) [2 PUNKTE] Wenn es ein viereckiges Dreieck gibt, dann ist 1 + 1 = 3.

(d) [2 PUNKTE] Ein Dreieck hat drei oder vier Ecken.

Hausaufgabe 3 [6 PUNKTE]Gegeben sei die Formel ¬(A⇒ B)⇔ (A ∧ ¬B).

(a) [4 PUNKTE] Stellen Sie die Wahrheitstabelle auf.

(b) [2 PUNKTE] Ist die Formel erfüllbar? Ist sie allgemeingültig?

Hausaufgabe 4 [10 PUNKTE]In dieser Aufgabe betrachten wir Formeln mit vollständiger Klammerung gemäß Definition 2.3im Vorlesungsskript. Die Länge einer solchen Formel ist die Anzahl ihrer Symbole als Zeichen-kette. Beispielsweise hat die Formel ((¬A)∧(B∨A)) die Länge 12. Für welche Zahlen n ≥ 1 gibtes eine Formel der Länge n? Argumentieren Sie ausführlich und formal, etwa per Induktion.