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

${\displaystyle {}\alpha }$

${\displaystyle {}\Gamma }$

${\displaystyle {}\alpha _{1},\ldots ,\alpha _{n}\in \Gamma }$

${\displaystyle \vdash \alpha _{1}\wedge \ldots \wedge \alpha _{n}\rightarrow \alpha }$

gilt.

${\displaystyle {}s{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}}$

1. Für eine Variable ${\displaystyle {}x}$ ist

   ${\displaystyle {}x{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}:={\begin{cases}x,{\text{ falls }}x\neq x_{i}{\text{ für alle }}i\,,\\t_{i},{\text{ falls }}x=x_{i}\,.\end{cases}}\,}$

2. Für eine Konstante ${\displaystyle {}c}$ ist

   ${\displaystyle {}c{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}:=c\,.}$

3. Für ein ${\displaystyle {}n}$-stelliges Funktionssymbol ${\displaystyle {}f}$ und ${\displaystyle {}n}$ Terme ${\displaystyle {}s_{1},\ldots ,s_{n}}$ ist

   ${\displaystyle {}fs_{1}\ldots s_{n}{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}:=fs_{1}{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}\ldots s_{n}{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}\,.}$

${\displaystyle {}n+k}$

${\displaystyle {}\alpha _{n}}$

${\displaystyle {}n}$

${\displaystyle {}\alpha _{n}}$

${\displaystyle \alpha _{n}\colon \mathbb {N} \longrightarrow \mathbb {N} ,\,k\longmapsto \alpha _{n}(k),}$

ist, für die

${\displaystyle \alpha _{n}(0)=n{\text{ und }}\alpha _{n}(k')=(\alpha _{n}(k))'{\text{ für alle }}k\in \mathbb {N} }$

gilt.

${\displaystyle {}T}$

${\displaystyle {}P}$

${\displaystyle n\in T{\text{ genau dann, wenn }}P(n){\text{ die Ausgabe }}0{\text{ besitzt}}}$

gilt.