Aufgabe 5

Man formalisiere die folgenden Aussagen:

(a) Es gibt eine Funktion f: N → N ohne Nullstellen:

"es gibt f" "für alle x" f(x) ≠ 0

(b) Zu je zwei Funktionen f,g: N
→N gibt es eine Funktion h: N → N, deren Nullstellen genau die gemeinsamen Nullstellen von f und von g sind:

"für alle f,g" "gibt es ein x mit" (hx=0 ↔  fx=0 UND gx=0)
                                                    x element FV ( - " - )


Aufgabe 6

Unter den Graphen einer Funktion f: N
→N versteht man die Relation {(n,m) I fn=m}.

(a) Man gebe eine induktive Definition des Prädikats G!, das den Graphen der Fakultätsfunktion darstellt (es war 0! := 1, (Sn!) := (Sn)*n!):

Klauseln:

   (G!)1+ : G! (0,1)
   (G!)2+ : G! (n,m) → G!(Sn,(Sn)*m)

(b) Wie lautet das Beseitigungsaxiom G!-?

   (G!)- : G! (n.m) →    A(0,1) →
                                     "für alle n`,m`(A(n`,m`) →
                                      A(Sn`,(Sn`)*m`)) → A(n,m)

                              A ist unter den Klauseln abgeschlossen.

Aufgabe 7:

Man stelle fest, ob die folgenden Relationen auf N Äquivalenzrelationen sind:

(R1(n,m):="es gibt k" 3*k=n UND "es gibt f" 3*l=m

a) Reflexiv: "für alle x" R(x,x)
b) Symmetrisch: "für alle x,y" (R(x,y) → R(y,x))
c) Transitiv: "für alle x,y,z" (R(x,y) → R(y,z) → R(x,z))

R1: nicht reflexiv, da nicht alle x (Bsp. 17) durch 3 teilbar sind!

R2: Äquivalenzrelation

R3: Äquivalenzrelation, denn Quadratfunktion ist injektiv, daher äquivalent zu n=m


Aufgabe 8:

Man definiere rekursiv eine Funktion f: N → N so, dass "für alle n" f(2n)=0 und "für alle n" f(2n+1)=1:

   f0 := 0     
                      Sg(fn)
   f(n+1)   :=  (1 - fn)   (Natürliche Zahlen!)

                                        
                                             1   für n=0
Man definiert oft sg(k) =
                                             0   für n>0