Einführung in die Logik

Institut für
Theoretische Informatik
ITI
Dr. Jürgen Koslowski
Einführung in die Logik
Aufgabenblatt 0, 2016-04-11
Allgemeine Hinweise
Bitte melden Sie sich in der ersten Semesterwoche ab Donnerstag, 2016-04-07, für eine
Übungsgruppe an, indem Sie sich in die vor Raum IZ 343 (Informatikzentrum, 3. Stock)
ausgehängten Listen eintragen.
Künftig wird ein neues Aufgabenblatt spätestens jeden Montag auf der Webseite zur Vorlesung bereitgestellt (http://www.iti.cs.tu-bs.de/ ˜ koslowj/Logik). Die Abgabe sollte für alle
Gruppen außer der Montagsgruppe in den gekennzeichneten Fächern des Kastens erfolgen!
Die Hausaufgaben sind in Zweiergruppen zu bearbeiten. Beide Personen sollten dieselbe
Übungsgruppe besuchen. Schreiben Sie stets beide Namen und Matrikelnummern sowie
die Nummer Ihrer Übungsgruppe auf die abgegebenen Lösungen. Eine geforderte Studienleistung für Studierende der Informatik besteht darin, 50% der Hausaufgabenpunkte zu
erreichen.
Bemühen Sie sich um eine formal korrekte Darstellung Ihrer Lösungen. Orientieren Sie sich
dafür an der Sprache und Notation der Vorlesung/Übung.
Alle Behauptungen sollen (kurz und prägnant!) begründet werden.
Übungsaufgabe 1
Eine kleine Logelei zum Warmwerden:
Jack schaut Anne an, aber Anne blickt auf George. Jack ist verheiratet, George nicht. Schaut
eine verheiratete Person auf jemanden, der/die unverheiratet ist?
Mögliche Antworten (bitte abstimmen lassen und nach Begründung fragen):
(a) Ja
(b) Nein
(c) Läßt sich nicht eindeutig sagen.
Übungsaufgabe 2
Definition. Eine Menge B heißt abzählbar, wenn es eine injektive Abbildung B
Anderfalls heißt sie überabzählbar.
IN gibt.
Insbesondere ist jede endliche Sprache abzählbar.
(a) Beweisen Sie folgenden
Satz 1. Teilmengen, endliche cartesische Produkte und abzählbare Vereinigungen abzählbarer Mengen sind wieder abzählbar. Dagegen sind Potenzmengen abzählbar unendlicher Mengen überabzählbar.
(b) Zeigen oder widerlegen Sie: B ist genau dann abzählbar, wenn es eine surjektive Abbildung
IN
B gibt.
Die folgenden beiden Aufgaben beziehen sich auf Stoff der Vorlesung 2016-04-06:
Aufgabe 3 [12 PUNKTE]
Untersuchen Sie die folgenden Mengen auf Abzählbarkeit:
(a) Die Sprache der Aussagenlogik.
(b) Die Menge der Formeln der Aussagenlogik.
(c) Die Menge der Variablenbelegungen, d.h., der Funktionen von der Menge der atomaren
Aussagen in die Menge der Wahrheitswerte 2 = {0, 1} .
(d) Die Menge der endlichen Mengen von Variablen.
Aufgabe 4 [15 PUNKTE]
Die Formeln der Aussagenlogik lassen sich auch als geordnete Bäume auffassen, sogenannte Syntaxbäume, deren Blätter atomare Aussagen oder ⊥ als Label tragen, während die 1bzw. 2-stelligen Junktoren ¬ , ∧ sowie ∨ als Label der inneren Knoten auftreten. (Aus dieser Sichtweise sind die Infix-, Präfix- oder Postfix-Schreibweisen für Formeln nur verschiedene
1-dimensoinale Darstellungen für inhärent 2-dimensionale Objekte, die Platz sparen und typographisch einfacher sind.)
(a) [6 punkte] Definieren Sie die Tiefe einer (syntaktisch korrekten) Formel F mittels struktureller Rekursion.
(b) [9 punkte] Setzen Sie die Anzahl der Knoten und der Kanten des Syntaxbaums einer
Formel F mit ihrer inhärenten Länge |F | und ihrer Präsentationslänge kF k in Beziehung.
Aufgabe 5 [6 PUNKTE]
Donald Duck hat seine Neffen Tick, Trick und Track zu Besuch. Da Tick am nächsten Tag
Geburtstag hat, backt er eine Torte und stellt sie in den Kühlschrank. Doch am nächsten Morgen
findet er dort zu seinem Schrecken nur noch ein paar Krümel eines nächtlichen Schmauses vor.
Da es wie üblich keiner der Neffen gewesen sein will, überlegt sich Donald folgendes:
0. Da er die Haustür abgeschlossen hatte, konnte niemand außer Tick, Trick und Track von
der Torte gegessen haben.
1. Track traut sich nur so etwas anzustellen, falls auch Tick mitmacht.
2. Trick ist zu klein um an den Kühlschrank heran zu kommen und ihn zu öffnen.
Noch haben wir das Projekt der Mechanisierung des Denkens nicht wirklich in Angriff genommen. Versuchen Sie trotzdem, mit Ihrem bisherigen Kenntinsstand, die Fragen zu beantworten:
Hat das Geburtstagskind von der Torte gegessen?
Wie alt ist es geworden?
Bitte geben Sie eine begründete Antwort!
Abgabe bis Montag, 2016-04-18, im Kasten neben IZ 343

Download Report