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

Определение. Предикатом P(x₁, x₂, …, x_n) называется функция, переменные которой принимают значения из некоторого множества М, а сама функция принимает два значения: И (истина) и Л (ложь), т.е.

Предикат от п аргументов называется п – местным предикатом. Высказывания считаются нуль – местными предикатами.

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

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

Кванторы бывают двух видов:

1) Квантор общности. Обозначается (" х) Р(х). Квантором общности называется высказывание истинное, когда Р(х) истинно для каждого элемента х из множества М, и ложное – в противном случае.

2) Квантор существования. Обозначается ($ х) Р(х). Квантором существования называется высказывание, истинное, когда существует элемент из множества М, для которого Р(х) истинно, и ложное в противном случае.

Операцию связывания квантором можно применять и к предикатам от большего числа переменных.

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

1) Перенос квантора через отрицание.

Ø(" x) A (x) º ($ x)Ø A (x); Ø($ x) A (x) º (" x)Ø A (x);

2) Вынесение квантора за скобки.

($ х)(А (х) & B) º ($ x) A (x) & B; (" x)(A (x) & B) º (" x) A (x) & B;

($ х)(А (х) Ú B) º ($ x) A (x) Ú B; (" x)(A (x) Ú B) º (" x) A (x) Ú B;

3) Перестановка одноименных кванторов.

(" y)(" x) A (x,y) º (" x)(" y) A (x,y); ($ y)($ x) A (x,y) º ($ x)($ y) A (x,y);

4) Переименование связанных переменных. Если заменить связанную переменную формулы А другой переменной, не входящей в эту формулу, в кванторе и всюду в области действия квантора получаем формулу, равносильную А.

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

Какими бы ни были формулы А и В для них справедливы следующие аксиомы:

1) A Þ (B Þ A);

2) (A Þ (B Þ C)) Þ ((A Þ B) Þ (A Þ C));

3) (ØB Þ ØA) Þ ((ØB Þ A) Þ B);

4) (" x_i) A (x_i) Þ A (x_j), где формула А (х_i) не содержит переменной x_i.

5) A (x_i) Þ ($ x_j) A (x_j), где формула А (х_i) не содержит переменной x_i.