Kurs:Einführung in die mathematische Logik/1/Klausur mit Lösungen/kontrolle

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

Aufgabe * (3 Punkte)Referenznummer erstellen

Aufgabe * (3 Punkte)Referenznummer erstellen

Aufgabe * (1 Punkt)Referenznummer erstellen

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)Referenznummer erstellen

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

Aufgabe * (4 Punkte)Referenznummer erstellen

Es sei ${}V$ eine Menge an Aussagenvariablen und ${}\Gamma \subseteq L^{V}$ eine maximal widerspruchsfreie Teilmenge der zugehörigen Sprache der Aussagenlogik. Zeige, dass für jedes ${}\alpha \in L^{V}$ entweder ${}\alpha \in \Gamma$ oder ${}\neg \alpha \in \Gamma$ gilt.

Aufgabe * (6 Punkte)Referenznummer erstellen

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)Referenznummer erstellen

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)Referenznummer erstellen

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)Referenznummer erstellen

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)Referenznummer erstellen

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

Aufgabe * (2 Punkte)Referenznummer erstellen

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

Aufgabe (6 (3+3) Punkte)Referenznummer erstellen

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)Referenznummer erstellen

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)Referenznummer erstellen

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)Referenznummer erstellen

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.