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

всеобщности (общности). Предикат ∀xi A( x1 , x2 ,..., xn ) является ( n − 1)-местным.
Он зависит от переменных x1 , x2 ,..., xi −1, xi +1 ,..., xn . Если дан одноместный предикат
P(x) , то утверждение ∀xP(x) представляет собой нульместный предикат, то есть
истинное или ложное высказывание.

      Пример. На множестве X = R дан предикат A( x) =" x ≤ 2" . Высказывание
∀x( x ≤ 2) ложно.

     Пусть дан n -местный предикат A( x1 , x 2 ,..., x n ) на множестве X , означающий,
что для набора ( x1 , x2 ,..., xn ) выполнено свойство A , и пусть xi – одна из
переменных. Тогда запись ∃xi A( x1 , x2 ,..., xn ) означает, что существует значение
переменной xi , такое, что выполняется свойство A . Символ ∃ называется
квантором существования. Предикат ∃xi A( x1 , x2 ,..., xn ) является ( n − 1 )-местным.
Если дан одноместный предикат P(x) , то утверждение ∃xP(x) представляет собой
нульместный предикат, то есть истинное или ложное высказывание.

       Пример. На множестве X = R дан предикат A( x) =" x ≤ 2" . Высказывание
∃x( x ≤ 2) истинно.

      Отметим, что запись ∀xA ( ∃xA ) не подразумевает, что в формуле A есть
переменная x .
      Пусть дана запись ∀xA (или ∃xA ). Переменная x называется переменной в
кванторе, а A – областью действия квантора.
      Имеют место эквивалентности:
  ∃xi A = ¬∀xi ¬A .       ∀xi A = ¬∃xi ¬A .
  ¬∃xi A = ∀xi ¬A .       ¬∀xi A = ∃xi ¬A .
      Отметим, что список переменных в предикате A мы будем указывать не
всегда.

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

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



                                                                 29