Преобразование функции в минимальную конъюнктивную нормальную форму (КНФ).

Лекция 3. Переключательная функция для пяти переменных.

 

В этой диаграмме, как и прежде, соседними являются крайние клетки каждого столбца и строки левой и правой половин. Кроме того, соседними являются клетки расположенные на одной строке и равноудаленные от центральной вертикальной линии, т.е. диаграмму следует представить ещё и сложную по центральной вертикальной линии как страница книги.

 

 

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

Рассмотрим пример:

Возьмем функцию четырех переменных:

f=v(4,14)

 

.