Характеристика языка предикатов первого порядка. Особенности представления знаний

2. Характеристика языка предикатов первого порядка. Особенности представления знаний.

В основе языка предикатов первого порядка лежит понятие предикатов, то есть логическая функция от одной или нескольких нелогических пременных. Функция может принимать значения истина (t) или ложь (f). В рамках логики утверждение считается истинным, если и относящееся к нему предположение считается истинным и заключение самого утверждения тоже истина.

Синтаксис языка предикатов включает: предикативные символы, символы переменных, константы (?), а также разделители ( ), [ ], “, ‘.

Предикативные символы используются для обозначения отношений. Объекты отношений записываются в ( ) после предикативного символа и наз-ся аргументами. Полная запись отношения наз-ся атомной или атомарной формулой.

Атомарная формула:

Является ( Иванов, спец.—поЭВМ)

предикативный терм 1 терм 2

символ

Термы могут представляться констанатами и переменными. Разрешено также в качестве термов использовать функции, к-рые обязательно должны быть определены в рамках ПО. Проектировщик ЭС заранеее определяет, как интерпретировать порядок термов в отношении. Допустимые выражения в исчислении предикатов, в частности атомарные формулы, наз-ся правильно построенными функциями ( ППФ ). В языке предикатов для каждой ППФ обязательно определяется конкретная интерпретация. Как только для ППФ определена интерпретация, говорят, что формула имеет значение “истина”, если соответствующее утверждение ПО истинно, в противном случае ППФ имеет значение “ложь”.

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

Конъюнкция ( ) используется для образования составных фраз:

Учится ( Иванов, эк.-университет )  располагается ( эк.-университет, Киев )

ППФ, построенные с помощью связки конъюнкция, наз-ся просто конъюнкциями.

Дизъюнкция (  ) реализует функцию не исключающего “или”.

Находятся ( Иванов, аудит.-147) И находится ( Иванов, библиотека ).

ППФ, построенные с помощью связки дизъюнкция, наз-ся дизъюнкциями.

Связка импликация (  ) используется для представления утверждения типа “если, то”.

Владеть ( Иванов, машина-1)  марка ( машина-1, “BMW”).

ППФ, построенная путем соединения формул с помощью связки импликация, наз-ся импликацией.

Левая сторона импликации наз-ся антецедент, правая - конциквент. Импликация имеет значение “истина”, если антецедент и конциквент имеют значения “истина”, либо антецедент имеет значение “ложь” независимо от конциквента. В остальных случаях импликация имеет значения “ложь”.

ППФ со знаком отрицания ( ~ ) пред ней наз-ся отрицанием.

В языке предикатов атомная формула может принимать только истинные значения, только ложные значения, а также в зависимости от значений переменных, которые в нее входят, либо итсина, либо ложь. Для того, чтобы при исчислении предикатов можно было манипулировать значениями переменных, потребовалось ввести понятие “квантор”.

Квантор - это операция, в которой участвуют все значения переменной одного предиката.

Квантор служит для указания меры, в какой экземпляры переменной (?), то есть константы должны быть истинными, чтобы все значения в целом были истинными.

Различают квантор общности  и квантор сущестовования  . Если перед предикатом записан квантор  для какой-то переменной, напр. (х), то это означает, что значение предиката будет истинным только в том случае, если все значения переменной х будут истинными.

(х) ( специалист-по-ЭВМ (х)  программист )

Если перед предикатом записан квантор , напр. (х), то для истинности предиката достаточно, чтобы только некотрые значения переменной, по крайней мере одно, были истинными.

 (х) ( специалист-по-ЭВМ(х)  оптимист(х) )

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

(х) (y) ( служащий (х)  руководитель (y, х))

Если некотрая переменная в ППФ проквантифицирована, то она называется связанной. В противном случае переменная называется свободной. Любое выражение, которое получается путем квантифицирования правильной формулы, является также ППФ.

Предикатами первого порядка наз-ся предикаты, в которых не допускается квантификация по предикатным или функциональным символам, а можно квантифицировать только переменные.

3. Аппарат логического вывода.

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

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

“Modus ponens” - используется для создания из ППФ вида А ППФ вида В

( А  В).  (“турникет”) интерпретируется как “следовательно”.

Операция специализации. Суть — позволяет доказать, что если некоторому классу обьектов присуще к.-л. свойство, то любой обьект данного класса будет обладать этим свойством. Для всех обьектов класса исп. свойство А, следовательно

x) W(x), A L*W(A) (?)

Операция — унификация. Использ-ся для док-ва теории, содержащих квантиоризированные формулы приводят в соответствие определенные подвыражения формы путем нахождения подстановок.

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

Для применения резолюции ППФ должны быть переведены в клаузальную форму путем упрощения, а затем представлено в форме дизьюнкции. Процесс преобразования сводится к следующ. основным этапам:

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 (x₁, x₂, ...)

(переменные и константы) : (i, i, ...) - выдает на текущее устройство записи констант и содержание переменных

writef (<формат>, x₁, x₂, ...)

(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 согласуется при N₁=3

2) M₁=N₁-3 согласуется при N₁=3 и M₁=2

3) posl (2, U₁) приводит ко второму рекурсивному обращению и так как это обращение не согласовано с первым, то последнее утверждение (V=U*N) откладывается.

2. Согласование posl (2, U₁) с posl (0, 1) приводит к неудаче. Происходит сопоставление с заголовком 2-го утверждения, что заканчивается удачей, при этом N₂=2 и V=U₁ . происходит доказательство по цели этого утверждения:

1) согласуется при N₂=2

2) согласуется при N₂=2 и М₂=1

3) posl (1, U₂) приводит к повторному рекурсивному обращению

4) откладывается

3. Согласование posl (1, U₂) с posl (0, 1) приводит к неудаче. Сопоставление с заголовком 2-го утверждения заканчивается неудачей, при N₃=1 и V=U₂ . Происходит доказательство по цели этого утверждения:

1) согласуется при N₃=1

2) согласуется при N₃=1 и М₃=0

3) posl (0, N₃) приводит к повторному рекурсивному обращению.

Полученное целевое утверждение сопоставляется с первым целевым утверждением posl (0, 1), при этом U₃ получает заначение 1.

На этом этап разбиения заканчивается.

II. Этап сборки решения.

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

1) U₂=U₃*1 , так как U₃=1 то U₂=1

2) U₁=U₂*2 U₁=2

3) X=U₁*3 X=6