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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

30
Таблица 6
Максимальные единичные
интервалы
Конституента
000 100 110 011 111
a
–
00 1 1 0 0 0
b
1
–
0 0 1 1 0 0
c
11
– 0 0 1 0 1
d
–
11 0 0 0 1 1
a
a ∨ b b ∨ c
d
c ∨ d
Таблицей Квайна называется двумерная таблица, каждой строке ко-
торой соответствует максимальный единичный интервал, а столбцу –
конституента. На пересечении i-й строки и j-го столбца таблицы ставится
единица, если j-я конституента входит в i-й интервал, иначе в клетке (i, j)
ставится ноль или она не заполняется ничем. Для рассматриваемого при-
мера таблица Квайна представлена табл. 6, строки которой обозначены
буквами a, b, c и d.
Покрытия таблицы Квайна могут быть определены путём составле-
ния некоторой мультипликативно-аддитивной формы и преобразования
её в аддитивно-мультипликативную. При составлении мультипликатив-
но-аддитивной формы для каждого j-го столбца записывают дизъюнкцию
строк, в которых содержится единица, и полученные дизъюнкции логи-
чески перемножают. В полученной после преобразований аддитивно-
мультипликативной форме каждая конъюнкция будет соответствовать
покрытию таблицы Квайна.
Для нашего примера исходная мультипликативно-аддитивная форма
и её преобразование c использованием законов коммутативности, погло-
щения и дистрибутивности будут выглядеть следующим образом:
a & (a ∨ b) & (b ∨ c) & d & (c ∨ d) = a & (b ∨ c) & d = a & b & d ∨ a & c & d.
Полученные конъюнкции определяют покрытия {a, b, d} и {a, c, d}
таблицы Квайна, которые обозначают множества максимальных единич-
ных интервалов {−
00, 1
−
0, −
11} и {−
00, 11
−, −
11}. Дизъюнкции про-
стых импликант, соответствующих элементам этих множеств, являются
тупиковыми ДНФ булевой функции f
:
f
l1
(x
1
, x
2
, x
3
) =
323132
xxxxxx ∨∨
,
f
l2
(x
1
, x
2
, x
3
) =
322132
xxxxxx ∨∨
.
В качестве минимальной ДНФ булевой функции выбирают такую её
тупиковую ДНФ, которая имеет минимальную сложность. В нашем слу-
чае сложности обеих тупиковых ДНФ функции f одинаковы (равны 6).

Страницы