Методы минимизации функций. Способы минимизации логических функций

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

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

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

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

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

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

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

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

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

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

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

б)

Студент должен:

Знать:

· Методы минимизации логических функций.

Уметь:

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

· Выполнять минимизацию функций с помощью карт Карно.

Метод непосредственных преобразований

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

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

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

Например, логическую функцию

в виде СДНФ, можно минимизировать следующим образом:

1. Добавим к данной функции слагаемое , которое уже есть в данной функции, используя правило х+х=х

2. Применим метод склеивания одинаково подчеркнутых элементарных конъюнкций

3. Применим метод склеивания для двух последних элементарных конъюнкций

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

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

Карты Карно

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

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

Карты Карно были изобретены в 1952 Эдвардом В. Вейчем и усовершенствованы в 1953 Морисом Карно, физиком из «Bell Labs», и были призваны помочь упростить цифровые электронные схемы.

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

Например, карта Карно для функции четырех переменных имеет 2 4 = 16 ячеек.

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

Рисунок 2.2

На рисунке 2.3 представлена структура карты Карно для функции трёх переменных.

а) таблица истинности; б) структура карты Карно

Рисунок 2.3

Карта размечается системой координат, соответствующих значениям входных переменных. Например, верхняя строка карты для функции трех переменных (рисунок 2.3) соответствует нулевому значению переменной x1, а нижняя - ее единичному значению.

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

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

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

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

Процесс минимизации рассмотрим на примере, представленном на рисунке 2.4.

а) таблица истинности; б) карта Карно

Рисунок 2.4

Сначала формируем прямоугольники, содержащие по 2k ячеек, где k - целое число.

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

Например, на рисунке 2.4,б объединены ячейки с координатами 001 и 101. При объединении этих ячеек образовался прямоугольник, в котором переменная x1 изменяет свое значение. Следовательно, она исчезнет при склеивании соответствующих элементарных произведений и останутся только х2 и х3, причем переменную х2 берем в инверсном виде, т.к. она равна 0.

Ячейки, расположенные в первой строке (рисунок 2.4 б), содержат единицы и являются соседними. Поэтому все они объединяются в прямоугольник, содержащий 2 2 = 4 ячейки.

Переменные х2 и х3 в пределах прямоугольника меняют свое значение; следовательно, они исчезнут из результирующего элементарного произведения. Переменная х1 остается неизменной и равной нулю. Таким образом, элементарное произведение, полученное в результате объединения ячеек первой строки рисунка 2.4 б, содержит лишь один х1, который берем в инверсном виде, т.к. он равен 0.

Это, в частности, следует из того, что четырем ячейкам первой строки соответствует сумма четырех элементарных произведений:

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

Функция, соответствующая рисунку 2.4 имеет вид:

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

Итак, можно сделать следующие выводы:

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

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

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

а) б) в)

Рисунок 2.5

Функция, соответствующая покрытию, показанному на рисунке 2.5 а, имеет вид:

Несмотря на то, что карты Карно изображаются на плоскости, соседство квадратов устанавливается на поверхности тора. Верхняя и нижняя границы карты Карно как бы «склеиваются», образуя поверхность цилиндра. При склеивании боковых границ получается тороидальная поверхность. Следуя изложенным рассуждениям, устанавливаем, что ячейки с координатами 1011 и 0011, изображенные на рисунке 2.5 б, являются соседними и объединяются в прямоугольник. Действительно, указанным ячейкам соответствует сумма элементарных произведений

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

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

Карта Карно, показанная на рисунке 2.5 в, содержит единичные ячейки, расположенные по углам. Все четыре ячейки являются соседними, и после объединения дадут элементарное произведение

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

1. Изображается таблица для n переменных и производится разметка ее сторон.

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

3. Выбирается наилучшее покрытие таблицы правильными прямоугольниками, которые обводим контурами. В каждом прямоугольнике должно быть 2 n ячеек.

4. Одни и те же ячейки с единицами могут входить в разные контуры.

5. Количество прямоугольников должно быть минимальным, а площадь прямоугольников максимальная.

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

7. Полученные произведения соединяем знаком логического сложения.

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

1. Что называют минтермами и минтермами?

2.Записать функции, заданные таблицами 2.9 и 2.10 в СДНФ и СКНФ.

Таблица 2.9

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

Логические элементы

Студент должен

Знать:

· Таблицы логических состояний для основных функциональных логических схем;

· Основные базисы построения логических схем.

Уметь:

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

· Выполнять логическое проектирование в базисах микросхем;

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

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

Логическое действие осуществляется как с одной (одновходовый логический элемент) так и с множеством (многовходовый логический элемент) входных переменных.

При работе логических устройств используются три основных действия согласно алгебры Буля – «И», «ИЛИ», «НЕ».

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

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

Зачем это нужно?

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

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

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

Минимизация логических функций при помощи карт Карно

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

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

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

Возможность поглощения следует из очевидных равенств

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

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

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

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

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

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

Для упрощения работы с булевыми функциями большого числа переменных был предложен следующий удобный приём. Куб, представляющий собой структуру термов, разворачивается на плоскость как показано на рисунке. Таким образом появляется возможность представлять булевы функции с числом переменных больше двух в виде плоской таблицы. При этом следует помнить, что порядок кодов термов в таблице (00 01 11 10) не соответствует порядку следования двоичных чисел, а клетки, находящиеся в крайних столбцах таблицы, соседствуют между собой.

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

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

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

