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

1. Die zugehörige Interpretation ${}I=I^{\lambda }$ wird rekursiv über den Aufbau der Sprache wie folgt festgelegt.
   1. ${}I(v)=\lambda (v)$ für jede Aussagenvariable ${}v\in V$.
   2. Bei ${}\alpha =\neg (\beta )$ ist

      ${}I(\alpha )={\begin{cases}1,{\text{ falls }}I(\beta )=0\,,\\0,{\text{ falls }}I(\beta )=1\,.\end{cases}}\,$

   3. Bei ${}\alpha =(\beta )\wedge (\gamma )$ ist

      ${}I(\alpha )={\begin{cases}1,{\text{ falls }}I(\beta )=I(\gamma )=1\,,\\0{\text{ sonst}}\,.\end{cases}}\,$

   4. Bei ${}\alpha =(\beta )\vee (\gamma )$ ist

      ${}I(\alpha )={\begin{cases}1,{\text{ falls }}I(\beta )=1{\text{ oder }}I(\gamma )=1\,,\\0,{\text{ falls }}I(\beta )=I(\gamma )=0\,.\end{cases}}\,$

   5. Bei ${}\alpha =(\beta )\rightarrow (\gamma )$ ist

      ${}I(\alpha )={\begin{cases}1,{\text{ falls }}I(\beta )=0{\text{ oder }}I(\gamma )=1\,,\\0,{\text{ falls }}I(\beta )=1{\text{ und }}I(\gamma )=0\,.\end{cases}}\,$

   6. Bei ${}\alpha =(\beta )\leftrightarrow (\gamma )$ ist

      ${}I(\alpha )={\begin{cases}1,{\text{ falls }}I(\beta )=I(\gamma )\,,\\0,{\text{ falls }}I(\beta )\neq I(\gamma )\,.\end{cases}}\,$

2. Ein Element ${}x\in I$ heißt obere Schranke für ${}J$, wenn ${}y\preccurlyeq x$ für jedes ${}y\in J$ gilt.
3. Unter einer ${}S$-Struktur versteht man eine nichtleere Menge ${}M$ mit den folgenden Festlegungen.
   1. Für jede Konstante ${}c\in K$ ist ein Element ${}c^{M}\in M$ festgelegt.
   2. Zu jedem ${}n$-stelligen Funktionssymbol ${}f$ (aus ${}S$) ist eine ${}n$-stellige Funktion

      $f^{M}\colon M^{n}\longrightarrow M$

      festgelegt.

   3. Zu jedem ${}n$-stelligen Relationssymbol ${}R$ (aus ${}S$) ist eine ${}n$-stellige Relation

      $R^{M}\subseteq M^{n}$

      festgelegt.

4. Man sagt, dass ${}\alpha$ aus ${}\Gamma$ folgt, wenn für jede ${}S$-Interpretation ${}I$ mit ${}I\vDash \Gamma$ auch ${}I\vDash \alpha$ gilt.
5. Man sagt, dass ${}T$ ${}R$-aufzählbar ist, wenn es ein Programm ${}P$ für eine Registermaschine gibt, die bei Eingabe von ${}0$ nach und nach genau die Zahlen aus ${}T$ ausdruckt.
6. Man sagt, dass eine Menge ${}\Gamma$ von modallogischen Ausdrücken in einem modallogischen Modell ${}(M,R,\mu )$ gilt, wenn

   $(M,R,\mu )\vDash \alpha$

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

Zur gelösten Aufgabe