Дискретная математика. Кулаков Ю.В - 23 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

f (x
1
, x
2
, x
3
) =
321321321321
&&&&&&&& xxxxxxxxxxxx ∨∨∨ .
Знак операции конъюнкция & обычно опускают:
f (x
1
, x
2
, x
3
) =
321321321321
xxxxxxxxxxxx ∨∨∨ .
В дальнейшем представление булевой функции f (x
1
, x
2
, ..., x
n
) в виде дизъюнкции конституент бу-
дем называть совершенной дизъюнктивной нормальной формой (ДНФ) функции f (x
1
, x
2
, ..., x
n
).
Количество первичных термов в представлении функции называется сложностью L(f) представле-
ния. Сложность представления рассматриваемой булевой функции f (x
1
, x
2
, x
3
) равна 12.
При задании булевой функции f (x
1
, x
2
, ..., x
n
) с помощью гиперкуба строят граф, каждой вершине
которого взаимно однозначно соответствует двоичный набор (σ
1
, σ
2
, ..., σ
n
); вершины упорядочивают по
ярусам: в i-й ярус входят
i
n
вершин, которым соответствуют двоичные наборы, содержащие i единиц;
вершины соединяют ребром, если соответствующие им наборы отличаются в одном и только одном
разряде; вершины, соответствующие наборам (σ
1
, σ
2
, ..., σ
n
), при которых функция равна 1, заштрихо-
вываются.
Гиперкуб для булевой функции f (x
1
, x
2
, x
3
), совершенная ДНФ которой имеет вид
f (x
1
, x
2
, x
3
) =
321321321321321
xxxxxxxxxxxxxxx ∨∨∨∨ ,
представлен на рис. 14.
Часто двоичные наборы задают десятичными эквивалентами (σ
1
, σ
2
, ..., σ
n
) ↔
∑
=
−
σ
n
i
in
i
1
2 , а булеву
функцию − перечислением десятичных эквивалентов, соответствующих конституентам (конъюнкциям
разложения Шеннона).
Булева функция, заданная выше совершенной ДНФ и гиперкубом, может быть представлена и пе-
речислением десятичных эквивалентов:
f (x
1
, x
2
, x
3
)|
1
= ∨(0, 3, 4, 6, 7).
Минимальной ДНФ булевой функции называется ДНФ этой функции, имеющая минимальную слож-
ность.
Рассмотрим метод Квайна (импликантных таблиц) для получения минимальной ДНФ булевой
функции. Этот метод заключается в последовательном выполнении двух следующих этапов.
1 Выделение максимальных единичных интервалов.
Под единичным интервалом понимается множество интервалов, на которых булева функция при-
нимает значение 1 и которые образуют гиперкуб некоторой размерности. Мощность интервала равна сте-
пени числа 2:
2
0
− вершина, 2
1
− ребро, 2
2
− грань и т.д.
Запишем множество единичных интервалов для рассматриваемого примера {000, 100, 110, 111, 011,
−00, 1−0, 11−, −11}. Здесь и далее «−» означает, что переменная, соответствующая этому разряду, в
конъюнкции отсутствует, т.е. по этой переменной после дизъюнкции соответствующих конъюнкций
произошло склеивание. Так, интервал −00, соответствующий множеству конституент {000, 100}, полу-
чается в результате преобразования
32321321
xxxxxxxx
=
∨ . Первые пять из выписанных выше интервалов
соответствуют вершинам гиперкуба, а остальные − ребрам. Соответствующие вершины гиперкуба на
рис. 14 заштрихованы, а ребра отмечены толстой линией.
Интервал I
α
называется максимальным интервалом булевой функции, если не найдется другого ин-
тервала I
β
этой функции, содержащего интервал I
α
: I
α
⊄ I
β
.
111
011
101
110
001
010
100
000
Рис
−00
1−0
11−
−11

Страницы