[figure]

Mathematisches Institut der Universität Bonn Abt. für Grundlagenforschung der Mathematik

Prof. Dr. Peter Koepke

Einführung in die Mathematische Logik WS 2000/2001

Übungsaufgaben, Folge 1, Abgabe: 26.10.2000 in der Vorlesung

Aufgabe 1 (a) Formalisieren Sie in einer geeigneten Quantorensprache folgende aus dem Grundstudium bekannten Eigenschaften einer Funktion f: ℝ → ℝ: (α) f ist monoton wachsend; (β) f ist stetig (im Sinne der ε-δ-Definition von Stetigkeit); (γ) f ist gleichmäßig stetig; (δ) f hat genau eine Unstetigkeitsstelle; (ε) f besitzt ein Maximum; (ζ) f hat die Zwischenwerteigenschaft; (η) f ist differenzierbar.

(b) Formalisieren Sie in einer geeigneten Quantorensprache folgende Eigenschaften der natürlichen Zahlen k und n: (α) n ist gerade; (β) n ist Summe von zwei Quadratzahlen; (γ) k ist ein Teiler von n; (δ) n ist eine Primzahl; (ε) Es gibt unendlich viele Primzahlen.

Aufgabe 2 (a) Zeigen Sie auf der Grundlage von EML die Richtigkeit folgender Aussagen: (α) ∅ ∈ V; (β) ∀x {x} ∈ V; (γ) ∀x, y {x, y} ∈ V; (δ) ∀x, y {{x}, {x, y}} ∈ V; (ε) ∀x, y x ∪ y ∈ V.

(b) Berechnen Sie 𝒫(∅), 𝒫(𝒫(∅)), 𝒫(𝒫(𝒫(∅))) sowie 𝒫(𝒫(𝒫(𝒫(∅)))) und argumentieren Sie auf der Grundlage von EML, dass es sich hierbei um Mengen handelt.

(c) Betrachten Sie naiv die Menge ℕ der natürlichen Zahlen und die Menge ℚ der rationalen Zahlen mit ihren kanonischen Ordnungen <. Interpretieren Sie das System EML in (ℕ, <) und (ℚ, <), d.h., bestimmen Sie, welche Aussagen entstehen, wenn man das Relationssymbol ∈ in den Axiomen von EML durch < ersetzt und den Laufbereich der Quantoren auf die Elemente von ℕ bzw. ℚ beschränkt. Formulieren Sie in Worten, welche Aussagen über natürliche bzw. rationale Zahlen dadurch entstehen. Bestimmen Sie, ob diese richtig oder falsch sind.

Aufgabe 3 Es sei n eine natürliche Zahl, n ≠ 0. 𝕎_{n} :≡ {f | f: {0, 1}^{n} → {0, 1}} ist die Menge der n-stelligen Wahrheitsfunktionen. Entsprechend den Junktoren der Aussagenlogik definieren wir ein- bzw. zweistellige Wahrheitswertfunktionen ¬, ∨, ∧, → und ↔ durch „Wahrheitstafeln“ , wobei wir z.B. P ∧ Q statt ∧(P, Q) schreiben:

\begin{matrix}P & ¬ P \\ 0 & 1 \\ 1 & 0 \end{matrix}  \begin{matrix}P & Q & P ∨ Q & P ∧ Q & P → Q & P ↔ Q \\ 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 1 & 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 & 1 \end{matrix}

(a) Schreiben Sie die Funktionen ∧, → und ↔ als Komposition von ¬ und ∨.

(b) Zeigen Sie, dass sich jede Wahrheitswertfunktion als eine aus ¬ und ∨ aufgebaute Komposition darstellen läßt.

(c) Läßt sich jede Wahrheitswertfunktion als Komposition von → darstellen?

(d) Zeigen Sie, dass 𝕎_{n} genau 2^{2^{n}} Elemente besitzt.

Aufgabe 4 Eine Boolesche Algebra ist ein Tupel (A, ∧ , ∨ , ( )^{∗}, 0, 1), wobei A eine Menge ist und 0, 1 ∈ A sowie ∧: A×A → A, (a, b) ↦ a ∧ b; ∨: A×A → A, (a, b) ↦ a ∨ b; ( )^{∗}: A → A, a ↦ a^{∗} gilt, so dass folgende Eigenschaften für alle a, b, c ∈ A erfüllt sind:

(i) 0 ≠ 1 (ii) a ∧ b = b ∧ a, a ∨ b = b ∨ a; (iii) a ∧ (b ∧ c) = (a ∧ b) ∧ c, a ∨ (b ∨ c) = (a ∨ b) ∨ c; (iv) (a ∧ b) ∨ b = b, (a ∨ b) ∧ b = b;

(v) (a ∧ b) ∨ c = (a ∨ c) ∧ (b ∨ c), (a ∨ b) ∧ c = (a ∧ c) ∨ (b ∧ c); (vi) a ∧ a^{∗} = 0, a ∨ a^{∗} = 1. Zeigen Sie:

(a) Falls X eine nichtleere Menge und 𝒪 eine Topologie auf X ist, so bildet die Menge der Teilmengen von X, die bezüglich 𝒪 offen und abgeschlossen sind, zusammen mit den Verknüpfungen ∩, ∪ und der Komplementbildung bzgl. X sowie den ausgezeichneten Elementen ∅ und X eine Boolesche Algebra.

(b) Folgt aus (a), dass (mit den in (a) angegebenen Verknüpfungen und ausgezeichneten Elementen) auch 𝒫(X) eine Boolesche Algebra ist (falls 𝒫(X) ∈ V gilt)?