Реферат: Конспект лекций по дискретной математике
в) раскрытие скобок с применением дистрибутивного закона
г) упрощения выражения с применением закона поглощения
Приведение произвольных нормальных форм Булевой функции к каноническим
Для приведения произвольной ДНФ к КНФ необходимо использовать правило дизъюнктивного развертывания применительно к каждому из неполных конъюнктивных термов.
_ _
P=P(xi Úxi )=Pxi ÚPxi, где P-неполный конъюнктивный терм (ранг этого терма
меньше n), а xi - недостающий в терме аргумент.
Пример:
_ _ _ _ _ _ _ _ _ _
y=x1 Úx2 x3 (ДНФ)=x1 (x2 Úx2 )(x3 Úx3 ) Úx2 x3 (x1 Úx1 )=x1 x2 x3 Ú x1 x2 x3 Ú
_ _ _ _ _ _ _ _ _
Úx1 x2 x3 Úx1 x2 x3 Ú x1 x2 x3 Ú x1 x2 x3 (КДНФ)
Замечание:
После раскрытия скобок могут получиться одинаковые термы, из которых нужно оставить только один.
y=
(0,1,2,3,5)=f3
Преобразование КНФ к ККНФ реализуется путем применения правила конъюнктивного развертывания к каждому неполному дизъюнктивному терму.
_ _
P=PÚxi xi =(PÚxi )(PÚxi )
_ _ _ _ _ _ _ _ _ _
y=x1 Úx2 x3 (ДНФ)=(x1 Úx2 )(x1 Úx3 )(КНФ)=(x1 Úx2 Úx3 x3 )(x1 Úx3 Úx2 x2 )=
_ _ _ _ _ _ _ _
=(x1 Úx2 Úx3 )(x1 Úx2 Úx3 )(x1 Úx2 Úx3 )(x1 Úx2 Úx3 )(ККНФ)
y=
(4,6,7)
Минимизация булевых функций на картах Карно(см . Практику) .
Метод Квайна-МакКласски базируется на кубическом представлении булевых функций.
Кубическое представление булевых функций .
В кубическом представлении булевой функции от n переменных все множество из 2n наборов ее аргументов рассматривается как множество координат вершин n-мерного куба с длинной ребра равной 1. В соответствии с этим наборы аргументов, на которых булева функция принимает значение равное 1 принято называть существенными вершинами.
Существенные вершины образуют так называемые ноль-кубы (0-кубы). Между 0-кубами существует отношение соседства и определена операция склеивания. Два 0-куба называются соседними если они отличаются только по одной координате.
Пример :n=4 0101
0001 - два соседних 0-куба
результат склеивания : 0x01 (*)
Склеивание 2-х соседних 0-кубов дает в результате 1-куб. Координата, отмечаемая символом х, называется свободной (независимой, несвязанной), а остальные (числовые) координаты называются зависимыми (связанными). Аналогичное отношение соседства существует между 1-кубами, в результате склеивания которых получается 2-куб.
0х01
0х11 - 0хх1 (**)