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

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

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

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

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

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

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) ("Xi)A(Xi) Þ A(Xj), где формула А(ХI) не содержит переменной Xi.

5) A(Xi) Þ ($Xj)A(Xj), где формула А(ХI) не содержит переменной Xi.

< Предыдущая		Следующая >