2015-07-21
1186
При минимизации функций наиболее трудоемким процессом является отыскание склеивающихся членов. Самым удобным методом для этого является использование карт Карно (диаграмм Вейча).
Карты Карно для функций от двух, трех и четырех переменных имеют вид:
На этих диаграммах (А,Б,В) каждая клетка соответствует определенному набору. Кодировка соответствует таблице истинности. Например, 0110 соответствует 
.
Заметим, что в этих диаграммах левый и правый края, а также верх и низ следует считать примыкающими друг к другу. В соседних по горизонтали и по вертикали клетках находятся склеивающиеся члены.
Если в СДНФ функции присутствует какая-либо конституента единицы, то в клетку, где она должна находиться ставится 1, если она отсутствует (т.е. на этом наборе функция равна 0), то в клетку ставится 0.
Каждая пара соседних клеток соответствует конъюнкции ранга n- 1, где n - число переменных, каждый прямоугольник, включающий 4 клетки - конъюнкции n -2 ранга, прямоугольник, включающий 8 клеток - конъюнкции n- 3 ранга. Для n >4 применение диаграммы Вейча затрудняется, т.к. теряется геометрический смысл соседних клеток.
|
|
|
Отыскание минимальной ДНФ функции сводится к определению варианта, при котором все единицы диаграммы накрываются наименьшим числом элементарных конъюнкций наименьшего ранга. Нахождение такого накрытия выполняется объединением единиц с помощью прямоугольников, включающих одну, две, четыре, восемь и т.д. единиц.
Пример 4. Две функции заданы таблицей истинности.
Применив метод карт Карно, получим.
