Логическое программирование. Язык ПРОЛОГ.

Как решается задача с помощью ЭВМ? Математик разрабатыва-
ет алгоритм решения задачи, а программист, используя один из
языков программирования, например PASCAL, реализует предло-
женный алгоритм в виде программы.
Возможен иной подход. Он основывается на следующих трех
моментах:
• На способности ЭВМ доказывать теоремы. Эта способность,
как мы знаем, называется автоматическим доказательством
теорем (см. § 2.5).
• На понимании, что вычисление — это частный случай логиче-
ского вывода.
• На осознании того, что алгоритм - формальное задание
функции (см. § 4.1).
Иначе говоря, задачу, решение которой ищется, надо предста-
вить в виде высказывания, доказательство которого следует предо-
ставить ЭВМ.
Таким образом, компьютеру предлагается не алгоритм, а опи-
сание предметной области задачи и сама задача в виде формул

формального исчисления. Решение задачи является в таком случае
выводом в данном исчислении. Какова при этом роль программи-
ста? От программиста при таком подходе требуется описать с до-
статочной степенью полноты предметную область и формулировку
задачи на языке этого исчисления, а поиск вывода, приводящего к
решению задачи, поручается компьютеру.

Логическая программа представляет собой конечный набор формул логики предикатов одного из следующих видов: P(t1,...,tn), где t-термы, а P-предикат. Эти формулы называются ФАКТАМИ (факт - единственный экземпляр, свой-во, отношение между объектами).

По аналогии можно записать в виде ПРАВИЛА:

Q(s1,...sk):-Q1(s1,...sk),...Qm(s1,...sk)

Читается как Q(s1,...sk), если истинны Q1(s1,...sk),...Qm(s1,...sk).

Q(s1,...sk) называется заголовком правила. Само правило позволяет выводить новые факты из уже имеющихся.

Таким образом, логическая прог-ма состоит из конечного числа фактов и правил.

ПРОЛОГ

Язык ПРОЛОГ существенно отличается от традиционных алгоритмических языков программирования, таких, как "Бейсик", "Паскаль" и т.п. При использовании последних для решения задач на компьютере пользователь сначала должен разработать алгоритм решения задачи, затем записать (закодировать) его на алгоритмическом языке программирования и, наконец, "прогнать" программу на компьютере и получить результат.

В ПРОЛОГЕ дело обстоит иначе. Пользователь лишь формулирует задачу, осуществляет ее постановку, т.е. сообщает компьютеру необходимые факты и правила, по которым эти факты соотносятся друг с другом. Затем формулируется вопрос, на который компьютер отвечает самостоятельно, исходя из той "базы знаний", т.е. набора фактов и правил, которые пользователь сообщил компьютеру. Запись фактов происходит на языке логики предикатов. Правило построения выводов из имеющихся фактов — правило резолюции. Таким образом, ПРОЛОГ — это язык описания фактов, правил вывода заключений и постановки вопросов к базам данных, записываемых на языке математической логики. Фактически вопрос представляет собой теорему логики предикатов, а работа программы состоит в том, чтобы доказать эту теорему на основе фактов и правил из базы данных.

Компьютерная система языка ПРОЛОГ представляет собой интерпретатор, состоящий из следующих независимых подпрограмм: сканер, унификатор, управление, печать.

Подпрограмма сканер осуществляет синтаксический контроль исходного текста программы и его перевод во внутреннюю форму хранения программы — в дерево. Дерево хранится в памяти машины в виде упорядоченной совокупности массивов.

Подпрограмма унификатор выполняет в процессе поиска доказательства по методу резолюций действия для унификации двух термов, т.е. проводит поиск такой совокупности значений переменных, входящих в данные термы, при подстановке которых в эти термы они станут равными, а соответствующие формулы резольвируемыми.

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

Наконец, подпрограмма печать выводит на экран все значения переменных, указанных в вопросе и удовлетворяющих совокупности фактов и правил.

Краткое описание языка ПРОЛОГ и примеры

Язык ПРОЛОГ начинается со следующих основных синтаксических конструкций.

Атом — последовательность букв, цифр и знаков минус, начинающаяся с буквы или знака минус, длиной не более 256 символов. Переменная — либо буква, либо атом, заканчивающийся символом апострофа, либо символом подчеркивания. Целое — значение целого находится в пределах от 0 до 32767. Терм — выражение вида $F(x,y,\ldots,z)$ , где $F$ — атом, называемый именем терма; $x,y,\ldots,z$ — аргументы, в качестве которых могут выступать любые синтаксические конструкции входного языка. Список — упорядоченная совокупность объектов (элементов списка), в качестве которых могут выступать любые синтаксические конструкции языка, включая сами списки.

