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

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

2 голосов
/ 12 июня 2011

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

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 ]

4 голосов
/ 12 июня 2011

Итак, начнем с 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.

Таким образом, интерпретатор возвращает true, с z' = s(s(s(0))) и z = s(z'), то есть z = s(s(s(s(0)))).Итак, z равно 4.

1 голос
/ 12 июня 2011

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

В арифметике Пеано натуральные числа представлены с использованием константы 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 голос
/ 12 июня 2011

Вы не получите числовые термины, такие как 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.
...