TechShape.ru

Информационные технологии

Основные разделы

Методика минимизации логических функций

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

В некоторых простых случаях минимизацию можно осуществить, непосредственно используя основные законы булевой алгебры. В качестве примера упростим выражение (1), используя закон склеивания:

Полученное выражение равносильно исходному, но значительно проще его.

Пусть имеется логическая функция:

Добавим дважды к ее правой части уже имеющийся член (отчего функция не изменится); тогда

И это выражение проще исходного.

Следует отметить, что такие элементарные приемы минимизации удается использовать нечасто - при малом количестве членов функции и небольшом числе переменных. В других случаях применяются специальные методы минимизации, облегчающие поиск склеивающихся членов. К ним относится метод минимизации с помощью карт Карно.

Карта Карно построена так, что в ее соседние клетки попадают смежные члены функции - члены, отличающиеся значение одной переменной: в один член эта переменная входит в прямой форме, а в другой - в инверсной. Благодаря этому возникает наглядное представление о различных вариантах склеивания смежных членов.

Карта Карно имеет столько клеток, сколько комбинаций (наборов) можно составить из прямых и инверсных значений n переменных по n членом в каждой. Т.к. при n=2 карта содержит четыре клетки рисунок 1, а при n=3 - восемь клеток рисунок 2, при n = 4 - шестнадцать клеток рисунок 3.

Рисунок 3

Рисунок 4

Рисунок 5

Каждая клетка соответствует определенной комбинации переменных. Так, например, левая верхняя клетка карты рисунок 1 соответствует комбинации : над столбцом левых клеток указан в прямой форме, возле верхней строки записан в прямой форме . Левая нижняя клетка той же карты соответствует комбинации , так как на нижнюю строку клеток не распространяется «действие» - клетки этой строки отвечают комбинациям, где присутствует . Клетке нижней строки третьего слева столбца рисунок 2 соответствует комбинация , клетке второго слева столбца третьей сверху строки рисунок 3 соответствует комбинация и т.д.

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

Общие правила склеивания членов, занесенных в карту Карно, следующие:

) склеиваться могут 2, 4. 8 и т. д. членов; при этом соответствующие единицы в клетках для наглядности охватывают контурами; каждый должен быть прямоугольником;

) одним контуром следует объединять максимальное количество клеток;

) одна и та же единица может охватываться разными контурами, т.е. один и тот же минтерм может склеиваться с несколькими смежными; последнее объясняется тем, что значение функции не меняется при прибавлении уже имеющихся членов;

Перейти на страницу: 1 2 3 4

Еще статьи

Вторичный источник электропитания ВИП–24В–3,5А
Целью данной работы является получение практических навыков конструирования вторичных источников электропитания (ВИП). К качеству питающего напряжения предъявляются разнообразные требования. Существует большое число типов источников вторичного электропитания. Выбор оптимального варианта, удовлетворя ...

Все права защищены! 2021 - www.techshape.ru