Минимизация функций проводится обычно в классе ДНФ, но возможна и в КНФ. В основу положены два закона

Л.С. Тихомирова

 

МЕТОДЫ

минимизации булевых функций

 

 

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

Способ преобразования информации любой физической системой характеризуется законом функционирования системы. Удобно кодировать информацию (отвлекаясь от ее характера и смысла) конечным набором символов (букв).

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

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

В настоящее время наибольшее распространение получил базис, состоящий из инверсии, конъюнкции и дизъюнкции ( ‾, Ù , Ú ). Образующие его функции наиболее просты с точки зрения математических преобразований и технической реализации, кроме того, от них легко перейти в любой другой базис.

Минимизация функций проводится обычно в классе ДНФ, но возможна и в КНФ. В основу положены два закона:

Закон склеивания (или , где - произвольная булева функция, - отдельный знак).

Закон поглощения (или , где - любая булева функция, - отдельный знак).

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

Обратите внимание, что речь идет о минимальном числе букв, а не переменных. Например, содержит 7 букв, но 3 переменных.

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

С элементами математической логики можно познакомиться по методической разработке “Элементы теории множеств и математической логики” (Л.С. Тихомирова, И.Н. Иноземцева. Издание ИМИ, 1974 г.).

Введем некоторые необходимые понятия.

Рассмотрим функцию . Каждое из слагаемых соответствует только одной единицы в таблице истинности данной функции. Говорят, что каждое слагаемое покрывает единицу функции, а в совокупности они покрывают данную функцию т.е. являются ее покрытием. Но заметим, что упростив функцию , получим более простое покрытие. Оба представления соответствуют одной и той же таблице истинности функции, т.е. обращаются в 1 и 0 на одних и тех же наборах переменных . Если обратиться к отдельным слагаемым 2-го представления, нетрудно заметить, что обращается в единицу на двух наборах (1, 0), (1, 1), а - на (0, 0), (1, 0), совместно они покрывают единицами все единицы данной функции. Отметим, что оба слагаемых и обращаются одновременно в нуль на наборе (0, 1), т.е. там, где функция равна нулю.

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

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

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

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

Например: - является простой импликантой

 

(знак означает вхождение в , означает, что условия вхождения не выполняются).

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

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

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

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

Приведем схему упрощения формы булевой функции

 

 

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

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

 

 

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

 

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

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

Так, например, конъюнкции и покрываются конъюнкцией (две вершины – ребро);

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

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

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

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

x1
x2
x3
f(x1, x2, x3)

 

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

 

 

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

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

 

 

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

 

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

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

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

 

(1)

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

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

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

 

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

 

 

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

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

 

 

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

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

(2)

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

 

 

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

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

 

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

 

Метод. Метод минимизирующих карт Карно.

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

Метод. Метод Квайна

Этот метод применим к функции, записанной в СДНФ. Метод минимизации функции проводится поэтапно. 1 этап. Нахождение первичных импликант. Все конъюнкции СДНФ данной функции сравнивают между собой попарно, применяя закон склеивания . Удобно члены функции…

Метод Патрика

Нахождение всех возможных тупиковых форм.

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

Метод. Метод Мак-Класки

Этот метод является модернизацией метода Квайна (его 1-го этапа). Мак-Класки предложил записывать исходные импликанты данной функции, заданной в… Далее все производится по методу Квайна, но в кодовых значениях импликант.…  

Метод. Метод карт (диаграмма) Вейча.

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

Задание

 

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

Примечание

 

В таблицах по горизонтали стоят номера функций соответственно варианту задания.

№1

 

 

 

№2

 

 

№3

 

ЛИТЕРАТУРА

 

1. Васильев Ю.Л., Ветухновский Ф.Я., Глаголев В.В., Журавлев Ю.И., Левенштейн В.И., Яблонский С.В. Дискретная математика и математические вопросы кибернетики. М.: Наука, 1974.
2. Поспелов Д.А. Логические методы анализа и синтеза схем. М.: Энергия, 1974.
3. Вавилов Е.Н., Портной Г.П. Синтез схем ЭЦВМ. М.: Советское радио, 1983.
4. Грейнер Г.Р., Ильяшенко В.П., Май В.П., Первушин Н.Н., Токмачева Л.И. Проектирование бесконтактных управляющих логических устройств промышленной автоматики. М.: Энергия, 1977.