Логические схемы и их таблицы истинности,

Правила минимизации

 

Каноническая сумма минтермов

 

Минтерм – это полное произведение всех входных переменных, соответствующее одной строке таблицы истинности, в которой значение выходной переменной (значение функции) равно логической 1.

Переменная входит в минтерм с инверсией, если ее значение в данной строке таблицы равно 0, и без инверсии, если ее значение в данной строке таблицы равно 1.

Каноническая сумма минтермов – это логическая сумма всех минтермов, которая представляет собой максимальное логическое выражение, соответствующее таблице истинности. Она составляется в следующей последовательности:

В заданной таблице истинности подсчитывается «n» – количество строк таблицы, в которой значение функции равно 1.

Затем записывается логическая сумма «n» полных произведений.

Далее в каждом произведении расставляются инверсии над переменными в соответствии с их значением в строке таблицы.

Для примера, представленного на рисунке 3.8, каноническая сумма минтермов будет выглядеть так:

            (3.2)

 

Рисунок 3.8 – Логическая схема и соответствующая ей таблица истинности

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

 

 

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

 

Правила минимизации логических схем с помощью карт Карно

 

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

Назначение карты Карно – найти логические суммы прямого и инверсного значения переменных. Для любой переменной, например, , такая сумма равна  при любом значении : при  это будет 0+1=1, при  это 1+0=1. Поэтому при вынесении за скобки в выражении:

 

 

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