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

Все логические функции задаются либо в виде формулы, либо в виде таблицы значений. Иногда бывает нужно определить простейшую форму записи этой функции с минимальным количеством элементарных логических функций И, ИЛИ, НЕ для удобства работы. Для этого используются все рассмотренные операции начиная с №4 и методы Квайна и Вейча.

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

Метод Вейча (карты Карно)

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

1) Функция одной переменной:

2) Функция двух переменных:

3) Диаграмма для дизъюнкции:

4) Диаграмма для конъюнкции:

5) Для трех аргументов:

6) Для четырех аргументов:

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

б)

Метод применим для функций от любого числа переменных, но мы рассмотрим его для функций от 3-х переменных.

Представим в виде ДНФ с неопределенными коэффициентамиk:

(**)

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

Будем рассматривать данную нам функцию на всех наборах и приравнивать выражение (**) на каждом из наборов (отбрасывая нулевые конъюнкции) соответствующему значению функции. Получим систему изуравнений вида:

Если в каком-то из этих уравнений правая часть равна 0, то все слагаемые левой части тоже равны 0. Эти коэффициенты можно исключить из всех уравнений, правые части которых равны 1. В этих уравнениях значение 1 следует присвоить тому коэффициенту, который соответствует коньюнкции наименьшего ранга. Эти коэффициенты и определят МДНФ.

Пример

Составляем систему, используя выражение (**).

После исключения нулевых слагаемых получаем

Полагаем остальные коэффициенты считаем нулевыми. Получаем МДНФ:

2.2. Метод Квайна - Мак - Класки

Рассмотренный метод неопределенных коэффициентов эффективен, если число аргументов функции не больше, чем 5 – 6. Это связано с тем, что число уравнений равно 2 n . Более эффективным является выписывание не всех возможных конъюнкций для функции, а только тех, которые могут присутствовать в ДНФ данной функции. На этом основан метод Квайна. При этом предполагается, что функция задана в виде СДНФ. В данном методе элементарные конъюнкции рангаn, входящие в ДНф, называются минитермами рангаn. Метод Квайна состоит из последовательного выполнения следующих этапов.

1. Нахождение первичных импликант

Просматриваем последовательно каждый минитерм функции и производим склеивание его со всеми минитермами, с которыми это возможно. В результате склеивания минитермов n-го ранга, мы получим минитермы (n-1)-га ранга. Минитермыn-го ранга, которые участвовали в операции склеивания, помечаем. Затем рассматриваем минитермы (n-1)-го ранга и операцию склеивания применяем к ним. Помечаем склеивающиеся минитермы (n-1)-го ранга и записываем получившиеся в результате склеивания минитермы (n-2)-го ранга и т. д. Этап заканчивается, если вновь полученные минитермыl -го ранга уже не склеиваются между собой. Все неотмеченные минитермы называются первичными импликантами. Их дизъюнкция представляет собой Сокр. ДНФ функции.

Склеиваем минитермы 4-го ранга и помечаем склеивающиеся минитермы звездочками

Образуем минитермы 2-го ранга:

Первичными (простыми) импликантами являются:

2. Расстановка меток

Для данной функции Сокр. ДНФ имеет вид:

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

Продолжение примера

3. Нахождение существенных импликант

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

В рассматриваемом примере исключаем строку и столбцы.

В результате получаем таблицу

4. Вычеркивание лишних столбцов и строк

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

5. Выбор минимального покрытия максимальными интервалами

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

Продолжение примера

Минимальное покрытие таблицы образуют строки, соответствующие импликантам . Тогда МДНФ имеет вид:

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

Идея метода Мак - Класки заключается в следующем. Все минитермы записываются в виде двоичных номеров, например, как 1010. Эти номера разбиваются на группы по числу единиц в номере, т. е. вi-ю группу попадают номера, имеющие в своей записиiединиц. По парное сравнение производится только между соседними по номеру группами, т. к. минитермы, пригодные для склеивания, отличаются друг от друга только в одном разряде. При образовании минитермов с ранга выше нулевого, в разряды, соответствующие исключенным переменным, ставится тире.

Пример

Найдем МДНФ для функции:

Минитермы 4-го ранга по группам

Минитермы 3-го ранга

Минитермы 2-го ранга

Непомеченные минитермы или простые импликанты

Строим таблицу меток

Обе первичные импликанты существенны и определяют минимальное покрытие, т. е. МДНФ имеет вид.

Продолжительность: 2 часа (90 мин.)

14.1 Ключевые вопросы

14 Лекция №13. Минимизация логических функций 1

14.1 Ключевые вопросы 1

14.2 Текст лекции 1

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

14.2.1.1 Расчетный метод 1

14.2.1.2 Карты Карно 4

14.2.2 Минимизация систем логических уравнений 7

14.2.3 Минимизация частично определенных логических функций 8

14.2.4 Вопросы для контроля 10

14.2 Текст лекции

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

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

расчетный;

карт Карно.

14.2.1.1 Расчетный метод

Здесь применяют:

– склеивание,

