Построение сокращенной ДНФ методом Блейка

Сокращенной д.н.ф.функции называется функция, которая содержит меньшее число букв, чем СДНФ. Если над СДНФ произвести все возможные операции склеивания, а затем все возможные операции поглощения то полученная функция будет иметь вид сокращенной ДНФ.

В основе использования метода Блейка лежат операции склеивания и операции поглощения.

Законы поглощения

,

,

,

Отметим, что формулы во втором столбце получаются из формул первого столбца с помощью принципа двойственности.

Закон склеивания (объединения конъюнкций): .

Закон обобщенного склеивания: .

Пример. Получить сокращенную ДНФ методом Блейка

1) .

М инимизация булевых функций методом Квайна– Мак-Класки.

Система импликант функции называется полной, если любая единица из таблицы значений функции накрывается хотя бы одной импликантой.

Сокращенной ДНФ функции называется дизъюнкция всех импликант из полной системы импликант.

Утверждение. Сокращенная ДНФ. функции совпадает с самой функцией.

Действительно, дизъюнкция всех импликант из полной системы импликант равна 1 на тех наборах, где равна 1 функция (в соответствии с определением импликанты ) и равна нулю на тех наборах, где равна нулю функция, т.е. значения сокращенной д.н.ф.функции и функции совпадают.

Сокращенная д.н.ф.функции содержит меньшее число букв, чем СДНФ Однако, во многих случаях допускается дальнейшее сокращение числа букв за счет того, что некоторые из импликант могут поглощаться дизъюнкциями других импликант.

Дата добавления: 2015-07-02; Просмотров: 3453; Нарушение авторских прав?; Мы поможем в написании вашей работы!