Спирина, М.С. Дискретная математика

множество элементов, обладающих таким свойством Q, будем называть объемом этого свойства. Если на множестве U задан предикат, выражающий некоторое свойство Р, то множество U можно разбить на два подмножества Т(Р) и U\T(P) . Так, в предыдущем примере Т(Р) = {5, 6, 7, 8, 9, 10, 11} множество истинности предиката Р: «5 ^ х < 12» из множества U - {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}. U\ T(P) = {1, 2, 3, 4, 12, 13, 14, 15}. Такое разбиение на непере- секающиеся подмножества мы называем классификацией множе­ ства U по основанию Р. Пусть на множестве U задано еще одно свойство Q. Тогда все множество U, разбиваясь на четыре подмножества, представляет новую классификацию. С помощью логических операций такую классификацию записывают в виде: Р(х) ■Q(x) vP(x) ■Q(x) vP(x) Q(x) v P(x) Q(x). Это аналогично разложению булевой функции по двум переменным (см. подразд. 4.7), с той разницей, что каждое слагаемое должно иметь вид Р(х) Q(x) ■ 1, так как мы разлагаем формулу исчисления предикатов, имеющую вид тавтологии. Пусть в нашем примере предикат Q выражает новое свойство — «быть нечетным числом». Тогда эти два свойства одновременно классифицируют множество U на подмножества: T(P) f )T(Q) = {5, 7, 9, 11}, выполнено Р(х) ■ (?(х); T(P)C\T(Q) - (6, 8, 10}, выполнено P(x) Q(x); Т ( Р ) Г \ Т (Q) = {1, 3, 13, 15}, выполнено Р(х) Q(x); Т ( Р ) Г \ Т (Q) = {2, 4, 12, 14}, выполнено P(x) Q(x). Уточним понятие «отношение» с помощью понятия «преди­ кат». Во всех л-местных предикатах (л > 2) устанавливаются неко­ торые отношения между переменными. Рассмотрим примеры. Высказывательная форма « jc — друг у» выделяет из всего мно­ жества людей пары х и у, которые связаны между собой отноше­ нием дружбы. Высказывательная форма «x_Ly» выделяет из множества пар прямых, например на плоскости, те пары, которые связаны от­ ношением перпендикулярности. Высказывательная форма «х2 + у2 + z2 = 16» выделяет из всего множества троек координат те, которые связаны отношением «точ­ ка с координатами (х; у; z) лежит на сфере с центром в начале координат и радиусом R = 4». Отрицания в исчислении предикатов. В разговорной речи для построения отрицания обычно перед сказуемым ставят частицу не. Например, 1а «Студент х учится на факультете программирова­ ния» имеет отрицание 16 «Студент х не учится на факультете про­ граммирования». 238