[ Скачать с сервера (163.5Kb) ] | |
С помощью эквивалентных преобразований приведите формулу к ДНФ, КНФ, СДНФ, СКНФ, полином Жегалкина ⌐((z→x)↔(y│x)); Решение: Приведем формулу ⌐((z→x)↔(y│x)) к ДНФ (дизъюнктивной нормальной Избавимся от эквиваленции, используя формулу (а↔b)=(a—>b)/\(b—>a): ⌐(((z→x)—>(y│x)) /\ ((y│x)—>(z→x))) Избавимся от импликации (a—>b=⌐a\/b)и от штриха Шеффера ( a|b=⌐ (a/\b) ): ⌐( ( (⌐z\/x)—>( ⌐(y/\x) ) ) /\ (⌐ (y/\x) —> (⌐z\/x) ) )= =⌐( (⌐ (⌐z\/x) \/ ( ⌐ (y/\x) ) ) /\ (⌐(⌐(y/\x)) \/ (⌐z\/x) ) ) Используя свойство, что ⌐(⌐а)=а, получим ⌐( (⌐ (⌐z\/x) \/ ( ⌐ (y/\x) ) ) /\ ( (y/\x) \/ (⌐z\/x) ) ) Используя законы Де Моргана: ⌐ (a\/b)= ⌐a /\ ⌐b ; ⌐ (a/\b)= ⌐a \/ ⌐b , упростим ⌐( (z /\ ⌐x) \/ ( ⌐y \/ ⌐x) ) ) /\ ( (y/\x) \/ (⌐z\/x) ) ) = ⌐ ( (z /\ ⌐x) \/ ( ⌐y \/ ⌐x) ) \/ ⌐ ((y/\x) = (⌐ (z /\ ⌐x) /\ ⌐ ( ⌐y \/ ⌐x) ) \/ (⌐ (y/\x) /\ ⌐(⌐z\/x))=((⌐z \/ x) /\ (y /\ x) ) \/ (⌐y\/⌐x)/\ (z/\⌐x)) (⌐z /\ y /\ x) \/ (x /\y/\x) \/ (⌐y/\z/\⌐x)\/(⌐x/\z/\⌐x) Зная, свойство идемпотентности: а /\ а = а, получим ДНФ(дизъюнкция элементарных (⌐z /\ y /\ x) \/ (x /\y) \/ (⌐y/\z/\⌐x)\/(⌐x/\z) Теперь получим СДНФ формулы, нужно чтобы в каждой конъюнкции a=(a /\ b) \/ (a /\ ⌐b)=a /\ (b \/ ⌐b): (⌐z /\ y /\ x) \/ (x /\y/\ (z \/ ⌐z)) \/ (⌐y/\z/\⌐x)\/(⌐x/\z/\ (y \/⌐y)) Используя свойство дистрибутивности, (⌐z /\ y /\ x) \/ (x /\y/\ z) \/ (x /\y/\ ⌐z) \/ =( х /\ у /\ ⌐z) \/ (x /\y/\ z) \/ (x /\y/\ ⌐z) \/ (⌐x /\ ⌐y /\ z) \/ (⌐x /\ y /\z) \/ (⌐x /\ ⌐y /\ z) ( х /\ у /\ ⌐z) \/ (x /\y/\ z) \/ (⌐x /\ ⌐y /\ z) \/ (⌐x/\ y /\z) Приведем формулу ⌐((z→x)↔(y│x)) к КНФ (конъюнктивной нормальной ⌐((z→x)↔(y│x))= ((⌐z \/ x) /\ (y /\ x) ) \/ (⌐y\/⌐x) /\ (z/\⌐x)) Воспользуемся свойством дистрибутивности (a/\b) \/ c=(a\/c) /\ (b\/c): ((⌐z \/ x) \/ ((⌐y\/⌐x) /\ (z/\⌐x)) ) /\ ((y /\ x) \/ ((⌐y\/⌐x) /\ (z/\⌐x)) )==(⌐z \/ x \/ ⌐y\/⌐x) /\ (⌐z \/ x \/ (z/\⌐x)) /\ ((y \/ ((⌐y\/⌐x) /\ (z/\⌐x)) ) /\(x\/((⌐y\/⌐x) /\ (z/\⌐x)))= Упростим множители за счет свойств ⌐a (⌐z \/ ⌐y \/ 1) /\ (x \/ 1) /\ (⌐z \/ 1) /\ (1\/⌐x) /\ (y \/ z) /\ (y \/ ⌐x) /\ (⌐y\/1) /\ (x\/z) /\ 1= = 1 /\ 1 /\ 1 /\ 1 /\ (y \/ z) /\ (y \/ ⌐x) /\ 1 /\ (x\/z) /\ 1 Получили КНФ (y \/ z) /\ (y \/ ⌐x) /\ (x\/z) Теперь получим СКНФ исходной формулы, для этого в (⌐a /\ a =0, a\/0=a)не достающие слагаемые , получим (y \/ z\/(х /\ ⌐x)) /\ (y \/ ⌐x \/(z /\ ⌐z)) /\ (x\/z\/(y /\ ⌐y)), можно записать: Избавимся от одинаковых множителей, получим СКНФ исходной формулы: |
14,937 total views, 2 views today