Лекции ДМ

4.Метод Карно.

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

0 0	01
10	11

000	010	011	001
100	110	111	101

0000	0010	0011	0001
0100	0110	0111	0101
1100	1110	1111	1101
1000	1010	1011	1001

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

0 b	1 c	0	0 d
0	1	1	1
1 a	1	0	1
0	1	0	0

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

Содержание