Метод Карно

в
Этот метод минимизации функции производится посредством таблицы, которая называется картой Карно. Карта Карно – это таблица, содержащая 2n ячеек. Каждой ячейке соответствует определенный набор переменных и указывается какое значение на этом наборе принимает функция. Причем соседние ячейки отличаются значением только одной переменной, что позволяет минимизировать ДНФ, используя закон склеивания, объединяя ячейки по 2n в прямоугольники, которые называются контурами. Соседними являются крайние верхние и крайние слева и справа. Необходимо стремиться к тому, чтобы контуры содержали как можно больше ячеек. А количество контуров должно быть минимально возможным. При создании контуров одну и туже ячейку (конъюнкцию) можно включать в несколько контуров в соответствии закона идемпотентности. Каждому контуру соответствует конъюнкция. При соединении двух ячеек исключается одна переменная, четырех – две, восьми – три и т.д. При объединении ячеек исключаются, согласно закона склеивания, переменные, которые входят в конъюнкции с разными значениями. Покажем карты Карно для функций от двух, трех и четырех переменных:

00  
   
       
       
       
       
       
       

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

b
0

c
1

0
d
0

0   1 1
a
1

     
0 1 0  

Получим такую же ДНФ:


Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:  



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