Математическая логика и теория алгоритмов

же из определения кванторов получаем, что там, где истинно \/х\/уА, истинно и V>'Vx/4, и. наоборот. В силу произвольности интерпрео-ации следует, что yx'iyA ~ V>'Vx4. (2.16) Точно та1слсе получаем что ЗхЗуА ~ ЗхЗуА. (2-17) Таким образом, при перемене мест стоящих рядом одноимен­ ных кванторов получаем равносильные формулы. Итак, одноименные кванторы, стоящие рядом, можно переставлять местами. Известно, что формулы- А и В равносильны тогда и только тогда, когда A s B является логически общезначимой формулой (тео­ рема 2.2). Тогда из (2,16) и (2.17) получаем, что формулы \/х\/уАш\/уУхА и ЗхЗуА^ЗуЗхА являются логически общезначимыми. Разноименные кванторы, оказывается, можно переставлять не в каждой формуле. Докажем теорему. Теорема 2.5. Для каждой формулы А и любых предметных переменныхх к у формула Зх\/уА =>Vy3xA (2.18) логически общезначима, а формула \/уЗхА^Зх\/уА (2.19) не является логически общезначимой (при любой формуле yd). Доказательство. Для доказательства логической общезначимо­ сти формулы (2.18) фиксируем произвольную интерпретацию форму­ лы Л, и из определений 1сванторов сразу получаем, что формула (2.18) истинна. Таким образом, в любой интерпретации формула (2.18) истинна, следовательно, она логически общезначима. Чтобы доказать, что формула (2.19) не является логически об­ щезначимой (при любой формуле А), достаточно привести пример формулы А и интерпретации для нее, где формула (2.19) неистинна. 67