Общезначимость

Формула (исчисления предикатов) общезначима, если она истинна в любой интерпретации.

Теорема 4.14. Формула x А(х) A(t), где терм t свободен для переменной х в формуле А, обще­значима.

Доказательство. Рассмотрим произвольную интерпретацию I, произвольную последовательность значений из об­ласти интерпретации s и соответствующую функцию . Пусть (t_i) = a_i и пусть t(x) — некото­рый терм, а t' = (... х...){t ₁ / /х}. Тогда (t) = (t'), где s ₁ имеет значение а ₁ на месте х.

Пусть А(х) — формула, а терм t свободен для х в А. Положим

A(t)=A(...x...){t//x}.

Имеем: (A(t)) = И (A(x)) = И, где s ₁ имеет значение (t) на месте х. Если ( x А(х)) = И и терм t свободен для x в А, то (A(t)) = И. Следовательно, формула x А(х) A(t) выполнена на всех последовательностях произвольной интерпретации.

Можно также показать, что формула A(t) x A(x), где терм t свободен для переменной x в формуле А, общезначима.

О полноте чистого исчисления предикатов

Существуют с ледующие две метатеоремы, которые устанавливают свойства исчисления предикатов, аналогичные тем, ко­торые установлены для исчисления высказываний в подразделе 4.3. Теоремы приводим без до­казательств.

Теорема 4.15. Всякая теорема чистого исчисления предикатов первого порядка общезначима.

Теорема 4.16. Всякая общезначимая формула является теоремой чистого исчисления предикатов первого порядка.