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

га „ конъюнкцией Э л ем ен т а р н о й ------------------ гг называется выражение, состоя- дизъюнкциеи щее из конечного числа переменных и их отрицаний, взятых в этом выражении не более одного раза и разделенных операциями конъюнкции . дизъюнкции S / \ У 1 , где у, = X/ или xj, например Х|Х2х^ — элементарная конъ- /=1 юнкция; S V .v„ где у, = х,- или х,-, например х, v х2 v х3 — элементарная i=i дизъюнкция. Дизъюнктивной „ . „ дизъюнкция гг-------------------- с- нормальной формой называется-------------------- Конъюнктивной конъю нкция КП1П.ЮТТК11ИИ конечного числа элементарных -----------------Сокращенно они дизъюнкции обозначаются ДНФ и КНФ соответственно. Нормальная форма называется со в ерш ен н о й , если в каждой ее элементарной дизъюнкции (конъюнкции) представлены все пе­ ременные, входящие в данную функцию (либо сами, либо с от­ рицанием). Любая булева функция и любая формула алгебры логики могут быть представлены множеством различных дизъюнктивных форм , равносильных между собой. Например: /Дх^, х2, х3) = Х| v х,хз v V Х|Х2Х3 = Х ( V Х ,Х2Х3 = X] V X ,Y 2r 3 = Х|Х2Х^ V Х|Х^Х3 V Х|Х2Х3 V х{х{ху Из всех различных ДНФ функции / г1(хь х2, х 3) особо выделяет­ ся последнее логическое выражение, которое является совершен­ ной ДНФ, сокращенно СДНФ. На СДНФ накладываются следу­ ющие требования: • формула не является тождественно-ложной; • формула приведена к одному из видов ДНФ ; • из формулы удалены элементарные конъюнкции, включа­ ющие одновременно переменную и ее отрицание, согласно зако­ ну инверсии; • из формулы удалены одинаковые элементарные конъюнкции, кроме одной, согласно правилу идемпотентности; • каждая элементарная конъюнкция в ДНФ включает все логи­ ческие переменные, входящие в эту формулу. Если в логической функции не выполняется последнее требо­ вание, то в неполную элементарную конъюнкцию необходимо ввести дополнительный множитель, включающий дизъюнкцию отсутствующей переменной и ее отрицание. Это всегда можно сде­ лать, так как согласно закону инверсии o v a = l , a l - a = a. 171