Дискретная математика. Громов Ю.Ю - 28 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

28
Этап 1. Выделение максимальных единичных интервалов и построе-
ние сокращённой ДНФ булевой функции.
Под единичным интервалом булевой функции понимается множест-
во двоичных наборов, на которых функция принимает значение 1 и кото-
рые образуют гиперкуб некоторой размерности. Мощность единичного
интервала может быть равна степени числа 2. Так, интервал мощности 2
0
представляет собой гиперкуб размерности 0 (вершину), интервал мощно-
сти 2
1
− гиперкуб размерности 1 (ребро), мощности 2
2
− гиперкуб раз-
мерности 2 (грань) и т.д.
Единичные интервалы булевой функции образуют множество еди-
ничных интервалов I. Множество единичных интервалов для рассматри-
ваемого примера будет содержать пять вершин и четыре ребра:
I = {000, 100, 110, 111, 011, −
00, 1
−
0, 11
−, −
11}.
При этом вершины из множества I в гиперкубе на рис. 14 заштрихованы,
а рёбра отмечены толстой линией.
Выявление всех единичных интервалов булевой функции f (x
1
, x
2
,
..., x
n
) возможно и без представления её с помощью гиперкуба, что осо-
бенно актуально для больших значений n. Для этого выписывают еди-
ничные интервалы нулевой размерности (вершины), разбивая их на пояса
так, что в некотором i-м поясе будут содержаться интервалы с i единица-
ми в каждом из них. Затем попарно сравнивают элементы из соседних
поясов и для каждой пары интервалов, отличающихся только в одном
разряде, записывают единичный интервал размерности 1 (ребро). Полу-
ченные единичные интервалы также разбивают на пояса и выявляют ин-
тервалы размерности 2 (грани), каждая из которых образуется двумя па-
рами противоположных рёбер. Описанную процедуру продолжают до тех
пор, пока не прекратится образование новых единичных интервалов.
На рисунке 15 изображена схема выявления всех единичных интер-
валов для рассматриваемого примера.
Здесь и далее, если в некотором разряде единичного интервала раз-
мещён символ «−», то соответствующая этому разряду переменная в
конъюнкции отсутствует. Например, ребру «−00» соответствует конъ-
юнкция
32
xx
, в которой отсутствует переменная x
1
.
Заметим, что исключение пере-
менной из конъюнкции происходит в
результате склеивания. Так, например,
множество вершин {000, 100} образует
ребро «−00», что соответствует преоб-
разованию дизъюнкции соответствую-
щих этим вершинам конъюнкций с по-
000
100
110
011
111
−00
1−0
11−
−11
Рис. 15

Страницы