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 gezeigte oben 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, lt, geq und leq.

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.

X

Fehler melden

X

Suche