Чтение онлайн

на главную

Жанры

Программирование на языке Пролог для искусственного интеллекта

Братко Иван

Шрифт:

not сделано( C1, C2, P) ] --->

 [ assert( дизъюнкт( CA v CB) ),

assert( сделано( C1, C2, P) ) ].

% Последнее правило: тупик

[] ---> [ write( 'Нет противоречия'), стоп ].

% удалить( P, E, E1) означает, получить из выражения E

% выражение E1, удалив из него подвыражение P

удалить( X, X v Y, Y).

удалить( X, Y v X, Y).

удалить( X, Y v Z, Y v Z1) :-

 удалить( X, Z, Z1).

удалить( X, Y v Z, Y1 v Z) :-

 удалить( X, Y, Y1).

%
внутри( P, E) означает P есть дизъюнктивное подвыражение

% выражения E

внутри( X, X).

внутри( X, Y) :-

 удалить( X, Y, _ ).

Рис. 16.7. Программа, управляемая образцами, для автоматического доказательства теорем.

Остается еще один вопрос: как преобразовать заданную пропозициональную формулу в конъюнктивную нормальную форму? Это несложное преобразование выполняется с помощью программы, показанной на рис. 16.8. Процедура

транс( Формула)

транслирует заданную формулу в множество дизъюнктов C1, C2 и т.д. и записывает их при помощи

assert
в базу данных в виде утверждений

дизъюнкт( C1).

дизъюнкт( C2).

...

Программа, управляемая образцами, для автоматического доказательства теорем запускается при помощи цели

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

?- транс(~(( а=>b) & ( b=>c) => ( а=>с)) ), пуск.

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

% Преобразование пропозициональной формулы в множество

% дизъюнктов с записью их в базу данных при помощи assert

:- op( 100, fy, ~). % Отрицание

:- op( 110, xfy, &). % Конъюнкция

:- op( 120, xfy, v). % Дизъюнкция

:- op( 130, xfy, =>). % Импликация

транс( F & G) :- !, % Транслировать конъюнктивную формулу

 транс( F),

 транс( G).

транс( Формула) :-

 тр( Формула, НовФ), !, % Шаг трансформации

 транс( НовФ).

транс( Формула) :- % Дальнейшая трансформация невозможна

 assert( дизъюнкт( Формула) ).

% Правила трансформаций для пропозициональных формул

тр( ~( ~X), X) :- !. % Двойное отрицание

тр( X => Y, ~X v Y) :- !. %
Устранение импликации

тр( ~( X & Y), ~X v ~Y) :- !. % Закон де Моргана

тр( ~( X v Y), ~X & ~Y) :- !. % Закон де Моргана

тр( X & Y v Z, (X v Z) & (Y v Z) ) :- !.

% Распределительный закон

тр( X v Y & Z, (X v Y) & (X v Z) ) :- !.

% Распределительный закон

тр( X v Y, X1 v Y) :- % Трансформация подвыражения

 тр( X, X1), !.

тр( X v Y, X v Y1) :- % Трансформация подвыражения

 тр( Y, Y1), !.

тр( ~X, ~Х1) :- % Трансформация подвыражения

 тр( X, X1).

Рис. 16.8. Преобразование пропозициональных формул в множество дизъюнктов с записью их в базу данных при помощи

assert
.

16.4. Заключительные замечания

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

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

Когда база данных велика, а программа содержит большое количество модулей, процесс сопоставления с образцами становится крайне неэффективным. Неэффективность можно уменьшить, усложнив организацию базы данных. В частности, можно ввести индексирование информации, записанной в базе данных, или разбить эту информацию на отдельные "подбазы данных", или же разбить все множество модулей на отдельные подмножества. Идея разбиения — в каждый момент дать доступ только к некоторому подмножеству базы данных или набора модулей, ограничив тем самым сопоставление образцов только этим подмножеством. Разумеется, в этом случае механизм управления должен усложниться, поскольку он должен будет обеспечить переход от одних подмножеств к другим с целью их активизации либо деактивизации. Для этого можно применить специальные метаправила.

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

assert
и
retract
. Это положение можно исправить, применив другой способ реализации базы данных, не требующий обращения к этим встроенным процедурам. Например, все состоять базы данных можно представить одним прологовским термом, передаваемым в процедуру
пуск
в качестве аргумента. Простейший способ реализации этой идеи — организовать этот терм в виде списка объектов базы данных. Тогда верхний уровень базы данных примет вид:

Поделиться:
Популярные книги

Бастард Императора

Орлов Андрей Юрьевич
1. Бастард Императора
Фантастика:
фэнтези
аниме
5.00
рейтинг книги
Бастард Императора

На границе империй. Том 10. Часть 1

INDIGO
Вселенная EVE Online
Фантастика:
космическая фантастика
попаданцы
5.00
рейтинг книги
На границе империй. Том 10. Часть 1

Имя нам Легион. Том 7

Дорничев Дмитрий
7. Меж двух миров
Фантастика:
боевая фантастика
рпг
аниме
5.00
рейтинг книги
Имя нам Легион. Том 7

Измена. Вторая жена мужа

Караева Алсу
Любовные романы:
современные любовные романы
5.00
рейтинг книги
Измена. Вторая жена мужа

Буря империи

Сай Ярослав
6. Медорфенов
Фантастика:
аниме
фэнтези
фантастика: прочее
эпическая фантастика
5.00
рейтинг книги
Буря империи

Пенсия для морского дьявола

Чиркунов Игорь
1. Первый в касте бездны
Фантастика:
попаданцы
5.29
рейтинг книги
Пенсия для морского дьявола

На изломе чувств

Юнина Наталья
Любовные романы:
современные любовные романы
6.83
рейтинг книги
На изломе чувств

Тринадцатый II

NikL
2. Видящий смерть
Фантастика:
фэнтези
попаданцы
аниме
5.00
рейтинг книги
Тринадцатый II

Сирота

Шмаков Алексей Семенович
1. Светлая Тьма
Фантастика:
юмористическое фэнтези
городское фэнтези
аниме
5.00
рейтинг книги
Сирота

Законы Рода. Том 9

Flow Ascold
9. Граф Берестьев
Фантастика:
городское фэнтези
попаданцы
аниме
дорама
фэнтези
фантастика: прочее
5.00
рейтинг книги
Законы Рода. Том 9

Красноармеец

Поселягин Владимир Геннадьевич
1. Красноармеец
Фантастика:
боевая фантастика
попаданцы
4.60
рейтинг книги
Красноармеец

Огненный князь 4

Машуков Тимур
4. Багряный восход
Фантастика:
попаданцы
аниме
5.00
рейтинг книги
Огненный князь 4

Начальник милиции. Книга 5

Дамиров Рафаэль
5. Начальник милиции
Фантастика:
попаданцы
альтернативная история
5.00
рейтинг книги
Начальник милиции. Книга 5

Инкарнатор

Прокофьев Роман Юрьевич
1. Стеллар
Фантастика:
боевая фантастика
рпг
7.30
рейтинг книги
Инкарнатор