– поглощение,

– развертывание.

Склеивание

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

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

Замечание:
и дистрибутивном законе конъюнкции относительно дизъюнкции (см. Лекцию № 10)

.

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

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

Замечание: Это правило основано на законе дополнительности

и дистрибутивном законе дизъюнкции относительно конъюнкции (см. Лекцию № 10)

в) Правила обобщенного склеивания.

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

Поглощение

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

б) Если в выражении встречается произведение двух сумм, одна из которых является частью другой, то это произведение сумм можно заменить меньшей суммой:

a (ab ) = a ; a (ab )(ac )…= a ; (ab )(abc )= ab .

Развертывание

Развертывание позволяет восстановить в формулах «потерянные» (например, в результате минимизации) переменные или перейти от ДНФ и КНФ к совершенным формам – СДНФ и СКНФ. Восстановление переменных для ДНФ и КНФ производится по–разному. Рассмотрим примеры.

Пусть имеем ДНФ

в которой, очевидно, потеряна переменная y . Для восстановления переменнойy произведение переменныхxz умножается на 1, затем 1 заменяется суммой прямого и инверсного обозначений недостающей переменной, и на основе дистрибутивного закона проводится преобразование

Пусть имеем КНФ
, где также потеряна переменнаяy . Для ее восстановления к сумме
добавляется 0, затем 0 заменяется произведением недостающей переменной на ее инверсию и применяется дистрибутивный закон

Используя развертывание, можно раскрыть смысл понятий «конституента единицы» и «конституента нуля».

Пусть n = 2 (переменныеa иb ).

Развернем единицу 1.

1= 1=
=.

Получили СДНФ функции двух переменных f = 1, где каждая конъюнкция является составляющей (конституентой) единицы.

Развернем 0.

Получили СКНФ функции двух переменных f = 0, где каждая дизъюнкция является составляющей (конституентой) нуля.

Полезность развертывания показывает пример доказательства правил обобщенного склеивания (см. п. 4.1.1):

Рассмотрим первое правило

Развернем левую часть тождества, в первом произведении которой недостает переменной c , во втором произведении недостаетb , а в третьем нетa .

После приведения подобных членов, применив простое склеивание

получаем правую часть, следовательно, тождество доказано.

Рассмотрим второе правило

Развернем левую часть тождества.

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

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

Получили правую часть, следовательно, правило доказано.

Общий порядок проведения минимизации функции, заданной СДНФ, здесь следующий.

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

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

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

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

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

После применения операции склеивания и приведения подобных членов получаем

Обобщенное склеивание здесь можно проводить по нескольким вариантам, которые дают следующие результаты:

.

Исключены
,
,
: (
), (
), (
).

В скобках показаны термы, участвующие в обобщенном склеивании.

Исключены
,
,
: (
), (
), (
).

Как видим, здесь имеется две минимальных нормальных формы. По сложности они одинаковы.

Пример 2: Продолжая решение задачи по созданию устройства рис. 3, проведем минимизацию мажоритарной функции (см. табл. 12), для которой выше были получены СДНФ и СКНФ.

Здесь первую сумму мы поочередно рассматривали в паре со второй, третьей и четвертой суммами и после склеивания этих пар получили результат.

8.3. Аналитические методы минимизации переключательных функций

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

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

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

Пусть имеется переключательная функция, заданная СДНФ:

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

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

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

Дальнейшие склеивания невозможны, поэтому полученные импликанты – простые, а сокращенная ДНФ имеет вид:

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

Как уже отмечалось, простая импликанта поглощает некоторую конституенту единицы, если является ее собственной частью. Соответствующая клетка импликантной таблицы на пересечении строки данной простой импликанты и столбцов с конституентами единицы отмечается, например, знаком «+». Минимальные ДНФ строятся по импликантной таблице следующим образом:

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

2) рассматриваются различные варианты выбора совокупности простых импликант, которые накроют крестиками остальные столбцы импликантной матрицы, и выбираются варианты с минимальным суммарным числом букв.

Ядром нашей функции (табл. 35) являются импликанты
и х 1 х 2 х 3 , т.е. функция имеет единственную тупиковую и минимальную ДНФ:

Таблица 35

Импликантная таблица Квайна

Видно, что импликанта х 2 х 3 х 4 является лишней, так как она покрывает конституенты, уже покрытые импликантами
, х 1 х 2 х 3 .

Число крестиков в строке является степенью числа 2; более того, можно убедиться, что оно равно N=2 n - k , где k – число букв в простой импликанте, n – число переменных, от которых зависит функция.

Если вначале не задана СДНФ, то ее надо получить, используя, например, уже известные нам методы.

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

Это означает, что тупиковая ДНФ содержит две простые импликанты (
и одновременно С=х 1 х 2 х 3) и имеет вид:

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

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

111101001000110.

Сгруппируем эти конституенты единицы по числу единиц:

Дальнейшие склеивания невозможны. Нахождение минимальных ДНФ далее производится по импликантной таблице (табл. 36):