Перечисленные грамматические конструкции могут образовывать предложения (или фразы, клаузы, формулы, дизъюнкты), на вид которых наложено следующее ограничение. Все они должны быть дизъюнктами Хорна. Это такие совершенные дизъюнктивные одночлены, которые имеют не более одного вхождения положительной переменной (т.е. переменной без знака отрицания). Их общий вид: $B\lor\lnot A_1\lor\lnot A_2\lor\ldots\lor\lnot A_n$ . Ясно, что этот вид равносилен следующему:

$\lnot(A_1\land A_2\land\ldots\land A_n)\lor B$ , то есть $(A_1\land A_2\land\ldots\land A_n)\to B$ .

Выделяют следующие три типа таких предложений: факт, правило и вопрос.

Факт (или допущение без условий) имеет вид: $B$ . Факт означает, что $B$ истинно, или что цель $B$ определена. Факты записываются в форме предикатов от одной или нескольких переменных. Например, высказывания "Водород — элемент 1-й группы", "Хлор — элемент 7-й группы" записываются на ПРОЛОГЕ в следующей форме:

! ЭЛЕМЕНТ $(H,1)$ ;

! ЭЛЕМЕНТ $(C1,7)$ .

Правило (или условное допущение) имеет вид: $B\lor\lnot A_1\lor\ldots\lor\lnot A_n$ , или в эквивалентной форме $B\leftarrow (A_1\land\ldots\land A_n)$ , При этом $B$ называется заключением, $A_1$ — условием $1,\ldots,A_n$ — условием $n$ . Читается: заключение $B$ будет истинным, если условия $A_1,\ldots,A_n$ будут все истинными. Правило — это формальная запись вывода умозаключения. Правило определяет зависимость одних объектов или действий от других.

Например, правило "Элемент х вступает в реакцию с элементом $y$ , если $x$ — элемент 7-й группы" на ПРОЛОГЕ запишется так:

! РЕАКЦИЯ $(x,y)~\leftarrow$ ЭЛЕМЕНТ $(x,1)$ , ЭЛЕМЕНТ $(y,7)$ .

Совокупность фактов и правил образует базу данных. К базе данных можно задавать вопросы, обеспечивая тем самым запуск программы на исполнение.

Вопрос имеет вид: $\lnot A_1\lor\ldots\lor\lnot A_n$ или $\lnot(A_1\land \ldots\land A_n)$ .

Работа программы направлена на поиск такого факта $B$ в базе данных, которое выводится из условий $A_1,\ldots,A_n$ . Таким образом, вопрос представляет собой теорему, а работа программы состоит в том, чтобы доказать эту теорему на основе фактов и правил из базы данных.

Пример 40.1. В качестве примера рассмотрим задачу из курса химии 7-го класса: какие химические элементы могут вступать в реакцию друг с другом.

Прежде всего создадим "базу знаний" для данной задачи. (Обратим внимание на то, что в конце каждого терма необходимо ставить знак ";", а в правилах вместо союза "и" ставить запятую.) База знаний данной задачи имеет вид:

! ЭЛЕМЕНТ $(H,1);$

! ЭЛЕМЕНТ $(C1,7);$

! ЭЛЕМЕНТ $(Na,1);$

! ЭЛЕМЕНТ $(I,7);$

! ЭЛЕМЕНТ $(C,4);$

РЕАКЦИЯМ $(x,y)~\leftarrow$ ЭЛЕМЕНТ $(x,1)$ , ЭЛЕМЕНТ $(y,7);$ .

Вопросы к базе знаний в ПРОЛОГЕ выражаются в форме предикатов, перед которыми ставится знак "?" При этом искомые значения обозначаются переменными:

? РЕАКЦИЯМ $(x,y);$ .

Ответ на этот вопрос компьютер ищет, руководствуясь правилом: "Элемент $x$ вступает в реакцию с элементом $y$ , если $x$ есть элемент 1-й группы и у есть элемент 7-й группы". В базе знаний отыскиваются факты, удовлетворяющие этим условиям. Ответ будет следующий:

$x=H,\quad y=C1,\quad x=Na,\quad y=1.$

Задачу можно усложнить, добавив в базу знаний в качестве фактов все элементы таблицы Менделеева, а в качестве правил — все возможные реакции взаимодействия между ними.

