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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

27
При этом знак конъюнкция & часто для простоты опускают:
f (x
1
, x
2
, x
3
) =
321321321321321
xxxxxxxxxxxxxxx ∨∨∨∨
.
В дальнейшем представление булевой функции f (x
1
, x
2
, ..., x
n
) в виде
дизъюнкции конституент будем называть совершенной дизъюнктивной
нормальной формой (ДНФ) функции от n переменных.
Количество первичных термов в совершенной ДНФ функции f назы-
вается сложностью представления и обозначается L(f). Так, сложность
представления L(f) рассматриваемой в качестве примера булевой функ-
ции равна 15.
Для задания булевой функции f (x
1
, x
2
, ..., x
n
) с помощью гиперкуба
строят граф, вершинам которого сопоставляют всевозможные двоичные
наборы значений переменных (x
1
, x
2
, ..., x
n
). Вершины этого графа упоря-
дочивают по ярусам так, что в i-й ярус входят
i
n
вершин, которым со-
ответствуют двоичные наборы, содержащие по i единиц каждый. Каждую
пару вершин графа соединяют ребром, если соответствующие им наборы
отличаются в одном и только в одном разряде. Вершины, соответствую-
щие наборам (σ
1
, σ
2
, ..., σ
n
), на которых функция принимает значение 1,
заштриховываются.
Гиперкуб для рассматриваемой булевой функции f (x
1
, x
2
, x
3
) пред-
ставлен на рис. 14.
Часто двоичные наборы (σ
1
, σ
2
, ..., σ
n
), на которых функция равна 1,
задают десятичными эквивалентами
∑
=
−
σ
n
i
in
i
1
2
, а булеву функцию − пе-
речислением этих десятичных эквивалентов.
Булева функция, представленная выше таблицей, совершенной ДНФ
и гиперкубом может быть задана и перечислением десятичных эквива-
лентов следующим образом:
f (x
1
, x
2
, x
3
) |
1
= ∨ (0, 3, 4, 6, 7).
Минимальной ДНФ булевой функции
называется ДНФ этой функции, которая
имеет минимальную сложность.
Рассмотрим метод Квайна (импли-
кантных таблиц) для получения мини-
мальной ДНФ булевой функции, кото-
рый заключается в последовательном
выполнении следующих двух этапов.
111
011
101
110
001
010
100
000
Рис. 14
−
1
−
0
11
−
−

Страницы