Минимизация с помощью диаграмм Вейча (карт Карно).
Для интерпретации любых логических функций широко используются диаграммы Вейча (карты Карно), которые можно рассматривать как упорядоченное представление подмножества. Множество клеток позволяет отобразить все наборы аргументов.
Каждой клетке таблицы ставится в соответствие определенная конъюнкция, причем делается это таким образом, чтобы в соседних клетках (снизу и сверху, слева и справа) конъюнкции отличались не более чем одним сомножителем. Т.е. порядок следования столбцов может быть любым, но с условием, что соседние столбцы (равно как и соседние строки) должны отличаться друг от друга значением только одной переменной. Поэтому нельзя, например, ставить рядом столбцы x2 и x3.
Для двух аргументов карта содержит четыре клетки, и количество всех комбинаций имеет вид:
х2
х1
х1·х2
х1·
·
·х2
При заполнении таблицы в соответствующую клетку ставится 1, если минимизируемая функция при данном наборе аргументов равна 1, а в оставшиеся – «0».
В заполненной таблице обводят прямоугольными контурами все единицы и затем записывают минимизированную функцию в виде суммы логических произведений, описывающих эти контуры. При проведении контуров придерживаются следующих правил:
Контур должен быть прямоугольным;
Внутри контура должны быть только клетки, заполненные единицами;
Число клеток, находящихся внутри контура, должно быть целой степенью числа 2, т.е. может быть равно 1, 2, 4, 8, …;
Одни и те же клетки, заполненные единицами, могут входить в несколько контуров;
При проведении контуров самая нижняя и самая верхняя строки таблицы считаются соседними, то же – для крайнего левого и крайнего правого столбцов, т.е. сворачивание карты в цилиндр, как по горизонтали, так и по вертикали оси с объединением противоположных граней карты.;
Число контуров должно быть как можно меньше, а сами контуры как можно большими.
Для того чтобы найти логическое выражение, которое описывает в карте Карно контур, охватывающий единицы, нужно рассмотреть обозначения строк и столбцов, входящих в этот контур, и исключить из этих обозначений те аргументы, которые изменяют свое значение внутри контура.
Если функция задана в СКНФ, то каждому члену соответствует своя клетка, куда записывается ноль. Минимизацию производят, объединяя нули функции. Особенность – запись логической функции содержит аргументы, инверсные аргументом, написанным на диаграмме Вейча.
Минимизация логической функции 3-х аргументов производится с помощью карты Карно, которая содержит 8 клеток.
|
х2 |
|
||
х1 |
|
|
|
|
|
|
|
|
|
|
|
х3 |
|
|
Для Примера 1 получим:
Для СДНФ:
-
х1 х2х3
00
01
1
110
0
0
0
1
0
1
0
1
1
1
Выписывая обозначения всех трех контуров, находим минимальное выражение:
МДНФ: F = x2x3 + x1x3 + x1x2
Для СКНФ:
-
х1 х2х3
00
01
11
10
0
0
0
1
0
1
0
1
1
1
МКНФ: F = (x2V x3) (x1V x2) (x1V x3)
Для минимизации функции можно применить основные законы алгебры логики:
F = x2x3 + x1 x3 + x1x2 + x1x2x3 = ( x2x3 + x1x2x3) + (x1 x3 + x1x2x3) + (x1x2 + x1x2x3) = x2x3 + x1x3 + x1x2
С увеличением числа аргументов число клеток быстро растет, для n аргументов получаем 2n клеток. На практике строят карты Карно не более чем для пяти-шести переменных. Так для представления функции пяти аргументов необходимо использовать две карты, каждая из которых представляет собой карту четырех переменных; одна для х5=1, а другая для х5=0. Эти карты располагаются одна под другой, и области охвата клеток могут быть трехмерными, т.е. в одну область могут входить клетки двух карт. Для минимизации функций с числом аргументов более 7-8 карты Карно практически не используются, и в этих случаях используются алгебраические методы.