Математическая логика и теория алгоритмов. Сергиевская И.М. - 34 стр.

     Пример. На множестве          X =R      рассмотрим формулу ∀xA( x, y ) .
Интерпретируем эту формулу следующим образом: A =" ≤" . Тогда мы получим
предикат ∀x( x ≤ y ) .
     Рассмотрим теперь формулу ∀x∃yA( x, y ) . При интерпретации она
превращается в истинное высказывание ∀x∃y ( x ≤ y ) .

     Определение. Интерпретация называется моделью формальной теории (или
некоторого множества формул), если все формулы формальной теории (или
множества формул) истинны в данной интерпретации.

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

      Определение. Формулы A и B называются логически эквивалентными
тогда и только тогда, когда формула A ↔ B логически общезначима.

         Справедлива теорема, аналогичная теореме из логики высказываний.

     Теорема. Отношение логической эквивалентности является отношением
эквивалентности.

     Определение. Говорят, что формула A логически влечет формулу B (из
формулы A логически следует формула B ), если формула A → B является
логически общезначимой.

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

     Определение. Формула                        называется противоречивой, если она ложна в
любой интерпретации.

           Теорема. Пусть A – формула, xi – переменная в формуле A , терм t свободен
для переменной xi в формуле A . Тогда формула ∀xi A( xi ) → A(t ) общезначима.
           Доказательство. Пусть имеется некоторая интерпретация исходной формулы,
то есть множество X и A( xi ) – предикат на X . Покажем, что ∀xi A( xi ) → A(t ) –
тождественно истинный предикат. Возьмем произвольный набор значений
( x10 , x20 ,..., xi0 ,..., xn0 ) переменных x1 , x2 ,..., xi ,..., xn . Подставим этот набор в предикат.
Получим высказывание:
∀xi A( x10 , x20 ,..., xi ,..., xn0 ) → A(t )( x10 , x 20 ,..., xi0 ,..., xn0 ) = B0 .
           Покажем, что это высказывание истинно. Возможны два случая.
1. ∀xi A( x10 , x 20 ,..., xi ,..., x n0 ) = 0 , следовательно B0 = 1 .
2. ∀xi A( x10 , x20 ,..., xi ,..., xn0 ) = 1 .


                                                        39