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

в § 2 установлено, что квантор общности является обобщением конъ­ юнкции, а квантор существования - дизъюнкции и для «-элементных областей интерпретации имеют место соотношения (2.7) и (2.8): VxP(x) равносильно P{a\)8iP{ai)8i...&P{a,^, ЭлгДх) равносильно /'(ai)v?(a (2 )v...v?(a „). Очевидно, высказывания равносильны тогда и только тогда, когда равносильны отрицания этих высказываний, поэтому первое из этих соотношений эквивалентно следую14ему: УхР{х) ~l(P(a,)&P (fl2 )&...&P(fl „))~lP(fl,)vlP (fl2 )v...v 1 Р{а,). Правая часть полученного соотношения есть не что иное, как запись высказывания Эх] Р(х). Таким образом, для «-элементных областей интерпретации имеем: lVxP(;c) ~ 3;с1 Р{х). (2.9) Аналогично получим: . 1 ЗхР(х) ~ 1 (P(a,)vP (a2 )v...vP(a „)) ~ 1 Р(д,)&1 Р(а2 >&.,.&1 Р(а„), следовательно, для и-элементных областей интерпретации имеет место: 13xP(jc)~Vxl Р(х). (2.10) Соотношения (2,9) и (2.10) показывают, что при перенесении отрицания через кванторы последние меняются на двойственнью. По­ кажем, что эти правила имеют место для указанных формул, но уже без ограничения конечности областей интерпретации. Рассмотрим формулу IVxP(x). Возьмем произвольную (но фик­ сированную) интерпретацию. В каждой интерпретации эта формула означает некоторое высказывание (так как не имеет свободных переменных). 64