Vorlesung 12 Merkelt

Folie 12

f(x,y) = \begin{cases} min~(z + 1)^2 > x & ,falls~(z + 1)^2 > x~existiert\\ y + 1 & ,sonst \end{cases}

f(19,19) = \begin{cases} min~(z + 1)^2 > 19 & ,falls~(z + 1)^2 > 19~existiert\\ 20 & ,sonst \end{cases}

Das kleinste z \in \N, welches die Bedingung erfüllt ist z = 4, da

• z = 0 \curvearrowright 1^2 = 1, zu klein
• z = 1 \curvearrowright 2^2 = 4, zu klein
• z = 2 \curvearrowright 3^2 = 9, zu klein
• z = 3 \curvearrowright 4^2 = 16, zu klein
• z = 4 \curvearrowright 5^2 = 25, erfüllt die Bedingung

Folie 24

µf(x) = \begin{cases} 0 & ,wenn~x~gerade\\ \perp & ,sonst \end{cases}

Folie 26

h_1(x) = \begin{cases} 0 & ,wenn~x~gerade\\ 1 & ,sonst \end{cases}

Folie 28

h_2(x) = x^2

Folie 30

h_3(x) = 0

Folie 32

Schema:

\mu{}f(x) = \begin{cases} \textrm{das kleinste } \_\_\_\_\_ & ,\textrm{mit } \_\_\_\_\_ = 0, \textrm{wenn }\\ & \textrm{(1) so ein } \_\_ \textrm{ existiert und} \\ & \textrm{(2) } \_\_\_\_\_\_ \textrm{ für alle } \_\_ \leq \_\_ \textrm{ definiert ist;} \\ \perp & ,sonst \end{cases}

Schema (2)

\mu{}f(x) = \begin{cases} \textrm{das kleinste } z \in \N & ,\textrm{mit } g(x,z) = 0, \textrm{wenn }\\ & \textrm{(1) so ein } z \textrm{ existiert und} \\ & \textrm{(2) } g(x,i) \textrm{ für alle } i \leq z \textrm{ definiert ist;} \\ \perp & ,sonst \end{cases}

g(x,n) ist zu definieren

Die beiden Bedingungen können durch zwei Hilfsfunktionen sicher gestellt werden und anschließend durch eine Multiplikation und verknüpft werden.

prim?(x) = \begin{cases} 1 & ,\textrm{wenn } y \textrm{ Primzahl}\\ 0 & ,sonst \end{cases}

gt(x,y) = \begin{cases} 1 & ,y \gt x\\ 0 & ,sonst \end{cases}

Daraus kann folgende Funktion entwickelt werden:

\mu{}f(x,y) = \begin{cases} \textrm{das kleinste } z \in \N & ,\textrm{mit } prim?(y) \cdot gt(y,x) \dot - z = 0, \textrm{wenn }\\ & \textrm{(1) so ein } z \textrm{ existiert und} \\ & \textrm{(2) } prim?(y) \cdot gt(y,x) \dot - i = 0 \textrm{ für alle } i \leq z \textrm{ definiert ist;} \\ \perp & ,sonst \end{cases}

Folie 34

Folie 36ff. - KA