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

Тождественно-истинным называется предикат, истинный всю­ ду на области определения: Т(Р) = D(P). Тождественно-ложным называется предикат, множество истинности которого пусто: Т(Р) = = 0 . Два предиката в одной и той же области определения различны в том и только в том случае, если их множества истинности не совпадают. Это определение совпадает с отрицанием обычного оп­ ределения равенства функций. Логические операции (связки) над предикатами. Связки, анало­ гичные связкам булевой алгебры и исчисления высказываний, соответствуют логическим операциям над предикатами. Операции над л-местными предикатами вводятся аналогично одноместным. Пусть, например, Р(х, ...) и Q(x, ...) — предикаты, которые определены на множестве D, причем Т(Р) и T(Q) — их множе­ ства истинности. ____ Отрицанием предиката Р(х , ...) называется предикат Р(х), также определенный на множестве D и истинный при тех значениях переменной х, при которых Р(х, ...) ложен, т.е. Т(Р) = D \ T(P) (рис. 5.1). Например, предикат Р(х): «х — простое число» определен на множестве D= Z целых чисел, а его областью истинности являют­ ся только простые числа, т.е. числа, имеющие два делителя: хи 1. Тогда предикат «х — составное (целое) число», также определен­ ный на Z, будет отрицанием предиката Р(х), т.е. Р(х), а его обла­ стью истинности будет множество всех целых составных чисел (имеющих три и более делителей): Т(Р(х)) - D \T (P (x ) ) . Аналогично вводятся и остальные операции. Конъюнкция предикатов Р(х, ...) и Q(x, ...) есть новый преди­ кат Р(х) л Q(х ) , определенный на множестве D и истинный при тех значениях переменной х, при которых истинны одновременно оба предиката Р(х, ...) и Q(x, ...), поэтому Т(Р л Q) = Т(Р) П T(Q) (рис. 5.2). Рассмотрим примеры. 1. Для предикатов Р(х): «х — четное число» и Q(x): «х кратно 7» конъюнкцией Р(х) л Q(x) служит предикат «х — четное и кратное 7 число» или «х —число, кратное 14». Рис. 5.1. Множество ис- Рис. 5.2. Множество истинности тинности предиката Р(х) конъюнкции предикатов 227