Материал: Захаров, Сайфутдинов - Вычислительная техника

в которых функция может быть записана единственным образом. Такие формы называют совершенными дизъюнктивными нормальными формами (СДНФ).

СДНФ определяется как сумма элементарных произведений, в которых каждая переменная встречается ровно один раз либо с отрицанием, либо без него.

Для преобразования функции (2.2) в СДНФ необходимо дополнить каждое элементарное произведение недостающими переменными так, чтобы тождественность преобразования не была нарушена:

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

х1 = 1, х2 = 0, х3 = 1 – первая комбинация; х1 = 0, х2 = 0, х3 = 1 – вторая комбинация; х1 = 1, х2 = 0, х3 = 0 – третья комбинация.

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

Таблица истинности такой функции (таблица 2.3) содержит три строки, в которых функция равна 1.

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

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

Применив это правило, мы получим

f(xl , x 2 , x3 ) х1 х2 х3 х1 х2 х3 х1 х2 х3 .

2.5. Минимизация логических функций

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

Наиболее распространенным является метод непосредственных тождественных преобразований. Этот метод, рассмотренный выше, состоит в последовательном применении к логической формуле законов и правил тождественных преобразований алгебры логики. Он пригоден для простых формул, когда последовательность преобразований очевидна. Наиболее часто этот метод применяется для окончательной минимизации выражений, полученных после минимизации их другими методами.

Рассмотрим применение метода непосредственных преобразований на примере минимизации функции трех переменных, заданных ее СДНФ:

Объединим попарно первое и третье, второе и третье, а также четвертое и пятое элементарные произведения:

22

у (х1 х2 х3 х1 х2 х3 ) (х1 х2 х3 х1 х2 х3 ) (х1 х2 х3

х1 х2 х3 ) х2 х3 (х1 х1 ) х1 х2 (х3 х3 ) х1 х2 (х3 х3 )

х2 х3 х1 х2 х1 х2 х2 х3 х1 (х2 х2 ) х2 х3 х1.

Эта формула гораздо проще исходной СДНФ. Здесь в формуле (2.4) в каждой паре объединяемые элементарные произведения различаются лишь одной переменной, которая входит в первое произведение с отрицанием, а во второе – без отрицания. Такие элементарные произведения называются соседними. К соседним произведениям применима операция склеивания, в результате которой уменьшается число суммируемых произведений и на единицу уменьшается число переменных.

2.6. Табличные методы минимизации. Карты Карно

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

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

На рис. 2.1, 2.2 и 2.3 приведены структуры карт Карно для функции двух, трех и четырех переменных, а в таблицах 2.4 и 2.5 представлены таблицы истинности для функции двух, трех переменных соответственно.

Таблица 2.4

Рис. 2.1. Структура карты Карно для функции двух переменных

23

Рис. 2.2. Структура карты Карно для функции трех переменных

Рис. 2.3. Структура карты Карно для функции четырех переменных

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

24

столбца. Так, в случае карты Карно для функции четырех переменных, функция, расположенная в ячейках столбца с координатами 01, вычисляется при значениях переменных х3 = 0, х4 = 1. Функция, расположенная в ячейке на пересечении этого столбца и строки с координатами 11, определяется при наборе входных переменных x1 = l, x2 = l, х3 = 0, х4 = 1.

Если на указанном наборе функция равна 1, то ее СДНФ обязательно содержит элементарное произведение х1 х2 х3 х4, принимающее при этом наборе единичное значение. Таким образом ячейки карты Карно, представляющие функцию, содержат столько единиц, сколько элементарных произведений содержится в ее СДНФ, причем каждой единице соответствует одно из элементарных произведений.

Координаты строк и столбцов в карте Карно следуют не в естественном порядке возрастания двоичных кодов, а в порядке 00; 01; 11; 10. Изменение порядка следования наборов кодов сделано для того, чтобы соседние наборы, отличающиеся между собой лишь цифрой какого-либо одного разряда, были соседними в геометрическом

25