1. Проблема разрешимости в случае конечных областей.
Очевидно, что проблема разрешимости в случае конечных областей разрешима. Действительно, в этом случае кванторные операции можно заменить операциями конъюнкции и дизъюнкции и тем самым свести формулу логики предикатов к формуле алгебры логики, для которой проблема разрешимости разрешима.
Например, \( \forall x \exists y \begin{bmatrix} P (x,y) \vee \overline { P (x,x) } \end{bmatrix} \) в области \( M = \begin{Bmatrix} a, b \end{Bmatrix} \), состоящей из двух элементов, приводится к виду:
$$\forall x \exists y \begin{bmatrix} P (x,y) \vee \overline { P (x,x) } \end{bmatrix} \equiv \forall x \begin{bmatrix} P (x,a) \vee \overline { P (x,x) } \vee P (x,b) \end{bmatrix} \equiv$$
$$\begin{bmatrix} P (a,a) \vee \overline { P (a,a) } \vee P (a,b) \end{bmatrix} \wedge \begin{bmatrix} P (b,a) \vee \overline { P (b,b) } \vee P (b,b) \end{bmatrix}.$$
Так как каждый член последней конъюнкции является дизъюнкцией, содержащей высказывание и его отрицание, то формула истинна.
2. Проблема разрешимости для формул, содержащих в предваренной нормальной форме кванторы одноrо типа.
Формула логики предикатов называется замкнутой, если она не содержит свободных предметных переменных.
Если формула логики предикатов \(C\) содержит свободные переменные \(x_{1}, x_{2}, ..., x_{n}\), то формула
$$A = \forall x_{1} \forall x_{2} … \forall x_{n} C (x_{1}, x_{2}, ..., x_{n} )$$
называется замыканием общности формулы \(C\), а формула
$$B = \exists x_{1} \exists x_{2} … \exists x_{n} C (x_{1}, x_{2}, ..., x_{n} )$$
называется замыканием существования формулы \(C\).
Теорема 1. Если замкнутая формула логики предикатов в предваренной нормальной форме содержит только кванторы существования, число которых равно \(n\), и
тождественно истинна на любой области, состоящей из одного элемента, то она общезначима.
Доказательство. Пусть формула логики предикатов в предваренной нормальной форме имеет вид:
| $$B = \exists x_{1} \exists x_{2} … \exists x_{n} C (q_{1}, q_{2}, ..., P_{1}, P_{2}, ..., Q_{1}, Q_{2}, ... ),$$ | (1) |
где \(C\) кванторов не содержит; \(q_{i}\) - логические переменные, \(P_{i}\) - одноместные предикаты, \(Q_{i}\) - двухместные предикаты.
Значение истинности этой формулы зависит от входящих в нее переменных \(q_{1}, q_{2}, ...\), предикатов \(P_{1}, P_{2}, ...\), \(Q_{1}, Q_{2}, ...\) и так далее.
По условию теоремы на любой области \(M = \begin{Bmatrix} a \end{Bmatrix}\), содержащей только один элемент \(a\), данная формула тождественно истинна, то есть тождественно истинной является формула:
| $$C ( q_{1}, q_{2}, ... , P_{1}(a), P_{2}(a), ..., Q_{1}(a,a), Q_{2}(a,a), ...)$$ | (2) |
Формула (2), очевидно, является формулой алгебры логики.
Предположим, что формула (1) не является общезначимой. Тогда существует такая область \(M_{1}\) и такой набор значений переменных \(q^{0}_{1}, q^{0}_{2}, ..., P^{0}_{1}, P^{0}_{2}, ..., Q^{0}_{1}, Q^{0}_{2}, ...\), на котором формула (1) принимает значение "ложь", то есть
| $$ \exists x_{1} \exists x_{2} … \exists x_{n} C (q^{0}_{1}, q^{0}_{2}, ..., P^{0}_{1}, P^{0}_{2}, ..., Q^{0}_{1}, Q^{0}_{2}, ... ) =0$$ | (3) |
Рассмотрим отрицание формулы (3). $$\overline { \exists x_{1} \exists x_{2} … \exists x_{n} C (q^{0}_{1}, q^{0}_{2}, ..., P^{0}_{1}, P^{0}_{2}, ..., Q^{0}_{1}, Q^{0}_{2}, ... )} \equiv$$ $$\equiv \forall x_{1} \forall x_{2} … \forall x_{n} \overline {C (q^{0}_{1}, q^{0}_{2}, ..., P^{0}_{1}, P^{0}_{2}, ..., Q^{0}_{1}, Q^{0}_{2}, ... )} =1$$
Отсюда следует, что формула
| $$C \overline { (q^{0}_{1}, q^{0}_{2}, ..., P^{0}_{1}, P^{0}_{2}, ..., Q^{0}_{1}, Q^{0}_{2}, ... ) }$$ | (4) |
тождественно истинна, независимо от выбора предметных переменных из области \(M\).
Возьмем из области \(M\) какой -нибудь элемент \(x_{0}\) и подставим ero в формулу (4) вместо всех предметных переменных. Тогда $$С \overline { (q^{0}_{1}, q^{0}_{2}, ..., P^{0}_{1} (x_{0}), P^{0}_{2} (x_{0}), ..., Q^{0}_{1}(x_{0}, x_{0}), Q^{0}_{2}(x_{0}, x_{0}), ... )} =1$$
И, значит, $$C (q^{0}_{1}, q^{0}_{2}, ..., P^{0}_{1} (x_{0}), P^{0}_{2} (x_{0}), ..., Q^{0}_{1}(x_{0}, x_{0}), Q^{0}_{2}(x_{0}, x_{0}), ... ) =0,$$
а это противоречит тождественной истинности формулы (2).
Теорема 2. Если замкнутая формула логики предикатов в предваренной нормальной форме содержит толь ко кванторы общности, число которых равно \(n\), и тождественно истинна на всяком множестве, содержащем не более, чем \(n\) элементов, то она общезначима.
Доказательство. Пусть формула логики предикатов в предваренной нормальной форме имеет вид:
| $$A \equiv \forall x_{1} \forall x_{2} … \forall x_{n} C (q_{1}, q_{2}, ..., P_{1}, P_{2}, ..., Q_{1}, Q_{2}, …) ,$$ | (5) |
Предположим, что формула (5) не является общезна чимой. Тогда существует область \(M_{1}\) с числом элементов, большим \(n\), на которой она не является тождественно истинной, то есть существует набор значений переменных \(q^{0}_{1}, q^{0}_{2}, ..., P^{0}_{1}, P^{0}_{2}, ..., Q^{0}_{1}, Q^{0}_{2}, ...\), на котором формула
| $$ \forall x_{1} \forall x_{2} … \forall x_{n} C (q^{0}_{1}, q^{0}_{2}, ..., P^{0}_{1}, P^{0}_{2}, ..., Q^{0}_{1}, Q^{0}_{2}, ...)$$ | (6) |
Таким образом, существует набор предметных переменных \(x^{0}_{1}, x^{0}_{2}, ..., x^{0}_{n}\) из области \(M_{1}\), при котором формула \( \overline { C (q^{0}_{1}, q^{0}_{2}, ..., P^{0}_{1}, P^{0}_{2}, ..., Q^{0}_{1}, Q^{0}_{2}, ...)} \) имеет значение 1, а формула \( C (q^{0}_{1}, q^{0}_{2}, ..., P^{0}_{1}, P^{0}_{2}, ..., Q^{0}_{1}, Q^{0}_{2}, ...) \) имеет значение 0.
Значит, из области \(M_{1}\) можно выделить область \(M_{2}\), содержащую не более \(n\) элементов, на которой данная формула не является тождественно истинной, а это противоречит условию теоремы.
