Kann mir jemand helfen, dieses rekursive Prolog -Beispiel zu verstehen?
-
27-10-2019 - |
Frage
Hier ist der Plus -Code, den ich nicht verstehe
plus(0,X,X):-natural_number(X).
plus(s(X),Y,s(Z)) :- plus(X,Y,Z).
während gegeben:
natural_number(0).
natural_number(s(X)) :- natural_number(X).
Ich verstehe diese Rekursion nicht. Wenn ich habe plus(s(0),s(s(s(0))),Z)
Wie kann ich die Antwort von bekommen 1+3=4
?
Ich brauche eine Erklärung für den ersten Code. Ich versuche das plus(0,X,X)
Ich werde die Rekursion stoppen, aber ich denke, dass ich es falsch mache.
Lösung
Beginnen wir also mit natural_number(P)
. Lesen Sie dies als "P ist eine natürliche Zahl". Wir werden gegeben natural_number(0).
, das erzählt uns das 0
ist immer eine natürliche Zahl (dh es gibt keine Bedingungen, die damit erfüllt werden müssen, dass es eine Tatsache ist). natural_number(s(X)) :- natural_number(X).
sagt uns das s(X)
ist eine natürliche Zahl, wenn X
ist eine natürliche Zahl. Dies ist die normale induktive Definition natürlicher Zahlen, aber "rückwärts" geschrieben, wie wir Prolog "q: = p" als "q ist wahr, wenn p wahr ist" lesen ".
Jetzt können wir uns ansehen plus(P, Q, R)
. Lesen Sie dies als "plus
Stimmt, wenn P plus q gleich R ". Wir sehen uns dann die Fälle an, die wir gegeben haben:
plus(0,X,X) :- natural_number(X).
. Lesen Sie als Hinzufügen von 0 zu x führt in x, wenn x eine natürliche Zahl ist. Dies ist unser induktiver Basisfall und die natürliche Definition der Addition.plus(s(X),Y,s(Z)) :- plus(X,Y,Z).
Lesen Sie als "Hinzufügen des Nachfolgers von x zu y führt zum Nachfolger z, wenn das Hinzufügen von X zu y z 'ist. Wenn wir die Notation ändern, können wir es algebraisch als" x + 1 + y = z + 1) lesen, wenn x + y = Z ", was wieder sehr natürlich ist.
Also, um Ihnen direkte Frage zu beantworten ", wenn ich habe plus(s(0),s(s(s(0))),z)
, wie kann ich die Antwort von 1+3 = 4 bekommen? "
- Wenden Sie die zweite Definition von an
plus
, wie es der einzige ist, der sich mit der Abfrage vereint.plus(s(0),s(s(s(0))), s(z'))
ist wahr, wennplus(0, s(s(s(0))), z')
gilt für einigez
- Wenden Sie nun die erste Definition von Plus an, da dies die einzige einheitliche Definition ist:
plus(0, s(s(s(0))), z')
wennz'
ists(s(s(0)))
unds(s(s(0)))
ist eine natürliche Zahl. - Die Definition von abwickeln
natural_number
ein paar Mal aufs(s(s(0)))
Zu sehen, dass das wahr ist. - Die Gesamtaussage ist also wahr, wenn
s(s(s(0)))
ist einheitlich mitz'
unds(z')
ist einheitlich mitz
.
Also gibt der Dolmetscher wahr, mit z' = s(s(s(0)))
und z = s(z')
, dh z = s(s(s(s(0))))
. So, z
ist 4.
Andere Tipps
Dieser Code ist eine einfache Implementierung von Ergänzung in Peano -Arithmetik.
In Peano -Arithmetik werden natürliche Zahlen unter Verwendung der Konstante dargestellt 0
und die unäre Funktion s
. So s(0)
ist eine Darstellung von 1, s(s(s(0)))
ist Darstellung von 3. und plus(s(0),s(s(s(0))),Z)
werde dir geben Z = s(s(s(s(0))))
, was eine Darstellung von 4 ist.
Sie werden keine numerischen Begriffe wie 1+3=4
, Alles, was Sie bekommen, ist der Begriff s/1
das kann sich in jede Tiefe einbetten und somit jede natürliche Zahl darstellen. Sie können solche Begriffe kombinieren (verwenden plus/3
) und damit eine Summierung erreichen.
Beachten Sie, dass Ihre Definition von plus/3
hat nichts mit Swi-Prologs integriert zu tun plus/3
(was mit Ganzzahlen und nicht mit dem funktioniert s/1
Bedingungen):
?- help(plus).
plus(?Int1, ?Int2, ?Int3)
True if Int3 = Int1 + Int2.
At least two of the three arguments must be instantiated to integers.