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

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

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) остановит рекурсию, но я думаю, что я делаю это неправильно.

Источник

3 ответа

Решение

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

Теперь мы можем посмотреть на plus(P, Q, R), Прочитайте это как "plus истинно, если P плюс 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?", давайте рассмотрим, как мы можем объединить что-то с z на каждом шаге индукции

  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.

Источник

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

В арифметике Пеано натуральные числа представлены с помощью константы 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.

Источник

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

Обратите внимание, что ваше определение plus/3 не имеет ничего общего со встроенным в SWI-Пролог 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.
Источник
Другие вопросы по тегам