Лекция 80. Карта Карно

Сначала смотрим, есть ли покрытия_1 из 16 клеток покрывающих хотя бы одну непокрытую. Приведем шаблоны, которые помогают строить покрытия 1 переменные считаем теми же, но их писать не будем. Нулевые значения не записываются. Для построения минимальной днф производится процедура склеивания. Число групп должно быть минимальным. Другой способ получения простых импликант формул с малым числом переменных и, значит, нахождения минимальной днф основан на использовании так называемых карт карно. Каждой клетке диаграммы ставится в соответствие двоичный n-мерный набор. Строится таблица истинности функции определенным образом. Карты карно - это графическое представление операций попарного неполного склеивания и элементарного поглощения. Смотрим, есть ли покрытия 1 из 4 клеток покрывающих хотя бы одну непокрытую. Каждая клетка должна входить хотя бы в одну группу. Переходим к покрытиям из 4 клеток. Карты карно для функций, зависящих от n переменных, разделенный, представляет собой прямоугольник. Смотрим, есть ли покрытия 1 из 8 клеток покрывающих хотя бы одну непокрытую. Переходим к покрытиям из 8 клеток. Нижние четыре клетки карты соответствуют двоичным наборам, в которых переменная x принимает значение 1, в которых переменная x принимает значение, четыре верхние клетки соответствуют наборам. Процесс склеивания 1 сводится к объединению в группы единичных клеток карты карно, входящих в одну группу, должно выражаться числом кратным 2,2, при этом необходимо выполнять следующие правила; количество клеток. Клеток, должна иметь m соседних в группе. Карты карно рассматриваются как перестроенная соответствующим образом таблица истинности функции. Четырем клеткам составляющим правую половину карты, соответствуют наборы, в которых переменная y; принимает значение. Карта карно - это специального вида таблица, которая позволяет упростить процесс поиска минимальных форм и успешно применяется, когда число переменных не превосходит шести. Считывание функции f по группе склеивания производится следующим образом: переменные, которые сохраняют одинаковые значения в клетках группы склеивания, причем значениям 1 соответствуют сами переменные, а значениям 0 их отрицания, входят в конъюнкцию. В каждую группу должно входить максимальное число клеток, ни одна группа не должна содержаться в другой группе. Для упрощения записи мы не будем отмечать переменные, хотя сохраним их обозначения как и в вышеприведенных таблицах. В первой таблице показан пример разметки карты карно для функции, зависящей от трех переменных. Переходим к покрытиям из 2 клеток. Склеивающимся значениям 1 соответствуют соседние клетки, клетки отличающиеся лишь значением одной переменной на графическом изображении разделенных вертикальной или горизонтальной линией с учетом соседства противоположных крайних клеток. Если 6 переменных - 4 карты, покрывающих p-клетки функции наилучшим образом, так чтобы в соседних картах соседние клетки имели одинаковые координаты: задача минимизации переключательной функции с помощью карт карно заключается в нахождении импликант высшего ранга соответствующих компактным группам наибольшей размерности. Каждая клетка таблицы соответствует вполне определенной вершине булева куба. Значения заданной функциивносятся в нужные квадраты, однако если клетке соответствует 0, то обычно она остается пустой.