Алгоритмы распознавания общезначимости формул в частных случаях

    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)
    где, как и раньше, \(q_{1}, q_{2}, ...\) - логические переменные, \(P_{1}, P_{2}, ...\) - одноместные предикаты, \(Q_{1}, Q_{2}, ...\) - двухместные предикаты и так далее.
    Предположим, что формула (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)
принимает ложное значение. Отсюда: $$\overline { \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}, ...)} \equiv $$ $$\equiv \exists x_{1} \exists x_{2} … \exists x_{n} \overline { C (q^{0}_{1}, q^{0}_{2}, ..., P^{0}_{1}, P^{0}_{2}, ..., Q^{0}_{1}, Q^{0}_{2}, ...)} =1$$
    Таким образом, существует набор предметных переменных \(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\) элементов, на которой данная формула не является тождественно истинной, а это противоречит условию теоремы.


2012-11-10 • Просмотров [ 1461 ]