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

формулой алгебры логики а -» b =a v b имеем: />-> Q = P v Q и Q) = (D \T (P ) ) \JT (Q ) (рис. 5.5). Например, импликацией предикатов Р(х): «х — нечетное число» и Q(x): «х кратно 5», определенных на NU{0}, служит предикат Р(х) -> £2(х): «Если х — нечетное число, то х кратно 5». Здесь Т(Р) = {y |(ymod2) = 1} = = {1, 3, 5, ...}; 7 4 0 ) = {у I (ymod5) - 0} = = {0, 5, 10, ...}. Тогда D/ Т(Р) = {у I (ymod2) = = 0} ={0, 2,4,...}; Т (Р -> Q ) = ф \ Т ( Р ) )U T(Q) = = {y |(ymod2) = 0 или (ymod5) = 0} = (0, 2, 4, 5, 6, ...}. Импликация верна, если число кратно двум или пяти. З а м е ч а н и е . Поскольку в данном нами алфавите связка -> является основной, a v и а — дополнительными, то дадим введе- def _ ние конъюнкции и дизъюнкции через —> и Р v Q = Р -> Q, def ---------— Р л Q = Р —> Q. Рис. 5.5. Множество истинности импли­ кации предикатов Эквиваленцией предикатов Р(х, ...) и Q(x, ...) называется пре­ дикат Р(х) = Q(x), определенный на множестве D и истинный при тех значениях переменной х, при которых либо оба предиката истинны , либо оба предиката ложны. Поэтому Т(Р <=> Q) = = (Т(Р) П T(Q))U((D\ T(P))C\(D\T(Q))). В силу законов Де Мор­ гана ( nP ) r iT (Q ) ) \ J (D \ { T (P ) \ J T (Q ) ) ) = D \T(P)AT(Q) ) . Если Т{Р) = T(Q), то Т(Р = Q) = D. Например, эквивалентны преди­ каты Р(х): «х — натуральное число, кратное 3» и Q(x): «х — нату­ ральное число, сумма цифр которого делится на 3». Следование и эквиваленция. Высказывательная форма Q2 следу­ ет из высказывательной формы Qu если импликация 0 , —у Q2 об­ ращается в истинное высказывание при любых наборах значений переменных, входящих в нее. Для операции логического следова­ ния принято обозначение Q j => Q2. Пусть даны предикаты Q\{x\, х2, хп) и Q2(X\, х2, ..., хп), а их множества истинности соответственно T(Q\) и T(Q2). Поскольку (?i => & то если (*ь х2, ..., хп) е 7Щ ) , т.е. Q\ истинна, то должна быть истинна Q2, т.е. (хь х2, ..., х„) е T(Q2). Поскольку такое свойство должно быть у любого элемента из Т( Q\), то это опреде­ ление подмножества. Итак, T(QX) с T(Q2). Пусть даны два предиката, определенные на одном множестве. Высказывательные формы 0 , и Q2 назовем равносильными, если при любом наборе значений переменных, входящих в них, вы­ сказывательные формы принимают одинаковые значения истин­ ности: Q, <=>Q2. Очевидно, что если => 0 2, a 0 2=> 0 Ь то Qx <=> Q2. Тогда T(QX) = T(Q2), т.е. множества истинности равносильных предикатов также совпадают. Например, пусть высказывательные формы заданы на множестве действительных чисел R. 229