Программирование на языке пролог

В этой программе аргументы используются для построения структур, представляющих смысл словосочетаний. Смысл каждого словосочетания определяет последний аргумент соответствующего правила. Однако смысл словосочетания может зависеть от некоторых других факторов, представленных другими аргументами. Например, глагол lives(живет) порождает высказывание вида lives(X),где X– это объект, обозначающий человека, который живет. Смысл слова livesне позволяет заранее определить, чем будет являться X. Чтобы быть полезным, понятие подобное livesдолжно быть применимо к некоторому конкретному классу объектов. Что представляет этот объект, будет определено из контекста, в котором используется глагол lives.Таким образом, имеем следующее определение: для любого X, применение глагола livesк Xимеет смысл lives(X).Слово, подобное every(каждый), является значительно более сложным. В этом случае понятие, соответствующее слову, должно применяться к некоторой переменной и к двум высказываниям, содержащим эту переменную. Результат можно сформулировать так: если подстановка некоторого объекта вместо переменной в первом утверждении делает что-то истинным, то подстановка того же объекта вместо переменной во втором утверждении также сделает что-то истинным.

Упражнение 9.4.Разберитесь в приведенной программе. Попробуйте проследить выполнение программы при обращении к ней с вопросами типа

?- предложение(Х, [every, man, loves, a, woman],[]).

Во что транслируются программой предложения «Every man that lives loves a woman» и «Every man that loves a woman lives». Предложение «Every man loves a woman» является в действительности двусмысленным - может существовать либо единственная женщина, которая нравится каждому мужчине, либо несколько женщин, каждая из которых нравится мужчине. Может ли программа породить альтернативные решения, описывающие смысл каждой из двух указанных интерпретаций предложения? Если нет, то почему? Какое простое предположение о построении структуры, отражающей смысл предложения, было сделано при написании программы?

ГЛАВА 10. ПРОЛОГ И МАТЕМАТИЧЕСКАЯ ЛОГИКА

Язык программирования Пролог был разработан коллективом во главе с Колмерауэром приблизительно в 1970 году. Это была первая попытка в разработке языка, который позволял бы программисту описывать свои задачи средствами математической логики, а не с помощью традиционных для программирования конструкций, указывающих чтои когдадолжна делать вычислительная машина. Эта идея нашла отражение в названии языка программирования «Пролог» (английское название «Prolog» является сокращением для Programming in Logic.– Перев.).

В этой книге основное внимание было уделено вопросам, связанным с использованием Пролога в качестве инструментального средства для решения практических задач. При этом ничего не говорилось о путях достижения конечной цели – создании системы логического программирования, шагом к которой является Пролог. В этой главе мы намереваемся отчасти исправить это несоответствие, рассмотрев вкратце связь Пролога с математической логикой и вопрос о том, в какой степени программирование на Прологе соответствует идее логического программирования.

10.1. Краткое введение в исчисление предикатов

Если мы намерены обсуждать связь Пролога с математической логикой, то прежде всего необходимо установить, что мы понимаем под логикой. Первоначально логика развивалась как некоторый способ представления определенного класса высказываний, так чтобы можно было, используя формальную процедуру, проверить, справедливы они или нет. Таким образом, логика может быть использована для выражения высказываний, отношений между высказываниями и правил выводаодних высказываний из других. Логическое исчисление специального вида, о котором будет идти речь в этой главе, называется исчисление предикатов.Здесь мы лишь затронем некоторые вопросы исчисления предикатов. Хорошим введением в математическую логику является книга Hodges W. Logic,Penguin Books, 1977. Более подробное обсуждение предмета дано в книге Mendelson E. Intro ductiontoMathematicalLogic,VanNostrandReinhold. [15] Вы так же можете обратиться к любой книге по математической логике. Другая книга, представляющая интерес, написана Chin L. С, Lee R. С.-Т. Symbolic Logic and Mechanical Theorem Proving,Academic Press, 1973. ^[16]

15

Имеется перевод: Мендельсон Э. Введение в математическую логику.- М.: Наука, 1971.- Прим. перев.

16

Имеется перевод: Чень Ч., Ли Р. Математическая логика и автоматическое доказательство теорем.- М.: Наука, 1983.- Прим. перев.

