TU Ilmenau, Fakultat IA

Institut TI, FG Theoretische Informatik

Prof. Dr. Dietrich Kuske, Dipl.-Inf. Roy Mennicke

http://www.tu-ilmenau.de/iti/lehre/lehre-ss-2011/ls/

Logische StrukturenUbungsblatt 1

Die Ubungsaufgaben werden in den Ubungsveranstaltungen der 16. Kalenderwoche bespro-chen. Die Abgabe der Losungen zu den Hausaufgaben hat bis spatestens 26. April 2011um 14.45 Uhr zu erfolgen. Nutzen Sie dafur bitte den Briefkasten des Instituts (Blechhaus,2. Obergeschoss).

Bitte heften Sie die einzelnen Blatter Ihrer Losung sorgfaltig zusammen und vermerken Sieauf Ihrer Losung Ihre Matrikelnummer und die Ubungsveranstaltung, in der Sie Ihre korrigierteLosung zuruckerhalten mochten. Falls nicht anders angegeben, sind alle Zwischenschritte, dieSie zu einer Losung einer Hausaufgabe gefuhrt haben, aufzufuhren.

Ubungsaufgaben

Aufgabe 1

Entscheiden Sie, welche der nachfolgenden Syllogismen gultig sind. Begrunden Sie Ihre Ant-wort oder geben Sie ein Gegenbeispiel an.

(a) Alle M sind P . Einige M sind S. Dann gilt: einige S sind P .

(b) Kein M ist P . Kein S ist M . Dann gilt: kein S ist P .

(c) Alle M sind P . Einige S sind nicht M . Dann gilt: einige S sind nicht P .

(d) Alle P sind M . Einige S sind nicht M . Dann gilt: einige S sind nicht P .

Aufgabe 2

Entscheiden Sie fur jede der nachfolgenden Zeichenketten, ob es sich um eine aussagenlogischeFormel handelt. Geben Sie im positiven Fall den entsprechender Syntaxbaum an.

(a) ¬¬(A1 ∨ (A2 ∧ ¬A3))

(b) A1¬A2

(c) (A1 ∨A2 ∨A3)

Aufgabe 3

Entwerfen Sie einen Algorithmus in einer Pseudo-Programmiersprache, der fur eine gegebe-ne Zeichenkette x = x1x2 . . . xn, bestehend aus Atomformeln und den Zeichen ∨,∧,¬, (, ),uberpruft, ob es sich bei x um eine aussagenlogische Formel handelt.

Aufgabe 4

Was soll heute im Fernsehen angeschaut werden – der “Tigerenten Club” oder “Der Gruffelo”?Sieben Freunde haben die folgenden Vorlieben:

(1) Luisa oder Margarete wollen den Tigerenten Club sehen.

2 Logische Strukturen Ubungsblatt 1

(2) Christoph oder Sebastian schwarmen fur den Gruffelo.

(3) Entweder will Theodor oder Margarete den Tigerenten Club sehen.

(4) Luisa und Beatrice sind entweder beide fur den Tigerenten Club, oder beide fur denGruffelo.

(5) Entweder entscheiden sich Christoph fur den Tigerenten Club und Beatrice fur den Gruffelo,oder es stimmen Margarete fur den Tigerenten Club und Alina fur den Gruffelo.

(6) Theodors und Christophs Interesse gilt dem Gruffelo, oder Margarete und Sebastian wollennicht den Gruffelo.

(7) Alina wahlt den Gruffelo, oder Theodor und Luisa sehen lieber den Tigerenten Club.

Fuhren Sie geeignete Atomformeln ein und geben Sie fur jede der obigen sieben Bedingungeneine entsprechende Formel an.

Um herauszufinden, wer sich welche Sendung ansehen mochte, konnen Sie beispielsweise denSAT-Solver limboole verwenden. Dieser ist unter der Internetadresse

http://ktxeon.theoinf.tu-ilmenau.de/cgi-bin/limboole.cgi

ohne vorherige Installation nutzbar (alternativ steht er unter http://fmv.jku.at/limboole/zum Download bereit). Unter der Adresse http://fmv.jku.at/limboole/README.limboole

ist die Eingabesyntax beschrieben. Verwenden Sie auf der Kommandozeile den Schalter -s bzw.auf der Internetseite die Option “Test auf Erfullbarkeit”, um eine Formel auf Erfullbarkeit zutesten.

Aufgabe 5

In der Vorlesung wurde folgender Satz bewiesen:

Satz: Folgende Aussagen sind aquivalent:

(1) F1, . . . , Fk |= G, d.h., G ist eine Folgerung von F1, . . . , Fk.

(2) ((∧k

i=1 Fi)→ G) ist gultig.

(3) ((∧k

i=1 Fi) ∧ ¬G) ist unerfullbar.

In der Vorlesung wurden direkte Beweise fur die Richtungen “(1) ⇒ (2)”, “(2) ⇒ (3)” und“(3) ⇒ (1)” angegeben. Geben Sie nun direkte Beweise fur die Richtungen “(2) ⇒ (1)” und“(3)⇒ (2)” an.

Aufgabe 6

Uberprufen Sie mittels Wahrheitstafeln, ob die folgenden Aquivalenzen gelten.

¬(A ∨B) ≡ (¬A ∧ ¬B)

(A ∧ (B ∨ C)) ≡ ((A ∧B) ∨ (A ∧ C))

(A→ B)→ C ≡ A→ (B → C)

(A→ B)→ C ≡ (A ∧B)→ C

(A↔ B)↔ C ≡ A↔ (B ↔ C)

Falls eine Aquivalenz vorliegt, so zeigen Sie diese bitte auch durch Umformen (Fundamental-satz der Aussagenlogik).

Logische Strukturen Ubungsblatt 1 3

Hausaufgaben

Aufgabe 7 (6 Punkte)

Tante Agnes ist ermordet in ihrem Zimmer aufgefunden worden. Zugang zu ihrem Zimmerhatten neben ihr nur noch ihr Butler und Carl. Ein Morder hasst immer das Opfer und istniemals reicher als das Opfer. Carl hasst niemanden, den Tante Agnes hasst. Agnes hasstjeden, außer den Butler. Der Butler hasst jeden, der nicht reicher als Tante Agnes ist. DerButler hasst jeden, den Tante Agnes hasst. Niemand hasst alle und keine zwei unterschiedlichenPersonen sind gleich reich.

Fuhren Sie geeignete Atomformeln ein, formalisieren Sie die Hinweise auf den Tater undverwenden Sie einen SAT-Solver (beispielsweise limboole), um den Morder von Tante Agneszu bestimmen.

Aufgabe 8 (6 Punkte)

(a) Stellen Sie die Wahrheitstafeln folgender aussagenlogischer Formeln auf:

F1 = ((A→ B)→ (¬B → ¬A))

F2 = ((A ∨B) ∧ (¬A ∨ (¬B ∨ C)))

Geben Sie an, welche der Formeln F1, F2, ¬F1 und ¬F2 erfullbar, unerfullbar oder gultigsind.

(b) Zeigen Sie durch Umformung (Fundamentalsatz der Aussagenlogik), dass gilt:

A↔ B ≡ (A→ B) ∧ (B → A)