Приведенные и нормальные формулы
Определение 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.
Q1xA(x) & Q2xB(x) º Q1xQ2z(A(x)&B(z (2.20)
Q1xA(x) Ú Q2xB(x) º Q1xQ2z(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), имея в виду, что Q1x есть "x, а Q2x есть $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) – нормальная формула, равносильная исходной.