Формальные системы.Исчисление предикатов

Формальная система  определена, если:

1) Задан конечный алфавит (конечное множество символов).

2) Определена процедура построения формул (или слов) формальной системы.

3)   Выделено некоторое множество формул, называемых аксиомами.

4)   Задано конечное множество правил вывода, которые позволяют получать из некоторого конечного множества формул другое множество формул.

Предикат - это высказывание, содержащее неопределенность. О предикате невозможно судить, является он истинным или ложным. Тем не менее, он может принимать только два значения: истина или ложь.

Примеры:

1. "Некто - знаток"

2. "х+2=3"

3. "кто-то любит кого-то"

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

"11 - знаток" - истинно 

" 2+2=3" - ложно 

"Саша любит Машу" - истинно  (будем считать) 

В зависимости от количества неопределенностей  предикаты бывают одноместными, двуместными  и т.д. В примерах первые два одноместные, третий - двуместный.

Понятие ''предикат'' обобщает понятие  ''высказывание''. Неформально говоря, предикат – это высказывание, в которое можно подставлять аргументы. Если аргумент один – то предикат выражает свойство аргумента, если больше – то отношение между аргументами.

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

Основными отличиями логики предикатов от логики высказываний являются:

- использование в формулах  кванторов;

- использование в формулах  предикатов и функций;

- в логике предикатов  к компонентам логического выражения  можно получить доступ, а в  логике высказываний - нет. Например:

- логика высказываний: «Я - человек» ® «Я - смертен»;

- логика предикатов: человек(X) ® смертен(X) - X = «Я», «Вася», «Петя» и т.д.

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

Квантор существования $ указывает, что предложение истинно, по крайней мере, для одного значения переменной в заданном множестве.

Квантор всеобщности " указывает, что предложение истинно, для всех значений переменной в заданном множестве.

Алфавит исчисления предикатов состоит из предметных переменных х₁ , х₂, ..., предметных констант а₁, а₂, ..., предикатных букв P₁¹, Р₂¹, ..., Р^j_k... и функциональных букв f₁¹, f₂¹,..., f^j_k, ..., а также знаков логических связок Ú, Ù,¬,→, кванторов , и скобок (,).

Понятие формулы определяется в два этапа. Сначала определяются термы, а потом формулы.

Терм - переменная, константа или функция (т.е. объект или его свойство).

Аксиомы исчисления предикатов делятся на две группы :

1) аксиомы исчисления высказываний

2) две предикатные аксиомы:

В исчислении предикатов первого  порядка (узком исчислении предикатов) два правила вывода (подстановки  и заключения) исчисления высказываний дополняют еще тремя правилами: правилом для квантора ", правилом для квантора $, правилом переименования связанных переменных.

Достоинства и  недостатки логики предикатов первого  порядка. 

Достоинства логики предикатов первого порядка:

- в качестве «фундамента»  используется классический аппарат  математической логики, методы которой  достаточно хорошо изучены и  формально обоснованы;

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

Недостатки логики предикатов первого порядка :

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

- невозможность применения  в качестве термов (параметров) предикатов  других предикатов, т.е. невозможность  формулирования знаний о знаниях.  

 

 

Литература:

 

1. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика  для инженера. 2 изд. М., Энергоатомиздат, 1988 г.

2. Горбатов В.В. Основы дискретной  математики. М., Высшая школа, 1986 г.

3. Лорьер Ж.Л. Системы искусственного интеллекта. М., Мир, 1992 г.

4. http://www.ebiblio.ru/book/bib/02_estestv_nauki/Diskretnaj_matematika/ Book/docs/piece007.htm

             5.Верещагин Н.К., Шень А. Языки и исчисления. М., Издательство МЦНМО, 2012 г.