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

     Покажем, что это высказывание истинно. Возможны два случая.
1. ∀xi A( x10 , x 20 ,..., xi ,..., x n0 ) = 0 , следовательно B0 = 1 .
2. ∀xi A( x10 , x20 ,..., xi ,..., xn0 ) = 1 .
   Соотношение выполнено при любых значениях xi , следовательно, и при
   значении xi = xi0 . При подстановке этого значения получаем:
   A( x10 , x20 ,..., xi0 ,..., xn0 ) = 1 .
   Следовательно, по свойству импликации получаем, что B0 = 1 , что и требовалось
   доказать.

     Теорема. Пусть A( x1 , x2 ,..., xn ) – n -местный предикат, xi – переменная в
предикате.   Тогда    предикат            A( x1 , x2 ,..., xn ) → ∃xi A( x1 , x2 ,..., xn ) является
тождественно истинным.
     Доказательство аналогично доказательству предыдущей теоремы.

     Предикат называется выполнимым,                         если   при         некоторых   значениях
переменных он принимает значение 1.

                                                                    (
     Пример. Найти значение высказывания ∃x∀y∃z xz = y 3 . Предикат xz = y 3      )
определен на множестве X = N .
                                     (        )
     Решение. Пусть ∃x∀y∃z xz = y 3 = 1 . Эквивалентность имеет место тогда и
                                                         (          )
только тогда, когда для некоторого x0 ∀y∃z x0 z = y 3 = 1 . Это означает, что для
некоторого      x0   предикат            (
                                     ∃z x0 z = y 3   )   является тождественно истинным
относительно y , то есть для некоторого x0 и для произвольного y0 ∃z x0 z = y 0 = 1 .  (        3
                                                                                                    )
Последнее равносильно тому, что предикат x0 z = y 0            (        3
                                                         выполним. Предикат )
действительно является выполнимым, поскольку он определен на множестве
натуральных чисел. Таким образом, поскольку все переходы были равносильными,
исходное высказывание истинно.

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

     Справедливы эквивалентности:
∀x∀yP( x, y ) = ∀y∀xP( x, y ) , ∃x∃yP( x, y ) = ∃y∃xP( x, y ) .
     Разноименные кванторы можно переставлять только следующим образом:
∃x∀yP( x, y ) → ∀y∃xP( x, y ) , ∃y∀xP( x, y ) → ∀x∃yP( x, y ) .
     Обратные формулы неверны.



                                                  30