Приведенные и нормальные формулы

Определение 2.5. Формулы, в которых из логических символов имеются только символы &, Ú и Ø, причем символ Ø встречается лишь перед символами предикатов, называются приведенными формулами.

Пример 2.12.

1. A (x)& B (x, y).

2. " xA (x) Ú $ x Ø B (x, y).

3. Ø(A (x)& B (x, y)).

4. " xA (x) É $ x Ø B (x, y).

5. Ø(" xA (x) É $ x Ø B (x, y)).

Первые две формулы в соответствии с определением являются приведенными, остальные не являются приведенными. В третьей формуле знак отрицания стоит перед формулой, а не перед символами предикатов. В четвертой формуле используется недопустимый для приведенной формулы символ импликации É. В пятой формуле знак отрицания стоит перед формулой и используется недопустимый для приведенной формулы символ импликации.

Теорема 2.1. Для каждой формулы существует равносильная ей приведенная формула, причем множества свободных и связанных переменных этих формул совпадают.

Действительно, пользуясь равносильностями логики высказываний, можно получить формулу, содержащую только символы &, Ú и Ø. Применяя затем правило переноса квантора через знак отрицания, можно получить равносильную приведенную формулу. Такая приведенная формула называется приведенной формулой данной формулы. Строгое доказательство теоремы 2.1 содержится, например, в [6].

Пример 2.13.

Рассмотрим третью, четвертую и пятую формулы примера 2.12 и получим для них приведенные формулы.

Для третьей формулы по закону де Моргана:

Ø (A (x)& B (x, y)) º Ø A (x) Ú Ø B (x, y).

Для четвертой формулы:

" xA (x) É $ x Ø B (x, y) º Ø" xA (x) Ú $ x Ø B (x, y) º $ x Ø A (x) Ú $ x Ø B (x, y).

Для пятой формулы:

Ø(" xA (x) É $ x Ø B (x, y)) º Ø($ x Ø A (x) Ú $ x Ø B (x, y)) º Ø($ x Ø A (x)) & Ø($ x Ø B (x, y)) º " xA (x) & " xB (x, y).

Определение 2.6. Приведенная формула называется нормальной, если она не содержит символов кванторов или все символы кванторов стоят впереди.

Пример 2.14.

1. " x $ y (Ø A (x) Ú B (x, y)) – нормальная формула.

2. " x (Ø A (x)) & $ yB (x, y) – приведенная формула, не являющаяся нормальной.

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

Строгое доказательство теоремы 2.2 приведено в [6].

Алгоритм, позволяющий из приведенной формулы получить равносильную ей нормальную формулу, основан на правиле переименования связанных переменных и использовании равносильностей (2.3) – (2.8), (2.14) и (2.17).

Пусть Q – любой из кванторов ", $.

Воспользуемся равносильными преобразованиями (см.предыдущий раздел):

QxA (x) Ú B º Qx (A (x) Ú B) (2.18)

QxA (x) & B º Qx (A (x) & B). (2.19)

В тождествах (2.18), (2.19) формула B не зависит от x.

Q ₁ xA (x) & Q ₂ xB (x) º Q ₁ xQ ₂ z (A (x)& B (z (2.20)

Q ₁ xA (x) Ú Q ₂ xB (x) º Q ₁ xQ ₂ z (A (x)Ú B ((2.21)

Тождества (2.18) и (2.19) есть обобщенная запись равносильных преобразований (2.3) – (2.6), а тождества (2.20) и (2.21) обобщают равносильности (2.14) – (2.17).

Мы видим, что тождества (2.18) – (2.21) позволяют поместить кванторы впереди формулы, что и требуется для нормальной формулы.

Пример 2.15.

Найти равносильную нормальную формулу для приведенной формулы: " x $ yA (x, y) & $ x $ u (x, u).

В формуле $ yA (x, y) переменная y связана, поэтому $ yA (x, y) не зависит от y. Обозначим D (x) = $ yA (x, y).

В формуле $ uB (x, u) переменная u связана, поэтому $ uB (x, u) не зависит от u. Обозначим F (x) = $ uB (x, u).

Тогда

" x $ yA (x, y) & $ x $ uB (x, u) = " xD (x) & $ xF (x). (2.22)

Применим равносильность (2.20), имея в виду, что Q ₁ x есть " x, а Q ₂ x есть $ x. Получим

" xD (x) & $ xF (x) º " x $ z (D (x) & F (z)). (2.23)

Рассмотрим формулу D (x) & F (z) = $ yA (x, y) & $ uB (z, u). Применив два раза равносильность (2.19), получим

$ yA (x, y) & $ uB (z, u) º $ y (A (x, y) & $ uB (z, u)) º $ y $ u (A (x, y) & B (z, u)). (2.24)

Учитывая (2.21), (2.22), (2.23), получим окончательно

" x $ yA (x, y) & $ x $ uB (x, u) º " x $ z $ y $ u (A (x, y) & B (z, u)). (2.25)

В тождестве (2.25) в левой части – исходная формула, а в левой части ее нормальная формула.

Теорема 2.3. Для каждой формулы существует равносильная ей нормальная формула.

Теорема 2.3. является очевидным следствием теорем 2.1 и 2.2.

Пример 2.16.

Найти равносильную нормальную формулу для формулы: " x $ yA (x, y) É $ x $ uB (x, u).

1. Найдем вначале приведенную формулу, равносильную данной. Избавимся от символа É:

" x $ yA (x, y) É $ x $ u (x, u) º Ø(" x $ yA (x, y)) Ú $ x $ uB (x, u).

Применим равносильности (2.1) и (2.2) (перенос квантора через отрицание):

Ø(" x $ yA (x, y)) º $ x " y Ø A (x, y),

Следовательно,

" x $ yA (x, y) É $ x $ uB (x, u) º $ x " y Ø A (x, y) Ú $ x $ uB (x, u). (2.26)

Правая часть тождества (2.26) – приведенная формула, равносильная данной.

2. Найдем теперь нормальную формулу, равносильную приведенной формуле $ x " y Ø A (x, y) Ú $ x $ uB (x, u). Проделаем преобразование этой формулы, аналогично предыдущему примеру:

$ x " y Ø A (x, y) Ú $ x $ uB (x, u) º $ x " y Ø A (x, y) Ú $ z $ uB (z, u)

º " x $ z (" y Ø A (x, y) Ú $ uB (z, u)) º " x $ z " y $ u (Ø A (x, y) Ú B (z, u)). (2.27)

В правой части (2.27) – нормальная формула, равносильная исходной.