Математическая логика и теория алгоритмов. Для изучающих компьютерные науки

Для завершения доказательства теоремы осталось доказать, что имплика­ ции, обратные к (2.29) и (2.30), точнее, формулы Vx(B(x) vC(x))^(VxB(x)) vVxC(x), (2.31) (ЗхВ(х))&ВхС(х) ^Вх(В(х)&С(х)) (2.32) не являются логически общезначимыми при любых формулах В(х) и С(х). Чтобы доказать это, достаточно для каждой из импликаций (2.31) и (2.32) ука­ зать формулы В(х) и С(х) и для них привести хотя бы одну интерпретацию, где формулы (2.31) и (2.32) не истинны. Пусть для формулы (2.31) область интерпретации есть множество целых чисел, формуле В(х) соответствует предикат "х - четное число", а формуле С(х) -предикат "х - нечетное число". Тогда, считая, что нуль четное число, получим истинное высказывание \/х{х - четное число или х - нечетное число), в то время, как высказывание [ Ь±(х-нечетное число ) или \/х{х - четное число)] ложно. По­ этому формула (2.31) в приведенной интерпретации ложна, следовательно, не логически общезначима. Для формулы (2.32) можно взять ту же интерпретацию, что и для формулы (2.31). При этом легко видеть, что формула (2.32) ложна, следовательно, не ло­ гически общезначима. Теорема доказана. Правила вынесения кванторов за скобки, когда задана импликация некото- эых формул, следуют из теоремы. Теорема 2.7. Пусть А - произвольная формула, не содержащая свободных вхождений переменой х, а В(х)- произвольная формула, возможно, и со­ держащая свободные вхождениях. Тогда ЗхВ(х)^А ~ Vx(B(x)^A); (2.33) A^VxB(x) ~ Vx(A^B(x)), (2.34) VxB(x)^A ~ Зх(В(х)^А), (2.35) А^ЗхВ(х) ~ Бх(А^В(х)). (2.36) Доказательство. Докажем соотношение (2.33). Рассмотрим формулу: Vx(B(x)^A). (2.37) Вместо формулы (2.37) введем равносильную формулу Vx( 1В(х) vA), ко­ торая по (2.24) равносильна формуле (VxlB(x))vA, которая равносильна фор­ муле lVx~B(x)^A. Используя соотношение (2.15) между кванторами, получим формулу (ВхВ(х))^А. Таким образом, формула Vx(B(x) ^А) равносильна фор­ муле (ЗхВ(х)) =^А, что и требовалось доказать. Доказательство равносильностей (2.34)-(2.36) можно провести примерно так же, как доказывалось соотношение (2.33). 47