Kurs:Einführung in die mathematische Logik/1/Test/Klausur

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

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. Die Addition in einem Dedekind-Peano-Modell ${}\mathbb {N}$.

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)

Gehört das leere Wort ${}\emptyset$ zur Sprache der Aussagenlogik ${}L^{V}$ zu einer Aussagenvariablenmenge ${}V$?

Aufgabe (2 Punkte)

Zeichne einen Abstammungsbaum für die Aussage

$(((\neg (\neg (p)))\rightarrow (\neg (q)))\vee (\neg (r)))\leftrightarrow ((\neg (r))\wedge (q)).$

Aufgabe * (1 Punkt)

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

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

Aufgabe * (3 Punkte)

Zeige, dass der aussagenlogische Ausdruck

${\left(r\rightarrow {\left(p\wedge \neg q\right)}\right)}\rightarrow {\left(\neg p\rightarrow {\left(\neg r\vee q\right)}\right)}$

allgemeingültig ist

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

Man gebe ein Beispiel für eine mathematische Existenzaussage, die mit dem Lemma von Zorn bewiesen wird, und führe den Beweis durch.

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 ${}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 * (1 Punkt)

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

Aufgabe * (4 Punkte)

Es sei das arithmetische Alphabet ${}\{0,1,+,\cdot \}$ zusammen mit der Variablenmenge ${}\{x,y\}$ gegeben. Interpretiere den Term

$((0+1)+x)\cdot (1+(y+1))$

unter den folgenden Interpretationen, wobei ${}M$ die Grundmenge der Interpretation bezeichne.

1. ${}M=\mathbb {N}$ mit der Standardinterpretation und der Variablenbelegung ${}I(x)=5$ und ${}I(y)=3$.
2. ${}M=\operatorname {Mat} _{2}(\mathbb {R} )$ mit der Standardinterpretation

   $I(0)={\begin{pmatrix}0&0\\0&0\end{pmatrix}},\,I(1)={\begin{pmatrix}1&0\\0&1\end{pmatrix}}$

   und der üblichen Matrizenaddition und Matrizenmultiplikation und der Variablenbelegung ${}I(x)={\begin{pmatrix}1&2\\3&4\end{pmatrix}}$ und ${}I(y)={\begin{pmatrix}3&-2\\0&5\end{pmatrix}}$.

3. ${}M=\mathbb {Z}$, mit

   $I(0)=5,\,I(1)=-1,\,I(x)=0,\,I(y)=0,$

   und wo sowohl ${}+$ als auch ${}\cdot$ als Subtraktion interpretiert werden.

4. ${}M=$ Potenzmenge von ${}\{1,2,3,4,5\}$ mit

   $I(0)=\emptyset ,\,I(1)=\{1,2,3,4,5\},\,I(x)=\emptyset ,\,I(y)=\{2,4\},$

   und wo ${}+$ als ${}\cup$ und ${}\cdot$ als ${}\cap$ interpretiert wird.

Aufgabe * (7 (3+4) Punkte)

Es sei ${}V=\{x,y,z,u,v,w\}$ eine Variablenmenge, ${}0$ eine Konstante und ${}-,+,\cdot$ zweistellige Funktionssymbole, die wir zentral unter der Zuhilfenahme von Klammern schreiben. Wir betrachten den prädikatenlogischen Ausdruck ${}\alpha$, der durch

$\forall x\forall y\forall z\forall u\forall v\forall w{\left(\left[(z-x)(z-y)+(w-u)(w-v)=0\right]\longrightarrow \left[(x-y)(x-y)+(u-v)(u-v)=(x-z)(x-z)+(u-w)(u-w)+(y-z)(y-z)+(v-w)(v-w)\right]\right)}$

gegeben ist.

1. Zeige, dass ${}\alpha$ bei Interpretation in einem Körper ${}K$ wahr wird, wenn man ${}0$ als ${}0$ und ${}\{-,+,\cdot \}$ als Subtraktion, Addition und Multiplikation interpretiert.
2. Welcher wichtige mathematische Satz verbirgt sich dahinter?

Aufgabe * (3 Punkte)

Formuliere die Injektivität für eine Abbildung

$f\colon D\longrightarrow Z$

prädikatenlogisch mit Hilfe der Verwendung von Sorten.

Aufgabe * (8 (3+5) Punkte)

Es sei ${}S$ ein Symbolalphabet erster Stufe und ${}U\subseteq S$ eine Teilmenge. Es sei ${}t$ ein ${}U$- Term und ${}\alpha$ ein ${}U$- Ausdruck. Es seien zwei ${}S$- Interpretationen ${}I_{1}$ und ${}I_{2}$ in einer gemeinsamen Grundmenge ${}M$ gegeben, die auf ${}U$ identisch seien. Beweise die folgenden Aussagen.

1. Es ist ${}I_{1}(t)=I_{2}(t)$.
2. Es ist ${}I_{1}\vDash \alpha$ genau dann, wenn ${}I_{2}\vDash \alpha$ (dazu genügt bereits, dass die Interpretationen auf den Symbolen aus ${}U$ und auf den in ${}\alpha$ frei vorkommenden Variablen identisch sind).

Aufgabe * (3 Punkte)

Es sei ${}(\mathbb {N} ,0,^{\prime })$ ein Dedekind-Peano-Modell der natürlichen Zahlen. Zeige, dass die Addition die Abziehregel erfüllt, also die Aussage, dass aus einer Gleichung ${}n+k=m+k$ die Gleichheit ${}n=m$ folgt (dabei dürfen grundlegendere Regeln wie die Assoziativität der Addition und ähnliches verwendet werden).

Aufgabe * (2 Punkte)

Formalisiere in der arithmetischen Sprache die (wahre) Aussage, dass es unendlich viele Primzahlen gibt.

Aufgabe * (6 (3+3) Punkte)

Es sei ${}(M,0,N)$ ein Modell für die Peano-Axiome für den Nachfolger.

1. Zeige, dass ${}N$ fixpunktfrei ist, d.h. dass

   ${}N(x)\neq x\,$

   für alle ${}x\in M$.

2. Zeige, dass ${}N$ periodenfrei ist. D.h. für jedes ${}\ell \in \mathbb {N} _{+}$ ist

   ${}N^{\ell }(x)\neq x\,,$

   wobei

   ${}N^{\ell }=N\circ \cdots \circ N\,$

   die ${}\ell$-fache Hintereinanderschaltung von ${}N$ bedeutet.