double arrow

Сокращенная ДНФ


Познакомимся с сопутствующими понятиями.

Максимальная грань: Nk называется максимальной гранью, если не существует Nk такая, что:

1. Nk ÍNf ÍNk’ ;

2. размерность грани Nk больше размерности Nk .

Пример:

для каждой конъюнкции найдем грани и выявим максимальные:

Nk1 ={(000), (100)}- одномерная, максимальная,

Nk2 ={(100), (101)}- одномерная, является подмножеством Nk3, или, покрывается гранью Nk3, поэтому не является максимальной.

Nk3 ={(100), (110), (101), (111)}- двухмерная, максимальная.

Конъюнкции, соответствующие максимальным граням, называются простыми импликантами.

В нашем примере простыми импликантами будут К1 и К3.

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

Алгоритм построения сокращенной ДНФ:

1. составить какую-либо КНФ функции (можно СКНФ);

2. раскрыть скобки;

3. удалить нулевые члены, поглащаемые и дублирующие, т.е. К1К2VK1º K1, K1VK1º K1.

Полученная ДНФ состоит только из простых импликант и является сокращенной.

Пример: Для функции построить сокращенную ДНФ.

Путем равносильных преобразований составим какую-либо КНФ и, выполняя пункты 2 и 3 алгоритма, получим сокращенную ДНФ:




Найдем грани конъюнкций:

Nk1 = {(000), (010)}- одномерная, максимальная,

Nk2 = {(100), (101)}- одномерная, максимальная,

Nk3 = {(000), (100)}- одномерная, максимальная.

Соответствующий рисунок:

 
 








Сейчас читают про: