Топологическая структура карт Карно

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

Для карт с тремя переменными карту следует рассматривать как цилиндр со склеенными правыми и левыми краями. Поскольку группы формируются на таком цилиндре, на плоском рисунке та или иная группа может оказаться разорванной.

рис. 1.5 Разорванные группы на карте Карно для функции трех переменных.

Разорванные прямоугольные группы могут появляться и на картах с четырьмя переменными. На таких картах нужно считать склеенными не только правый и левый края, но также верхний и нижний. Таким образом, карта с четырьмя переменными должна рассматриваться как поверхность тора. В примере на рис. 1.6 (а), группа из четырех ячеек соответствует терму , а группа из двух ячеек – терму . Особое внимание нужно обратить на рис. 1.6 (б). Ячейки в четырех углах образуют одну группу, если поверхность считать тороидальной. Этой группе соответствует терм .

рис. 1.6 Примеры разорванных групп на карте Карно для функции четырех переменных.

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

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

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