Kurs:Einführung in die mathematische Logik (Osnabrück 2011-2012)/Klausur

Wählen Sie eines der Themen A,B,C (Aufsatzthemen) oder D (Einzelaufgaben) aus. Zum Bestehen: Bei den Themen A,B,C sollte deutlich werden, dass Sie die Theorien in ihren Grundzügen verstanden haben und darüber sachgerecht und detailliert referieren können. Bei D sollten Sie die Hälfte der insgesamt 32 Punkte erhalten.

Thema A: Schildern Sie den Aufbau einer prädikatenlogischen Sprache einschließlich der Semantik und eines Ableitungskalküls.

Thema B: Beschreiben Sie Registermaschinen und das Halteproblem einschließlich einer Beweisskizze für dessen Unlösbarkeit.

Thema C: Erläutern Sie die Unentscheidbarkeit der Arithmetik, und skizzieren Sie einen Beweis dafür.

D - Einzelaufgaben

Aufgabe (3 Punkte)

Eine Grundtermmenge sei durch die Variablenmenge ${}V=\{x,y,z\}$ , eine Konstantenmenge ${}K=\{c_{1},c_{2}\}$ , die einstelligen Funktionssymbole ${}F_{1}=\{f,g\}$ und die zweistelligen Funktionssymbole ${}F_{2}=\{\alpha ,\beta ,\gamma \}$ gegeben. Entwerfe einen Termstammbaum für den Term

gf\beta \beta \alpha fxy\gamma c_{1}zggc_{2}.

Aufgabe (3 Punkte)

Formuliere die folgenden Beziehungen (ein- oder mehrstellige Prädikate) innerhalb der natürlichen Zahlen ${}\mathbb {N} =\{0,1,2,3,\ldots \}$ allein mittels Gleichheit, den Konstanten ${}0$ und ${}1$ , Addition, Multiplikation und unter Verwendung von aussagenlogischen Junktoren und Quantoren.

${}x<y$ .
${}x$ ist ein Vielfaches von ${}y$ .
${}x$ ist ein Vielfaches von ${}3$ .
${}x$ ist eine dritte Potenz.
${}x$ ist keine Primzahl.
${}x$ und ${}y$ besitzen die gleichen Primfaktoren.

Aufgabe * (2 Punkte)

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

Aufgabe (1 Punkt)

Erstelle einen prädikatenlogischen Ausdruck ${}\alpha$ , der in einer Struktur genau dann gilt, wenn die Grundmenge der Struktur genau ${}5$ 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.

${}M=\mathbb {N}$ mit der Standardinterpretation und der Variablenbelegung ${}I(x)=5$ und ${}I(y)=3$ .
${}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}}$ .
${}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.
${}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 (3 Punkte)

Es sei ${}\Gamma$ eine Ausdrucksmenge und ${}\alpha$ ein Ausdruck in einer Sprache erster Stufe. Zeige, dass ${}\Gamma \vDash \alpha$ genau dann gilt, wenn ${}\Gamma \cup \{\neg \alpha \}$ nicht erfüllbar ist.

Aufgabe (6 (1+2+3) Punkte)

a) Formuliere die Existenzeinführung im Sukzedens.

b) Formuliere die Existenzeinführung im Antezedens.

c) Zeige durch ein Beispiel, dass die Bedingung an die Variable in der Existenzeinführung im Antezedens wesentlich ist.

Aufgabe * (4 Punkte)

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

Aufgabe (4 Punkte)

Entwerfe ein Programm für eine Registermaschine, das die Potenz ${}r_{i}^{r_{j}}$ berechnet (und ausgibt), wobei ${}r_{i}$ bzw. ${}r_{j}$ die Registerinhalte der Register ${}R_{i},R_{j}$ , ${}i\neq j$ , sind.

Aufgabe (2 Punkte)

Was besagt die Repräsentierbarkeit einer Abbildung

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

durch eine Menge ${}\Gamma$ von arithmetischen Ausdrücken?

Zur pdf-Version der Klausur