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

          9. ПРЕДИКАТЫ. ОПЕРАЦИИ НАД ПРЕДИКАТАМИ

      Понятие предиката обобщает понятие высказывания.
      Предложение или утверждение, содержащее одно или несколько пе-
ременных, при подстановке вместо которых конкретных значений из неко-
торых множеств мы получаем высказывание (истинное или ложное), назы-
вается предикатом. Количество переменных, от которых зависит преди-
кат, называется местностью или арностью.
      Пусть M 1 , M 2 ,� , M n – множества элементов произвольной природы.

         Определение 1: n -местным предикатом называется функция
P � x1 , x 2 ,� , x n � , зависящая от n переменных, определенная на множестве
M � M 1 � M 2 � � � M n и принимающая на этом множестве значение
1(истина) или 0 (ложь).

         Например, P � x � = [натуральное число x кратно 5] — одноместный
предикат: P �4 � � 0 , P �15� � 1, P �11� � 0 , P �20� � 1. Q � x , y � � [город x нахо-
дится на территории государства y] — двухместный предикат:
Q � Москва , Россия � � 1, Q � Париж , Венгрия � � 0 , Q � Париж , Франция � � 1.
         Само высказывание считается нуль-местным предикатом.
         Переменные x1 , x 2 ,� , x n , от которых зависит предикат, называются
предметными переменными. Конкретные значения предметных перемен-
ных называются предметными константами.
         Множество M , на котором задан предикат, называется областью
определения предиката.
         Множество E p � M , на котором предикат принимает только ис-
тинные значения, называется множеством истинности предиката
P � x1 , x 2 ,� , x n � : E p � ��a1 , a 2 ,� , a n � � M P �a1 , a 2 ,� , a n � � 1�.
         Различают четыре типа предикатов:
1. Предикат P � x1 , x 2 ,� , x n � называется тождественно истинным на
    множестве M � M 1 � M 2 � � � M n , если E p � M , т.е. если на любом
   наборе �a1 , a 2 ,� , a n � � M предикат принимает значение 1 (истина).
2. Предикат P � x1 , x 2 ,� , x n � называется тождественно ложным на
   множестве M , если E p � � , т.е. если на любом наборе значений пере-
   менных предикат принимает значение 0 (ложь).
3. Предикат P � x1 , x 2 ,� , x n � называется выполнимым, если его множест-
   во истинности E p не пусто: E p � � .
4. Предикат P � x1 , x 2 ,� , x n � называется опровержимым, если его множе-
   ство истинности E p не совпадает с его областью определения, т.е. су-

                                          55