2.2. Геометрическая интерпретация
Для
наглядности воспользуемся геометрическим
представлением булевой функции. Множество
всех наборов
= (
)
переменных
,…,
будем рассматривать как множество точек
с
{0,1}
и обозначать как
.
Иными словами,
– это множество всех вершин единичного
n-мерного
куба. Каждой функции f(
,…,
)
поставим в соответствие подмножество
вершин (
)
таких, что f(
)
= 1.
Ограничимся значением n = 3. Построим 3-мерный единичный куб (рис. 2.1).
Рис. 2.1
Функция
f
представляется подмножеством
= {101, 100, 110, 010, 111},
.
Выделим подмножества вершин, которым сопоставляются функции, представимые единственной конъюнкцией, и введем для них специальные обозначения.
КАДР
2.2.1. Интервалы и их свойства
Определение.
Подмножество
называется интервалом ранга 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)-мерную грань.
КАДР
2.2.2. Допустимые и максимальные интервалы
О допустимых и максимальных интервалах говорят, когда задана некоторая булева функция, то есть известно множество , ее представляющее.
Определение. Интервал является допустимым для функции 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 и более. Компьютерные эксперименты, проведенные С.В. Быковой, показали, что для таких функций сокращенная ДНФ по числу символов переменных может превосходить совершенную ДНФ этой же функции. На практике функции указанного числа переменных встречаются довольно часто. В этом случае не имеет смысла строить сокращенную ДНФ целиком, приходится ограничиваться подмножествами ее простых импликант.
КАДР