Элементы схемотехники цифровых устройств обработки информации | страница 9
Пример: Минимизировать функцию трёх переменных, заданную таблицей истинности (таблица 6).
Таблица 6 Таблица истинности функции трёх переменных
| X1 | X2 | X3 | Y |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 0 |
СДНФ функции:
Составляем карту Карно и производим разметку её сторон:
Рисунок 8 Карта Карно функции 3-х переменных.
На карте Карно формируем два прямоугольника. Первый из них объединяет (как бы заключает в скобки) два первых минтерма (слагаемых), а второй — первое и третье слагаемые СДНФ минимизируемой функции, приведённой выше. Минтермы, объединённые в прямоугольники, отличаются только в одном разряде. Их неизменяемая часть, которая при минимизации расчётным методом выносится за скобки, и является минимизированным значением функции:
Таким образом, карта Карно позволяет поместить рядом, то есть в соседних ячейках, соседние элементарные произведения, отличающиеся только одним сомножителем.
Последовательность действий при минимизации:
1 Изображается карта Карно и производится разметка её сторон.
2 Ячейки карты Карно, соответствующие наборам переменных, обращающих функцию в «1», заполняются единицами, остальные — нулями.
3 Выбирается наилучшее покрытие карты прямоугольниками. Наилучшим считается покрытие, образованное минимальным числом прямоугольников, а если таких вариантов несколько, то выбирается тот, который даёт максимальную площадь прямоугольников.
Пример: Минимизировать функцию четырёх переменных, представленную картой Карно: (Рисунок 9).
Рисунок 9 Карта Карно функции 4-х переменных
Из карты Карно записываем минимизированное значение функции:
2.4.2 Минимизация неопределённых логических функций
Если функция имеет запрещённые наборы входных переменных, при которых функция может иметь произвольное значение (0 либо 1), то такая функция называется неопределённой. Для удобства минимизации её следует доопределить, то есть неопределённые значения карты Карно произвольным образом заменить «1» либо «0». Если функция имеет m запрещённых наборов, то может быть 2>m вариантов доопределения. Следует выбрать тот вариант, при котором минимизированная функция будет более простой.
2.5 Запись структурных формул в универсальных базисах
Запись в базисе И-НЕ производится в два этапа:
а) Логическая формула, минимизированная в основном базисе, представляется в форме ДНФ.
б) Над правой частью полученной формулы ставится два знака инверсии и с помощью формул де Моргана осуществляется переход в базис И-НЕ.
Пример. Записать в базисе И-НЕ минимизированную функцию мажоритарного логического элемента:также производится в два этапа:
