Einführung in die Logik

Institut für
Theoretische Informatik
ITI
Dr. Jürgen Koslowski
Einführung in die Logik
Aufgabenblatt 6, 2016-05-30
Wir listen zunächst alle 12 Regeln der natürlichen Deduktion auf, nur die ersten 5 waren in der
letzten Vorlesung behandelt worden. Die Regeln erscheinen zunächst in Baumform und dan in
linearer Form:
Konjunktion
Implikation
Introduktion
Elimination
G H
G∧H
G∧H
G
G, H ` G ∧ H
G∧H `G , G∧H `H
[G]
..
..
H
G⇒H
G
[G] . . . H ` G ⇒ H
Disjunktion
Negation
G
G∨H
sowie
H
G∨H
sowie
G∧H
H
G⇒H
H
G, G ⇒ H ` H
[G] [H]
..
..
..
..
G∨H K
K
K
G`G∨H , H `G∨H
G ∨ H, [G] . . . K, [H] . . . K ` K
[G]
..
..
⊥
¬G
G ¬G und ¬¬G und ⊥
G
⊥
G
[G] . . . ⊥ ` ¬G
G, ¬G ` ⊥ , ¬¬G ` G , ⊥ ` G
Übungsaufgabe 30
Donald Duck will seine Neffen Tick, Trick und Track zum Bierholen in den Supermarkt schicken.
Das stößt allerdings auf wenig Begeisterung:
Tick: Ich habe keine Zeit, ich muss Hausaufgaben machen. Trick: Ich will nicht allein gehen.
Track: Ich gehe nur, wenn auch Tick mitkommt.
(a) Formulieren Sie die Aussagen von Tick, Trick und Track als aussagenlogische Formeln.
(b) Zeigen Sie mittels natürlicher Deduktion, dass Donald heute nüchtern bleibt.
Lösungsvorschlag:
(a) Atomare Aussagen: A: Tick geht mit, B: Trick geht mit, C Track geht mit.
Aussagen der Neffen: Tick ¬A; Trick: B ⇒ (A ∨ C); Track: C ⇒ A
(b) Herzuleiten ist die Konjunktion ¬A∧¬B∧¬C mit diesen Prämissen. Hinsichtlich der Baumdarstellung genügt es offenbar, die Terme ¬A, ¬B und ¬C einzeln herzuleiten, anschließend
können diese mit zwei (∧i)-Regeln zur gewünschten Konjunktion verbunden werden. Der
Fall ¬A ist dabei trivial, während die Herleitung von ¬C deutlich einfacher ist als die von
¬B.
[C] C ⇒ A
¬E
A
¬A
⇒E
⊥
¬I
¬C
oder linear

¬A
Praemisse

C⇒A
Praemisse

C
Kastenpraemisse

A
(⇒e), 3, 2

⊥
(⊥i), 1, 4

¬C
(¬i), 3 − 5
bzw.
¬A
[B] B ⇒ (A ∨ C)
⇒E
A ∨ C (∗)
¬A
¬A ⇒ C
⇒E
C
A
⊥I
⊥
¬I
¬B
C⇒A
⇒E
oder linear

¬A
Praemisse

B ⇒ (A ∨ C)
Praemisse

C⇒A
Praemisse

B
Kastenpraemisse

A∨C
(⇒e), 2, 4

¬A ⇒ C
(∗), siehe unten

C
(⇒e), 1, 6

A
(⇒e), 7, 3

⊥
(⊥i), 1, 8
¬B
(¬i), 4 − 9

Dabei kommt bei (∗) folgende Dedunktion zum Einsatz:
[A]
A∨C
[¬A]
¬E
⊥
⊥I
C
[C]
∨E
C
⇒I
¬A ⇒ C
In linearer Darstellung

A∨C
Praemisse

¬A
Kastenpraemisse

A
Kastenpraemisse

⊥
(⊥i), 2, 3

C
(⊥e), 4

C
Kastenpraemisse

C
(∨e), 1, 3 − 5, 6

¬A ⇒ C
(⇒i), 2 − 7
Ob die Verwendung der Herleitung (∗) zwecks Herleitung von ¬B aus den Prämissen so geschickt
war, sei dahingestellt, aus semantischer Sicht ist sie sicher zu rechtfertigen. Es geht aber auch
ohne diesen Umweg, und sogar insgesamt kürzer:

¬A
Praemisse

B ⇒ (A ∨ B)
Praemisse

C⇒A
Praemisse

C
Kastenpraemisse

A
(⇒e), 3, 4

⊥
(¬e), 1, 5

¬C
(¬i), 4 − 6

B
Kastenpraemisse

A∨C
(⇒e), 2, 8

A
Kastenpraemisse

C
Kastenpraemisse

A
(⇒e), 3, 11

A
(∨e), 9, 10 − 10, 11 − 12

⊥
(¬e), 1, 13

¬B
(¬i), 8 − 14

¬A ∧ ¬B
(∧i), 11, 15

(¬A ∧ ¬B) ∧ ¬C
(∧i), 7, 16
Aufgabe 31 [28 PUNKTE]
Untersuchen Sie die folgenden syntaktischen Sequenzen auf Gültigkeit. Genauer: Finden Sie für
die gültigen Sequenzen einen formalen Beweis mittels natürlicher Deduktion (in linearer Form
mit Kästen; optional dürfen Sie zusätzlich Bäume erstellen). Bei den nicht gültigen Sequenzen
können Sie die Korrektheit des Kalküls der natürlichen Deduktion verwenden.
(a) [4 punkte] F ` F ∧ (F ∨ G)
(b) [4 punkte] F, F ∨ G ` F ∧ G
(c) [6 punkte] ¬(F ⇒ G) ⇒ H, F ∧ ¬H ` G
(d) [10 punkte] (F ⇒ G) ⇒ G ` (G ⇒ F ) ⇒ F
(e) [4 punkte] F ∨ (G ∧ H) ` F ∧ (G ∨ H)
Abgabe bis Montag, 2016-06-07, im Kasten neben IZ 343

Download Report