MATHEMATISCHES INSTITUT DER UNIVERSITÄT BONN Arbeitsgruppe Mathematische Logik Prof. Dr. Peter Koepke

Bonn, den 20.06.2002

Einführung in die Mathematische Logik SS 2002 Übungsaufgaben, Folge 9, Abgabe: 27.06 nach der Vorlesung

Definition 1 S_{aok} := {<, +, ·, 0, 1} ist das Alphabet der Sprache L_{aoK} der angeordneten Körper. Die Theorie Φ_{aoK} der angeordneten Körper besteht aus folgenden Aussagen:

1. ∀x∀y(x + y = y + x). (Kommutativität der Addition.)

2. ∀x∀y∀z((x + y) + z = x + (y + z)). (Assozivität der Addition.)

3. ∀x(x + 0 = x). (Neutrales Element der Addition.)

4. ∀x∃y(x + y = 0). (Existenz des additiven Inversen.)

5. ∀x∀y(x · y = y · x). (Kommutativität der Multiplikation.)

6. ∀x∀y∀z((x · y) · z = x · (y · z)). (Assozivität der Multiplikation.)

7. ∀x(x · 1 = x). (Neutrales Element der Multiplikation.)

8. ∀x∃y(x · y = 1). (Existenz des multiplikativen Inversen.)

9. ∀x∀y∀z((x + y) · z = (x · z) + (y · z)). (Distributivität.)

10. ¬(0 = 1).

11. ∀x(¬(x < x)). (Irreflexivität.)

12. ∀x∀y((¬(x = y) → (x < y ∨ y < x)). (Konnexität.)

13. ∀x∀y∀z((x < y ∧ y < z) → (x < z)). (Transitivität.)

14. ∀x∀y∀z((x < y) → (x + z < y + z)).

15. ∀x∀y((0 < x ∧ 0 < y) → (0 < x · y)).

Aufgabe 1 Schreiben Sie die folgenden Aussagen (i) – (iii) als Formeln der Sprache L_{aoK} und leiten Sie diese Formeln aus Φ_{aoK} im Ausdruckskalkül ab.

(i) ∀x∀y (−x) · (−y) = x · y; (ii) ∀x (x > 0 → −x < 0); (iii) 0 < 1. Hinweis: Zeigen Sie die Ableitbarkeit der Formeln in der hier angegebenen Reihenfolge.

Aufgabe 2 Untersuchen Sie, ob die folgenden Regeln korrekt sind.

\frac{{(φ_{2} → ψ_{2}) \atop (φ_{2} → ψ_{2})}}{((φ_{1} ∨ φ_{2}) → (ψ_{1} ∨ ψ_{2}))}; \frac{{(φ_{2} → ψ_{2}) \atop (φ_{2} → ψ_{2})}}{((φ_{1} ∨ φ_{2}) → (ψ_{1} ∧ ψ_{2}))}; \frac{(φ → ψ)}{((∃xφ) → (∃xψ))};

\frac{(φ → ψ)}{((∀xφ) → (∃xψ))}; \frac{φ \frac{fy}{x}}{∀xφ}, falls f einstellig ist und f, y nicht in ∀xφ vorkommen.

Aufgabe 3 Es sei (∃∀) die Regel \overline{((∃xφ) → (∀xφ))} .

Der Kalkül S′ entstehe aus dem Ausdruckskalkül durch Hinzunahme der Regel (∃∀).

(a) Ist (∃∀) eine im Ausdruckskalkül ableitbare Regel?

(b) Ist jeder Ausdruck in S′ ableitbar?

Aufgabe 4 Es folgt der Text einer Flaschenpost aus Freudesien:

Lieber Empfänger, seit Wochen quält mich die Frage, ob es einen Rhinodetiker gibt, der nicht unter Spuckzwang leidet. Bislang habe ich nur folgendes herausbekommen: Wenn jeder, der sich in der Pedalphase befindet, keinesfalls ein Altrotiker sein kann, dann gibt es einen Mysteriker ohne Niesophobie.

Wenn alle Rhinodetiker unter dem Spuckzwang leiden, dann hat kein Physiopath eine Lachneurose. Wenn alle Freudesier, die einen Damokleskomplex haben, unter Kitzelzwang leiden, dann hat jeder Libidot ein gestörtes Unterich.

Wenn es einen nicht unter Kitzelzwang leidenden Freudesier gibt, der einen Damokleskomplex hat, und kein Physiopath unter Lachneurose leidet, dann haben alle Mysteriker eine Niesophopie. Sollte es einen Altrotiker geben, der sich in der Pedalphase befindet, dann gibt es auch einen Libidoten ohne ein gestörtes Unterich. Freilich hat jeder Libidot dann und nur dann ein gestörtes Unterich, wenn alle Mysteriker eine Niesophobie haben.

Ich bin sicher, daß ich mit diesen Informationen meine Frage beantworten kann, leider weiss ich nicht wie. Ich hoffe, du kannst dieses Mysterium klären. Gruß

Dein Forscher

Helfen Sie das Rätsel zu lösen, indem sie obige Aussagen in einer geeigneten Sprache formalisieren und anschliessend mit dem Ausdruckskalkül die Lösung folgern.

Homepage der Vorlesung:

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