Это означает, что тупиковые ДНФ содержат по три простые импликанты и имеют вид:

(две инверсии);

(три инверсии).

Таблица 36

Импликантная таблица Квайна-Мак-Класки

Заметим, что склеивание двух импликант с тире возможно только при соответствующем их расположении, например:

Можно выбрать любую из полученных ТДНФ, а с учетом меньшего числа инверсий – первую.

Метод Блейка-Порецкого .

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

Пусть задана ДНФ функции:

Видно, что к первой и второй конъюнкциям можно применить закон обобщенного склеивания по переменной х 1 ; получим:

Аналогично для первой и третьей конъюнкций:

т.е. все остается, как есть!

Вторая и третья конъюнкции допускают обобщенное склеивание по х 2:

Переходим к ДНФ:

После применения закона идемпотентности (повторения) и поглощения получаем:

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

Таблица 37

Импликантная таблица для иллюстрации метода Блейка-Порецкого

Таким образом, рабочие (единичные) наборы можно покрыть тремя простыми импликантами, например,
,
,
. В ядро входят импликанты
,
. Тогда тупиковые ДНФ имеют вид:

(лучше по числу инверсий).

Существует два направления минимизации:

• Ш Кратчайшая форма записи (цель - минимизировать ранг каждого терма);
• Ш Получение минимальной формы записи (цель - получение минимального числа символов для записи всей функции сразу).
• 1. Метод эквивалентных преобразований

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

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

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

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

Для этого:

• Ш Составляются таблицы, в строках которых пишутся найденные первичные импликанты, а в столбцах указываются термы первичной ФАЛ.
• Ш Клетки этой таблицы отмечаются в том случае, если первичная импликанта входит в состав какого-нибудь первичного терма.
• Ш Задача упрощения сводится к нахождению такого минимального количества импликант, которые покрывают все столбцы.

Алгоритм метода Квайна (шаги):

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

Пусть задана функция:

Для удобства изложения пометим каждую конституенту единицы из СДНФ функции F каким-либо десятичным номером (произвольно). Выполняем склеивания. Конституента 1 склеивается только с конституентой 2 (по переменной х3) и с конституентой 3 (по переменной х2) конституента 2 с конституентой 4 и т. д. В результате получаем:

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

с появлением одного и того же элементарного произведения. Дальнейшие склеивания невозможны. Произведя поглощения (из полученной ДНФ вычеркиваем все поглощаемые элементарные произведения), получим сокращенную ДНФ:

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

Импликантная матрица имеет вид см. табл. 1.1

Таблица 1.1 Импликантная матрица

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

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

Следовательно функция имеет вид:

3. Метод Квайна-Мак-Класки.

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

• 1. Все конституенты единицы из СДНФ булевой функции F записываются их двоичными номерами.
• 2. Все номера разбиваются на непересекающиеся группы. Признак образования і-й группы: і единиц в каждом двоичном номере конституенты единицы.
• 3. Склеивание производят только между номерами соседних групп. Склеиваемые номера отмечаются каким-либо знаком (зачеркиванием, звездочкой и т.д.).
• 4. Склеивания производят всевозможные, как и в методе Квайна. Неотмеченные после склеивания номера являются простыми импликантами.

Образуем группы двоичных номеров. Признаком образования і-й группы является і единиц в двоичном номере конституенты единицы (табл.1.2).

Таблица 1.2 Группы двоичных номеров

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

Таблица 1.4 Результаты склеивания 2

По табл. 5. определяем совокупность простых импликант - 0--1 и 111-, соответствующую минимальной ДНФ. Для восстановления буквенного вида простой импликанты достаточно выписать произведения тех переменных, которые соответствуют сохранившимся двоичным цифрам:

Разбиение конституент на группы позволяет уменьшить число попарных сравнений при склеивании.

4. Метод диаграмм Вейча.

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

Рис.1.

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

Рис.2.

Добавление к ней еще такой же таблицы дает диаграмму для функции 4-х переменных (Рис 3).

Рис.3.

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

5. Карты Карно.

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

Построим таблицу метода карт Карно (табл. 1.6).

Таблица 1.6 Карты Карно

Теперь подсчитаем совокупность всех крестиков с метками минимальным количеством крестиков. Таких крестиков в нашем случае будет 5: три четырехклеточных и два двухклеточных. Этим крестикам соответствуют следующие простые импликанты:

для первого - X 3 X 4 ;

для второго - X 1 X 3 ;

для третьего - X 2 X 3 ;

для четвертого - X 1 X 2 X 4 ;

для пятого - X 1 X 2 X 4 ;

Минимальная ДНФ будет выглядеть так:

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

Этот метод может быть использован для любого числа аргументов. Но так как этот метод достаточно громоздок, то применяется только в тех случаях, когда число аргументов не более 5-6.

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

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

Приравняем все коэффициенты 0 в тех строках, которым соответствует 0 в векторе столбце. Затем приравняем 0 соответствующие коэффициенты в других строках. После этих преобразований система примет следующий вид (Рис 4):

Рис.4.

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

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