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

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

Aufgabe * (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

1. Eine Primzahl.
2. Die Sprache der Aussagenlogik $L^V$ zu einer Aussagenvariablenmenge $V$.
3. Die Uminterpretation $I\frac{m}{x}$ zu einer $S$-Interpretation $I$ in einer Menge $M$, wobei $x$ eine Variable und $m\in M$ ein Element der Grundmenge ist.
4. Der Rang eines prädikatenlogischen Ausdrucks $\alpha$.
5. Eine $R$-berechenbare Funktion

   $F:{\mathbb{N}}^k⟶\mathbb{N}.$

6. Eine $K$-Modallogik.

Aufgabe * (3 Punkte)

Formuliere die folgenden Sätze.

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

Aufgabe * (4 (2+1+1) Punkte)

Folgende Aussagen seien bekannt.

1. Der frühe Vogel fängt den Wurm.
2. Doro wird nicht von Lilly gefangen.
3. Lilly ist ein Vogel oder ein Igel.
4. Für Igel ist 5 Uhr am Morgen spät.
5. Doro ist ein Wurm.
6. Für Vögel ist 5 Uhr am Morgen früh.
7. Lilly schläft bis 5 Uhr am Morgen und ist ab 5 Uhr unterwegs.

Beantworte folgende Fragen.

1. Ist Lilly ein Vogel oder ein Igel?
2. Ist sie ein frühes oder ein spätes Tier?
3. Fängt der späte Igel den Wurm?

Aufgabe * (8 Punkte)

Es sei $\alpha$ eine aussagenlogische Aussage und es seien $p_1,\dots ,p_n$ die darin vorkommenden Aussagenvariablen. Es sei

$\gamma =\pm p_1\wedge \dots \wedge \pm p_n$

eine fixierte Konjunktion dieser (negierten) Aussagenvariablen. Zeige, dass dann

$⊢\gamma \to \alpha \text{ oder }⊢\gamma \to \mathrm{\neg }\alpha$

gilt.

Aufgabe * (2 Punkte)

Es sei $K=\{E,m,c\}$ eine Konstantenmenge, $Q$ ein einstelliges Funktionssymbol und $P$ ein zweistelliges Funktionssymbol. Es sei $I$ die Interpretation mit  $M=\mathbb{N}$  als Grundmenge, bei der $Q$ als Quadrieren, $P$ als Multiplikation und die Konstanten als  $I(E)=9000000000$   $I(m)=1$  und  $I(c)=300000$  interpretiert wird. Ist der Ausdruck

$E=PmQc$

unter dieser Interpretation gültig?

Aufgabe * (4 (1+2+1) Punkte)

1. Bestimme die kleinste natürliche Zahl, die größer als die ersten drei Quadratzahlen ist.
2. Beschreibe die Bedingung (und zwar so, dass die Bedingung erkennbar ist) aus (1) durch einen prädikatenlogischen arithmetischen Ausdruck (also mit dem Symbolalphabet $+,\cdot ,0,1$ und Variablen) in der einen freien Variablen $x$.
3. Beschreibe das Ergebnis aus (1) durch einen einfachen prädikatenlogischen Ausdruck in der einen freien Variablen $x$.

Aufgabe * (3 Punkte)

Formuliere die Injektivität für eine Abbildung

$f:D⟶Z$

prädikatenlogisch mithilfe der Verwendung von Sorten.

Aufgabe * (5 (3+2) Punkte)

Es sei $S$ ein Symbolalphabet und $L^S$ die zugehörige Sprache und $T$ die zugehörige Termmenge. Es sei  $\Gamma \subseteq L^S$  eine Ausdrucksmenge.

1. Zeige, dass durch

   $s{\cong }_{\Gamma }t\text{ genau dann, wenn }I(s)=I(t)\text{ für jede Interpretation }I\text{ mit }I\models \Gamma$

   eine Äquivalenzrelation auf $T$ definiert wird.

2. Wenn man $\Gamma$ vergrößert, werden dann die Äquivalenzklassen größer oder kleiner?

Aufgabe * (5 (1+1+1+1+1) Punkte)

In einer Wohngemeinschaft leben die Personen $A,B,C,D,E$. Wir betrachten die folgenden Relationen:

1. $Txy$ bedeutet, dass $x$ und $y$ manchmal miteinander Tennis spielen,
2. $Sxyz$ bedeutet, dass $x,y$ und $z$ manchmal miteinander Skat spielen,
3. $Kxyzw$ bedeutet, dass $x,y,z$ und $w$ manchmal miteinander Doppelkopf spielen.

In der WG gilt

$TDE,SABC,SABE,KACED.$

1. Charakterisiere umgangssprachlich die Person $D$ allein unter Bezugnahme auf die gegebenen Spielrelationen.
2. Charakterisiere umgangssprachlich die Person $C$ allein unter Bezugnahme auf die gegebenen Spielrelationen.
3. Charakterisiere prädikatenlogisch durch einen Ausdruck mit der einzigen freien Variablen $x$ und den Relationssymbolen $T,S,K$ die Person $A$.
4. Charakterisiere prädikatenlogisch durch einen Ausdruck mit der einzigen freien Variablen $x$ und den Relationssymbolen $T,S,K$ die Person $B$.
5. Charakterisiere prädikatenlogisch durch einen Ausdruck mit der einzigen freien Variablen $x$ und den Relationssymbolen $T,S,K$ die Person $E$.

Aufgabe (4 Punkte)

Entwerfe ein Programm für eine Registermaschine, das nach und nach alle Quadratzahlen ausdruckt.

Aufgabe (4 Punkte)

Es seien $T,S\subseteq \mathbb{N}$ entscheidbare Mengen. Zeige, dass dann auch die Vereinigung $T\cup S$, der Durchschnitt $T\cap S$ und auch das Komplement $\mathbb{N}\setminus T$ entscheidbar sind.

Aufgabe * (4 Punkte)

Zeige, dass die Abbildung

$f:{\mathbb{N}}^3⟶\mathbb{N},(x,y,z)⟼x{y}^2-z^2+2z^3,$

(wohldefiniert und) arithmetisch repräsentierbar ist.

Aufgabe * (4 Punkte)

Beweise das Unvollständigkeitslemma.

Aufgabe * (6 (1+1+4) Punkte)

Wir interpretieren den Satz von Sokrates, „Ich weiß, dass ich nichts weiß“, als modallogisches Axiomenschema

$◻\mathrm{\neg }◻\alpha .$

Zeige die folgenden Aussagen.

1. Dieses Axiomenschema ist paradox.
2. Dieses Axiomenschema ist innerhalb der $K$-Modallogik äquivalent zu

   $◻◊\alpha .$

3. Dieses Axiomenschema ist innerhalb der $K$-Modallogik äquivalent zu

   $◻\alpha ,$

   also zum Leerheitsaxiom.

Aufgabe * (5 Punkte)

Zeige, dass in einem gerichteten Graphen $(M,R)$ das modallogische Transitivitätsaxiom genau dann gilt, wenn $R$ transitiv ist.