Может ли кто -нибудь помочь мне понять этот рекурсивный пример пролога?

Question

Вот код плюс, который я не понимаю

plus(0,X,X):-natural_number(X).
plus(s(X),Y,s(Z)) :- plus(X,Y,Z).

в то время как дано:

natural_number(0).
natural_number(s(X)) :- natural_number(X).

Я не понимаю эту рекурсию. Если у меня есть plus(s(0),s(s(s(0))),Z) Как я могу получить ответ 1+3=4?

Мне нужно объяснение для первого кода. Я пробую это plus(0,X,X) Остановим рекурсию, но я думаю, что я делаю это неправильно.

Answer 1

Итак, начнем с natural_number(P). Анкет Прочитайте это как «P - естественное число». Были даны natural_number(0)., что говорит нам, что 0 всегда естественное число (то есть нет условий, которые должны быть выполнены, чтобы это было фактом). natural_number(s(X)) :- natural_number(X). говорит нам об этом s(X) это естественное число, если X это естественное число. Это нормальное индуктивное определение естественных чисел, но написано «назад», когда мы читаем Prologo «Q: = p», как «Q - это правда, если P верно».

Теперь мы можем посмотреть plus(P, Q, R). Анкет Прочитайте это как "plus это правда, если P plus q равно R ". Затем мы рассмотрим случаи, которые нам даны:

1. plus(0,X,X) :- natural_number(X).. Анкет Читать как добавление 0 к x приводит к x, если x - это естественное число. Это наш индуктивный базовый случай, и является естественным определением дополнения.
2. plus(s(X),Y,s(Z)) :- plus(X,Y,Z). Читайте как «добавление преемника x к Y приводит к преемнику Z, если добавление x в y равен z». Если мы изменим нотацию, мы можем прочитать его алгебраически как «x + 1 + y = z + 1, если x + y = Z ", что снова очень естественно.

Итак, чтобы ответить вам на прямой вопрос «если у меня есть plus(s(0),s(s(s(0))),z), как я могу получить ответ 1+3 = 4?

1. Применить второе определение plus, так как это единственный, который объединяется с запросом. plus(s(0),s(s(s(0))), s(z')) это правда, если plus(0, s(s(s(0))), z') верно для некоторых z
2. Теперь примените первое определение плюса, так как это единственное объединяющее определение: plus(0, s(s(s(0))), z') если z' является s(s(s(0))) а также s(s(s(0))) это естественное число.
3. Раскрутить определение natural_number Несколько раз на s(s(s(0))) видеть это правдой.
4. Так что общее утверждение верно, если s(s(s(0))) объединен с z' а также s(z') объединен с z.

Таким образом, переводчик возвращает правда, с z' = s(s(s(0))) а также z = s(z'), т.е. z = s(s(s(s(0)))). Анкет Так, z 4.

Answer 2

Этот код является простой реализацией дополнение в арифметике Peano.

В арифметике Peano натуральные числа представлены с использованием постоянной 0 и уникальная функция s. Анкет Так s(0) является представлением 1, s(s(s(0))) представление 3. и plus(s(0),s(s(s(0))),Z) дам тебе Z = s(s(s(s(0)))), что является представлением 4.

Answer 3

Вы не получите численные термины, как 1+3=4, все, что вы получаете, это термин s/1 который может встроить себя на любую глубину и, следовательно, может представлять любое естественное число. Вы можете объединить такие термины (используя plus/3) и тем самым достичь суммирования.

Обратите внимание, что ваше определение plus/3 не имеет ничего общего со встроенным SWI-Prolog plus/3 (что работает с целыми числами, а не с s/1 условия):

?- help(plus).
plus(?Int1, ?Int2, ?Int3)
    True if Int3 = Int1 + Int2.
    At least two of the three arguments must be instantiated to integers.