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

что при указанных значениях уи yj, формула ASi\lxB{x) принима­ ет значение истины. Последнее означает, что для y\=b\, Уг-Ьг,...,у„= Ь„ истинны А и В(х) при любом jc из М, следовательно, для выбранных значений свободных переменных истинно высказывание \/х(А&В(х)). Очевидно, верно и обратное. Соотношение (2.23) доказано. Доказательство равносильностей (2.24)-{2.28) и логической общезначимости формул (2.29) и (2.30) можно провести аналогично доказательству равносильности (2.23), т.е. фиксированием интерпре­ тации. Для завершения доказательства теоремы осталось доказать, что импликации, обратные к (2.29) и (2.30), точнее, формулы не являются логически общезначимыми при любых формулах В{х) и С{х). Чтобы доказать это, достаточно для каждой из импликаций (2.31) и (2.32) указать формулы В(х) и С{х) и для них привести хотя бы одну интерпретацию, где формулы (2.31) и (2.32) не истинны, Пусть для формулы (2.31) область интерпретации есть множество целых чисел, формуле В(х) соответствует предикат "х - четное число", а формуле С(х) — предикат "х — нечетное число". Тогда, считая, что нуль четно, получим истинное высказывание V;c(x- четное число или х - нечетное число), в то время, как высказывание [Vx(x - нечетное число ) или Vx(x - четное число)] ложно. Поэтому формула (2.31) в приведенной интерпретации ложна, следовательно, не логически общезначима. Для формулы (2,32) можно взять ту же интерпретацию, что и для формулы (2.31). При этом легко видеть, что формула (2.32) ложна, следо­ вательно, не логически общезначима. Теорема доказана. \fx(B(x)vC(x))z^{yxB(x))vyxC(x), {ЗхВ(хУ)&ЗхС(х)=>Зх{В(х)&С(хУ) (2.31) (2.32) 72