Допустимые и максимальные интервалы
КАДР
Глава 2. Минимизация ДНФ
Введение
Известно, что функция булевой алгебры (алгебры логики) может быть представлена множеством формул, даже если для их построения используются только элементарные функции. Среди формул особый интерес представляют дизъюнктивные нормальные формы, построенные без применения скобок на подмножестве элементарных функций: {Ú, Ù, 
}. Интерес к этим формулам объясняется, с одной стороны, простотой их вида, а с другой – возможностью для разработчика аппаратуры задавать в виде ДНФ поведение проектируемых устройств.
Функция 
, где 
= {0, 1}, называется функцией алгебры логики или булевой функцией.
Для отдельной функции в общем случае можно построить несколько ДНФ, отличающихся числом символов, образующих формулу. Под символом будем понимать переменную и ее знак инверсии. Переменную вместе со знаком инверсии часто называют буквой или литерой.
Введенная ранее совершенная дизъюнктивная нормальная форма, как правило, не является компактной формулой по сравнению с другими ДНФ, представляющими эту же функцию.
Например, мажоритарная функция, значения которой определяются значениями большинства ее аргументов, представляется следующей совершенной ДНФ:
Ú 
Ú 
Ú 
.
В то же время она может быть представлена в виде ДНФ:
Ú 
Ú 
.
Вторая формула содержит 6 символов переменных, а первая – 12.
|
|
|
При решении различных задач проектирования дискретных систем важно получать для булевых функций по возможности более компактные их представления в виде ДНФ. Теория ДНФ позволяет это делать.
КАДР
Для выяснения главной проблемы теории ДНФ введем ряд определений.
Определение. Элементарной конъюнкцией называется логическое произведение K = 
r переменных, в котором все 
различны. Число r называется рангом конъюнкции. При r = 0 конъюнкция полагается равной единице.
Определение. Дизъюнктивной нормальной формой называется дизъюнкция D = 
Ú…Ú 
элементарных конъюнкций 
, в которой все различны, j = 1,…, n. Число l называется длиной ДНФ. Для l = 0 ДНФ называется пустой и полагается равной 0.
Определение. Минимальной ДНФ функции f( 
,…, 
) называется ДНФ, реализующая f и содержащая наименьшее число символов переменных по сравнению со всеми другими ДНФ, реализующими эту функцию.
Определение. Кратчайшей ДНФ функции f( ,…, ) называется ДНФ, реализующая f и содержащая наименьшее число элементарных конъюнкций по сравнению со всеми другими ДНФ, реализующими эту функцию.
Главной проблемой теории ДНФ является проблема построения минимальных и кратчайших ДНФ для булевых функций.
|
|
|
Существует тривиальный алгоритм построения минимальной (кратчайшей) ДНФ для произвольной булевой функции.
Все ДНФ, составленные из символов переменных ,…, , 
,…, 
, упорядочиваются по числу символов переменных (числу конъюнкций), и для каждой ДНФ проверяется соотношение D = f( ,…, ).
Первая по порядку ДНФ, для которой это соотношение выполняется, есть минимальная (кратчайшая) ДНФ для функции f( ,…, ).
Этот алгоритм не применим на практике, так как уже для небольших значений n требует перебора огромного числа ДНФ.
Теорема 2.1. Число различных ДНФ функций, зависящих от n переменных, равно 
.
Доказательство. Число различных элементарных конъюнкций, составленных из n переменных, равно 
. Действительно, каждая из n переменных либо не входит в конъюнкцию, либо входит в нее с отрицанием, либо входит в нее без отрицания. Это значит, что всевозможных конъюнкций . В конкретную ДНФ каждая из конъюнкций либо входит, либо нет. Это значит, что число различных ДНФ функций, зависящих от n переменных, равно числу подмножеств множества из элементов: . Ч.Т.Д.
Из теоремы 2.1 следует, что число различных ДНФ от n переменных существенно больше числа ( 
) функций от n переменных.
КАДР
|
|
|
Геометрическая интерпретация
Для наглядности воспользуемся геометрическим представлением булевой функции. Множество всех наборов a = ( 
) переменных ,…, будем рассматривать как множество точек с 
Î{0,1} и обозначать как 
. Иными словами, – это множество всех вершин единичного n-мерного куба. Каждой функции f( ,…, ) поставим в соответствие подмножество 
вершин ( ) таких, что f( ) = 1.
Ограничимся значением n = 3. Построим 3-мерный единичный куб (рис. 2.1).
Рис. 2.1
Функция f представляется подмножеством = {101, 100, 110, 010, 111}, Î 
.
Выделим подмножества вершин, которым сопоставляются функции, представимые единственной конъюнкцией, и введем для них специальные обозначения.
КАДР
Интервалы и их свойства
Определение. Подмножество 
Î называется интервалом ранга r, если оно соответствует элементарной конъюнкции ранга r в том смысле, что на всех элементах этого подмножества и только на них конъюнкция k обращается в единицу.
Элементарной конъюнкцией называется логическое произведение K = = r переменных, в котором все различны. Число r называется рангом конъюнкции. При r = 0 конъюнкция полагается равной единице.
Пример. Пусть подмножество 
= {101, 100, 110, 111} сопоставляется конъюнкции 
= x, а подмножество 
= {110, 010} – конъюнкции = 
.
|
|
|
Рассмотрим основные свойства интервала.
1. Конъюнкции K = соответствует интервал , состоящий из всех вершин куба , у которых 
= 
,…, 
= 
, а значения остальных координат встречаются во всевозможных комбинациях.
2. Число элементов интервала равно 
, где r – ранг интервала.
Будем иметь в виду, что каждая вершина единичного n-мерного куба является интервалом n-го ранга, а множество всех вершин считается интервалом нулевого ранга.
Интервал r-го ранга геометрически представляет подмножество вершин единичного n-мерного куба, заполняющих его (n – r)-мерную грань.
КАДР
Допустимые и максимальные интервалы
О допустимых и максимальных интервалах говорят, когда задана некоторая булева функция, то есть известно множество , ее представляющее.
Определение. Интервал является допустимым для функции f( ), если для него выполняется условие Í . Сопоставляемая ему конъюнкция k называется допустимой конъюнкцией или импликантой функции f.
Определение. Интервал является максимальным для f( ), если он допустим, и не существует допустимого интервала 
такого, что Ì Í .
Сопоставляемая максимальному интервалу конъюнкция называется простой импликантой.
Приведенные выше интервалы , являются допустимыми и одновременно максимальными. Интервал 
= {111, 011} является недопустимым интервалом, а интервал 
= {100, 110} – допустимый, не максимальный интервал.
Свойства максимального интервала:
1. Исключим из простой импликанты k одну (любую) переменную, тогда полученная конъюнкция 
не является импликантой функции f, то есть сопоставляемый ей интервал не является допустимым для функции f. Очевидно, что конъюнкция поглощает конъюнкцию k: k £ .
2. Для всякого допустимого для функции f интервала, не являющегося максимальным, существует хотя бы один, объемлющий его максимальный интервал этой функции. Если 
– конъюнкция, сопоставляемая допустимому и не максимальному интервалу, а k – конъюнкция, сопоставляемая объемлющему максимальному интервалу, то £ k, причем содержит больше символов переменных, чем k.
Рассмотрим множество допустимых интервалов ,…, 
такое, что 
.
Будем говорить, что это множество интервалов образует покрытие интервалами.
Всякому покрытию множества интервалами соответствует ДНФ Ú…Ú 
функции f, составленная из конъюнкций, сопоставляемых интервалам этого покрытия. Следовательно, проблему поиска различных ДНФ функции f( ,…, ) можно свести к проблеме поиска покрытий допустимыми интервалами множества этой функции.
В примере (рис. 2.1) интервалы , образуют покрытие множества , им сопоставляется ДНФ: Ú 
.
Из свойства 2 максимального интервала следует, что множество всех максимальных интервалов образует покрытие множества .
Определение. ДНФ, сопоставляемая покрытию множества всеми максимальными интервалами, является сокращенной ДНФ функции f. Очевидно, что сокращенная ДНФ единственна для f.
Определение. Сокращенная ДНФ есть дизъюнкция всех простых импликант функции f.
Минимальной ДНФ соответствует покрытие множества допустимыми интервалами с минимальной суммой рангов этих интервалов.
Минимальной ДНФ функции f( ,…, ) называется ДНФ, реализующая f и содержащая наименьшее число символов переменных по сравнению со всеми другими ДНФ, реализующими эту функцию.
Кратчайшей ДНФ соответствует покрытие множества минимальным числом допустимых интервалов.
Кратчайшей ДНФ функции f( ,…, ) называется ДНФ, реализующая f и содержащая наименьшее число элементарных конъюнкций по сравнению со всеми другими ДНФ, реализующими эту функцию.
Из сказанного следует, что построение минимальных и кратчайших ДНФ можно свести к поиску соответствующих покрытий множества интервалами.
Покажем, что при этом можно ограничиться рассмотрением только максимальных интервалов.
Будем иметь в виду, что сокращенная ДНФ функции f в общем случае не является ни минимальной, ни кратчайшей ДНФ этой функции. Так, например, сокращенная ДНФ функции, представленной табл. 2.1, имеет вид 
Ú 
Ú 
Ú 
.
Таблица 2.1
| x | y | z | f |
| 0 | 0 | 0 | 1 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 |
А ее минимальная (она же кратчайшая) ДНФ есть Ú Ú .
КАДР
Связь между минимальными и кратчайшими ДНФ с сокращенной ДНФ устанавливается следующими теоремами.
ДНФ, сопоставляемая покрытию множества всеми максимальными интервалами, является сокращенной ДНФ функции f. Очевидно, что сокращенная ДНФ единственна для f.
Теорема 2.2. Минимальная ДНФ функции f( ,…, ) получается из сокращенной ДНФ этой функции путем выбрасывания некоторых конъюнкций.
Доказательство. Из приведенного выше примера ясно, что минимальная ДНФ может быть получена из сокращенной ДНФ путем выбрасывания некоторых конъюнкций. Покажем, что минимальная ДНФ состоит только из простых импликант. Действительно, если бы минимальная ДНФ содержала импликанту, не являющуюся простой, то ее можно было бы заменить поглощающей простой импликантой, сократив тем самым число символов переменных в ДНФ. Последнее противоречит условию минимальности ДНФ. Ч.Т.Д.
Кратчайшая ДНФ не обязательно состоит из простых импликант. Например, ДНФ 
и 
являются кратчайшими ДНФ одной и той же булевой функции:
= x Ú y, = 
Ú y.
Однако в ДНФ конъюнкция не является простой импликантой.
Теорема 2.3. Кратчайшая ДНФ функции f( ,…, ) может быть получена из сокращенной ДНФ этой функции путем выбрасывания некоторых конъюнкций.
Доказательство. Рассмотрим произвольную кратчайшую ДНФ. Если некоторая ее конъюнкция k не является простой импликантой, то ее можно заменить поглощающей простой импликантой . Поступим так со всеми импликантами сокращенной ДНФ, не являющимися простыми. В результате получим сокращенную ДНФ, состоящую только из простых импликант. Ч.Т.Д.
В дальнейшем будем рассматривать кратчайшие ДНФ, состоящие только из простых импликант.
Из теорем 2.2, 2.3 следует, что для получения минимальных и кратчайших ДНФ достаточно ограничиться рассмотрением всех простых импликант, игнорируя допустимые конъюнкции, не являющиеся простыми импликантами. Это значит, что необходимо уметь находить простые импликанты, желательно всевозможные. Все простые импликанты содержатся в сокращенной ДНФ. Методы ее построения ориентированы на способы представления булевой функции.
Прежде чем перейти к изложению некоторых из них, отметим, что сокращенные ДНФ могут быть достаточно сложными выражениями для функций большого числа переменных, порядка 20 и более. Компьютерные эксперименты, проведенные С.В. Быковой, показали, что для таких функций сокращенная ДНФ по числу символов переменных может превосходить совершенную ДНФ этой же функции. На практике функции указанного числа переменных встречаются довольно часто. В этом случае не имеет смысла строить сокращенную ДНФ целиком, приходится ограничиваться подмножествами ее простых импликант.
КАДР
Дата добавления: 2018-02-18; просмотров: 2947; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!