Министерство Образования И Науки РФ

Федеральное Агентство По Образованию РФ

Санкт-Петербургский Государственный Политехнический Университет

Физико – Механический Факультет

Прикладная Математика.

Реферат

Булевы функции: Минимизация формул.

Выполнил:

группа 2057/3

Проверил:

ст. преподаватель

Санкт – Петербург 2010

Оглавление

Оглавление. 2

Введение. 3

Постановка задачи. 4

1. Упрощение дизъюнктивных нормальных форм.. 4

1.1 Локальные методы упрощения ДНФ.. 4

1.2 Устранение избыточности в ДНФ.. 4

1.3 Удаление избыточных элементарных конъюнкций. 4

1.4 Удаление избыточных букв элементарных конъюнкций. 4

1.5 Получение безызбыточной ДНФ.. 4

2. Минимизация ДНФ: метод Квайна – МакКласки. 4

2.1 Сокращённые и минимальные дизъюнктивные нормальные формы.. 4

2.2 Получение множества всех простых импликант. 4

Заключение. 4

Список литературы.. 4

Введение

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

Безымянный.jpg

Рис. 1. Задача синтеза для функции

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

НЕ нашли? Не то? Что вы ищете?

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

построении быстродействующих сетей. Базовым методом Интернет - маршрутизации является сопоставление по наиболее длинному префиксу. Каждая запись таблицы маршрутизации содержит префикс узла назначения и соответствующий ему узел, на который необходимо отправлять трафик. Одному адресу назначения может соответствовать несколько записей в таблице – выбирается же из них та, которая имеет наиболее длинную маску подсети.

В настоящее время существует ряд программных и аппаратных методик повышения скорости поиска в таблицах маршрутизации. Общим недостатком алгоритмических подходов является то, что они требуют нескольких обращений к памяти. Требования к производительности современных сетей являются очень высокими, в то время как время отклика современных архитектур памяти ограничивают возможное количество обращений к памяти. Среди аппаратных средств можно выделить два основных решения – это специализированные интегральные схемы (ASIC) и контентно – адресуемая память (CAM). При этом наибольшее распространение получила именно CAM.

Главной особенностью CAM является то, что адресация осуществляется на основе содержания данных, поиск нужной записи, при этом, может быть осуществлен за одно обращение к памяти. В каждой позиции CAM может быть только 0 или 1. CAM поддерживают только сравнения образцов с фиксированной длиной и, следовательно, в явном виде не подходят для поиска префиксов. Для построения таблиц маршрутизации, как правило, используется тернарная контентно - адресуемая память (TCAM). Помимо индекса, TCAM хранят также отдельную маску для каждой записи. Маска определяет, какие из битов индекса являются активными. Основным недостатком TCAM является высокая стоимость и большое энергопотребление. При этом потребляемая мощность пропорциональна количеству записей, хранимых в ТМ.

Сжатие таблиц маршрутизации позволяет повысить скорость поиска нужной записи, а также использовать память меньшего размера. Методы

Запись

Префикс

Маска

Следующий узел

1

1

2

1

3

2

4

3

5

2

Таблица 1. Таблица префиксов в TCAM

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

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

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

Постановка задачи

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

и

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

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

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

1. Упрощение дизъюнктивных нормальных форм

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

1) Поглощение определяется формулой

x ∨ xy = x

2) Склеивание определяется формулой

3) Удаление литерала производится по формуле

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

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

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

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

Её матричное представление будет следующим:

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

ДНФ безызбыточна, если из неё нельзя удалить ни одной элементарной конъюнкции и ни одной буквы в какой-либо конъюнкции. В матричной интерпретации троичная матрица U (представляющая ДНФ) безызбыточна, если из неё нельзя удалить ни одной строки и нет такого элемента в матрице, обладающего значение 0 или 1, чтобы это значение можно было заменить на « - », получив при этом матрицу, эквивалентную исходной.

Введём две операции упрощения ДНФ и троичной матрицы U, основанные на вышеприведённых определениях:

- удаление элементарной конъюнкции и соответственно выбрасывание строки матрицы U;

- удаление буквы из элементарной конъюнкции и соответственно замена значения 0 или 1 элемента матрицы U на « - ».

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

Условие возможности удаления элементарной конъюнкции. Рассмотрим ДНФ D = , представляющую функцию f(). Выделим из неё элементарную конъюнкцию , представив ДНФ в виде D = , где - дизъюнкция остальных членов ДНФ D.

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

,

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

Множество всех наборов в пространстве переменных , на которых , образуют интервал I(), в котором переменные, входящие в под знаком отрицания, принимают значение 0; переменные, входящие в без знака отрицания, принимают значение 1, а значение остальных переменных остаются произвольными.

Обозначим через : результат подстановки в ДНФ таких значений переменных из конъюнкций , которые обращают в единицу.

