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

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

Aufgabe * (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

1. Ein Primzahlzwilling.
2. Eine Wahrheitsbelegung für eine Menge an Aussagenvariablen.
3. Eine maximal widerspruchsfreie Teilmenge ${}\Gamma \subseteq L^{V}$ zu einer Menge ${}V$ an Aussagenvariablen.
4. Die Interpretation der Terme zu einem Symbolalphabet ${}S$ in einer gegebenen ${}S$- Interpretation auf einer Grundmenge ${}M$.
5. Ein allgemeingültiger prädikatenlogischer Ausdruck ${}\alpha \in L^{S}$.
6. Ein gerichteter Graph.

Aufgabe * (3 Punkte)

Formuliere die folgenden Sätze.

1. Das Lemma von Zorn.
2. Der Vollständigkeitssatz der Aussagenlogik.
3. Der Satz über die induktive Definition einer Abbildung auf einem Peano-Dedekind-Modell ${}(N,0,\prime )$.

Aufgabe * (1 Punkt)

Negiere die Aussage „Martina findet alle Jungs im Kurs außer Markus zuckersüß“ durch eine Aussage, in der eine Existenzaussage und eine Oder-Verknüpfung vorkommen.

Aufgabe * (7 Punkte)

Beweise den Satz über die Auffüllung widerspruchsfreier aussagenlogischer Mengen im abzählbaren Fall.

Aufgabe * (7 (1+1+2+3) Punkte)

Der Planet Trigeno wird von einer einzigen Tierart bevölkert, den Trigos. Diese Tierart besitzt drei Geschlechter: Antilopen (A), Büffel (B) und Cnus (C). Bei der Paarung treffen zwei Individuen zusammen und erzeugen ein neues Individuum. Wenn das Paar gleichgeschlechtlich ist, so ist das Ergebnis wieder dieses Geschlecht, wenn das Paar gemischtgeschlechtlich ist, so ist das Ergebnis das dritte unbeteiligte Geschlecht. Alle Tiere gehören einer eindeutigen Generation an.

1. Die ${}n$-te Generation bestehe nur aus einem einzigen Geschlecht. Zeige, dass jede weitere Generation auch nur aus diesem Geschlecht besteht.
2. Die ${}n$-te Generation bestehe nur aus zwei Individuen unterschiedlichen Geschlechts. Zeige, dass diese Geschlechter mit ihrer Generation aussterben.
3. Es gelte nun die zusätzliche Bedingung, dass jedes Paar nur einen Nachkommen erzeugen darf. Zeige, dass die Tierart genau dann aussterben muss, wenn es in einer Generation nur zwei oder weniger Individuen gibt.
4. Es gelte nun die zusätzliche Bedingung, dass jedes Paar nur einen Nachkommen erzeugen darf, und in jeder Generation gebe es genau drei Individuen. Beschreibe die möglichen Generationsabfolgen. Welche Periodenlängen treten auf?

Aufgabe * (2 Punkte)

Es seien ${}p,q$ verschiedene Aussagenvariablen. Begründe die (Un)Richtigkeit der beiden folgenden Aussagen.

1. ${}\vdash p$ genau dann, wenn ${}\vdash q$.
2. ${}\vdash p\leftrightarrow q$.

Aufgabe * (4 Punkte)

Es sei ein Symbolalphabet ${}S$ einer Sprache erster Stufe gegeben. Es seien ${}x_{1},\ldots ,x_{k}$ paarweise verschiedene Variablen und ${}t_{1},\ldots ,t_{k}$ fixierte ${}S$- Terme. Zeige, dass für jeden ${}S$-Satz ${}\alpha \in L_{0}^{S}$ die Gleichheit

${}\alpha {\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}=\alpha \,$

gilt.

Aufgabe (0 Punkte)

Aufgabe * (5 Punkte)

Beweise den Satz über die Division mit Rest in einem Peano-Halbring.

Aufgabe * (5 (3+2) Punkte)

Es sei ${}S$ ein Symbolalphabet ohne Funktionssymbole und sei ${}M$ eine endliche ${}S$- Struktur.

1. Charakterisiere die Automorphismengruppe von ${}M$ mit Hilfe der elementaren Äquivalenzklassen.
2. Beweise Satz 17.6 (Einführung in die mathematische Logik (Osnabrück 2021)) in diesem Fall.

Aufgabe * (3 Punkte)

Erstelle ein Programm für eine Registermaschine, das abwechselnd ${}1$ und ${}0$ ausdruckt, das mit sechs Befehlszeilen auskommt und lediglich einen Druckbefehl verwendet.

Aufgabe (0 Punkte)

Aufgabe (0 Punkte)

Aufgabe * (4 Punkte)

Es sei ${}M$ eine beliebige Menge. Zeige, dass es keine surjektive Abbildung von ${}M$ in die Potenzmenge ${}{\mathfrak {P}}\,(M)$ geben kann.

Aufgabe (0 Punkte)

Aufgabe * (4 Punkte)

Zeige, dass in einem gerichteten Graphen ${}(M,R)$ das modallogische Möglichkeitsaxiom genau dann gilt, wenn in ${}M$ jeder Punkt einen Nachfolger besitzt.