Минимизация булевых функций
 Скачать 0.5 Mb.
|
|
Минимизация булевых функций. Совершенные нормальные формы записи логических функций дают однозначное представление логических функций, но иногда являются очень громоздкими. Поэтому для булевых функций, представленных в виде СДНФ или СКНФ, возникает задача минимизации. Индексом простоты (или сложностью) булевой функции называется функция  , определенная на множестве всех ДНФ и удовлетворяющая следующим свойствам:
Примеры. 1)  - число букв переменных, встречающихся в записи  . Под буквой понимают символ переменной или ее отрицание, если переменная  входит в формулу m раз, то говорят, что формула содержит m букв . Например в выражении  число переменных равно 3, а число букв равно 5, т.е. число букв равно числу вхождений переменных. 2)  - число элементарных конъюнкций, входящих в .3)  - число символов отрицаний, встречающихся в записи . Каждый из указанных индексов удовлетворяет перечисленным свойствам. Пример. Пусть  задана вектором состояний. Тогда для нее может быть записана СДНФ в виде Эту функцию можно упростить  Вычислим индексы простоты для  и  . ,  ; ,  ; , .Следовательно, проще для всех трех индексов простоты.Задача минимизации заданной логической функции сводится к представлению ее дизъюнктивной (или конъюнктивной) нормальной формой, имеющей наименьший индекс простоты. В качестве индекса простоты наиболее часто используется индекс .Пример.   Построение сокращенной ДНФ методом Блейка. Сокращенной д.н.ф. функции  называется функция, которая содержит меньшее число букв, чем СДНФ. Если над СДНФ произвести все возможные операции склеивания, а затем все возможные операции поглощения то полученная функция будет иметь вид сокращенной ДНФ. В основе использования метода Блейка лежат операции склеивания и операции поглощения. Законы поглощения  ,   ,   ,    Отметим, что формулы во втором столбце получаются из формул первого столбца с помощью принципа двойственности. Закон склеивания (объединения конъюнкций):  .Закон обобщенного склеивания:  .Пример. Получить сокращенную ДНФ методом Блейка 1)  . Минимизация булевых функций методом Квайна– Мак-Класки. Импликантой  функции  называется конъюнкция некоторых аргументов из набора  и их отрицаний, обладающая следующими свойствами:1) Если на некотором наборе импликанта  принимает значение 1, то и принимает на этом наборе значение 1.2 При исключении хотя бы одного множителя из свойство 1) не выполняется.Пример.   на наборах (0,0,0), (0,0,1), (0,1,1). Рассмотрим  .  на наборах (0,0,0), (0,0,1). На этих наборах , т.е. выполняется условие 1). Если вычеркнуть один множитель из и оставить, например,  , то. принимает значение 1 на наборах (0 0 0), (0 0 1), (0 1 0), (0 11), причем на выделенном наборе  . Аналогичным образом ,  принимает значение 1, причем на выделенных наборах . Следовательно, при вычеркивании одного множителя у свойство 1) не выполняется. Это означает, что является импликантой функции. Пусть на некотором наборе  функция обращается в 1. Если на этом наборе импликанта функции обращается в 1, то говорят, что импликанта накрывает эту единицу функции . Система импликант функции называется полной, если любая единица из таблицы значений функции накрывается хотя бы одной импликантой. Сокращенной ДНФ функции называется дизъюнкция всех импликант из полной системы импликант. Утверждение. Сокращенная ДНФ. функции совпадает с самой функцией.Действительно, дизъюнкция всех импликант из полной системы импликант равна 1 на тех наборах, где равна 1 функция ( в соответствии с определением импликанты  ) и равна нулю на тех наборах, где равна нулю функция, т.е. значения сокращенной д.н.ф. функции и функции совпадают.Сокращенная д.н.ф. функции содержит меньшее число букв, чем СДНФ Однако, во многих случаях допускается дальнейшее сокращение числа букв за счет того, что некоторые из импликант могут поглощаться дизъюнкциями других импликант. Система импликант функции называется приведенной, если эта система полна, а никакая ее часть не является полной системой импликант функции . Тупиковой ДНФ называется дизъюнкция всех импликант, составляющих приведенную систему. Тупиковая ДНФ- выражение, полученное из сокращенной ДНФ, дальнейшее упрощение которого невозможно в рамках ДНФ. Минимальной ДНФ называется тупиковая ДНФ, состоящая из наименьшего числа букв. Одна и та же сокращенная ДНФ может иметь несколько тупиковых ДНФ и несколько минимальных ДНФ. Процесс минимизации на первом этапе сводится к построению полной системы импликант, затем приведенной системы существенных импликант, из которых строится сокращенная ДНФ, затем строятся тупиковые ДНФ и затем уже выбирается минимальная ДНФ. Решение задачи осуществляется в соответствии со схемой  Получение сокращенной ДНФ (нахождение импликантов функции ). Пример 1.    Получение сокращенной ДНФ основывается на законе склеивания  . Из него следует, что можно склеивать или объединять минтермы, отличающиеся только одним сомножителем. Будем склеивать не минтермы, а наборы. Выпишем все наборы переменных, соответствующие минтермам, входящим в разложение функции, в столбик, разбивая их на группы так, чтобы в каждую группу входили наборы с одинаковым числом единиц.
Проводим попарное склеивание наборов из соседних групп (для склеивания наборы должны отличаться на одну переменную). При склеивании общие элементы сохраняются, а элементы, которыми различаются наборы, заменяются чертой. Наборы, участвующие в склеивании, помечаются *. В результате образуется второй столбец, к которому также применяется операция склеивания. При этом склеивают наборы из соседних групп с одинаковым положением черточек. Далее образуется 3-й столбец и т.д. Процесс продолжается до тех пор, пока склеивание возможно.Импликантами функции будут наборы во всех столбцах, не участвующие в склеивании (не помеченные). ,  ,  ,  ,  ,  .Сокращенная ДНФ  , ее длина составляет 17 букв На рис. изображены импликанты и склеиваемые наборы переменных. Отметим, что на рисунке номера наборов приведены в восьмеричной системе счисления. 2. Следующий этап – построение тупиковой ДНФ. Для этого нужно составить импликантную таблицу. Строки этой таблицы обозначены импликантами функции, а столбцы минтермами функции. Каждая импликанта является частью какого-нибудь дизъюнктивного члена в СДНФ и обращается в единицу на том же наборе, что и соответствующий минтерм. На пересечении строки, в которой записана импликанта, и столбцов соответствующих минтермов, частью которых является импликанта, поставим крестики. Тупиковые формы являются дизъюнкциями тех импликантов, которые накрывают все минтермы, т.е. в таблице нужно выбрать такие строки, чтобы во всех столбцах был как минимум один плюс. Чтобы построить тупиковую форму, нужно выбрать минимальное число строк, покрывающих крестиками все столбцы. Ясно, что в систему выбранных строк должны обязательно входить строки, содержащие плюсы, которые являются единственными в столбце. Такие строки называются базисными. Простые импликанты, стоящие в базисных строках, образуют ядро рассматриваемой функции. Обведем кружочками плюсы в строках, соответствующих этим импликантам. Из оставшихся импликант выбираем минимальное число таких, которые покрывают крестиками все свободные столбцы (т.е. те, которые не содержат  ).Импликантная таблица
В тупиковую ДНФ обязательно должна входить  , иначе первые два столбца не накрываются. Следовательно, первая строка является базисной, а импликанта образует ядро функции. При таком выборе автоматически накрываются и еще два столбца . Тупиковыми импликантами являются ( 8) (11) (11) (11) (11) (11) (11)На рисунке изображены все тупиковые ДНФ:  Среди всех тупиковых ДНФ выбираем ДНФ наименьшей длины: МДНФ:  Матричный метод Карно. Матричный метод основан на некоторых геометрических построениях. Соотношение между двоичными переменными можно представить в наглядной геометрической форме. Рассмотрим логическую функцию двух переменных. Все четыре конъюнкции двух двоичных переменных (члены СДНФ) могут быть изображены на плоскости в виде точек с координатами 00,01,10,11, где первая цифра соответствует переменной , а вторая – переменной  . Эти точки можно соединить линиями и полученный в результате квадрат будет наглядно изображать члены СДНФ двух переменных.  Координаты вершин квадрата, выраженные двоичными числами, соответствуют двоичным номерам конъюнкций.: 00 сответствует  , 01 -  , 10 - , 11 -  . Координаты соседних вершин отличаются только одним двоичным знаком и, следовательно, минтермы, соответствующие этим числам, отличаются только одной переменной. Если объединить члены, соответствующие двум различным вершинам, то эта переменная будет исключена. Например, сложив минтермы и , изображаемые вершинами 00 и 01, получим = . Ту же операцию исключения переменной можно выполнить, сравнивая непосредственно два двоичных числа 00 и 01.В первом разряде двоичные знаки у обоих чисел одинаковы, поэтому в объединении ставим 0, во втором разряде знаки различны, поэтому во втором разряде ставим черту.  Число 0 соответствует переменной . Черта указывает, что исключена переменная . Следовательно, если два двоичных числа отличаются двоичными цифрами только в одном разряде, то их можно заменить двоичным числом, у которого в этом разряде можно поставить черточку. Черточка указывает номер исключенной переменной. Линия, соединяющая вершины 00 и 01 может быть названа линией . Геометрической моделью функции трех переменных может служить трехмерный куб, вершины которого соответствуют членам СДНФ. Координаты соседних вершин отличаются, как и в случае плоской модели, только одним двоичным знаком, а соответствующие члены только одной переменной. Вследствие этого линии, соединяющие соседние вершины куба можно обозначить двумя переменными, которые на этой линии не меняют свое значение, а грани куба – одной переменной.  Соединение двух соседних вершин линией позволяет исключить одну переменную, причем это исключение можно выполнить, сравнив двоичные обозначения вершин. Например, сравнивая 011 и 111, получим  , что соответствует операции сложения конъюнкций  Точно также соединение линиями 4 вершин, лежащих на одной грани, позволяет исключить две переменные. Действительно, сравнив 011 с 111 и 001 с 101, получим   Вначале была исключена переменная , а затем переменная  .В результате осталась одна переменная  .Для функции четырех переменных геометрической моделью является четырехмерный куб. Однако изобразить его на плоскости невозможно и использовать для минимизации сложно. Более удобной для минимизации является карта Карно. Карта Карно построена так, что два соседних столбца (строки) отличаются одним знаком. Любая конъюнкция четырех переменных изображается на карте одной клеткой, находящейся на пересечении строки и столбца, обозначения которых образуют двоичный номер конъюнкции. Конъюнкции, соответствующие соседним клеткам, отличаются только одной переменной. Соседними на карте Карно являются не только клетки, находящиеся внутри карты, но и на концах каждой строки и каждого столбца. Любая функция может быть задана на матрице единицами в клетках, соответствующих входящим в СДНФ конъюнкциям – минтермам, и нулями в остальных клетках, которые можно не записывать. Например, функция  имеет единицы в клетках 0000, 0001,1100, 1101. Четыре минтерма можно сгруппировать по два, объединив для этого соседние минтермы. Объединенные минтермы обводятся замкнутыми линиями. В результате функция приводится к сумме двух конъюнкций трех переменных.   В результате минимизации получим функцию  .Преобразования, выполненные на карте Карно, соответствуют следующим алгебраическим преобразованиям  Будем называть конфигурации, образованные соседними заполненными клетками, подквадратами. Подквадрат – набор клеток, в которых одна или несколько переменных имеют постоянное значение. Так, по карте четырех переменных для двухклеточного квадрата характерно то, что в нем три переменные постоянны, а четвертая принимает оба своих значения. Для четырехклеточного подквадрата постоянны две переменные, а две другие принимают все четыре возможные комбинации значений. Объединяя две соседние клетки, мы тем самым будем исключать одну переменную, объединяя четыре соседних клетки, исключаем две переменных, объединяя восемь соседних клеток, - исключаем три переменных. (Это справедливо в том случае, когда форма подквадрата является прямоугольной или квадратной). В подквадраты можно объединять клетки, находящиеся на разных концах строки или столбца.Пример. 2. Пусть функция  задана картой Карно.     2.. Пусть функция задана картой Карно.    В результате минимизации получится функция  3.. Пусть функция задана картой Карно. Здесь имеется два четырехклеточных подквадрата.   В результате получится функция  Эту задачу можно решить иначе, если рассматривать один восьмиклеточный подквадрат   Отсюда сразу получается результат  , Таким образом, задача минимизации сводится к геометрической задаче отыскания правильных конфигураций. При использовании карты Карно нужно стремиться объединить единичные клетки в подквадраты с возможно большим числом клеток, чтобы количество подквадратов было как можно меньше. При решении задачи таким способом могут получиться объединения клеток в одинаковое число подквадратов с одним и тем же числом клеток. Каждый из таких вариантов будет соответствовать одной из минимальных форм функции. Следует отметить, что не всегда матричный метод оказывается эффективным. Пусть, например нужно минимизировать функцию Карта Карно в этом случае имеет вид  Размещение единиц здесь таково, что их нельзя объединить в подквадраты. В то же время функцию легко минимизировать методом Блейка.  С помощью матрицы Карно можно найти минимальное выражение для функции не только в дизъюнктивной форме, но и в конъюктивной форме. Для этого в карте Карно необходимо выбирать подквадраты из нулей, а не из единиц и помнить о том, что в этом случае 0x, а 1  . Пример. Найти минимальную функцию в к.н.ф, если  .Составим  , она содержит в СДНФ конъюнкции, которых нет в СДНФ функции . Они соответствуют тем клеткам матрицы, которых стоит 0  .  Отсюда получим = . Найдем теперь отрицание от левой и правой частей этого равенства. В результате получим  Полученное выражение является минимальной КНФ. Матричный метод является наиболее эффективным при решении задачи минимизации функций четырех переменных. Для большего числа переменных его использовать затруднительно. При пяти и шести переменных приходится прибегать к некоторым преобразованиям функции для того, чтобы в дальнейшем можно было использовать матричный метод. Например, если имеется функция пяти переменных, то можно вынести за одну скобку некоторую переменную, а за вторую скобку ее отрицание. Тогда внутри скобок окажется функция четырех переменных, которую можно минимизировать матричным методом. Пример.         :    :   Минимизация частично определенных булевых функций. В реальных задачах очень часто бывает так, что значение булевой функции на некоторых наборах не определено и может доопределяться произвольно. В этом случае доопределение функции было бы целесообразно производить таким образом, чтобы ее минимальная нормальная форма имела наименьшее число букв из всех возможных вариантов доопределения. Рассмотрим простой пример. Пусть функция задана картой Карно или диаграммой Вейча, представленных соответственно таблицами  Эту функцию можно доопределить на неопределенных наборах единицами или нулями Это приводит к разным минимальным ДНФ. Однако более простая минимальная ДНФ получается, если произвести доопределение так, как это сделано на следующей диаграмме Вейча Алгоритм поиска минимальной ДНФ частично определенной функции можно представить следующим образом 1) Найти любым известным способом сокращенную ДНФ функции, получающейся доопределением единицами исходной функции на всех неопределенных наборах.2) Выбрать минимальную ДНФ по импликантной матрице, где в столбцах выписаны лишь те минтермы (конституенты единицы) функции , которые соответствуют полностью определенным единичным наборам.Аналогичный алгоритм (с доопределением нулевыми наборами) может быть предложен для поиска КНФ. При этом доопределение таблицы значений функции может быть произведено по разному для КНФ и ДНФ. Заметим, что для решения рассматриваемой задачи практически достаточно тех навыков, которые были получены при минимизации полностью определенных булевых функций непосредственно по карте Карно.  |
;
, где 
-элементарная конъюнкция, 
.
путем переименования переменных без отождествления, то 
.
)9 *
10 *
)12 *
)11 *
) 13 *
14 *
10–1
1–10
110–
11–0