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

§ 9. Правила вынесения кванторов за скобки. Предваренная Выясним, каким образом выносятся кванторы за скобки, при этом получим и правила внесения кванторов под скобки. Теорема 2.6. Пусть А обозначает формулу, не имеющую свободных вхожде­ ний переменной х; В(х) и С(х) -произвольные формулы , возможно, и содер- жаш,ие свободные вхождениях. Тогда: А& VxB(x) ~ Vx(A&B(x)), (2.23) AvVxB(x) ~ Vx(AvB(x)), (2.24) А&ЗхВ(х) ~ Зх(А&В(х)), (2.25) Av3xB(x) ~БХ(АУВ(Х)), (2.26) (VxB(x))&VxC(x) ~ Vx(B(x)&C(x)), (2.27) (3xB(x))v3xC(x) ~ 3x(B(x)vC(x)). (2.28) Кроме того, формулы (VxB(x)) vVxC(x)^Vx(B(x) vC(x)), (2.29) Зх(В(х)&С(х)) =^(ЗхВ(х))&3xC(x) (2.30) логически обш,езначимы, а импликации, обратные к (2.29) и (2.30), уже не являются логически обш,езначимыми (при любых формулах В(х) и С(х)). Доказательство. Докажем соотношение (2.23). Для этого возьмем произ­ вольную, но фиксированную интерпретацию формулы Л& VxB{x). Если свободных переменных в формуле А& VxB(x) нет, то в интерпретации получим высказывание. Пусть это высказывание истинно, тогда истинны А и В{х) при любом значении х из области интерпретации Ж Поэтому будет истин­ но высказывание Vx(A&B(x)). Аналогичным образом из истинности Vx(A&B(x)) следует истинность Л cfe VxB(x). Пусть формула VxB(x) имеет свободные переменные, для определенно­ сти пусть это будут 3^7, у2, ..,Уп- Придадим им произвольные значения из на­ пример, bi, b2,...,bn соответственно. Положим, что при указанных значениях у2, ...,Уп A&VxB(x) принимает значение истины. Последнее означает, что для yi=bi, у2=Ь2,---,Уп= Ьп истинны А и В(х) при любом X из М, следователь­ но, для выбранных значений свободных переменных истинно высказывание Vx(A&B(x)). Очевидно, верно и обратное. Соотношение (2.23) доказано. Доказательство равносильностей (2.24) - (2.28) и логической обш,езначи- мости формул (2.29) и (2.30) можно провести аналогично доказательству рав­ носильности (2.23), т.е. фиксированием интерпретации. 46