Übungsblatt 3

Institut für Informatik der
Universität Zürich
Sommersemester 2003
3. Hausaufgabe
Formale Grundlagen der Informatik
Norbert E. Fuchs ([email protected])
Verantwortlicher Assistent:
Gérard Milmeister ([email protected])
Abgabe bis 20. Mai 2003, 17.00 Uhr
Briefkasten 67-c, Stockwerk K, Institut für Informatik der Universität Zürich
Bitte die Lösungen direkt in die vorgesehenen Lücken der Blätter schreiben!
Thema: Aussagenlogik
Name
Aufgabe 1
Aufgabe 2
Vorname
Aufgabe 3
Matrikelnummer
Aufgabe 4
1
Aufgabe 5
Aufgabe 6
Summe
Aufgabe 1 (2 Punkte)
Bestimmen Sie die konjunktive und die disjunktive Normalform folgender Formeln.
1.1 (1 Punkt)
P → ((Q → R) → S)
1.2 (1 Punkt)
¬(P ↔ Q)
2
Aufgabe 2 (1.5 Punkte)
Kreuzen Sie für jeden Satz die richtige aussagenlogische Formalisierung an. Nur eine
Antwort ist richtig. Verwenden Sie die angegebenen Abkürzungen für die Teilaussagen.
2.1 (0.25 Punkte)
Wir kaufen entweder einen BMW oder einen Mercedes, vorausgesetzt wir haben genug
Geld.
b: Wir kaufen einen BMW.
m: Wir kaufen einen Mercedes.
g: Wir haben genug Geld.
g → (b ∧ ¬m) ∨ (¬b ∧ m)
g → (b ∧ m)
(b ∨ m) → g
(g → b) ∨ (g → m)
2.2 (0.25 Punkte)
Ohne zu schummeln, hat Markus acht Punkte in der Klausur erzielt; hätte er geschummelt, hätte er die nicht bekommen.
s: Markus hat geschummelt.
p: Markus hat acht Punkte in der Klausur gekriegt.
p ∧ (s → ¬p)
s → ¬p
¬s ∧ p
p∨s
2.3 (0.25 Punkte)
Es ist nicht wahr, dass Informatikstudenten weder intelligent noch gebildet sind.
i: Informatikstudenten sind intelligent.
g: Informatikstudenten sind gebildet.
i∧g
¬(¬i ∨ ¬g)
i∨g
¬(i ∧ g)
3
2.4 (0.25 Punkte)
Wenn man sich gut vorbereitet, besteht man die Prüfung, sonst fällt man durch; schwierig wird es aber so oder so.
v: Man bereitet sich gut vor.
b: Man besteht die Prüfung.
s: Es wird schwierig.
(s ∧ v) ↔ b
(b → v) ∨ s
(v → b) ∧ s
(v ↔ b) ∧ s
2.5 (0.25 Punkte)
Es wird regnen oder schneien; falls es regnet, bleiben wir zu Hause.
r: Es wird regnen.
s: Es wird schneien.
h: Wir bleiben zu Hause.
(s ∨ r) ∧ (r ∧ h)
(s ∨ r) → (s → h)
(r ∨ s) ∧ (¬r ∨ h)
s∨r∨h
2.6 (0.25 Punkte)
Sollten wir ins Kino gehen, werden wir uns zwar keinen Actionfilm ansehen, wohl aber
eine Komödie.
r: Wir gehen ins Kino.
s: Wir schauen uns einen Actionfilm an.
k: Wir schauen uns eine Komödie an.
(¬r ∨ ¬s) ∧ (¬r ∨ k)
r → (k ∨ ¬s)
¬r → (¬s ∧ k)
r ∧ ¬s ∧ k
4
Aufgabe 3 (2 Punkte)
Vereinfachen Sie folgende Formeln soweit wie möglich. Geben Sie zu jedem Schritt die
verwendete Regel an.
3.1 (1 Punkt)
(P → (P ∧ ¬Q)) ∨ (Q → (Q ∧ ¬P))
3.2 (1 Punkt)
((Q ∨ ¬Q) → P) ∧ ((¬P ∧ R) ∨ (¬P ∧ ¬R))
5
Aufgabe 4 (1.5 Punkte)
4.1 (1 Punkt)
Bestimmen Sie durch Aufstellen einer Wahrheitstabelle, ob folgende Formel tautologisch ist oder nicht.
((P → Q) ∧ (Q → R)) → ¬(¬R ∧ P)
4.2 (0.5 Punkte)
Klammern Sie folgende Formel vollständig unter Beachtung der Vorrangsregeln für
Konnektoren:
¬P ∧ Q ∨ R → ¬¬S ∨ T ∧ U
6
Aufgabe 5 (1.5 Punkte)
Viele Programmiersprachen implementieren die logischen Konnektoren und und oder
als conditional and (cand) und conditional or (cor). So können logische Ausdrücke auch
evaluiert werden, wenn ein Term nicht definiert ist. So ist z.B. x 6= 0 cand 1x > 1 immer
definiert und ergibt W, falls 0 < x < 1, und F sonst; aber x1 > 1 cand x 6= 0 ist nicht
definiert, wenn x = 0.
Wir definieren eine 3-wertige Logik L3 mit den Wahrheitswerten W (wahr), F (falsch)
und U (undefiniert), und den binären logischen Konnektor cand folgendermassen:
A
W
W
W
F
F
F
U
U
U
B
W
F
U
W
F
U
W
F
U
A cand B
W
F
U
F
F
F
U
U
U
5.1 (0.5 Punkte)
Wieviele verschiedene binäre logische Funktionen gibt es in L3 ?
7
5.2 (0.5 Punkte)
Geben Sie analog zu cand die Wahrheitstabelle von cor an.
5.3 (0.5 Punkte)
Ist cand kommutativ oder nicht? Begründen Sie Ihre Antwort.
8
Aufgabe 6 (1.5 Punkte)
Gegeben sind folgende natürlichsprachliche Überlegungen, die sich Sherlock Holmes
bei der Lösung eines schwierigen Falles machte:
P1 : Falls Professor Moriarty noch lebt, ist er der Täter.
P2 : Wenn Moriarty tot ist, dann ist er in den Reichbachfällen umgekommen oder wurde von seinen Komplizen umgebracht.
P3 : Falls er in den Reichbachfällen gestorben ist, hat man seine Leiche gefunden.
P4 : Wenn man seine Leiche nicht gefunden hat, wurde er nicht von den Komplizen
ermordet.
P5 : Moriartys Leiche wurde nicht gefunden.
Holmes schliesst daraus:
K: Moriarty ist also der Täter.
6.1 (0.5 Punkte)
Stellen Sie die Aussagen P1 bis P5 als aussagenlogische Formelmenge M dar und die
Konklusion als aussagenlogische Formel K (Hinweis: Sie brauchen nicht das exklusive
Oder). Verwenden Sie dabei folgende Abkürzugen:
t:
r:
k:
f:
m:
Moriarty lebt nicht mehr.
Moriarty ist in den Reichbachfällen umgekommen.
Moriarty wurde von seinen Komplizen umgebracht.
Man hat Moriartys Leiche gefunden.
Professor Moriarty ist der Täter.
9
6.2 (1 Punkt)
Zeigen Sie mittels eines Beweises durch Widerspruch, dass M |= K. Gehen Sie dabei vor
wie auf den Folien Seite 33 angegeben.
10