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

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

Aufgabe * (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

1. Die zu einer (aussagenlogischen) Wahrheitsbelegung

   $\lambda \colon V\longrightarrow \{0,1\}$

   auf einer Aussagenvariablenmenge ${}V$ zugehörige Interpretation auf der Sprache ${}L^{V}$.

2. Das Alphabet einer Sprache erster Stufe.
3. Ein Nichtstandardmodell zu einem fixierten ${}S$-Modell ${}M$.
4. Die Arithmetische Repräsentierbarkeit einer Abbildung

   $F\colon \mathbb {N} ^{r}\longrightarrow \mathbb {N} ^{s}.$

5. Eine vollständige Theorie ${}T\subseteq L_{0}^{S}$.
6. Das universelle modallogische Modell zu einem ${}K$- modallogischen System ${}\Gamma$.

Aufgabe * (3 Punkte)

Formuliere die folgenden Sätze.

1. Der Satz von Henkin.
2. Der Satz über das Halteproblem.
3. Der Satz über die Unvollständigkeit der Peano-Arithmetik.

Aufgabe * (1 Punkt)

Beurteile die Snookerweisheit „Ein Snookerspiel kann man in der ersten Session nicht gewinnen, aber verlieren“ vom logischen Standpunkt aus.

Aufgabe * (14 (2+5+2+5) Punkte)

Es sei ${}p_{i}$, ${}i\in I$, eine Familie von Aussagenvariablen und ${}L$ die zugehörige aussagenlogische Sprache. Es sei ${}S$ ein Symbolalphabet bestehend aus den Variablen ${}x_{i}$, ${}i\in I$, und dem einen Konstantensymbol ${}c$ und es sei ${}L^{S}$ die zugehörige prädikatenlogische Sprache. Es sei

${}\beta _{i}:=x_{i}=c\in L^{S}\,.$

1. Definiere rekursiv eine natürliche Abbildung

   $\Psi \colon L\longrightarrow L^{S},$

   die ${}p_{i}$ auf ${}\beta _{i}$ abbildet.

2. Ist ${}\Psi$ injektiv?
3. Ist ${}\Psi$ surjektiv?
4. Zeige für alle ${}\alpha \in L$, dass ${}\vdash \alpha$ (im Ableitungskalkül der Aussagenlogik) genau dann gilt, wenn ${}\vdash \Psi (\alpha )$ (im Ableitungskalkül der Prädikatenlogik) gilt.

Aufgabe * (5 Punkte)

Es seien ${}A,B,C$ einstellige Relationssymbole. Zeige, dass der Modus Barbara, also die Aussage

$(\forall x(Ax\rightarrow Bx)\wedge \forall x(Bx\rightarrow Cx))\rightarrow (\forall x(Ax\rightarrow Cx))$

im Prädikatenkalkül ableitbar ist.

Aufgabe * (8 Punkte)

Beweise den Satz über die induktive Definition einer Abbildung auf einem Peano-Dedekind-Modell ${}(N,0,\prime )$.

Aufgabe * (4 Punkte)

Es sei ${}S$ ein Symbolalphabet und ${}\Gamma \subseteq L^{S}$ eine Ausdrucksmenge. Begründe, warum man im Allgemeinen bei der Hinzunahme von Beispielen (innerhalb des Beweises des Vollständigkeitssatzes) nicht für alle Existenzaussagen ${}\exists x\alpha \in L^{S}$ mit einer einzigen neuen Variablen ${}z$ arbeiten kann.

Aufgabe * (5 Punkte)

In einem Zugabteil sitzen die sechs Personen ${}A,B,C,D,E,F$. Wir betrachten die folgenden Relationen:

1. ${}Mx$ bedeutet, dass ${}x$ über die deutsche Bahn motzt.
2. ${}Px$ bedeutet, dass ${}x$ einen Fensterplatz hat.
3. ${}Sxy$ bedeutet, dass ${}x$ der Person ${}y$ die Fahrkarte klaut.

Es gelten die Beziehungen

$MA,MB,MC,MD,ME,MF,PA,PD,SAD,SBE.$

1. Für welche Personen ist die Äquivalenzklasse zur elementaren Äquivalenz einelementig, für welche nicht?
2. Bestimme die Automorphismengruppe des Zugabteils.
3. Charakterisiere umgangssprachlich die Person ${}A$ allein unter Bezugnahme auf die gegebenen Relationen.
4. Charakterisiere prädikatenlogisch durch einen Ausdruck mit der einzigen freien Variablen ${}x$ und den Relationssymbolen ${}M,P,S$ die Person ${}E$.
5. Charakterisiere prädikatenlogisch durch einen Ausdruck mit der einzigen freien Variablen ${}x$ und den Relationssymbolen ${}M,P,S$ diejenigen Äquivalenzklassen, die aus mindestens zwei Personen bestehen.

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

Die Registerabteilung des VW-Konzerns hat - ohne Wissen des Vorstandes und am Aufsichtsrat vorbei - in jedes real existierende Registerprogramm ${}P$ an einer willkürlich gewählten Stelle die aufeinanderfolgenden Befehlszeilen eingebaut (und dabei die Zeilennummern und die Sprungbefehlsnummern angepasst, ${}k$ ist die Nummer eines in ${}P$ nicht verwendeten Registers und ${}h'$ ist die neue Haltebefehlsnummer)

$k+$

$k+$

${\text{Drucke}}$

$C(k,h').$

1. Ändert sich durch diese Manipulation die Halteeigenschaft des Programms?
2. Ändert sich durch diese Manipulation die Programmabbildung?
3. Nachdem der Skandal herauskommt und die Öffentlichkeit eine Erklärung fordert, diskutieren Vorstand, Aufsichtsrat und Abteilungsleiter die folgenden möglichen Stellungsnahmen für die anstehende Pressekonferenz:
   a) Man wollte Speicherplatz sparen.
   
   b) Man wollte aus Werbezwecken erreichen, dass jedes Registerprogramm mindestens einmal „VW“ ausdruckt.
   
   c) Man wollte einen Beitrag zur Entschleunigung leisten, indem man manche Programme etwas langsamer macht.
   
   d) Man wollte einen Beitrag zur Entschleunigung leisten, indem man alle Programme etwas langsamer macht.
   Welche dieser Erklärungen passen inhaltlich zu den Manipulationen?

Aufgabe (4 Punkte)

Erläutere die Unentscheidbarkeit der Arithmetik und skizziere in Grundzügen, wie man sie beweisen kann.

Aufgabe * (4 Punkte)

Es sei ${}n\in \mathbb {N}$ eine fixierte natürliche Zahl und

${}\alpha (x):=x=n\,,$

wobei ${}n$ durch die ${}n$-fache Summe der ${}1$ mit sich selbst realisiert werde. Zeige direkt, dass es Sätze ${}p,q\in L_{0}^{\rm {Ar}}$ mit

$\mathbb {N} \vDash \alpha (GN(p))\leftrightarrow p$

und mit

$\mathbb {N} \vDash \neg \alpha (GN(q))\leftrightarrow q$

gibt.

Aufgabe * (3 Punkte)

Zeige, dass im ${}K$- System der Ausdruck

$\Box (\alpha \rightarrow \beta )\rightarrow (\Diamond \alpha \rightarrow \Diamond \beta )$

ableitbar ist.

Aufgabe * (7 Punkte)

Zeige, dass in einem gerichteten Graphen ${}(M,R)$ das modallogische Löb-Axiom genau dann gilt, wenn ${}R$ transitiv ist und es in ${}M$ keine unendlichen Ketten gibt.