Использование равносильностей для упрощения формул

Равносильности 1-26 (см. табл.9.1) зачастую используются также для преобразования формул к равносильным им формулам нужного вида.

В качестве примеров рассмотрим преобразование формул алгебры предикатов к так называемым приведённым и предваренным формулам.

Определение 9.12. Формула алгебры предикатов называется приведенной, если в ней не используется операция «®», а отрицание или не используется совсем, или относится лишь к элементарным формулам.

Определение 9.13. Предваренной (или нормальной, или пренексной) формулой алгебры предикатов называется любая формула вида

, (9.4)

где δ₁, …, δ_k — кванторы, а А — приведенная формула, не содержащая кванторов.

Теорема 9.14. Для всякой формулы А алгебры предикатов существует равносильная ей приведенная формула. Докажем теорему индукцией по рангу r(А) формулы А. Если r(А) = 0, то утверждение верно. Пусть r(А) > 0. Тогда по определению формулы А совпадает с одной из формул вида

A₁ & A₂, A₁ Ú A₂, δxA₁, A₁ ® A₂, . (9.5)

Доказательство. По предположению индукции формулы А₁, А₂ равносильны приведенным формулам. Заменив ими в (9.5) формулы А₁, А₂, мы в трех первых случаях сразу получим приведенные формулы. А так как A₁ ® A₂ º`А<sub>1</sub> Ú А<sub>2</sub> (см. п.24 табл.9.1), то остается рассмотреть случай, когда . Если А<sub>1</sub> элементарна, то А — приведенная формула. Если же А<sub>1</sub> не элементарна, то она может иметь вид B<sub>1</sub> & B<sub>2</sub>, B<sub>1</sub> Ú B<sub>2</sub>, δxB<sub>1</sub>, B<sub>1</sub> ® B<sub>2</sub>,`B₁, где r(B_i) < r(A) –2. Тогда по свойствам равносильности 11, 12, 20, 21, 24, 14 (см. табл.9.1) формула А равносильна одной из формул:

B₁ Ú B₂, `B₁ & B₂, δ*xB₁, B₁ ® B₂, B₁. (9.6)

Остается применить предположение индукции к формулам B₁,`B<sub>1</sub>,`B₂ и заменить их в (9.6) приведенными формулами.

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

Доказательство. По теореме 9.14, не теряя общности, можно считать, что А — приведенная формула. Снова применим индукцию по r(А). Для r(А) = 0 утверждение верно. Пусть r(А) > 0. Тогда формула А может иметь вид

1) A₁ & A₂,

2) A₁ Ú A₂,

3) δxA₁,

4)`A_1.

Причем в случае 4 А₁ — элементарная формула и для нее утверждение теоремы верно. Рассмотрим случаи 1-3.

1. A = A₁ & A₂. По предположению индукции А_i равносильна предваренной формуле B_i, i = 1, 2, причем согласно равносильности 26 (см. табл.9.1) связанные переменные любой из формул В₁, В₂ можно считать отличными от всех переменных другой формулы. Таким образом, A = B₁ & B₂, где можно считать B₁ = δ₁x₁…δ_kx_kC₁, B₂ = δ_{k + 1}x_{k + 1}…δ_nx_nC₂, где x₁, …, x_k не входят в С₂, а x_{k + 1}, …, x_n не входят в С₁, и формулы С₁, С₂ не содержат кванторов. Отсюда, используя равносильность 25, получим

A º δ₁x₁…δ_kx_kδ_{k + 1}x_{k + 1} … δ_nx_n(C₁ & C₂).

2. Для A = A₁ Ú A₂, рассуждения двойственны.

3. A = δxA₁. По предположению индукции А₁ равносильна приведенной формуле A º δ₁x₁…δ_kx_kB, причем можно считать, что x ¹ x₁, …, x_k. Возможны два случая:

а) В содержит свободные вхождения х. Тогда А равносильна предваренной формуле δxδ₁x₁…δ_kx_kB;

б) В не содержит свободных вхождений х. Тогда из равносильности 4 (см. табл.9.1) следует, что значения формулы А₁ не зависят от значений переменной х, а потому А º А₁ и теорема доказана.