Для применения резолюции ППФ
должны быть переведены в клаузальную форму путем упрощения, а затем
представлено в форме дизьюнкции. Процесс преобразования сводится к следующ.
основным этапам:
1 — исключение символов
импликации из формул и ограничение области действия символа отрицания
2 — разделение переменных,
т.е. замена одной связанной квантором переменной, кот. встречается в выражении
несколько раз — различными именами
3 — исключение кванторов
существования путем их замены функциями, аргументами которых являются
переменные, связанные квантором общности, область действия кот. включает
область действия исключенного квантора существования.
4 — преобразование
предположений в префиксную форму, т.е. в ППФ не остается кванторов
существования. Каждый квантор общности имеет свою переменную, поэтому все
кванторы общности можно переместить в начало ППФ и считать, что область
действия каждого квантора включает всю ППФ.
5 — приведение матрицы к
коньюнктивной нормальной форме, т.е. коньюнкции конечного множества дизьюнкций.
6 — исключение кванторов
общности. Это возможно, т.к. все переменные, оставшиеся на этом этапе
относятся к квантору общности.
7 — исключение символов
коньюнкции. В результате матрица остается только в виде дизьюнкций, над
которыми возможно проведение операций резлюции.
4. Особенности машинной реализации языка предикатов
первого порядка.
Машинная реализация языка
предиката первого порядка имеет ряд серьезных проблем, которые связаны с
универсальностью аппарата логического вывода. 1-я проблема — монотонность
рассуждений (в процессе логического вывода нельзя отказаться от промежуточного
заключения, если становятся известными дополнительные факты, которые
свидетельствуют о том, что полученные на основе этого заключения решения не
приводят к желаемому результату. 2-я проблема — комбинаторный взрыв ( в
процессе логического вывода невозможно применять оценочные критерии для выбора
очередного правила. Безсистемное применение правил в рассчете на случайное
доказательство приводит к тому, что возникает много лишних цепочек ППФ ,
активных в определенный момент времени. Это чаще всего приводит к переполнению
рабочей памяти.
В процессе исследований по
отысканию эффективных процедур машинной реализации языка предиката наметилось 2
основных подхода(кон. 60-х гг.):
1 — Отбрасывается принцип
универсальности языка предиката и производится поиск конкретных процедур,
эффективных для конкретной предметной области. В этом случае в БЗ вводились
обширные знания предметной области. Наиболее типичный представитель — LISP
2 — развивался в рамках
традиционной логики и был направлен на сохранение универсальности ,
свойственной языку- предикату путем разработки эффективных процедур
логического вывода универсальных по своему характеру, но позволяющих
нейтрализовать монотонность и комбинаторный взрыв.
Наиболее эффективной
разработкой этого подхода явл. язык PROLOG. В нем принята обратная стратегия
вывода. Полностью реализованы все средства описания знаний языка-предиката, в
т.ч. и кванторами для порождения новых высказываний используется операция
резолюции.В качестве процедуры поиска решения, позволяющей устранить
монотонность и комбинаторный взрыв используют поиск в иерархически
упорядоченном пространстве состояний.
PROLOG. Реализация на ПЭВМ
1. Интегрировання Среда языка
Turbo Prolog.
2. Структура программы
3. Стандартные типы доменов
4. Прототипы предиката
5. Утверждения и цели
6. Арифметические выражения.
7. Встроенные прдикаты языка
1. Интегрировання Среда языка Turbo Prolog.
Функционирование Т.Р. требует
наличие следующих стандартных каталогов:
·
корневой Prolog, в котором должны
находится следующие файлы:
·
prolog.exe
·
prolog.ovl для создания exe
файла
·
prolog.r тексты сообщения об
ошибках
·
prolog.hlp файл помощи
·
prolog.sys конфигурация среды
·
prolog.lib библиотеки
·
prolog.obj вспомагательный файл
для создания пользов-их exe файлов
·
подкаталог PRO для
пользовательских исходных файлов (расширение .pro)
·
подкаталог OBJ для
пользовательских обьктных и prg файлов
·
подкаталог EXE для хранения пользовательских
exe файлов
·
подкаталог DOS для команд ОС в том
случае, если предполагается их использование из пользовательских
программ. (min command.com)
2
Структура программы на
TURBO PROLOG
1.Domains
2.predicates
3.clauses
1
Для определения типов доменов или данных, используемых в программе
2
описание прототипов пользовательских предикатов
3
“утверждения” включает описание фактов в виде предикатов и правил, т.е.
декларативных и процедурных знаний
4
содержит цель решения задач, при его отсутствии система запрашивает цель
решения задачи в окне диалога и в этом-же окне получаем ответ, при его
присутствии в нем помещаем пользовательский интерфейс.
Место для печатания
-35--36--37-
readint
(<целое>)
(integer)
: (0) - читает целое число, чтение заканчивается нажатием <Enter>
readreal
(<вещественное>)
(real)
: (0) - вещ.
readchar(<знак>)
(char)
: (0) - читает единичный символ
readln
(<строка>) (string) : (0) - читает строку символов
inkey
(<знак>) (char) : (0) - заканчивается истиной, если после предыдущей
операции была нажата клавиша, возвращается её код. Если не была нажата, то
предикат оканчивается неудачей
nl
- код двух клавиш - переход на новую строку
write
(x1, x2, ...)
(переменные
и константы) : (i, i, ...) - выдает на текущее устройство записи констант и
содержание переменных
writef
(<формат>, x1, x2, ...)
(string,
<переменные и константы>) : (i, i, ...)
Структура
формата:
“ %
- m.pw “, где % - признак форматного вывода
если
задан “-”, то знаки должны выравниваться по левому краю, если не задан - по
правому
m -
длина поля вывода
p -
кол-во цифр после точки
w -
тип числа, вместо w записывается f, если выводится число в десятичном виде, e -
в экспотенциальной форме, q - в самом коротком формате.
Предикаты
работы с символьными данными.
str_lon
(<строка>, <длина>)
(string,
integer) : (i, i) (i, 0)
если
задано (i, i), проверяется длина строки, если (i, 0) - возвращается длина
строки
Преобразование
типов
Все
предикатные преобразования действуют в обе стороны. Случай (i, i) проверяет истинность
для всех типов, кроме real. Преобразование между типами string, symbol и real,
integer пр-ся (?) автоматически.
char_int
(<знак>, <целое>)
(сhar,
integer) : (i, 0) (0, i) (i, i)
str_char
(<знак как строка>, <знак>)
(string,
сhar) : (i, 0) (0, i) (i, i)
str_int
(<строка>, <вещ.>)
(string,
real) : (i, 0) (0, i)
и
т. д.
Работа
с командами операционной системы
Необходимым
условием для работы с предикатами этой группы есть наличие подкаталога DOS, в
котором бы был записан минимум command.com
system
(<команда OS>)
(string)
: (i) - передает команду OS
date
(<год>, <месяц>, <день>)
(integer,
integer, integer) : (i, i, i) (0, 0, 0) - устанавливает, если (i, i, i), или
возвращает, если (0, 0, 0) системную дату
time
... - то же
dir
(<маршрут>, <спецификатор файла>, <имя файла>)
(string,
string, string) : (i, i, 0) - выдаются на экран специфицированные файлы из
каталога по маршруту. Возможно выбрать из каталога имя одного файла с помощью
стрелок управления курсором, при нажатии <Enter> имя этого файла присваивается
третьему аргументу предиката
Специальные предикаты языка Turbo Prolog
bouncl
(<переменная>) - “истина, если переменная является конкретизированной
free
(<переменная>) - “истина, если переменная не является конкретизированной
fail
- всегда ложн. вызывает возврат для проверки базы в правилах
!
- (cat) - предикат отсечения, ограничивает возврат
exit
- останавливает выполнение пользовательской программы и передает управление
меню Turbo Prolog
trace
- общее включение режима отладки. Указывается в начале исходной программы
trace
(<статус>)
(symbol)
: (i) (0) - устанавливает, если i, или возвращает, если 0, текущий режим
отладки. В качестве статуса можно использовать on/off. Использование этого
предиката предполагает наличие trace в начале программы
diagnostics
- позволяет выдать анализ программы в процессе компиляции. Анализ включает
имена используемых предикатов. Для каждого имени определяется, являются ли
аргументы конкретного предиката фактами или указывается конкретность предиката.
nowarnings
- отключает предупреждения в процессе компиляции
project
“имя файла” - данная программа является частью проекта
include
“имя файла” - в компиляцию включается файл с указанным именем
Управление ходом выполнения программ на языке ТР.
1.
Рекурсия.
2.
Возврат и отсечение.
1. Рекурсия.
В механизм обработки программ
на языке ТР заложена рекурсия, то есть вычисление значения функции с помощью
той же функции, но с измененными параметрами. Рекурсия в ТР реализуется в 2
этапа:
1) исходная задача
разбивается на более мелкие частные задачи и формируются частные решения и на
основе которых затем будет получено общее решение задачи.
Процесс разбиения задачи на
подзадачи наз-ся редукцией. Редукция завершается в том случае, если
сформирована подзадача, которая может быть решена непосредственно.
2) сборка решения, начиная от
самого (?) последнего к самому общему. Для использования рекурсии в программах
необходимо использовать следующий формат правила рекурсии:
<имя правила рекурсии с
аргументами или без них> if
<список
предикатов> (1)
<предикат
условия выхода из рекурсии> (2)
<список
предикатов> (3)
<имя
правила рекурсии с аргументами или без них > (4)
<список
предикатов> (5)
В структуре правила
компоненты (1), (3), (5) могут присутствовать или отсутствовать с учетом
специфики решаемой задачи. Компоненты (2), (4) обязательны, так как они
организуют аппарат активизации правила рекурсии. Обычно компонента (1) - это
предикаты, которые не влияют на рекурсию. Компонента (3) содержит предикаты, с
помощью которых формируются новые значения аргументов, участвующих в рекурсии,
а (5) включает предикаты, которые формируют с помощью аппарата рекурсии искомые
значения. (5) - сборка решения. (2) - используется для останова рекурсии, а (4)
- реализует повторный вызов рекурсивного правила для новых значений аргумента.
В зависимости от заданных граничных условий различают нисходящую и восходящую
рекурсию.
Пример.
Определение n-го терма
последовательности 1, 1, 2, 6, 24, ...
N 0 1 2 3 4 ...
0 терм=1 3
терм=2*3
1 терм=1*1 4
терм=6*4
2 терм=1*2 5
терм=24*5
Для обозначения того факта,
что n-й член последовательности равен V, вводится предикат следующего вида:
posl (N, V)
Фрагмент программы:
domains
N, V = integer
predicates
posl = (N, V)
clauses
posl (0, 1)
posl (N, V) if
1) N>0
2) M=N-1
3) posl (M, U)
4) V=U*N
goal
posl (3, x)
Решение задачи производится в
2 этапа:
I этап.
1. Производится попытка
удовлетворить запрос пользователя, используя первое утверждение в разделе
clauses (posl (3,x) сопоставляется с posl (0, 1)). Так как 0 не сопоставляется
с 3, то попытка завершается неудачей. После этого posl (3, x) сопоставляется с
заголовком 2-го утверждения posl (N, V). Отсюда N получает значение 3, а V
связывается с х и система переходит к доказательству подцели в теле правила:
1) N>0 согласуется при N1=3
2) M1=N1-3
согласуется при N1=3 и M1=2
3) posl (2, U1)
приводит ко второму рекурсивному обращению и так как это обращение не
согласовано с первым, то последнее утверждение (V=U*N) откладывается.
2. Согласование posl (2, U1)
с posl (0, 1) приводит к неудаче. Происходит сопоставление с заголовком 2-го
утверждения, что заканчивается удачей, при этом N2=2 и V=U1
. происходит доказательство по цели этого утверждения:
1) согласуется при N2=2
2) согласуется при N2=2
и М2=1
3) posl (1, U2)
приводит к повторному рекурсивному обращению
4) откладывается
3. Согласование posl (1, U2)
с posl (0, 1) приводит к неудаче. Сопоставление с заголовком 2-го утверждения
заканчивается неудачей, при N3=1 и V=U2 . Происходит
доказательство по цели этого утверждения:
1) согласуется при N3=1
2) согласуется при N3=1
и М3=0
3) posl (0, N3)
приводит к повторному рекурсивному обращению.
Полученное целевое
утверждение сопоставляется с первым целевым утверждением posl (0, 1), при этом
U3 получает заначение 1.
На этом этап разбиения
заканчивается.
Страницы: 1, 2, 3, 4, 5, 6
|