Далее берём первую область и смотрим какие переменные не меняются в пределах этой области, выписываем конъюнкцию этих переменных, если неменяющаяся переменная нулевая, проставляем над ней инверсию. Берём следующую область, выполняем то же самое что и для первой, и т. д. для всех областей. Конъюнкции областей объединяем дизъюнкцией.
Например(для Карт на 2-ве переменные):

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

В формате КНФ:

Метод применим для функций от любого числа переменных, но мы рассмотрим его для функций от 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,3,4,5 и 6 переменных. Номера столбцов в матрицах Карно образуют младшие разряды, а номера строк - старшие разряды наборов. Номера клеток составляются из номеров строк и столбцов и соответствуют наборам переменных.

Рассмотрим матрицу Карно для функции алгебры логики на наборах из 4-х переменных (табл. 1).

Таблица 1. Матрица Карно

Столбцы и строки в этой матрице обозначены двоичными соседними числами: 00-0I-II-I0. Поэтому номера смежных по горизонтали и вертикали клеток, а также крайних в строках и столбцах клеток являются соседними числами, например:

клетки с номерами и;

клетки с номерами;

клетки с номерами.

Для минимизации функции алгебры логики, заданной в совершенной дизъюнктивной нормальной форме, с помощью матрицы Карно необходимо: подготовить матрицу Карно, вписав в клетки, соответствующие обязательным конституентам, единицы, объединить клетки с единицами в «подкубы», записать минимизированную функции алгебры логики в дизъюнктивной нормальной форме.

В «подкубы» объединяются:

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

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

Пусть необходимо минимизировать следующую функцию алгебры логики:

Матрица Карно, заполненная в соответствии с этой формулой, может быть представлена в виде таблицы 2:

Таблица 2. Матрица Карно

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

Метод Квайна

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

На первом этапе выполняется переход от функции, заданной в форме ДНФ, к сокращенной ДНФ. Суть метода заключается в последовательном выполнении всех возможных склеиваний и затем всех поглощений, что приводит к сокращенной ДНФ. Метод применим к совершенной ДНФ. Из соотношения поглощения следует, что произвольное элементарное произведение поглощается любой его частью. Для доказательства достаточно показать, что произвольная простая импликанта р = xi1 xi2 ... xin может быть получена. В самом деле, применяя к р операцию развертывания (обратную операции склеивания):

по всем недостающим переменным x ik , ..., xim исходной функции f, получаем совокупность S конституент единицы. При склеивании всех конституент из S получим импликанту р. Последнее очевидно, поскольку операция склеивания обратна операции развертывания. Множество S конституент обязательно присутствует в совершенной ДНФ функции f поскольку р - ее импликанта.

В результате выполнения склеивания получается конъюнкция n-1 ранга, а конъюнкции остаются в исходном выражении и участвуют в сравнении с другими членами СДНФ. Таким образом, удается снизить ранг термов.

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

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

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

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

f СДНФ = V (1,2,5,6,7)=x1 x2 x3 + x1 x2 x3 + x1 x2 x3 + x1 x2 x3 + x1 x2 x3

1 2 3 4 5

Выполним операцию склеивания:

1 - 3 (x1 ) x2 x3 1
2 - 4 (x1 ) x2 x3 2
3 - 5 (x2 ) x1 x3 3
4 - 5 (x3 ) x1 x2 4

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

f сокр СДНФ =x2 x3 + x2 x3 + x1 x3 + x1 x2

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

Таблица 3. Импликантная таблица

x 1 x2 x3	X 1 x2 x3	x 1 x2 x3	x 1 x2 x3	x 1 x2 x3

Простые импликанты являются обязательными так как только они покрывают конституэнтыи включаются в минимальное покрытие. Остается одна непокрытая конституэнта x1 x2 x3 которая может быть покрыта одной из двух оставшихся простых импликант. Это приводит к получению двух тупиковых форм.

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

Метод позволяет получать сокращенную ДНФ булевой функции f из ее произвольной ДНФ. Базируется на применении формулы обобщенного склеивания:

справедливость которой легко доказать. Действительно,

Следовательно,

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

Рассмотрим пример. Пусть булева функция f задана произвольной ДНФ.

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

Первый и третий элемент исходной ДНФ допускают обобщенное склеивание как по переменной х 1 , так и по х2 . После склеивания по x1 имеем:

После склеивания по x 2 имеем:

Второй и третий элемент ДНФ допускают обобщенное склеивание по переменной х 2 . После склеивания получаем:

Выполнив последнее обобщенное склеивание, приходим к ДНФ:

После выполнения поглощений получаем:

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

Минимизация не полностью определенных ФАЛ

Если при синтезе логической схемы, реализующей некоторую ФАЛ n переменных, окажется, что некоторые наборы из общего числа 2n никогда не смогут появиться на входах схемы, то данная логическая функция не определена на этих наборах. Тогда 2n наборов переменных можно подразделить на три группы: наборы, на которых функция принимает единичное значение L, нулевое значение D и группа наборов, на которых функция не определена N (неопределенные наборы). ФАЛ, содержащая неопределенные наборы, называется неполностью или частично определенной. Неопределенные наборы могут быть использованы для улучшения качества минимизации. При этом неопределенные наборы (при минимизации, например, картами Вейча, Карно) могут участвовать в образовании контуров как с единичными, так и с нулевыми наборами. Это приводит к формированию более простой минимизированной логической функции.

Универсальным методом минимизации является использование законов и соотношений алгебры логики, которые позволяют проводить минимизацию ФАЛ при любом числе переменных.