Формула \(A\) логики предикатов называется выполнимой в области \(M\), если существуют значения переменных, входящих в эту формулу и отнесенных к области \(M\), при которых формула \(A\) принимает истинные значения.
Формула \(A\) называется выполнимой, если существует область, на которой эта формула выполнима.
Из предыдущего определения следует, что, если формула выполнима, то это не означает, что она выполнима в любой области.
Формула \(A\) называется тождественно истинной в области \(M\), если она принимает истинные значения для всех значений переменных, входящих в эту формулу и отнесенных к этой области.
Формула \(A\) называется общезначимой, если она тождественна истинна на всякой области.
Формула \(A\) называется тождественно ложной в области \(M\), если она принимает ложные значения для всех значений переменных, входящих в эту формулу и отнесенных к этой области.
Из приведенных определений следует:
1. Если формула \(A\) общезначима, то она и выполнима на всякой области.
2. Если формула \(A\) тождественно истинна в области \(M\), то она и выполнима в этой области.
3. Если формула \(A\) тождественно ложна в области \(M\), то она не выполнима в этой области.
4. Если формула \(A\) не выполнима, то она тождественно ложна на всякой области.
В связи с данными определениями естественно выделить два класса формул логики предикатов: выполнимых и не выполнимых формул.
Отметим, что общезначимую формулу называют логическим законом.
Приведем соответствующие примеры:
Пример 1. Формула \( \forall x \exists y P (x,y) \) выполнима. Действительно, если \( P (x,y) \) - предикат "\(x\)\(\prec\)\(y\)", определенный в области \(M = E \times E\), где \(E = \begin{Bmatrix} 0, 1, 2, ..., n, ... \end{Bmatrix}\), то формула \( \forall x \exists y P (x,y) \) тождественно истинная в области \(M\), и, следовательно, выполнима в этой области. Однако, если предикат "\(x\)\(\prec\)\(y\)" рассматривается в конечной области \(M_{1} = E _{1} \times E_{1}\), где \(E_{1} = \begin{Bmatrix} 0,1,2,...,k \end{Bmatrix}\), то формула \( \forall x \exists y P (x,y) \) будет тождественно ложной в области \(M_{1}\), и, следовательно, не выполнима в области \(M_{1}\). При этом ясно, что формула \( \forall x \exists y P (x,y) \) не общезначима.
Пример 2. Формула \( \exists x \exists y \)\(\begin{bmatrix} P (x) \wedge \overline { P (y) } \end{bmatrix}\) выполнима. Действительно, если \(P (x)\) - предикат "Число \(x\) - четно", определенный в области \(M = E \times E\), где \(E = \begin{Bmatrix} 0,1,2, ..., n,... \end{Bmatrix}\), то эта формула тождественно истинна в области \(M\), и, следовательно, выполнима в области \(M\). Однако, если предикат "Число \(x\) - четно" рассматривать в области \(M_{1} = E _{1} \times E_{1}\), где \(E_{1}\) - множество четных чисел, то формула \( \exists x \exists y \)\(\begin{bmatrix} P (x) \wedge \overline { P (y) } \end{bmatrix}\) будет тождественно ложной в области \(M_{1}\), и, следовательно, не выполнимой.
Пример 3. Формула \(\forall x \begin{bmatrix} P (x) \vee \overline { P (x) } \end{bmatrix}\) тождественно истинная в любой области \(M\). Значит, она является общезначимой, то есть является логическим законом (законом исключенного третьего).
Пример 4. Формула \(\forall x \begin{bmatrix} P (x) \wedge \overline { P (x) } \end{bmatrix}\) тождественно ложная в любой области \(M\), и по-этому она не выполнима.
Легко установить связь между общезначимостью и выполнимостью формул логики предикатов.
Теорема 1. Для того, чтобы формула \(A\) была общезначима, необходимо и достаточно, что бы ее отрицание было не выполнимо.
Доказательство. Необходимость. Пусть формула \(A\) общезначима. Тогда, очевидно, \(\bar{A}\) - тождественно ложная формула в любой области, и по-этому формула \(\bar{A}\) не выполнима.
Достаточность. Пусть формула \(\bar{A}\) не выполнима в любой области. Тогда по определению невыполнимой формулы \(\bar{A}\) - тождественно ложная в любой области. Значит, формула \(A\) - тождественно истинная формула в любой области, и, следовательно, она общезначима.
Теорема 2. Для того, чтобы формула \(A\) была выполнимой, необходимо и достаточно, чтобы формула \(\bar{A}\) была не общезначима.
Доказательство. Необходимо. Пусть формула \(A\) выполнима. Это означает, что существует область \(M\) и набор значений переменных, входящих в формулу \(A\), при которых формула \(A\) принимает истинное значение. Очевидно, что на этом наборе значений переменных формула \(\bar{A}\) принимает ложное значение, и, следовательно, формула \(\bar{A}\) не общезначима.
Достаточность. Пусть формула \(\bar{A}\) не общезначима. Тогда существует область \(M\) и набор значений переменных, входящих в формулу, при которых формула \(\bar{A}\) принимает ложное значение. На этом наборе значений переменных формула \(A\) принимает значение "истинна", и по-этому формула \(A\) выполнима.
Пример 5. Доказать, что формула \( A \equiv ( P (x) \rightarrow \overline { Q (x) } ) \rightarrow \overline { \exists x P (x) \wedge \forall x Q (x) } \) является общезначимой.
Решение. Считая, что формула \(A\) определена на любой области \(M\), проведем равносильные преобразования:
$$A \equiv \forall x ( P (x) \rightarrow \overline { Q (x) } ) \rightarrow \overline { \exists x P (x) \wedge \forall x Q (x) } \equiv$$
$$\equiv \overline { \forall x ( P (x) \rightarrow \overline { Q (x)} ) } \vee \overline { \exists x P (x) \wedge \forall x Q (x) } \equiv$$
$$\equiv \exists x ( \overline { \overline { P (x) } \vee \overline { Q (x) } ) } \vee \overline { \exists x P (x) } \vee \overline { \forall x Q (x) } \equiv$$
$$\equiv \exists x (P (x) \wedge Q (x) ) \vee \overline { \exists x P (x) } \vee \overline { \forall x Q (x) } \equiv$$
$$\equiv \exists x (P (x) \wedge Q (x) ) \vee \exists x \overline { Q (x) } \vee \overline { \exists x P (x) } \equiv$$
$$\equiv \exists x (P (x) \wedge Q (x) \vee \overline { Q (x) } ) \vee \overline { \exists x P (x) } \equiv$$
$$\equiv \exists x (P (x) \vee \overline { Q (x) }) \vee \overline { \exists x P (x) } \equiv$$
$$\equiv ( \exists x P (x) \vee \overline { \exists x P (x) } ) \vee \exists x \overline { Q (x) } \equiv 1 \vee \exists x \overline { Q (x) } \equiv 1,$$
то есть, формула \(A\) тождественно истинна для любых одноместных предикатов \( P (x) \) и \( Q (x) \) и в любой области.
Пример 6. Доказать, что формула:
\(A \equiv \exists (( F (x) \rightarrow \overline { F (x) } ) \wedge ( \overline { F (x) } \rightarrow F (x) )) \) тождественно ложна.
Решение. Так как формула \( ( F (x) \rightarrow \overline { F (x) } ) \wedge ( \overline { F (x) } \rightarrow F (x) ) \equiv F (x) \leftrightarrow \overline { F (x) } \), а формула \( F (x) \leftrightarrow \overline { F (x) } \), очевидно, тождественно ложна, то тождественно ложна и формула \( A\).
