2.5. Предикатные формулы

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

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

Если S(A1,…,AN) – общезначимая схема исчисления высказываний, то она является также общезначимой схемой исчисления предикатов.

Пример. Схема исчисления высказываний: А  А общезначима, следовательно справедлива формула: (XP(X)  XP(X)).

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

Определение1. Пусть P(X₁, X₂, … X_N) – некоторый N-местный предикат на некотором множестве M. Этот предикат называется:

1. общезначимым (тождественно-истинным), если для любого набора значений аргументов его значение равно истина.

2. тождественно–ложным, если для любого набора значений аргументов, его значение равно ложь.

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

Пример тождественно-ложного предиката:

Определение 2. Пусть R(X₁, X₂, … X_N) и Q(X₁, X₂, … X_N) – два N-местных предиката от одних и тех же переменных, заданных на одном и том же множестве. Предикат Q(X₁, X₂, … X_N) называется следствием предиката R(X₁, X₂, … X_N), если для любого набора переменных, на которых предикат R(X₁, X₂, … X_N) является истинным, предикат Q(X₁, X₂, … X_N) также истинен.

Следствие обозначается как R(X₁, X₂, … X_N)  Q(X₁, X₂, … X_N).

Пример. XN, R(X) = “X делится 6”, Q(X) = “X делится на 3”

R(X)  Q(X), но не наоборот.

Теорема. Предикаты R(X₁, X₂, … X_N) и Q(X₁, X₂, … X_N) равносильны тогда и только тогда, когда каждый из них есть следствие другого.

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

2.6. Предварённая нормальная форма

В логике высказываний были введены две нормальные формы: конъюнктивная и дизъюнктивная. Приведение формулы логики высказываний к одной из этих форм позволяет упростить алгоритмы доказательства выполнимости и общезначимости. По аналогичным причинам вводится нормальная форма и в исчислении предикатов.

Определение. Предварённой формой называется формула, состоящая из высказываний, перед которыми стоит префикс, т.е. некоторая конечная последовательность квантификаций. Внутри высказываний кванторов нет.

Таким образом, предваренная формула имеет вид:

K1K2…KN A,

где Кi – обозначает либо , либо , для i = 1,…N и А – формула, не содержащая квантификаций.

Теорема. Для любой логической формулы существует логически эквивалентная ей предварённая нормальная форма.

Этапы получения предварённой формы.

Исключить связки эквивалентности и импликации.

Переименовать (если необходимо) связанные переменные таким образом, чтобы никакая переменная не имела бы одновременно свободных и связанных вхождений. XA(X)  TA(T) X, T M.

Удалить те квантификации, область действия которых не содержит вхождений квантифицированной переменной.

Преобразовать все вхождения отрицания, состоящие непосредственно перед атомами.

Переместить все квантификации в начало формулы. Для этого используется правила:

(X A & XB) X(A & B),

(X A(X) & B) X(A(X) & B), если В не содержит X,

(A & X B(X) ) X(A & B(X)), если A не содержит X,

(X A(X) & B)  X(A(X) & B), если В не содержит X,

(A & X B(X))  X(A& B(X)), если A не содержит X.

Замечание. Одна формула может допускать много эквивалентных предварённых форм. Вид результата зависит от порядка применения правил, а также от произвола при переименовании переменных.

Пример. Найдём предварённую нормальную форму для формулы:

X[P(X) & yX( Q(X, y) ® z R(A, X, y))] X[P(X) & y X ((Q(X, y) v R(A, X, y))] X[P(X) & y T(Q(T, y) v R(A, T, y)] X[P(X) & q T(Q(T, q) v R(A, T, q))] Xq T [P(X) & (Q(T, q) v R(A, T, q))].

Контрольное задание. Найти предварённую нормальную форму для следующих формул.

1. P(X)v(XQ(X,z)& yR(y,z));

2. X (Q(X,z) ®R(X,T))vyT (P(y,T)~S(y));

3. X(P(X,z) ÛQ(X,z)) ®Xz(R(X,z)®S(X,z).