MATHEMATISCHES INSTITUT Bonn, den 02.05.2002 DER UNIVERSITÄT BONN Prof. Dr. Peter Koepke

Einführung in die Mathematische Logik SS 2002

Übungsaufgaben, Folge 3, Abgabe: 07.05.2002 vor der Vorlesung

Aufgabe 1 Zeigen Sie, dass die folgenden Regeln im \underline{Sequenzenkalkül} über der Sprache \{∨, ¬\} ableitbar sind:

\frac{{( A → B) \atop (¬A → B)}}{B};  \frac{{(¬A → B) \atop (¬A → ¬B)}}{A};  \frac{{A \atop ¬A}}{B};  \frac{( B → A)}{(¬B → ¬A)}.

Hierbei steht (A → B) als Abkürzung für (¬A ∨ B).

Aufgabe 2 Zeigen Sie, dass folgende Aussagen im \underline{Aussagenkalkül} über der Sprache \{ → , ¬\} ableitbar sind:

(¬¬A → A);  (A → ¬¬A);  (A → (B → (A ∧ B)));  (A → (A ∨ B)).

Hierbei steht (A ∧ B) als Abkürzung für ¬(B → ¬A) und (A ∨ B) als Abkürzung für (¬A → B).

Aufgabe 3 Wir betrachten zwei Personen, Anton(A) und Berta(B). Eine Person kann entweder ein Ritter oder ein Knappe sein. Ritter lügen nie und Knappen lügen immer.

(a) Formalisieren Sie die obigen Axiome in der {∨, ¬}-Sprache des Sequenzenkalküls.

(b) Formen Sie die Aussage

Anton sagt:„Ich bin ein Knappe, oder Berta ist ein Ritter“

in eine Aussage in der {∨, ¬}-Sprache des Sequenzenkalküls um.

(c) Beweisen Sie im Sequenzenkalkül, dass sowohl Anton als auch Berta Ritter sind.

Aufgabe 4 Zeigen Sie, dass ({0, 1}, ⊕, ⊙) ein Körper der Größe 2 ist. Dabei seien ⊕ und ⊙ die durch folgenden Wahrheitstafeln definiert:

\begin{matrix}⊕ & 0 & 1 \\ 0 & 0 & 1 \\ 1 & 1 & 0 \end{matrix}  \begin{matrix}⊙ & 0 & 1 \\ 0 & 0 & 0 \\ 1 & 0 & 1 \end{matrix}

(Bemerkung: ⊕ und ⊙ sind die aussagelogischen Relationen XOR und AND.)

Homepage der Vorlesung:

http://www.math.uni-bonn.de/people/logic/Lectures/SoSe2002/Vorlesung.html
Newsgroup: uni-bonn.math.logik