Дискуссионный математический форумМатематический форум

Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 4 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

Часовой пояс: UTC + 4 часа [ Летнее время ]


Математическая логика и логическое программирование

Математическая логика и логическое программирование


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


Возникновение языка ПРОЛОГ и его развитие


После того как Робинсон в 1965 г. открыл правило вывода, названное им правилом резолюции, значительно активизировались работы по созданию автоматизированного метода доказательства теорем через опровержение. Первоначально попытки создания алгоритма решения задач, базирующегося на правиле резолюции, оказывались успешными только для очень небольших задач. Существенно усовершенствовали такие алгоритмы Лавленд, Ковальски и Куэнер, разработав метод устранения моделей (1968) и метод селектирующей функции (1971). В 1974 г. Ковальски первым предложил метод, в соответствии с которым логический язык (именно язык логики предикатов) можно было бы использовать как язык программирования. Кольмерор и Руссель воспользовались результатами этих работ и к 1975 г. создали язык программирования, основывающийся на логике предикатов и правиле резолюции, названный ими ПРОЛОГ.


В течение 1970-х гг. язык ПРОЛОГ прошел путь развития от интересующего лишь узких специалистов экспериментального языка, созданного европейскими учеными, до одного из ведущих языков программирования, широко используемого во всем мире. В 1977 г. Уоррен и Перейра из Эдинбургского университета (Великобритания) создали интерпретатор/компилятор языка ПРОЛОГ для компьютера DEC-10, а в 1980 г. в Империэл Колледже разработан интерпретатор языка микроПРОЛОГ для персональных компьютеров.


В 1981 г. в Японии было объявлено о начале работ по созданию компьютеров пятого поколения. Они должны отличаться от компьютеров предыдущих поколений тем, что в них встроены функции программиста. По словесному заданию задачи, сформулированному на ограниченном профессиональном языке, эти компьютеры способны сами построить необходимую рабочую программу (синтезировать ее из отдельных модулей, хранящихся в памяти компьютера) и выполнить ее. В качестве основной методологии разработки программных средств для компьютеров пятого поколения было избрано логическое программирование. В состав такого компьютера должна входить так называемая база знаний, в которой хранится информация о закономерностях, присущих' данной проблемной области, и методах решения характерных для нее задач. Кроме того, в его состав должен входить специальный блок — решатель, который осуществляет процедуры логического вывода. С помощью решателя на основании сведений из базы знаний автоматически синтезируются нужные для пользователя программы. Полезный эффект от таких систем будет заключаться в том, что в распоряжение широких слоев общества будут предоставлены мощные вычислительные ресурсы и что возрастет производительность труда в ряде отраслей промышленности, в которых сейчас она традиционно низка.




Общая характеристика языка ПРОЛОГ


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


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


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


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


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


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


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




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


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


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


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


[math]\lnot(A_1\land A_2\land\ldots\land A_n)\lor B[/math], то есть [math](A_1\land A_2\land\ldots\land A_n)\to B[/math].

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


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


! ЭЛЕМЕНТ [math](H,1)[/math];

! ЭЛЕМЕНТ [math](C1,7)[/math].


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


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


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


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


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


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




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


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


! ЭЛЕМЕНТ[math](H,1);[/math]

! ЭЛЕМЕНТ[math](C1,7);[/math]

! ЭЛЕМЕНТ[math](Na,1);[/math]

! ЭЛЕМЕНТ[math](I,7);[/math]

! ЭЛЕМЕНТ[math](C,4);[/math]

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


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


? РЕАКЦИЯМ[math](x,y);[/math].


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


[math]x=H,\quad y=C1,\quad x=Na,\quad y=1.[/math]

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




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


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


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

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

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


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


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


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

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


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




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


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


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


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


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


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


Часовой пояс: UTC + 4 часа [ Летнее время ]


Яндекс.Метрика

Copyright © 2010-2016 MathHelpPlanet.com. All rights reserved