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

24 Из принципа двойственности следует, что 1 1 * 1 ** 1 1 ,..., ( ,..., ) 1 ( ,..., ) & ... n n n n n f f x x x x           . (5.1) Левая часть равенства (5.1) есть f(x 1 ,…,x n ) , а правая может быть преобразована следующим образом: 1 1 1 1 * 1 1 1 1 1 1 1 ,..., ,..., ( ,..., ) 0 ( ,..., ) 1 1 ,..., ( ,..., ) 0 & ... & ... & ... . n n n n n n n n n n n f f n f x x x x x x                               Таким образом, получаем разложение n 1 n 1 n 1 n 1 0 f n 1 x x f x x           ... ) & ,..., ( ) ,..., ( ,..., (5.2) Данная формула носит конструктивный характер, т.к. она по таблице функции позволяет построить формулу, являющуюся СКНФ (если f 1  ). СКНФ функции f содержит ровно столько дизъюнкций, сколько нулей в таблице f . Каждому «нулевому» набору (  1 ,…,  n ) значений переменных, т.е. набору, на котором значение функции равно 0, соответствует дизъюнкция всех переменных, в которых x i взято с отрицанием, если  i =1 и без отрицания, если  i =0 . Пример 5.5. Записать СКНФ для функции . 2 1 x x  Запишем в табличном виде данную функцию, и все соответствующие основные элементарные дизъюнкции (ОЭД) (Таблица 5.2). Заметим, что ОЭД строятся на значениях функции равных 0, переменные x 1 и x 2 берутся с отрицанием, если на данном наборе принимают значение 1, иначе без отрицания.