Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 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
| 1 1 | 0 1 |
| 1 0 | 0 0 |
n = 3
| 11 1 | 01 1 | 01 0 | 11 0 |
| 10 1 | 00 1 | 00 0 | 10 0 |
n =4
| 111 1 | 011 1 | 010 1 | 110 1 |
| 101 1 | 001 1 | 000 1 | 100 1 |
| 101 0 | 001 0 | 000 0 | 100 0 |
| 111 0 | 011 0 | 110 0 |
n =5
| 1111 1 | 0111 1 | 0101 1 | 1101 1 | 1101 0 | 0101 0 | 0111 0 | 1111 0 |
| 1011 1 | 0011 1 | 0001 1 | 1001 1 | 1001 0 | 0001 0 | 0011 0 | 1011 0 |
| 1010 1 | 0010 1 | 0000 1 | 1000 1 | 1000 0 | 0000 0 | 0010 0 | 1010 0 |
| 1110 1 | 0110 1 | 0100 1 | 1100 1 | 1100 0 | 0100 0 | 0110 0 | 1110 0 |
Заметим следующее. На каждой карте Карно представлены все 2 n минтермов. Распределение минтермов по клеткам карты однозначно (при заданном алгоритме) и может быть сделано один заранее для каждой карты требуемого размера.
Карту Карно можно рассматривать как развертку тора, то есть считать верхнюю сторону смежной с нижней, а правую – с левой. В этом случае легко видеть, что для каждой ячейки (при использовании данного алгоритма заполнения клеток минтермамами) все её четыре соседа отличаются ровно в одном разряде. Подобным же свойством обладают коды Грея и вершины единичного гиперкуба.
Date: 2015-07-23; view: 328; Нарушение авторских прав; Помощь в написании работы --> СЮДА... |