Kurs:Einführung in die mathematische Logik/8/Klausur

Aufgabe	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	${}\sum$
Punkte	3	3	1	3	3	2	4	4	8	2	2	4	0	6	0	5	50

Aufgabe * (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

1. Eine widersprüchliche Ausdrucksmenge ${}\Gamma \subseteq L^{V}$ in der Sprache der Aussagenlogik zu einer Aussagenvariablenmenge ${}V$.
2. Die Produktmenge aus zwei Mengen ${}L$ und ${}M$.
3. Die Ableitbarkeit eines Ausdrucks ${}\alpha \in L^{S}$ im prädikatenlogischen Kalkül.
4. Die Repräsentierbarkeit einer Funktion

   $F\colon \mathbb {N} ^{r}\longrightarrow \mathbb {N} ^{s}$

   in einer Menge ${}\Gamma$ von arithmetischen Ausdrücken.

5. Das modallogische Möglichkeitsaxiom.
6. Die Nachfolgermenge in einem gerichteten Graphen.

Aufgabe * (3 Punkte)

Formuliere die folgenden Sätze.

1. Der Satz über die Vorgängereigenschaft in einem Peano-Halbring.
2. Der Endlichkeitssatz für die Prädikatenlogik.
3. Die Unentscheidbarkeit der Arithmetik.

Aufgabe * (1 Punkt)

In einer psychologischen Längsschnittstudie wird die Entwicklung von Einstellungen und Verhaltensweisen von Personen untersucht. Ein Fallbeispiel: Im Alter von ${}20$ Jahren geht Linda regelmäßig auf Demonstrationen, sie hilft im Eine-Welt-Laden mit, braut ökologisches Bier, kocht Bio-Gemüse und studiert manchmal Soziologie.

Welcher der folgenden Befunde ist nach 10 Jahren am unwahrscheinlichsten?

1. Linda arbeitet für eine Versicherungsagentur.
2. Linda engagiert sich bei Attac und arbeitet für eine Versicherungsagentur.
3. Linda engagiert sich bei Attac.

Aufgabe * (3 Punkte)

Erläutere das Prinzip Beweis durch Widerspruch für eine Aussage der Form „Aus ${}A$ folgt ${}B$“.

Aufgabe * (3 Punkte)

Es sei ${}\Gamma \subseteq L^{V}$ eine Ausdrucksmenge in der Sprache der Aussagenlogik über einer Aussagenvariablenmenge ${}V$ und es sei ${}\alpha \in L^{V}$. Es gelte

$\Gamma \not \vdash \alpha .$

Zeige, dass dann

$\Gamma \cup \{\neg \alpha \}$

widerspruchsfrei ist.

Aufgabe * (2 Punkte)

Es sei ein Symbolalphabet ${}S$ einer Sprache erster Stufe gegeben, ${}\alpha \in L^{S}$ und ${}I$ eine Interpretation mit ${}I\vDash \alpha$. Zeige durch ein Beispiel, dass daraus nicht im Allgemeinen die Gültigkeit ${}I\vDash \alpha {\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}$ unter einer Substitution folgt.

Aufgabe * (4 Punkte)

Es sei ${}(\mathbb {N} ,0,^{\prime })$ ein Dedekind-Peano-Modell der natürlichen Zahlen. Zeige, dass die Addition durch die Bedingungen

$x+0=x{\text{ für alle }}x\in \mathbb {N} {\text{ und }}x+y'=(x+y)'{\text{ für alle }}x,y\in \mathbb {N}$

eindeutig bestimmt ist.

Aufgabe * (4 (1+1+1+1) Punkte)

Es sei ${}(M,\preccurlyeq )$ eine nichtleere geordnete Menge. Wir betrachten die Relation ${}\prec$ auf ${}M$, die durch ${}x\prec y$, falls ${}x\preccurlyeq y$ und ${}x\neq y$ gilt, definiert ist.

1. Ist ${}\prec$ transitiv?
2. Ist ${}\prec$ reflexiv?
3. Charakterisiere, wann ${}\prec$ symmetrisch ist.
4. Ist ${}\prec$ antisymmetrisch?

Aufgabe * (8 Punkte)

Beweise den Satz von Henkin.

Aufgabe * (2 Punkte)

Zeige, dass mit

$\vdash \alpha \rightarrow \beta$

auch

$\vdash \forall x\alpha \rightarrow \forall x\beta$

gilt.

Aufgabe * (2 Punkte)

Zeige

$\vdash \forall x{\left(\alpha \wedge \beta \right)}\rightarrow \forall x\alpha \wedge \forall x\beta .$

Aufgabe * (4 Punkte)

Beweise den Isomorphiesatz für (zweitstufige) Dedekind-Peano-Modelle.

Aufgabe (0 Punkte)

Aufgabe * (6 (4+2) Punkte)

Es sei

${}S=\{0,1,+,\cdot ,\geq \}\,$

das Symbolalphabet für einen angeordneten Körper und es sei ${}\mathbb {R}$ die ${}S$- Struktur mit der Standardinterpretation.

1. Zeige, dass die Äquivalenzklassen zur elementaren Äquivalenz einelementig sind.
2. Zeige, dass es für die Elemente im Allgemeinen keinen charakterisierenden Ausdruck gibt.

Aufgabe (0 Punkte)

Aufgabe * (5 Punkte)

Zeige, dass in einem gerichteten Graphen ${}(M,R)$ das modallogische euklidische Axiom genau dann gilt, wenn ${}R$ euklidisch ist.