Для того чтобы делать высказывания о мире, необходимо уметь описывать объекты этого мира. В исчислении предикатов объекты представляются с помощью термов.Существуют термы трех типов:

• Константа.Это символ, обозначающий индивидуальный объект или понятие. Константы можно рассматривать как атомы языка Пролог и далее будет использоваться соответствующая форма записи. Так, грек, агатаи мирявляются константами.

• Переменная.Это символ, используемый в разное время для обозначения разных индивидуальных объектов. Переменные вводятся лишь одновременно с кванторами, о которых будет сказано далее. Термы, являющиеся переменными, можно рассматривать как переменные языка Пролог и далее для их обозначения будет использоваться синтаксис, принятый в Прологе. Таким образом, X, Человеки Грекявляются переменными.

• Составной терм.Составной терм состоит из функционального символаи упорядоченного множества термов, являющихся его аргументами.Идея состоит в том, что составной терм обозначает тот или иной индивидуальный объект, зависящий от других индивидуальных объектов, представленных его аргументами. Функциональный символ описывает характер зависимости. Например, можно было бы иметь функциональный символ, обозначающий «расстояние» и имеющий два аргумента. В этом случае составной терм обозначает расстояние между объектами, представленными его аргументами. Составной терм можно рассматривать как структуру языка Пролог, имеющую в качестве функтора функциональный символ. Составные термы будут записываться по правилам синтаксиса Пролога так, что, например, жена(генри)может обозначать жену Генри, расстояние(точка1, X)может обозначать расстояние между некоторой заданной точкой и каким-то другим объектом, который будет указан, а классы(мэри, на_следующий_ день_после(Х))может обозначать классы, в которых преподавала Мэри на следующий после X(необходимо указать день).

Таким образом, способы, используемые для представления объектов в исчислении предикатов, в точности соответствуют способам, имеющимся для этого в Прологе.

Для того чтобы делать высказывания об объектах, необходимо иметь возможность описывать отношения между объектами. Это делается с помощью предикатов. Атомарное высказывание(атомарная формула) состоит из предикатного символа и соответствующего ему упорядоченного множества термов, являющихся его аргументами. Это полностью аналогично целевому утверждению Пролога. Так, например, человек(мэри), владеет(Х,осел(Х))и нравится (Мужчина, вино)являются атомарными высказываниями (атомарными формулами). В языке Пролог структура может быть использована как в качестве целевого утверждения, так и в качестве аргумента для другой структуры. В исчислении предикатов дело обстоит иначе. Там имеется строгое разделение между функциональными символами, используемыми в качестве функторов для построения аргументов, и предикатными символами, используемыми в качестве функторов для построения высказываний (формул).

Используя атомарные высказывания, можно различными способами создавать составные высказывания. Именно здесь начинают появляться понятия не имеющие непосредственных аналогов в языке Пролог. Существует несколько способов построения более сложных высказываний из более простых. Прежде всего, можно использовать логические связки.Таким способом можно выразить понятия 'не', 'и', 'или', 'влечет' и 'является эквивалентным'. Далее приведено краткое описание этих связок и вкладываемых в них значений. Здесь ? и ? используются для обозначения произвольных высказываний (формул). В следующей таблице приводятся традиционная форма записи высказываний, используемая в исчислении предикатов, и форма записи, используемая в этой главе.

Логическая связка	Исчисление предикатов	Обозначение в книге	Значение
Отрицание		~	«не »
Конъюнкция		&	« и »
Дизъюнкция		#	« или »
Импликация		– ›	« влечет »
Эквивалентность		‹-›	« эквивалентна »

Так, например, конструкция

мужчина(фред) # женщина (фред)

могла бы быть использована для представления высказывания о том, что Фред является мужчиной илиФред является женщиной. Конструкция

мужчина(джон) -› человек (джон)

могла бы представлять высказывание: то, что Джон является мужчиной, влечетто, что он является человеком (еслиДжон мужчина, то он – человек). Понятия импликации и эквивалентности иногда при первом знакомстве с ними представляются несколько сложными. Мы говорим, что влечет , если всякий раз, когда истинно, то также истинно. Мы говорим, что эквивалентно , если истинно в точности в тех же случаях, что и . В действительности, эти понятия могут быть определены через понятия 'и', 'или', 'не'. А именно: