Anwendung - Operationen auf natürlichen Zahlen

Operationen auf natürlichen Zahlen

Operationen auf natürlichen Zahlen lassen sich alle aus einer einzigen Grundoperationen entwickeln. Man benötigt hierzu nur die Nachfolger-Operation s: N -> N, die jeder natürlichen Zahl n ihren Nachfolger s(n) zuordnet.

Betrachte als Beispiel die Definition der Additionsfunktion add. Die folgenden Problemreduktionsregeln legen für alle Paare natürlicher Zahlen die Addition fest.

add(x,0) -> x
add(x,s(y)) -> s(add(x,y))

In Python kann man diese beiden Reduktionsregeln folgendermaßen implementieren:

def s(x):
    return x+1

def p(x):
    return x-1

def add(x, y):
    if y == 0:
        return x
    else:
        return s(add(x, p(y)))

Aufgabe 1

Berechne mit einer Reduktionskette den Wert add(2, 3).

add(2, 3) ->
s(add(2, 2)) ->
...

Teste auch die oben gezeigte Implementierung der Funktion add.

Aufgabe 2

Die folgenden Reduktionsregeln definieren eine Funktion subtr.

subtr(x,0) -> x
subtr(0, y) -> 0
subtr(s(x),s(y)) -> subtr(x,y)

Was leistet dies Funktion? Beschreibe ihr Verhalten möglichst präzise. Beachte auch die Besonderheit der Definition.

Implementiere die Funktion in Python und überprüfe, ob das Verhalten richtig beschrieben ist.

Aufgabe 3

Entwickle Reduktionsregeln zur Definition einer Funktion mult.

mult(x,0) -> 
mult(x,s(y)) -> 

Implementiere die Reduktionsregeln und teste das Verhalten der neu definierten Funktion.

Aufgabe 4

Die folgenden Regeln beschreiben, wie man eine Vergleichsoperation auf natürlichen Zahlen festlegen kann.

equal(0, 0) -> 1
equal(s(x), 0) -> 0
equal(0, s(y)) -> 0
equal(s(x), s(y)) -> equal(x, y)

Welcher Vergleich wird hier festgelegt? Wie werden Wahrheitswerte als Ergebnisse eines Vergleichs codiert?

Definiere analog die Vergleichsoperation gt (greater than), lt (less than), geq (greater or equal) und leq (less or equal).

Aufgabe 5

Definiert die folgende Regel wirklich das Minimum zweier natürlicher Zahlen?.

min(x,y) -> add(mult(lt(x,y),x),mult(geq(x,y),y))

Wie könnte man entsprechend das Maximum zweier natürlicher Zahlen festlegen?

Aufgabe 6

Wie könnte man die Divisionsoperationen div und mod rekursiv definieren?

Aufgabe 7

Für Experten: Schaffst du es auch, eine Operation prime rekursiv zu definieren, mit der man überprüfen kann, ob eine Zahl eine Primzahl ist. Tipp: Definiere zuerst eine Operation divleq(x, y), mit deren Hilfe man die Anzahl der Teiler von x kleiner oder gleich der Grenze y bestimmen kann.