Aufgabe 1:

Man gebe je ein Beispiel für Objekte folgender Typen an:

(a) (N kreuz N ) -> N:

z.B. eine Projektion auf die erste Komponente

(b) (N -> N) -> N:

z.B.  λf (f 0)

(c) N-> (N -> N):

z.B. λn λm n ( eine Funktion, die die Zahl n auf die Funktion  λm abbildet, wiederum abgebildet auf n (das hab ich irgendwie mitgeschrieben, was auch immer das bedeutet...)

(d) N -> ( N -> ( N kreuz N ):

z.B. n -> (m -> (2n,3m))

oder: n -> (m -> 00 )

Aufgabe 2:

Man gebe Formeln für folgende Aussagen an (die Funktionen +, * : N -> N-> N  dürfen verwendet werden):

(a) x ist eine gerade Zahl

"es gibt y mit"  2*y = x    (nimmt man eine beliebige natürliche zahl mal zwei, ergibt das immer eine gerade zahl: bsp. 2*1 =2, 2*3 = 6, ...)

(b) x ist größer als y

"es gibt a mit" (y + a =x UND a ≠ 0 )   (Bsp: y =2, a =1: 2+1=3, also ist x=3 größer als y)

oder: "es gibt a mit" y + Sa =x  (Sa ist der Nachfolger von a) (das würde das UND a ≠ 0 ersetzen, weil Sa ja in den natürlichen Zahlen mindestens mit a=0 und Sa=0+1=1 wär)

(c) Es gibt unendlich viele ungerade Zahlen:

"für alle x" "gibt es y mit " ( y > x UND U (y))     (U bedeutet hier ungerade, man könnte auch "nicht" G (y) schreiben mit G = gerade)

(d) x ist größer als der ggT von y und z:

"für alle n gilt" ( GGT (y,z,n) -> x > n )

Aufgabe 3:

Man gebe rekursive Definitionen folgender Funktionen an:

(a) sg (x) gibt der Zahl 0 den Wert 0, allen anderen Zahlen den Wert 1:

sg (x)             sg(0) = 0

                                   sg(Sx) = 1

(Sx ist der Nachfolger von x,)

 (b)  P(x) gibt der Zahl 0 den Wert 0, allen anderen Zahlen den Wert ihres Vorgängers:

P(x)                             P(0) = 0

                                    P(Sx) = x

 (c) x - y gibt den Wert der Differenz x - y falls dieser größergleich 0 ist und 0 sonst:

 7-8 = 0

 7-7 = 0

 7-6 = 1

 also:

 x-0 = x

x - (Sy) = P (x-y) 

 (Beispiel: x=7, y=5: 7 - (5+1) = 7-6 = 1 = P(7-5) = P (2) = P (S1) = 1)

allgemein: f(x; Sy) = l (x,y ; ; f (x;y))

Aufgabe 4:

Man gebe rekursive Definitionen folgender Funktionen an: Hinweis: man verwende die Funktionen von Aufgabe 3

(a) R (x,y) gibt den Rest der Division von x durch y an, bzw. x für y = 0

R (x,y)

R ( 0;y) = 0                   

R ( x+1 ; y) = sowohl 0 als auch R(x,y)+1

(b) [x/y] gibt den ganzzahligen Anteil des Wertes x/y an bzw. x für y = 0

[0/y] = 0

                         [x/y]          l. 0<R(x,y)

[x+y)/y] =

                         [x/y] +1    s