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

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

Aufgabe * (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe. Bei 3.-7. bedeutet ${}S$ ein Symbolalphabet einer prädikatenlogischen Sprache erster Stufe.

1. Ein Primzahlzwilling.
2. Die Bestandteile einer Grundtermmenge.
3. Eine ${}S$-Struktur zu einem Symbolalphabet ${}S$ einer Sprache erster Stufe.
4. Ein allgemeingültiger prädikatenlogischer Ausdruck ${}\alpha \in L^{S}$.
5. Ein ${}S$-Homomorphismus

   $\varphi \colon M\longrightarrow N$

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

6. Eine arithmetisch repräsentierbare Relation ${}R\subseteq \mathbb {N} ^{r}$.

Aufgabe * (3 Punkte)

Formuliere die folgenden Sätze.

1. Der Isomorphiesatz für (zweitstufige) Dedekind-Peano-Modelle.
2. Der Vollständigkeitssatz der Prädikatenlogik.
3. Der erste Gödelsche Unvollständigkeitssatz.

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

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

Aufgabe * (3 Punkte)

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

$\Gamma \cup \{\alpha \}\vdash \beta$

zu

$\Gamma \vdash \alpha \rightarrow \beta$

äquivalent ist.

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

Erstelle einen prädikatenlogischen Ausdruck ${}\alpha$, der in einer Struktur genau dann gilt, wenn die Grundmenge der Struktur genau ${}4$ Elemente besitzt.

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 * (12 (1+1+4+2+4) Punkte)

Es sei ${}G$ ein dreistelliges Relationssymbol und ${}L$ die zugehörige prädikatenlogische Sprache. Es sei ${}I$ die Interpretation, bei der die Grundmenge die euklidische Ebene ist und ${}G$ durch die dreistellige Relation interpretiert wird, bei der ${}G(A,B,C)$ zutrifft, wenn die Punkte ${}A,B,C$ auf einer Geraden liegen.

1. Zeige ${}I\vDash Gxyz\leftrightarrow Gyxz$.
2. Zeige, dass im Allgemeinen nicht ${}I\vDash \forall x\forall y\forall z{\left(Gxyz\rightarrow Gxyu\right)}$ gelten muss.
3. Es sei ${}\Gamma =\{\forall x\forall y\forall z{\left(Gxyz\leftrightarrow Gyxz\right)},\,\forall x\forall y\forall z{\left(Gxyz\leftrightarrow Gxzy\right)}\}$. Erstelle eine Ableitung für ${}\Gamma \vdash Gxyz\leftrightarrow Gyzx$.
4. Zeige, dass der Ausdruck ${}Gxyz\wedge Gxyu$ bei der gegebenen Interpretation nicht bedeutet, dass die die freien Variablen ${}x,y,z,u$ belegenden Punkte auf einer Geraden liegen.
5. Formuliere einen Ausdruck aus ${}L$ in vier freien Variablen, der bei der gegebenen Interpretation besagt, dass die die freien Variablen belegenden Punkte auf einer Geraden liegen.

Aufgabe (3 Punkte)

Erläutere den Begriff Sortenprädikat an einem mathematischen Beispiel.

Aufgabe * (2 Punkte)

Man gebe ein Beispiel für einen kommutativen Halbring, der kein Peano-Halbring ist.

Aufgabe (6 (3+3) Punkte)

1. Entwerfe ein Programm für eine Registermaschine, das die Potenz ${}r_{j}^{r_{k}}$ berechnet, wobei ${}r_{j}$ und ${}r_{k}$ die Inhalte im ${}j$-ten bzw. ${}k$-ten Register sind.
2. Entwerfe ein Programm für eine Registermaschine, das entscheidet, ob der Registerinhalt ${}r_{i}$ des Registers ${}R_{i}$ die echte Potenz einer natürlichen Zahl ist.

Aufgabe * (5 Punkte)

Es sei ${}T\subseteq \mathbb {N}$ eine Teilmenge von natürlichen Zahlen. Zeige, dass ${}T$ genau dann ${}R$- entscheidbar ist, wenn sowohl ${}T$ als auch das Komplement ${}\mathbb {N} \setminus T$ ${}R$- aufzählbar ist.

Aufgabe * (6 Punkte)

Man gebe für die Abbildung

$F\colon \mathbb {N} \longrightarrow \mathbb {N}$

mit

${}F(n)={\begin{cases}{\sqrt {n}}\,,{\text{ falls }}{\sqrt {n}}\in \mathbb {N} \,,\\0{\text{ sonst}}\,,\end{cases}}\,$

einen Ausdruck an, der ${}F$ arithmetisch repräsentiert.

Aufgabe * (7 Punkte)

Es sei ${}\Gamma \subseteq L^{\rm {Ar}}$ eine arithmetische Ausdrucksmenge ohne freie Variablen und ${}R\subseteq \mathbb {N}$ eine Relation. Es seien ${}\alpha ,\beta \in L^{\rm {Ar}}$ Ausdrücke in einer freien Variablen ${}x$. Zeige, dass aus

$\Gamma \vdash \alpha \leftrightarrow \beta$

folgt, dass ${}\alpha$ in ${}\Gamma$ die Relation ${}R$ genau dann repräsentiert, wenn ${}\beta$ in ${}\Gamma$ die Relation ${}R$ repräsentiert.