Игошин Математическая логика и теория алгоритмов (1019110), страница 102
Текст из файла (страница 102)
Кольмерор и Руссель воспользовались результатами этих работ и к !975 г. создали язык программирования, основывающийся на логике предикатов и правиле резолюции, названный ими ПРОЛОГ. В течение !970-х гг. язык ПРОЛОГ прошел путь развития от интересующего лишь узких специалистов экспериментального языка, созданного европейскими учеными, до одного из ведущих языков программирования, широко используемого во всем мире. В 1977 г.
Уоррен и Перейра из Эдинбургского университета (Великобритания) создали интерпретатор/компилятор языка ПРОЛОГ для компьютера ПЕС-10, а в 1980 г. в Империэл Колледже разработан интерпретатор языка микроПРОЛОГ для персональных компьютеров. В 1981 г. в Японии было объявлено о начале работ по созданию компьютеров пятого поколения. 'Они должны отличаться от компьютеров предьщущих поколений тем, что в них встроены функции программиста. По словесному заданию задачи, сформулированному на ограниченном профессиональном языке, эти компьютеры способны сами построить необходимую рабочую программу (синтезировать ее из отдельных модулей, хранящихся в памяти компьютера) и выполнить ее.
В качестве основной методологии разработки программных средств для компьютеров пятого поколения было избрано логическое программирование. В состав такого компьютера должна входить так называемая база знаний, в которой хранится информация о закономерностях, присущих'данной проблемной области, и методах решения характерных для нее задач.
Кроме того, в его состав должен входить специальный блок — решатель, который осуществляет процедуры логического вывода. С помощью решателя на основании сведений из базы знаний автоматически синтезируются нужные для пользователя программы. Полезный эффект от таких систем будет заключаться в том, что в распоряжение широких слоев общества будут предоставлены мощные вычислительные ресурсы и что возрастет производительность труда в ряде отраслей промышленности, в которых сейчас она традиционно низка. Общая характеристика языка ПРОЛОГ.
Язык ПРОЛОГ существенно отличается от традиционных алгоритмических языков программирования, таких, как «Бейсик», «Паскаль» и т.п. При использовании последних для решения задач на компьютере пользователь сначала должен разработать алгоритм решения задачи, затем записать (закодировать) его на алгоритмическом языке 409 программирования и, наконец, «прогнать» программу на комль ютере и получить результат.
В ПРОЛОГЕ дело обстоит иначе. Пользователь лишь формули рует задачу, осуществляет ее постановку, т.е. сообшает компьютеру необходимые факты и правила, по которым эти факты соотносятся друг с другом. Затем формулируется вопрос, на который компьютер отвечает самостоятельно, исходя из той «базы знаний», т.е. набора фактов и правил, которые пользователь сообщил компьютеру. Запись фактов происходит на языке логики предикатов. Правило построения выводов из имеющихся фактов— правило резолюции. Таким образом, ПРОЛОà — это язык описания фактов, правил вывода заключений и постановки вопросов к базам данных, записываемых на языке математической логики. Фактически вопрос представляет собой теорему логики предикатов, а работа программы состоит в том, чтобы доказать эту теорему на основе фактов и правил из базы данных.
Компьютерная система языка ПРОЛОГ представляет собой интерпретатор, состоящий из следующих независимых подпрограмм: сканер, унификатор, управление, печать. Подпрограмма сканер осуществляет синтаксический контроль исходного текста программы и его перевод во внутреннюю форму хранения программы — в дерево. Дерево хранится в памяти машины в виде упорядоченной совокупности массивов. Подпрограмма унификатор выполняет в процессе поиска доказательства по методу резолюций действия для унификации двух термов, т.е. проводит поиск такой совокупности значений переменных, входящих в данные термы, при подстановке которых в эти термы они станут равными, а соответствующие формулы резольвируемыми.
Подпрограмма управления осуществляет процесс поиска доказательства. Алгоритм ее действия основан на правиле резолюции. Чтобы этот процесс произошел, программист должен четко описать задачу при помощи так называемых фраз (или клауз, или формул, или дизъюнктов) Хорна, выраженных на языке ПРОЛОГ. В каждой фразе формулируется некоторое отношение между термами. Терм — это обозначение, представляющее некоторую сущность из исследуемой области. Для того чтобы привести в действие данный алгоритм решения задачи, программист должен написать вопрос, согласно которому будет необходимо выяснить, является ли конкретная формула следствием заданного множества формул, представленных в программе. Наконец, подпрограмма печать выводит на экран все значения переменных, указанных в вопросе и удовлетворяющих совокупности фактов и правил.
Краткое описание языка ПРОЛОГ и примеры. Язык ПРОЛОГ начинается со следующих основных синтаксических конструкций. 410 Атом — последовательность букв, цифр и знаков минус, начинающаяся с буквы или знака минус, длиной не более 256 символов. Переменная — либо буква, либо атом, заканчиваюшийся символом апострофа, либо символом подчеркивания. Целое — значение целого находится в пределах от О до 32767. Терм — выражение вида с(х, у, ..., г), где с — атом, называемый именем терма; х, у, ..., г— аргументы, в качестве которых могут выступать любые синтаксические конструкции входного языка. Список — упорядоченная совокупность объектов (элементов списка), в качестве которых могут выступать любые синтаксические конструкции языка, включая сами списки. Перечисленные грамматические конструкции могут образовывать предложения (или фразы, клаузы, формулы, дизъюнкты), на вид которых наложено следуюшее ограничение.
Все они должны быть дизыонктами Хорна. Это такие совершенные дизъюнктивные одно- члены, которые имеют не более одного вхождения положительной переменной (т.е. переменной без знака отрицания). Их общий вид: В» А, ы Аз г ... ~ 4„. Ясно, что этот видравносиленследуюшему: -(А~ л Аз л ... н А„) ы В, т.е. (А1 н Аз л ... л А„) †> В. Вьиеляют следующие три типа таких предложений: факт, правило и вопрос.
Факт (или допушение без условий) имеет вид: В. Факт означает, что В истинно, или что цель В определена. Факты записываются в форме предикатов от одной или нескольких переменных. Например, высказывания «Водород — элемент 1-й группы», «Хлор — элемент 7-й группы» записываются на ПРОЛОГЕ в следующей форме: ! ЭЛЕМЕНТ (Н, 1); ! ЭЛЕМЕНТ (С1, 7). Правило (или условное допущение) имеет вид: В « — А1 ы ...
ы — А„, или в эквивалентной форме В» — (А, л ... л А„). При этом В называется заключением, А, — условием 1, ..., А„— условием п. Читается: заключение В будет истинным, если условия А„...,А„будут все истинными. Правило — это формальная запись вывода умозаключения. Правило определяет зависимость одних объектов или действий от других. Например, правило «Элемент х вступает в реакцию с элементом у, если х — элемент 7-й группы» на ПРОЛОГЕ запишется так: ! РЕАКЦИЯ(х, у) +- ЭЛЕМЕНТ(х, 1), ЭЛЕМЕНТ(у, 7). Совокупность фактов и правил образует базу данных. К базе данных можно задавать вопросы, обеспечивая тем самым запуск программы на исполнение.
Вопрос имеет вид: А, ы ..м А„или -(А, л ... л А„). Работа программы направлена на поиск такого факта В в базе данных, которое выводится из условий Ап ..., А„. Таким образом, вопрос представляет собой теорему, а работа программы состоит в том, чтобы доказать зту теорему на основе фактов и правил из базы данных. 411 Пример 40.1. В качестве примера рассмотрим задачу из курса химии 7-го класса: какие химические элементы могут вступать в реакцию друг с другом. Прежде всего создадим «базу знаний» для данной задачи.
(Обратим внимание на то, что в конце каждого терма необходимо ставить знак «;», а в правилах вместо союза «и» ставить запятую.) База знаний данной задачи имеет вид: ! ЭЛЕМЕНТ(Н, 1); ! ЭЛЕМЕНТ(С1, 7); ! ЭЛЕМЕНТ(Ха, 1); ! ЭЛЕМЕНТ(1, 7); ! ЭЛЕМЕНТ(С, 4); РЕАКЦИЯ(х, у) < — ЭЛЕМЕНТ(х, 1), ЭЛЕМЕНТ(у, 7);. Вопросы к базе знаний в ПРОЛОГЕ выражаются в форме предикатов, перед которыми ставится знак «?» При этом искомые значения обозначаются переменными: ? РЕАКЦИЯ(х, у);. Ответ на этот вопрос компьютер ищет, руководствуясь правилом: «Элемент х вступает в реакцию с элементом у, если х есть элемент 1-й группы и у есть элемент 7-й группы».
В базе знаний отыскиваются факты, удовлетворяющие этим условиям. Ответ будет следующий: х = Н, у = С1, х = Ха, у = 1. Задачу можно усложнить, добавив в базу знаний в качестве фактов все элементы таблицы Менделеева, а в качестве правил— все возможные реакции взаимодействия между ними. Пример 40.3. Рассмотрим еше один пример ПРОЛОГ-программы. Составим программу классификации животных. Это — одна из ведущих тем в курсе биологии 7-го класса. Прежде всего необходимо установить существенные определяющие признаки для такой системы классификации животных.
Введем предикат, фиксирующий эти признаки животного: ! ПРИЗНАК(<животное>, <строение>, <дыхание>, <кровообращение>, <размножение>). Введем в базу знаний следующие факты: ! ПРИЗНАК(волк, хордовое, легочное, теплокровное, живородяшее); ! ПРИЗНАК(крокодил, хордовое, легочное, холоднокровное, яйцекладушее); ! ПРИЗНАК(окунь, хордовое, жаберное, холоднокровное, икрокладушее); ! ПРИЗНАК(голубь, хордовое, легочное, теплокровное, яйцекладушее). Теперь введем в базу знаний следующие правила: ! МЛЕКОПИТАЮ(ЦЕЕ(х)»- ПРИЗНАК(х, хордовое, легочное, теплокровное, живородяшее); 412 ! ПТИЦА(х) « — ПРИЗНАК(х, хордовое, легочное, теплокровное, яйцекладушее); ! ПРЕСМЫКАЮЩЕЕСЯ(х) « — ПРИЗНАК(х, хордовое, легочное, холоднокровное, яйцекладущее); ! РЫБА(х) +- ПРИЗНАК(х, хордовое, жаберное, холоднокровное, икрокладушее); .
Теперь можем задавать вопросы. На вопрос «? РЫБА(х);» получим ответ х = окунь; на вопрос «? МЛЕКОПИТАЮЩЕЕ(х);» получим ответ х = волк и т. д. Имеющуюся базу знаний можно расширять, вводя в нее новые факты и новые правила. Например, предикат поведения: ! ПОВЕДЕНИЕ(<животное>, <питание>, <среда обитания>);. Соответственно новые правила: хищное млекопитающее, водоплавающее млекопитающее и т. д. ! ХИЩМЛЕКОПИТАЮЩЕЕ(х) « — МЛЕКОПИТАЮЩЕЕ(х), ПОВЕДЕНИЕ(х, плотоядное, — ); ! ВОДМЛЕКОПИТАЮЩЕЕ(х) +- МЛЕКОПИТАЮЩЕЕ(х), ПОВЕДЕНИЕ(х, —, вода);. (В случае, если какой-либо признак не имеет значения, в правилах и вопросах ставится знак « — ».) Таким образом, используя минимальные средства логического программирования и создавая простейшие информационно-логические системы, можно строить интересные и полезные обучающие компьютерные системы по различным предметам.
При этом обучающие возможности таких систем реализуются не только (а может, и не столько) в процессе задавания вопросов и получения ответов, но и в процессе построения самой «базы знаний». Примеры таких систем по некоторым школьным предметам (географии, истории, иностранному языку) описаны в статье'. Сферы применения языка ПРОЛОГ. Во-первых, на языке П РОЛОГ прекрасно реализуется модель реляционной базы данных, представляющая собой хорошо разработанный формализм. Во-вторых, исследователи, специализирующиеся в области программной инженерии, показали, что логическую спецификацию системы можно непосредственно преобразовать в логическую программу на языке ПРОЛОГ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
