Дискретная математика. Элементы теории задачи и упражнения. Часть 2. Булгакова И.Н - 63 стр.

                                            109
Операция замыкания. Основные замкнутые классы.
__________________________________________________________________________________________
      Из определений следует, что каждый тождественно истинный преди-
кат является выполнимым, но не является опровержимым, тогда как каж-
дый тождественно ложный предикат является опровержимым, но не явля-
ется выполнимым. Выполнимый предикат не обязательно является тожде-
ственно истинным. Опровержимый предикат не обязательно является тож-
дественно ложным.
      Заметим, что отношение равносильности двух предикатов является
отношением эквивалентности. Переход от предиката P ( x ) к равносильно-
му ему предикату Q( x ) называется равносильным преобразованием пер-
вого.
      Уравнения и системы уравнений, неравенства и системы неравенств,
прочие математические объекты представляют собой предикаты. При их
решении мы проделываем равносильные преобразования над ними, целью
которых является поиск множества истинности данного исходного преди-
ката.
      Имеет место утверждение:
      Два предиката, имеющие одну область определения, равносильны
тогда и только тогда, когда один из них является следствием другого:
              P ⇔ Q тогда и только тогда, когда P ⇒ Q и Q ⇒ P .
  Так как предикаты могут принимать два значения 1 или 0, то к ним при-

  менимы все логические операции алгебры высказываний. В результате

  получаем новые предикаты.

       Например, конъюнкцией двух предикатов P ( x ) и Q( x ) называется
новый предикат P ( x ) & Q ( x ), который принимает значение 1 при тех и
только тех конкретных значениях x ∈ M , при которых каждый из преди-
катов P ( x ) и Q( x ) принимает значение 1, и принимает значение 0 во всех
остальных случаях.
       (P & Q )(a1 , a 2 , , a n ) =P (a1 , a 2 , , a n ) & Q(a1 , a 2 , , a n ). Очевидно,
E P &Q = E P  E Q .
       Аналогично определяются операции ∨ (дизъюнкция), → (имплика-
ция), ↔ (эквиваленция), � (отрицание) и т.д.
       Легко видеть, что
1. E P ∨Q =E P  E Q ;
           ~
2. E P =E P =M \ E P ;
              ~
3. E P → Q =E P  E Q ;