Пример 40.2. Рассмотрим еще один пример ПРОЛОГ-программы. Составим программу классификации животных. Это — одна из ведущих тем в курсе биологии 7-го класса. Прежде всего необходимо установить существенные определяющие признаки для такой системы классификации животных. Введем предикат, фиксирующий эти признаки животного:

! ПРИЗНАК(<животное>, <строение>, <дыхание>, <кровообращение, <размножение>).

Введем в базу знаний следующие факты:
! ПРИЗНАК(волк, хордовое, легочное, теплокровное, живородящее);
! ПРИЗНАК(крокодил, хордовое, легочное, холоднокровное, яйцекладущее);
! ПРИЗНАК(окунь, хордовое, жаберное, холоднокровное, икрокладущее);
! ПРИЗНАК(голубь, хордовое, легочное, теплокровное, яйцекладущее).

Теперь введем в базу знаний следующие правила:
! МЛЕКОПИТАЮЩЕЕ(х) $\leftarrow$ ПРИЗНАК^, хордовое, легочное, теплокровное, живородящее);
! ПТИЦА(х) $\leftarrow$ ПРИЗНАКАХ, хордовое, легочное, теплокровное, яйцекладущее);
! ПРЕСМЫКАЮЩЕЕСЯ $(x)~\leftarrow$ ПРИЗНАКАХ, хордовое, легочное, холоднокровное, яйцекладущее);
! РЫБА(x) $\leftarrow$ ПРИЗНАКА(x, хордовое, жаберное, холоднокровное, икрокладущее);.

Теперь можем задавать вопросы. На вопрос "? РЫБА(x);" получим ответ x = окунь; на вопрос "? МЛЕКОПИТАЮЩЕЕ(x);" получим ответ x = волк и т. д.

Имеющуюся базу знаний можно расширять, вводя в нее новые факты и новые правила. Например, предикат поведения:

! ПОВЕДЕНИЕ(<животное>, <питание>, <среда обитания>);.

Соответственно новые правила: хищное млекопитающее, водоплавающее млекопитающее и т. д.

! ХИЩМЛЕКОПИТАЮЩЕЕ(x) $\leftarrow$ МЛЕКОПИТАЮЩЕЕ(x), ПОВЕДЕНИЕ(x, плотоядное, — );
! ВОДМЛЕКОПИТАЮЩЕЕ(x) $\leftarrow$ МЛЕКОПИТАЮЩЕЕ(х), ПОВЕДЕНИЕ(x, — , вода);.
(В случае, если какой-либо признак не имеет значения, в правилах и вопросах ставится знак "—".)

[indent]Таким образом, используя минимальные средства логического программирования и создавая простейшие информационно-логические системы, можно строить интересные и полезные обучающие компьютерные системы по различным предметам. При этом обучающие возможности таких систем реализуются не только (а может, и не столько) в процессе задавания вопросов и получения ответов, но и в процессе построения самой "базы знаний".

Сферы применения языка ПРОЛОГ

Во-первых, на языке ПРОЛОГ прекрасно реализуется модель реляционной базы данных, представляющая собой хорошо разработанный формализм.

Во-вторых, исследователи, специализирующиеся в области программной инженерии, показали, что логическую спецификацию системы можно непосредственно преобразовать в логическую программу на языке ПРОЛОГ.

В-третьих, Кольмеррор, создавший язык ПРОЛОГ, первоначально предназначал его для обработки естественного языка. Он разработал на ПРОЛОГЕ систему грамматического разбора естественного языка нисходящим методом. Этот формализм был доработан учеными, которые продемонстрировали его успешное применение к системам, которые обрабатывают запросы, сформулированные на естественном языке.

В-четвертых, все основные концепции, используемые в формализмах представления знаний для задач искусственного интеллекта, включая семантические сети, фреймы, правила продукций и объектно-ориентированное программирование, можно выразить при помощи логики и реализовать средствами логического программирования.

В-пятых, при представлении знаний одной из главных задач является выбор такой формы представления, которая может быть использована в экспертных системах. При помощи ПРОЛОГА были построены экспертные системы для ряда сфер, включая решение уравнений, медицину, законодательство, юриспруденцию, архитектуру, автоматизацию заводского производства, проектирование электронных схем, синтез микропрограмм, анализ финансового положения и помощь в принятии решений. Простейшие примеры экспертных систем были рассмотрены в предыдущем пункте.