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

Наибольшее распространение в системах искусственного интеллекта получила формальная система, носящая название исчисления предикатов первого порядка (ИППП).

Алфавит ИППП состоит из:

· предметных переменных , , , ... (для их обозначения используются строчные буквы из конца латинского алфавита);

· предметных констант , , , ... (для их обозначения используются строчные буквы из начала латинского алфавита);

· -местных предикатных букв , , (для их обозначения используются прописные буквы из середины латинского алфавита);

· -местных функциональных букв , , (для их обозначения используются строчные буквы из середины латинского алфавита);

· знаков связок: (коньюнкция), (дизъюнкция), (отрицание), (импликация);

· кванторов общности и существования ;

· круглых скобок и запятой.

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

1. Терм:

o всякая предметная переменная и константа является термом;

o если — функциональная буква и — термы, то — также терм.

2. Формула:

o если — предикатная буква и — термы, то — элементарная формула (атом), являющаяся частным случаем правильно построенной формулы (п.п.ф.);

o если и — п.п.ф., а — предметная переменная, то , , , , и — также п.п.ф..

Элементарная формула (атом) и ее отрицание называются литералами (соответственно, положительным и отрицательным).

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

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

Формула называется незамкнутой, если она содержит свободные переменные.

Рассматриваемое исчисление предикатов является исчислением первого порядка, поскольку в нем допустимы кванторы лишь по переменным (в исчислении второго порядка — дополнительно по предикатным и функциональным буквам).