Глава 1. Минимизация функций алгебры логики в классе днф[*]

Из известных методов минимизации булевых функций в данной главе рассматриваются наиболее простые и распространенные в базисе {-,&, Ú }.

I Геометрический метод.

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

В геометрической интерпретации изобразим область определения произвольной булевой функции трех переменных множеством вершин трехмерного куба. Элементам куба можно поставить во взаимо-однозначное соответствие конъюнкции различного ранга: вершинам куба – конъюнкции третьего ранга, ребрам – второго, граням – первого. Ранг – число букв, образующих конъюнкцию. Каждый геометрический эквивалент меньшей размерности покрывается всеми геометрическими эквивалентами большей размерности (рис. 1-1).

x 1 x 2 x 3

Так, например, конъюнкции и покрываются конъюнкцией (две вершины- ребро); конъюнкции , , , покрываются либо двумя конъюнкциями и , либо и либо только (четыре вершины –либо два ребра, либо одна грань).

рис. 1-1

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

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

Пример 1-1: Минимизировать функцию, заданную следующей таблицей истинности

Таблица 1-2
x 1
x 2
x 3
f (x 1, x 2, x 3)

Ее формула в СДНФ имеет вид:

.

Отметим на рис. 1-3 вершины, соответствующие конъюнкциям, входящим в СДНФ данной функции.

x 2

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

2 Метод неопределенных коэффициентов.

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

Представим функцию в виде следующей ДНФ:

Здесь представлены все возможные конъюнктивные члены, которые могут входить в . Коэффициенты с различными индексами являются неопределенными и подбираются так, чтобы полученная форма была минимальной. Если задать наборы аргументов, подставить в формулу и приравнять полученные выражения (отбрасывая нулевые конъюнкции) значению функции на выбранных наборах, то получим систему уравнений для определения коэффициентов . В общем случае в системе будет уравнений, - число аргументов функции.

(1)

Если функция задана таблицей, то в правой части соответствующих уравнений будут стоять нули и единицы. Для удовлетворения уравнения, в правой части которого стоит нуль, необходимо приравнять нулю все коэффициенты , входящие в это уравнение (это вытекает из определения дизъюнкции).

Рассмотрев все уравнения, в правой части которых стоят нули, и приравняв все коэффициенты этих уравнений нулю, в остальных уравнениях вычеркивают вошедшие в них нулевые коэффициенты. Удобно полученную систему переписать в более сокращенной форме, оставив в ней уравнения, в правой части которых стоят единицы, убрав при этом из этих уравнений нулевые коэффициенты. Затем выбирают в системе самые короткие уравнения. В этих уравнениях приравнивают единице коэффициенты, определяющие конъюнкции наименьшего возможного ранга (это возможно, т.к. дизъюнкция равна единице при обращении в единицу хотя бы одного члена). При этом надо выбрать такие конъюнкции наименьшего ранга, которые чаще встречаются в уравнениях системы. Остальные коэффициенты можно положить равными 0 или 1. Затем рассматривают оставшиеся уравнения и в них выбирают коэффициенты, соответствующие конъюнкциям наименьшего ранга по тому же принципу, и т.д.

Найденные единичные коэффициенты определяют конъюнкции с наименьшим числом знаков, а форма, записанная с этими коэффициентами, определяет минимальную ДНФ данной функции.

Пример 1-2. Минимизировать функцию (см. пример 1-1).

Составим систему (обратите внимание на то, что она имеет стандартный вид, лишь в правой части изменяются значения в зависимости от таблицы истинности функции). Для удобства записи системы слева помещают координаты вершин (область определения функции). Верхние индексы коэффициентов комбинируют соответственно из записанных координат вершин с учетом взятых нижних индексов. Например, для второй вершины (0,0,1) верхним индексом для коэффициента будет 00; для - 01 и т.д.

Из уравнений 2, 5, 6 в силу свойств дизъюнкции вытекает, что

