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

Равносильности 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) следует, что значения формулы А ₁ не зависят от значений переменной х, а потому А º А ₁ и теорема доказана.

Дата добавления: 2014-12-29