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

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

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

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

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

, (9.4)

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

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

A1 & A2, A1 Ú A2, δXA1, A1 ® A2, . (9.5)

Доказательство. По предположению индукции формулы А1, А2 равносильны приведенным формулам. Заменив ими в (9.5) формулы А1, А2, мы в трех первых случаях сразу получим приведенные формулы. А так как A1 ® A2 º`А1 Ú А2 (см. п.24 табл.9.1), то остается рассмотреть случай, когда . Если А1 элементарна, то А — приведенная формула. Если же А1 не элементарна, то она может иметь вид B1 & B2, B1 Ú B2, δXB1, B1 ® B2,`B1, где R(BI) < R(A) –2. Тогда по свойствам равносильности 11, 12, 20, 21, 24, 14 (см. табл.9.1) формула А равносильна одной из формул:

B1 Ú B2, `B1 & B2, δ*XB1, B1 ® B2, B1. (9.6)

Остается применить предположение индукции к формулам B1,`B1,`B2 и заменить их в (9.6) приведенными формулами.

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

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

1) A1 & A2,

2) A1 Ú A2,

3) δXA1,

4)`A1.

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

1. A = A1 & A2. По предположению индукции АI равносильна предваренной формуле BI, I = 1, 2, причем согласно равносильности 26 (см. табл.9.1) связанные переменные любой из формул В1, В2 можно считать отличными от всех переменных другой формулы. Таким образом, A = B1 & B2, где можно считать B1 = δ1X1…δKXKC1, B2 = δK + 1XK + 1…δNXNC2, где X1, …, XK не входят в С2, а XK + 1, …, XN не входят в С1, и формулы С1, С2 не содержат кванторов. Отсюда, используя равносильность 25, получим

A º δ1X1…δKXKδK + 1XK + 1 … δNXN(C1 & C2).

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

3. A = δXA1. По предположению индукции А1 равносильна приведенной формуле A º δ1X1…δKXKB, причем можно считать, что X ¹ X1, …, XK. Возможны два случая:

А) В содержит свободные вхождения Х. Тогда А равносильна предваренной формуле δXδ1X1…δKXKB;

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

< Предыдущая		Следующая >