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

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

Aufgabe * (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

1. Eine Mersennesche Primzahl.
2. Die (rekursiv definierte) Gültigkeit eines prädikatenlogischen ${}S$-Ausdruckes ${}\alpha$ bei einer ${}S$- Interpretation auf einer Menge ${}M$.
3. Ein Isomorphismus

   $\varphi \colon M\longrightarrow N$

   zwischen zwei ${}S$-Strukturen ${}M$ und ${}N$.

4. Die ${}R$-Aufzählbarkeit einer Teilmenge ${}T\subseteq \mathbb {N}$.
5. Das modallogische Transitivitätsaxiom.
6. Die rekursive Definition der Gültigkeit eines modallogischen Ausdrucks ${}\alpha$ in einem modallogischen Modell ${}(M,R,\mu )$.

Aufgabe * (3 Punkte)

Formuliere die folgenden Sätze.

1. Der Satz über die Auffüllung widerspruchsfreier aussagenlogischer Mengen (abzählbarer Fall).
2. Das Koinzidenzlemma.
3. Das Unvollständigkeitslemma.

Aufgabe * (1 Punkt)

Finde einen möglichst einfachen aussagenlogischen Ausdruck, der die folgende tabellarisch dargestellte Wahrheitsfunktion ergibt.

${}p$ ${}q$ ${}?$ w w w w f f f w w f f f

Aufgabe * (2 Punkte)

Beweise die aussagenlogische Tautologie

$\vdash \alpha \rightarrow (\beta \rightarrow \alpha \wedge \beta )$

aus den aussagenlogischen Axiomen.

Aufgabe * (5 Punkte)

Es sei ${}\Gamma \subseteq L^{V}$ eine Ausdrucksmenge in der Sprache der Aussagenlogik zu einer Aussagenvariablenmenge ${}V$. Es sei ${}\Gamma$ widerspruchsfrei, abgeschlossen unter Ableitungen und für jede Aussagenvariable ${}p\in V$ gelte ${}p\in \Gamma$ oder ${}\neg p\in \Gamma$. Zeige, dass dann ${}\Gamma$ maximal widerspruchsfrei ist.

Aufgabe * (1 Punkt)

Wir betrachten den Satz „Lucy Sonnenschein tanzt auf allen Hochzeiten“. Negiere diesen Satz durch eine Existenzaussage.

Aufgabe * (2 Punkte)

Es seien ${}x,y,z,w$ Variablen und ${}V$ ein zweistelliges Funktionssymbol. Welche der folgenden Wörter sind Terme?

1. ${}VxyzVVw$,
2. ${}VVxyVzw$,
3. ${}VVxyzVw$,
4. ${}VxVyVzw$,
5. ${}xVyVzVw$,
6. ${}VVVxyzw$,
7. ${}VxyVVzw$,
8. ${}VVxVyzw$,
9. ${}VxyVzw$,
10. ${}VxVyzVw$,
11. ${}VxVVyzw$,
12. ${}VxyVzVw$.

Aufgabe (2 Punkte)

Man erläutere für einen Ableitungskalkül den Unterschied zwischen einer syntaktischen Grundtautologie und einer Ableitungsregel.

Aufgabe * (8 Punkte)

Es seien ${}x,y$ Variablen, ${}s,t$ Terme und ${}\alpha$ ein Ausdruck in einer prädikatenlogischen Sprache. Es seien ${}u,v$ neue Variablen, die weder in ${}s$ noch in ${}t$ noch in ${}\alpha$ vorkommen. Zeige, dass

$\alpha {\frac {s,t}{x,y}}\leftrightarrow \alpha {\frac {s{\frac {v}{y}}}{x}}{\frac {t{\frac {u}{x}}}{y}}{\frac {x}{u}}{\frac {y}{v}}$

allgemeingültig ist, wobei der Ausdruck rechts als die Hintereinanderausführung von vier Einzelsubstitutionen (von links nach rechts) zu lesen ist.

Aufgabe * (3 Punkte)

Zeige

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

Aufgabe * (4 Punkte)

Zeige, dass die Vorgängereigenschaft

$\forall x{\left(x\neq 0\rightarrow \exists y(x=Ny)\right)}$

aus der Menge der Peano-Axiome für den Nachfolger folgt.

Aufgabe (0 Punkte)

Aufgabe * (10 Punkte)

Beweise den Fixpunktsatz der Prädikatenlogik.

Aufgabe (0 Punkte)

Aufgabe * (4 Punkte)

Es sei ${}M$ ein ${}K$- modallogisches System, in dem zusätzlich das Transitivitätsaxiom gelte. Ferner sei ${}s$ ein modallogischer Ausdruck, für den

$M\vdash \neg \Box s\leftrightarrow s$

gelte. Zeige für einen beliebigen Ausdruck ${}p$ die Ableitbarkeit

$M\vdash \neg \Box (p\wedge \neg p)\rightarrow \neg \Box s.$

Aufgabe (0 Punkte)