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

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

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

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

,

,

,

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

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

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

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

1) .

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

Импликантой функции называется конъюнкция некоторых аргументов из набора и их отрицаний, обладающая следующими свойствами:

1) Если на некотором наборе импликанта принимает значение 1, то и принимает на этом наборе значение 1.

2 При исключении хотя бы одного множителя из свойство 1) не выполняется.

Пример.

на наборах (0,0,0), (0,0,1), (0,1,1).

Рассмотрим . на наборах (0,0,0), (0,0,1). На этих наборах , т.е. выполняется условие 1).

Если вычеркнуть один множитель из и оставить, например, , то. принимает значение 1 на наборах (0 0 0), (0 0 1), (0 1 0), (0 11), причем на выделенном наборе . Аналогичным образом, принимает значение 1, причем на выделенных наборах . Следовательно, при вычеркивании одного множителя у свойство 1) не выполняется. Это означает, что является импликантой функции.

Пусть на некотором наборе функция обращается в 1. Если на этом наборе импликанта функции обращается в 1, то говорят, что импликанта накрывает эту единицу функции .

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

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

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

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

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

Дата добавления: 2015-07-02