Логика булевых функций

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


Определение 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).