ДНФ должна принять значений 1 на любом наборе из I( вне зависимости от значений переменных, не входящих в конъюнкцию . Отсюда следует, что необходимым и достаточным условием выполнения условия является тождество

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

Получение ДНФ : сводится к выделению из матрицы U минора, получаемого путём удаления строки u и всех ортогональных ей строк, в также столбцов, в которых строка u имеет значение, отличное от « - ».

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

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

Действительно, если этот минор не вырожден, то найдётся некоторый ортогональный ему булев вектор. Заменив значениями его компонент значения « - » соответствующих компонент строки u, получим булев вектор, поглощаемый строкой u и не поглощаемый более ни одной другой строкой матрицы U. Очевидно, что в этом случае строку u выбрасывать нельзя. Если же минор вырожден, то такого булева вектора не существует.

Рассмотрим ДНФ D= и одну из её элементарных конъюнкций , включающую букву . Эту ДНФ можно представить в виде D=. Удаление буквы из конъюнкции превращает её в конъюнкцию . Это действие эквивалентно добавлению в ДНФ D конъюнкции (так как = ). В результате ДНФ D превращается в

D=

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

Таким образом, из элементарной конъюнкции ДНФ D можно исключить букву , если элементарная конъюнкция имплицирует ДНФ D, а точнее, дизъюнкцию :

⇒

Видно, что проверка возможности удаления буквы в элементарной конъюнкции такая же, как и проверка возможности удаления всей конъюнкции. Она сводится к проверке соотношения импликации между элементарной конъюнкцией , с одной стороны, и ДНФ D, с другой стороны. Это отношение представляется тождеством

=1

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

=1

Матричная интерпретация. Пусть ДНФ представляется троичной матрицей U, a элементарная конъюнкция – некоторой её строкой . Исключение буквы из конъюнкции сводится к смене значения элемента матрицы U с 0 или 1 на « - ». Такая смена значения компоненты j строкой матрицы U эквивалентна добавлению в матрицу строки , соседней по этой компоненте и выполнению операции склеивания строк и . Это возможно, если представляемая U булева функция при этом не изменится, что выполняется в том случае. если любой булев вектор, поглощаемый строкой, соседней по компоненте j, поглощается в то же время ещё какой-то строкой матрицы U. Строками – кандидатами на поглощение булевых векторов, порождаемых строкой , являются строки, неортогональные .

Аналогично рассуждая, строим минор матрицы U, представляющий ДНФ : либо : . Для этого:

1) рассматривая строки матрицы U, кроме , выбираем из них неортогональные строке ;

2) из полученного строчного минора исключаем столбцы, в которых строка имеет значение, отличное от « - ».

Проверка условия =1 либо =1 сводится к проверке полученного минора на вырожденность.

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

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

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

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

2. Минимизация ДНФ: метод Квайна – МакКласки

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

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

Импликанты булевой функции. Булева функция g() называется импликантой булевой функции

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

g() ⇒ f()

Отношение импликации транзитивно (соответственно и отношение «быть импликантой»), т. е. если

g() ⇒ h() и h() ⇒ f(), то и g() ⇒ f()

Если при этом g() ≠ h(), то можно сказать, что функция h() ближе к функции f(), чем функция g().

Учитывая эквивалентность отношений g() ⇒ f() и , можно подсчитать число различных, импликант заданной функции f(): оно оказывается равным , где т = ||. Одной из этих импликант оказывается сама функция f().

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

Из определения формальной импликации следует, что если g() ⇒ f() и h() ⇒ f(), то и g() h() ⇒ f().

Отсюда справедливы, следующие утверждения.

1) Дизъюнкция любого множества импликант булевой функции так­же является импликантой этой функций, т. е. если g() и h() являются импликантами функции f(), то g() h() - также импликанта функции f().

2) Дизъюнкция всех импликант булевой функции совпадает с этой функцией.

3) Дизъюнкция всех простых импликант булевой функции совпада­ет с этой функцией.

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

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

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

Справедливы следующие утверждения.

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

2) Булева функция может иметь несколько различных кратчайших и минимальных ДНФ.

3) Существуют безызбыточные ДНФ, не являющиеся ни кратчай­шими, ни минимальными.

4) Существуют кратчайшие ДНФ, не являющиеся минимальными.

5) Существуют кратчайшие ДНФ, которые не являются безызбы­точными: не все члены этих ДНФ простые импликанты.

Метод Квайна - МакКласки. Этот метод нахождения множества всех простых импликант был предложен первоначально Квайном и усовершенствован МакКласки. Метод предполагает, что функция f задана первоначально в виде совершенной ДНФ, составленной из пол­ных элементарных конъюнкций, каждая из которых содержит символы всех переменных. Такую форму легко получить из таблицы значений функции f, поскольку каждый член совершенной ДНФ соответствует некоторому набору значений аргументов, на котором функция f при­нимает значение 1. При матричном представлении совершенной ДНФ эти наборы будут непосредственно заданы строками матрицы.

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

Операции склеивания (полного) по пере­менной х и поглощения"(24.1) определяются формулами

∨ x = x,

где — элементарная конъюнкция.

Применяемая в методе Квайна операция неполного склеивания определяется формулой

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

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

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

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

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

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

3) Переход от ДНФ к ДНФ (n = 1, 2, ... , p) производится по следующему правилу: в форме выполняются все операции неполного склеивания, применимые к элементарным конъюнк­циям ранга n - i, после чего исключаются все элементарные конъюнкции ранга n - i, к которым применима операция элемен­тарного поглощения.

4) Результатом применения алгоритма Квайна к совершенной ДНФ является сокращенная ДНФ булевой функции .

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

Заключение

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

Список литературы

, Дискретная математика. М.: Издательский центр «Академия», 2008. – 448 с.

, Применение методов минимизации булевых функций

для оптимизации цифровых устройств. Известия Самарского научного центра Российской академии наук, т. 11, №3(2), 2009

, , Логические основы проектирования дискретных устройств. М.: «Физматлит», 2007. – 592 с.

Дискретная математика. Курс лекций. М.: «Эксмо», 2008. – 352 с.

Введение в дискретную математику. М.: «Высшая школа», 2008 – 384 с.

Олдридж X., Силверман Дж., Применение интегральных схем: Практическое руководство. М.: «Мир», 1987 – 432 c.

Основы теоретической логики. М.: Государственное издательство иностранной литературы, 1947 – 302 с.

Дискретная математика. Математика для менеджера в

примерах и упражнениях: Учебное пособие. М.: «Логос», 2000. – 240 с.

Дискретная математика для программистов. СПб: «Питер»,

2009. – 384 с.