Определение 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 1 xA (x) & Q 2 xB (x) º Q 1 xQ 2 z (A (x)& B (z)) (2.20)
Q 1 xA (x) Ú Q 2 xB (x) º Q 1 xQ 2 z (A (x)Ú B (z)) (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 1 x есть " x, а Q 2 x есть $ x. Получим
" xD (x) & $ xF (x) º " x $ z (D (x) & F (z Рассмотрим формулу 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) – нормальная формула, равносильная исходной.
|