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

Aus Wikiversity
Zur Navigation springen Zur Suche springen
  1. Die Teilmenge heißt maximal widerspruchsfrei, wenn widerspruchsfrei ist und jede echt größere Menge widersprüchlich ist.
  2. Die folgenden rekursiv definierten Wörter heißen die Ausdrücke dieser Sprache.
    1. Wenn und Terme sind, so ist
      ein Ausdruck.
    2. Wenn ein -stelliges Relationssymbol ist und Terme sind, so ist

      ein Ausdruck.

    3. Wenn und Ausdrücke sind, so sind auch

      Ausdrücke.

    4. Wenn ein Ausdruck ist und eine Variable, so sind auch

      Ausdrücke.

  3. Die Terminterpretation wird induktiv über den Aufbau der Terme für jeden -Term definiert.
    1. Für jede Konstante und jede Variable ist die Terminterpretation durch die Interpretation bzw. die Belegung direkt gegeben, also und .
    2. Wenn Terme mit Interpretationen sind und wenn ein -stelliges Funktionssymbol ist, so wird der Term als interpretiert.
  4. Unter einem atomaren Ausdruck versteht man Ausdrücke der Form , wobei und Terme sind, und der Form , wobei ein -stelliges Relationssymbol ist und Terme sind.
  5. Die Funktion

    heißt -berechenbar, wenn es ein Programm für eine Registermaschine gibt, die bei jeder Eingabe (in den ersten Registern) anhält und als (einzige) Ausgabe besitzt.

  6. Unter dem Reflexivitätsaxiom versteht man das modallogische Axiomenschema
Zur gelösten Aufgabe