Зарипова, Э.Р. Дискретная математика Часть II. Математическая логика

18 двойственной к формуле F , нужно в формуле F всюду заменить 0 на 1 , 1 на 0 , & на  ,  на & . Пример 4.1. Пусть F 1 (f 1 )=f 1 (х 1 ,x 2 )=x 1 &x 2 . Тогда F 1 *(f 1 )=F 1 (f 1 *)=f 1 *(x 1 ,x 2 )=x 1  x 2 . Пусть . ), ( ( ), ( ))) ( ( , ( , , ) 1 2 1 2 2 1 1 2 1 3 1 3 2 2 1 2 3 x x x x f f x x f f x f x F f f f    Здесь f 1 – конъюнкция, f 2 – дизъюнкция, f 3 – отрицание. Тогда ) ) & ( ))) ( ), ( ), ( ( ( ( , ( , , ) ( , , ) * * * * * * * * * 1 2 1 2 2 1 1 2 1 3 1 3 2 2 1 2 3 2 1 2 3 x x x x f f x x f f x f x F f f f F f f f       Из принципа двойственности вытекает, что если F(f 1 ,…,f m ) =  (g 1 ,…,g n ), то F * (f 1 ,…,f m ) =  *(g 1 ,…,g n ) Пример 4.2. Используя принцип двойственности, можно выводить формулы. Читателю предлагается самостоятельно из равенства ) ( 1 2 1 2 x x x x   вывести равенство 1 2 1 2 x x x x   . При рассмотрении свойств булевых функций принцип двойственности позволяет почти в два раза сокращать усилия на вывод равенств. Совершенная дизъюнктивная нормальная форма (СДНФ) Введем обозначения x o = x , x 1 =x . Пусть  0,1  . Тогда       . , , x 0 x 1 x    Очевидно, что x  =1  x=  . Определение. Выражение вида 1 2 1 2 ... n n x x x    называется элементарной конъюнкцией.