Правило минимизации логических функций с помощью карты Карно

Карты Карно

Карты Карно также являются методом минимизации логических функций. Карты Карно представляют собой способ задания логических функций с помощью специальной таблицы, число клеток которой равно числу всех возможных наборов аргументов логической функции. Таким образом, каждой клетке карты Карно можно поставить а соответствие набор переменных, на которых функция равна единице.

Для записи конкретной логической функции в те клетки, для которых набор переменных, на которых функция равна единице, входит в исходную логическую функцию, записывается «1», в оставшиеся «0».

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

Для логической функции двух переменных F(x,y) карта Карно имеет вид:

F(x,y)

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

Для карты Карно трех переменных соседними клетками являются также клетки левого и правого столбцов для одноименных строк. Для логической функции трех переменных карта Карно имеет следующий вид:

F(x,y,z)

Следует отметить, что карта является объемной фигурой. т.е. представляет собой «цилиндр», поскольку боковые стороны совмещены. В связи с этим можно считать, например, для карты Карно логической функции трех переменных соседними клетки 010 и 000; 110 и 100.

Карты Карно для большего числа переменных могут быть составлены из карт меньшего числа переменных.

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

1. Рассматриваются поочередно клетки, содержащие единицы и анализируются все возможные варианты склеивания. Сначала выполняется склеивание только для тех клеток (единиц), для. которых вариант склеивания единственный.

2. Оставшиеся не склеенные клетки (единицы) необходимо склеивать таким образом, чтобы образовать минимальное число групп с максимальным числом клеток в каждой группе.

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

Дата добавления: 2015-05-06