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

Aus Wikiversity
Zur Navigation springen Zur Suche springen
  1. Man sagt, dass aus ableitbar ist, wenn es endlich viele Ausdrücke derart gibt, dass

    gilt.

  2. Unter einer - stelligen Relation auf versteht man eine Teilmenge der -fachen Produktmenge .
  3. Man sagt, dass aus folgt, wenn für jede -Interpretation mit auch gilt.
  4. Die Termsubstitution wird rekursiv folgendermaßen definiert.
    1. Für eine Variable ist
    2. Für eine Konstante ist
    3. Für ein -stelliges Funktionssymbol und Terme ist
  5. Die Addition wird über die Addition mit festem definiert, wobei die eindeutig bestimmte Abbildung

    ist, für die

    gilt.

  6. Die Teilmenge heißt Register-entscheidbar, wenn es ein Programm für eine Registermaschine gibt, die bei jeder Eingabe anhält und für die die Äquivalenz

    gilt.

Zur gelösten Aufgabe