Удобно вычеркнуть уравнения, в правой части которых стоят нули, а в остальных уравнениях вычеркнуть коэффициенты равные нулю.

После этого система примет вид:

(2)

В системе (2) в силу свойства дизъюнкции можно приравнять единице коэффициент , тогда 2, 3, 4 и 5 уравнения этой системы превращаются в тождества, из первого же уравнения системы возьмем . Все остальные коэффициенты во всех уравнениях положим равными нулю.

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

Итак, мы нашли , остальные коэффициенты равны нулю. Отсюда минимальная форма данной функции:

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

3.Метод минимизирующих карт (гарвардский метод).

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

Рассмотрим следующую таблицу

(3)

Эта таблица служит более компактной записью системы уравнений (1) метода неопределенных коэффициентов, где вместо коэффициентов в соответствующей клетке записываются сами конъюнкции. Каждая строка таблицы (3) заменяет собою соответственно 1-ое, 2-ое, …… 8-ое уравнения системы (1). Дизъюнкция всех элементов строки таблицы есть значение функции в вершине, определяемой соответствующими переменными. Так, первая строка есть значение функции в вершине , четвертая в или в переводе на координаты соответственно в (1, 1, 1), (1, 0, 0).

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

Пусть, например, в СДНФ не входит конъюнкция , тогда в минимальную форму не входит, например, член (аналогично и другие конъюнкции 3-ей строки):

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

Таблица (3) называется минимизирующей картой.

Минимизация функции производится по следующим правилам:

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

2. В столбцах оставшихся строк вычеркивают все элементы, попавшие в вычеркнутые строки.

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

4. Взяв по одной конъюнкции для всех незачеркнутых строк и записав их дизъюнкцию, получают минимальную форму.

Заметим, что нахождение МДНФ неоднозначно, ибо произволен выбор минимальных конъюнкций в строках. Однако, все получаемые по этому методу МДНФ будут “одинаково минимальны”.

Пример 1-3. Минимизировать функцию (см. пример 1-1)

.

Строим для функции минимизирующую карту.

Отметим справа от последнего столбца те конъюнкции, которые входят в СДНФ данной функции. Вычеркнем неотмеченные строки (правило 1), затем вычеркнем в остальных строках (действуя по столбцу) те элементы, которые попали в вычеркнутые строки (правило 2). Во 2-ом столбце (с одной переменной) положим , при этом остальные элементы строк (1, 2, 5, 6 строки), где стоит элемент , положим равными нулю. В строке 8 положим элемент , .

Итак, получим МДНФ данной функции в виде:

.

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

Пример 1- 4. Минимизировать функцию

.

Согласно правилам 1, 2 вычеркиваем конъюнкции

Для удобства табличку оставшихся конъюнкций начертим отдельно, выбросив 1-3 столбцы, 1, 8 строки.

Положим во 2-ой строке равным 1, обведем рамочкой, остальные члены положим равными нулю. Вычеркнем нулевые члены в 6-й строке, в 1-й строке. Выберем 1 из оставшихся строк самые короткие, 1-я и 6-я строки. Положим в них соответственно , остальные члены равными нулю. В строках 4 и 5 будет по одному члену, равному 1. Итак, в каждой строке таблицы есть один член, равный 1, следовательно, минимальная форма функции будет

.

Возможен другой вариант минимальной формы. Рассмотрим на таблице.

Пусть в 4-й строке , а остальные члены равны нулю. Тогда в строке 5: можно положить равными нулю. Вычеркнем в 1-й и 6-й строках (они короче других), положим соответственно . Тогда в строках 2 и 3 будет по одному члену, равному единице. Итак, минимальная форма функции

.

Методы неопределенных коэффициентов и минимизирующих карт приводят к громоздким записям (число строк таблицы для функции переменных равно , а число столбцов ). Использование этих методов уже для порядка 8-10 становится затруднительным.