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	2	1	2	5	1	2	2	8	3	4	0	10	0	4	50

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 * (2 Punkte)

Ein Mann steht mit einem Wolf, einer Ziege und einem Kohl am Ufer eines Flusses und möchte diesen überqueren. Es steht ein Boot zur Verfügung, in dem neben ihm nur ein weiterer Passagier Platz hat. Wie kann er den Fluss überqueren, ohne dass dabei der Wolf die Ziege oder die Ziege den Kohl frisst?

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.$