Зарипова, Э.Р. Дискретная математика Часть II. Математическая логика

61 Для приведения формулы исчисления предикатов к предваренной нормальной форме рассмотрим ряд эквивалентностей, содержащих кванторы. Пусть F - формула, содержащая свободную переменную x (обозначим этот факт как F [ x ]). Пусть G - формула, не содержащая переменную x . Пусть Q есть или  или  . Тогда имеют место следующие эквивалентности: ( )( [ ] ) ( ) [ ] Qx F x G Qx F x G    (12.1) ( )( [ ] ) ( ) [ ] Qx F x G Qx F x G    (12.2) ( ) [ ] ( ) [ ] x F x x F x    (12.3) ( ) [ ] ( ) [ ] x F x x F x    (12.4) Эквивалентности (12.1) и (12.2) очевидны, т.к. G не содержит x и, следовательно, может быть внесена в область действия квантора Q . Докажем эквивалентности (12.3) и (12.4). Пусть I - произвольная интерпретация с областью D . Если ( ) [ ] x F x  истинна в I , то (  x)F [ x ] ложна в I . Это означает, что существует такой элемент e в D , что F [ e ] ложна, т.е. [ ] F e истинна в I . Следовательно, ( ) [ ] x F x  истинна в I . С другой стороны, если ( ) [ ] x F x  ложна в I , то (  x)F [ x ] истинна в I . Это означает, что F [ x ] истинна для каждого элемента x в D , т.е. [ ] F x ложна для каждого элемента x в D . Следовательно, ( ) [ ] x F x  ложна в I . Т.к. ( ) [ ] x F x  и ( ) [ ] x F x  всегда принимают одно и то же истинностное значение при произвольной интерпретации, то по определению ( ) [ ] ( ) [ ] x F x x F x    . Таким образом (12.3) доказано. Аналогично можно доказать и (12.4). Предположим далее, что F [ x ] и H [ x ] - две формулы, содержащие свободную переменную x . Нетрудно доказать, что (  x)F [ x ]  (  x)H [ x ] = (  x)(F [ x ]  H [ x ] ), (12.5) (  x)F [ x ]  (  x)H [ x ] = (  x)(F [ x ]  H [ x ] ), (12.6)