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

Теорема 2,6. Пусть Л обозначает формулу, не имеющую свободных вхождений переменной х, В{х) и С{х) - произвольные формулы, возможно, и содержащие свободные вхождения х. Тогда: логически общезначимы, а импликации, обратные к (2.29) и (2.30), уже не являются логически общезначимыми (при любых форму­ лах В(х) и С{х)). Доказательство. Докажем соотношение (2.23). Для этого возь­ мем произвольную, но фиксированную интерпретацию формулы А81УхВ(х). Если свободных переменных в формуле ^&V^:JS(x) нет, то в ин­ терпретации получим высказывание. Пусть это высказывание истин­ но, тогда истинны А и В(х) при любом значении х из области интер­ претации М. Поэтому будет истинно высказывание V JC (/1&JS( JC ). Аналогичным образом из истинности V^:(^4&i?(jc)) следует истинность А&\/хВ(х). Пусть формула А&\/хВ(х) имеет свободные переменные, для определенности пусть это будут >1, >2, Придадим им произволь­ ные значения из М, например, bi, Ь2,-.,Ъп соответственно. Положим, А8сУхВ{х) ~ \/х{А&В{х)), Л vVxS(x) ~ Vx(AvB(x)}, А&ЗхВ(х) ~ Зх(А&В(х)), Av3xB(x) ~ 3x(AvB(x)X (VxB(x))&VxC(x) ~ Ух{В(х)& С(х)), (3xB(x))v3xC(x) ~ 3x(i?(jc)vC(jc)). (2.23) (2.24) (2.25) (2.26) (2.27) (2.28) Кроме того, формулы (VxB(x))vVxC(x)=>Vx(B(x)vC(x)), Зх(В(х)&С(х))=>(ЭхВ(х))&ЭхС(х) (2.29) (2.30) 71