Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
|
Карты Карно. Карта Карно[1](используется также термин диаграмма Вейча) — это замечательное представление булевой функцииКарта Карно [1](используется также термин диаграмма Вейча) — это замечательное представление булевой функции, позволяющее наглядно и эффектно описать и реализовать многие, в том числе сложные, операции с булевыми функциями и реализующими их формулами. В картах Карно применяются сразу несколько понятий, рассматриваемых в этом учебнике: код Грея (1.3.3.), таблицы истинности (3.1.1.), минтермы (3.4.1.'), единичный гиперкуб (3.4.5), табличные представления булевой функции (3.6.1.). Карта Карно для представления функций n переменных является таблицей, которая содержит 2 n клеток. Если n чётное, n =2 k, то таблица содержит 2 k строк и 2 k столбцов, а если нечётное, n =2 k –1, то таблица содержит 2 k– 1 строк и 2 k столбцов. Каждая ячейка карты Карно символизирует один минтерм. Существует 2 nn! способов расставить минтермы по ячейкам карты Карно. Зафиксируем один из них с помощью следующего неформально описанного индуктивного алгоритма. База. Карта Карно для n =1
Индуктивный переход. При переходе от n к n +1, если n нечётное, и карта имеет форму прямоугольника, следует зеркально отразить карту относительно нижней стороны и после этого приписать всем минтермам в верхней половине справа 1, а всем минтермам в нижней половине — 0. Если же n чётное, и карта имеет форму квадрата, следует зеркально отразить карту относительно правой стороны и после этого приписать всем минтермам в левой половине справа 1, а всем минтермам в левой половине — 0. Ниже приведены таблицы для n = 2, 3, 4 и 5, в клетках которых выписаны вектора соответствующих минтермов. n =2
n = 3
n =4
n =5
Заметим следующее. На каждой карте Карно представлены все 2 n минтермов. Распределение минтермов по клеткам карты однозначно (при заданном алгоритме) и может быть сделано один заранее для каждой карты требуемого размера. Карту Карно можно рассматривать как развертку тора, то есть считать верхнюю сторону смежной с нижней, а правую – с левой. В этом случае легко видеть, что для каждой ячейки (при использовании данного алгоритма заполнения клеток минтермамами) все её четыре соседа отличаются ровно в одном разряде. Подобным же свойством обладают коды Грея и вершины единичного гиперкуба.
|