Математическая логика и теория алгоритмов. Стенюшкина В.А. - 35 стр.

      12 Классификация формул логики предикатов

      12.1 Тавтология. Противоречие. Выполнимая формула

      Формула ЛП называется тождественно истинной, или тавтологией, если
она истинна в любой интерпретации.
      Пример - Формула (∃x1 Р(x1) →∀x2 Р(x2)) не является тавтологией.
      Формула ЛП называется тождественно ложной, или противоречием, если
она ложна в любой интерпретации.
      Формула ЛП называется выполнимой, если она истинна хотя бы в одной
интерпретации.

      12.2 Логическое следствие. Логическая эквивалентность

      Формула ЛП G называется логическим следствием формулы F, если G
истинна во всех интерпретациях, в которых F истинна. Запись: F→ G.
      Имеют место логические следования:
      7)∃x(F(x)∧G(x)) ∃xF(x)∧∃xG(x), ∀x F(x)∨∀ ∃xG(x)⇒∀x(F(x)∨G(x)) ;
      8)∀ xF(x) → H ⇒ ∃ x(F(x) → H), ∃ xF(x) → H ⇒ ∀ x(F(x) → H),
где формула Н не содержит вхождений переменной х.
      Формулы F и G называются логически эквивалентными, если они явля-
ются логическими следствиями друг друга. Запись: F⇔ G.

      12.3 Подстановка

       Пусть F(x) – формула, t – терм. Положим по определению F(t):= F(…x …)
 t//xТогда имеют место следующие теоремы.
       Теорема 12.1 Формула ∀xF(x)→F(t),где t – терм, свободный для перемен
ной x в формуле F, есть тавтология.
       Теорема 12.2 Формула F(t) →∃ x F(x), где t – терм, свободный для пере-
менной x в формуле F, есть тавтология.

      12.4 Предваренная нормальная форма

      В логике высказываний были введены нормальные формы – конъюнктив-
ная и дизъюнктивная. В логике предикатов первого порядка также имеется но-
рмальная форма, называемая предваренной нормальной формой (ПНФ).
      Формула ЛП F называется находящейся в ПНФ, если она имеет вид:

                               Q1 x1 … Qn xn F0 ,                      (12.1)

     где Qi, i,= 1..n – один из кванторов (∀,∃),
     x i≠ xj, если i≠j,