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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

29
следовательным применением законов ассоциативности, коммутативно-
сти и склеивания:
32132132321321321321
)()()()( xxxxxxxxxxxxxxxxxxxx =∨=∨=∨
.
Единичный интервал булевой функции I
α
∈ I называется максималь-
ным единичным интервалом, если не найдётся другого единичного ин-
тервала большей размерности I
β
∈ I этой функции, содержащего интер-
вал I
α
. Например, единичные интервалы −
00, 1− 0, 11−, −11 являются
максимальными, поскольку в гиперкубе отсутствуют грани, содержащие
соответствующие рёбра (см. рис. 14). Но интервалы 000, 100, 110, 111,
011 нельзя считать максимальными единичными интервалами, поскольку
каждая из соответствующих вершин гиперкуба содержится по крайней
мере в одном ребре. Заметим, что в схеме на рис. 15 из максимальных
единичных интервалов не выходят стрелки, т.е. они не содержатся в еди-
ничных интервалах большей размерности.
Максимальные единичные интервалы образуют множество макси-
мальных единичных интервалов I
max
. Конъюнкция, соответствующая мак-
симальному единичному интервалу булевой функции, называется про-
стой импликантой этой функции, а дизъюнкция простых импликант
представляет её сокращённую ДНФ. В рассматриваемом примере множе-
ство I
max
состоит из четырёх рёбер:
I
max
= {−
00, 1
−
0, 11
−, −
11},
а сокращённая ДНФ имеет следующий вид:
f
s
(x
1
, x
2
, x
3
) =
32213132
xxxxxxxx ∨∨∨
.
Получением сокращённой ДНФ булевой функции заканчивается
первый этап метода импликантных таблиц. Заметим, что на этом этапе
сложность представления булевой функции f (x
1
, x
2
, x
3
) |
1
= ∨ (0, 3, 4, 6, 7)
в классе ДНФ уменьшилась от 15 до 8.
Этап 2. Получение тупиковых ДНФ булевой функции и выбор из них
минимальной ДНФ.
Тупиковой ДНФ булевой функции f (x
1
, x
2
, ..., x
n
) называется такая её
ДНФ, которая при вычёркивании хотя бы одного первичного терма не
определяет функцию f. Заметим, что минимальная ДНФ булевой функции
является тупиковой ДНФ.
Покрытием столбцов строками в двумерной таблице называется
такое множество строк, при котором для каждого столбца найдётся хотя
бы одна строка, на пересечении с которой этот столбец имеет единицу, а
при исключении хотя бы одного элемента из этого множества строк ука-
занное свойство не выполняется.
Построение тупиковых ДНФ булевой функции сводится к покрытию
столбцов строками в таблице Квайна.

Страницы