Минимизация функций алгебры логики.

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

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

Рисунок 15.1 – Диаграммы Вейча для функций двух (а),трех (б) и четырех (в) переменных

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

Все диаграммы построены таким образом, что рядом расположенные единицы по горизонтали или вертикали склеиваются в соответствии с законом склеивания алгебры логики. Одну и ту же конституенту единицы можно использовать для склеивания с несколькими другими конституентами единицы для получения наиболее простого окончательного выражения. Цель всех операций – получить как можно меньшее число прямоугольников (в том числе квадратов), чтобы число членов СДНФ уменьшилось, получив в итоге МДНФ.

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

На Рисунке 15.2 приведены некоторые правила склеивания конституент единицы для функций двух и трех переменных.

Рисунок 15.2 – Примеры для иллюстрации правил склеивания

Поскольку для ФАЛ трех переменных диаграмма представляет как бы развертку цилиндра, разрезанного по поэтому единицы, расположенные по краям диаграммы (например, как это изображено на рисунке 15.2), считаются расположенными рядом.

Метод минимизации СДНФ с помощью диаграмм Вейча включает в себя следующие шаги:

• производится занесение в соответствующую диаграмму конституент единицы, входящих в СДНФ минимизируемой функции;

• используя приведенные выше правила склеивания, находят простые импликанты функций (простой импликантой называется некоторая конъюнкция, полученная в результате склеивания конституент единицы, не участвующая в склеивании ни с одной другой из конъюнкций);

• находится искомая минимальная дизъюнктивная нормальная форма (МДНФ) ФАЛ выбором минимальной совокупности простых импликант, покрывающей все конституенты единицы диаграммы.

В качестве примера найдем МДНФ функции, заданной таблице 15.1. Диаграмма Вейча этой функции представлена на рисунке 15.3.

Рисунок 15.3 – Пример минимизации функции, заданной в таблице 15.1

Из рисунка 15.3 видно, что в результате склеивания образовались две простые импликанты: и . Импликанта участвует в склеивании с конъюнкциями ВС и и поэтому не является простой. Таким образом, полученная МДНФ имеет вид . В истинности полученного выражения можно убедиться путем подстановки всех наборов переменных А, В и С.

Аналогом Диаграмм Вейча являются карты Карно. Они позволяют изображать на плоскости прямоугольника конституенты единицы (нуля) для ФАЛ более четырех переменных. В отличие от диаграмм Вейча, в которых отдельным строкам и столбцам соответствуют отдельные переменные, в картах Карно им можно присваивать значения нескольких переменных. При этом должны быть представлены все возможные комбинации этих переменных, например: , , , и . Таким образом, общее число переменных минимизируемой с помощью карты Карно ФАЛ может быть больше, чем в случае использования диаграмм Вейча. Сам процесс минимизации аналогичен описанному на примере диаграмм Вейча.

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

Одним из таких методов является метод Квайна и Мак-Класски. Суть метода состоит в следующем:

· все конституенты единицы, записанные в виде двоичных кодов, разбиваются на группы, содержащие одинаковое количество единиц,

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

· все склеенные конституенты, образующие импликанты, отмечают каким-либо признаком, например звездочкой;

· не отмеченные при склеивании импликанты являются простыми и заносятся в импликантную матрицу, в первой строке которойзаписываются все конституенты единицы функции f, а в первом столбце – все простые импликанты;

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

· ищутся столбцы импликантной матрицы, имеющие только по одной звездочке;

· соответствующие этим звездочкам простые импликанты называются базисными, образуют ядро функции f и обязательно входят в МДНФ;

· рассматриваются столбцы импликантной матрицы и выделяются те, которые содержат более одной звездочки;

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

Рассмотрим пример минимизации ФАЛ четырех переменных методом Квайна и Мак-Класски. Пусть задана функция в виде последовательности десятичных чисел:

f (A, B, C, D) = (l, 2, 3, 5, 6, 7, 10, 11, 14, 15).

Запишем конституенты единицы функции f в виде двоичных кодов:

.

Разобьем все конституенты единицы по группам из количества единиц.

группа 0: ;

группа 1: 0001**, 0010***;

группа 2: 0011***, 0101**, 0110**, 1010***;

группа 3: 0111****, 1011***, 1110**;

группа 4: 1111***.

Произведем склеивание конституент из соседних групп, помечая склеиваемые конституенты звездочками. Полученные импликанты разобьем по группам:

группа 1: 00-1*, 0-01*, 001-**, 0-10**, -010*;

группа 2: 0-11***, -011**, 01-1*, 011-**, 101-*, 1-10**;

группа 3: -111*, 1-11**, 111-*.

Продолжим дальнейшее склеивание импликликант из соседних групп, причем склеивание возможно только между импликантами с прочерками в одинаковых позициях:

группа 1: 0--1, 0--1, 0-1-, -01-, 0-1-, --10, -01-;

группа 2: --11, --11, -11-, 1-1-, I-1-.

Перепишем, оставив только неповторяющиеся импликанты:

группа 1: 0--1, 0-1-*, -01-*, --10*;

группа 2: --11*, -11-*, 1-1-*.

Продолжим склеивание:

группа 1: --1-, --1-, --1-.

Не отмеченные звездочками импликанты являются простыми: 0--1 и --1-. Построим импликантную матрицу (таблица 15.2).

Таблица 15.2

Простые импликанты	Конституенты единицы
0--1	*		*	*		*
--1-		*	*			*			*	*

Из матрицы видно, что столбцы, содержащие по одной звездочке, соответствуют обеим простым импликантам и, следовательно, обе эти импликанты являются базисными, образуют ядро ФАЛ и входят в МДНФ. Заменяя двоичные коды импликант соответствующими переменными, запишем вид МДНФ: . В истинности полученного выражения можно убедиться подстановкой всех возможных значений входных переменных A, B, C, и D.

Рис.15.4 – Пример минимизации частично определенной ФАЛ

Контрольные вопросы

1 Дайте определение функции алгебры логики. Приведите различные формы записи для произвольной логической функции трех переменных

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

3 Изобразите кубические комплексы произвольной логической функции двух переменных геометрической фигурой.

Лекция 16