Mathematische Logik/Gemischte Definitionsabfrage/4/Aufgabe/Lösung

1. Eine natürliche Zahl ${}n\geq 2$ heißt eine Primzahl, wenn die einzigen natürlichen Teiler von ihr ${}1$ und ${}n$ sind.
2. Die Sprache der Aussagenlogik ${}L^{V}$ wird rekursiv durch folgende Regeln definiert.
   1. Jedes ${}p\in V$ gehört zu ${}L^{V}$.
   2. Wenn ${}\alpha \in L^{V}$, so ist auch ${}\neg (\alpha )\in L^{V}$.
   3. Wenn ${}\alpha ,\beta \in L^{V}$, so sind auch ${}(\alpha )\wedge (\beta ),\,(\alpha )\vee (\beta ),\,(\alpha )\rightarrow (\beta ),\,(\alpha )\leftrightarrow (\beta )\in L^{V}$.
3. Unter der Uminterpretation ${}I{\frac {m}{x}}$ versteht man diejenige Interpretation von ${}S$ in ${}M$, die strukturgleich zu ${}I$ ist und für deren Variablenbelegung

   $\left(I{\frac {m}{x}}\right)(y)={\begin{cases}I(y),\,{\text{ falls }}y\neq x\,,\\m,\,{\text{ falls }}y=x\,,\end{cases}}$

   gilt.

4. Der Rang ${}\rho$ von ${}\alpha$ wird rekursiv durch
   1. ${}\rho (\alpha )=0$, falls ${}\alpha$ atomar ist.
   2. ${}\rho (\alpha )=\rho (\beta )+1$, falls ${}\alpha =\neg (\beta )$ ist.
   3. ${}\rho (\alpha )=\rho (\beta )+\rho (\gamma )+1$, falls ${}\alpha =(\beta )\circ (\gamma )$ mit ${}\circ =\wedge ,\,\vee ,\,\rightarrow ,\leftrightarrow$ ist.
   4. ${}\rho (\alpha )=\rho (\beta )+1$, falls ${}\alpha =\exists x\beta$ oder ${}\alpha =\forall x\beta$ ist.

   definiert.

5. Die Funktion

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

   heißt ${}R$-berechenbar, wenn es ein Programm ${}P$ für eine Registermaschine gibt, die bei jeder Eingabe ${}(r_{1},\ldots ,r_{k})$ (in den ersten ${}k$ Registern) anhält und ${}F(r_{1},\ldots ,r_{k})$ als (einzige) Ausgabe besitzt.

6. Eine Modallogik heißt eine ${}K$-Modallogik, wenn das Axiomenschema

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

   für beliebige Ausdrücke ${}\alpha ,\beta$ und die Nezessisierungsregel

   aus ${}\vdash \alpha$ folgt ${}\vdash \Box \alpha$

   für alle ${}\alpha$ gilt.

Zur gelösten Aufgabe