Исчисление предикатов

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

Пусть имеется некоторое множество объектов, называемых предметной областью М. Знаки, обозначающие элементы этого множества, называют предметными константами, а знак, обозначающий произвольный элемент этого множества, – предметной переменной. Терм – это всякая предметная область или предметная константа если f – функциональная n-местная буква, и t₁, t_2,…,t _n – термы, то f(t_1,…,t _n) есть терм.

Выражение Р (x₁,x₂,…,x_n), где x_i, i= - предметные переменные, а Р принимает значения 0 и 1, называется логической функцией или предикатом. Переменные принимают значения из произвольного конечного и бесконечного множества М.

Предикатом или логической функцией называется функция от любого числа аргументов, принимающая истинные значения 1 и 0. Если в данном выражении заменить x_i на y_i, где y_i – предметные константы, то получим элементарную формулу, т.е. предикатные буквы применимы также и к предметным константам. Элементарные формулы иногда называют атомными. Из элементарных формул с помощью логических связок Ú (или), Ù (и), Ø (отрицание), ® (импликация) строят предметные формулы (иногда их называют правильно построенными формулами - ППФ). ППФ – один из важных классов выражений в исчислении предикатов. Кроме логических связок в рассмотрение вводят кванторы общности " или существования $.

Если Р – предметная формула, а х – предметная переменная, то выражения

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

Если P(x) в действительности не зависит от x, то выражения "х Р(х) и $ х Р(х) обозначают то же, что и P(x).

Конкретное вхождение переменной x в формулу P называется связанным, если оно либо непосредственно следует за каким-либо квантором, либо содержится в области действия некоторого квантора " или $. Вхождение переменной является свободным, если оно не является связанным. В выражении "x P(x,y) x - связанная, y - связанная.

Связанной переменной называется переменная, если в P имеется вхождение этой переменной.

Использование обоих кванторов не является обязательным. Рассмотрим выражение , оно обозначает высказывание « ложно», равносильное высказыванию «существует элемент x, для которого P(x)» ложно или, что тоже «существует элемент x, для которого истинно». Следовательно, равносильно выражению : = .

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

Вывод на предикатах.

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

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

Определим основные формы логического вывода.

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

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

Последовательность дедукции определяет “план” того, как достигнуть цели из начального состояния.

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