ВУЗ:
Составители:
Рубрика:
таблицы Квайна соответственно буквами a, b, c и d. Для каждого j-го столбца запишем множество
строк, покрывающих этот столбец:
j = 1 → A
1
= {a}, j = 2 → A
1
= {a, b}, j = 3 → A
3
= {b, c},
j = 4 → A
4
= {d}, j = 5 → A
5
= {c, d}.
Если каждое множество A
j
представить в виде дизъюнкции ее элементов и найти конъюнкцию по-
лученных дизъюнкций
j
& A
j
, то каждая конъюнкция в полученной аддитивной форме будет соответство-
вать покрытию, а число всех покрытий будет равно числу различных конъюнкций в полученной адди-
тивно-мультипликативной форме:
j
& A
j
= a & (a ∨ b) & (b ∨ c) & d & (c ∨ d) = a & (b ∨ c) & d =
= (a & b ∨ a & c) & d = a & b & d ∨ a & c & d.
Полученные конъюнкции a & b & d и a & c & d обозначают покрытия {−00, 1−0, −11} и {−00, 11−,
−11}, соответствующие тупиковым ДНФ f
т,1
(x
1
, x
2
, x
3
) =
323132
xxxxxx ∨∨ и f
т,2
(x
1
, x
2
, x
3
) =
322132
xxxxxx ∨∨ . В
качестве минимальной ДНФ можно выбрать любую из этих двух тупиковых ДНФ, поскольку сложно-
сти их представления равны. Выберем, например, первую:
f
мин
(x
1
, x
2
, x
3
) =
323132
xxxxxx ∨∨ .
Таким образом, в результате упрощения сложность L(f) представления булевой функции уменьши-
лась с 15 до 6.
Дальнейшее уменьшение сложности выражения, определяющего заданную функцию, возможно, ес-
ли из класса ДНФ перейти в класс скобочных форм. Выражение, определяющее булеву функцию, назы-
вается скобочной формой, если кроме первичных термов и знаков операций конъюнкции и дизъюнкции
в него входят скобки (, ).
В рассматриваемом примере сложность представления функции, равная 6, понижается до 5 в ре-
зультате применения закона дистрибутивности конъюнкции относительно дизъюнкции
f
СФ
(x
1
, x
2
, x
3
) =
32123
)( xxxxx ∨∨ .
Большое значение имеют слабоопределенные булевы функции f
i
(x
1
, x
2
, ..., x
n
), которые обладают сле-
дующими свойствами:
а) число переменных n велико;
б) мощность объединения единичной V
1
и нулевой V
0
областей намного меньше, чем 2
n
, где еди-
ничную и нулевую области образуют вершины, в которых функция равна соответственно 1 и 0;
в) единичная и нулевая области задаются соответствующими интервалами.
Множество вершин гиперкуба, на которых функция равна нулю и которые образуют гиперкуб не-
которой размерности, называется нулевым интервалом. Сокращенную ДНФ слабоопределенных функ-
ций строят с помощью таблицы различий.
Таблицей различий называется двумерная таблица размера n × |V
0
|, каждой строке которой взаимно
однозначно соответствует разряд рассматриваемого единичного интервала, столбцу – нулевой интервал,
а на пересечении i-й строки с j-м столбцом находится результат операции:
0 ⊕ 0 = 0, 1 ⊕ 0 = 1, − ⊕ 0 = 0,
0 ⊕ 1 = 1, 1 ⊕ 1 = 0, − ⊕ 1 = 0,
0 ⊕ − = 0, 1 ⊕ − = 0, − ⊕ − = 0,
причем в качестве первого аргумента берется значение i-го разряда единичного интервала, в качестве
второго − значение i-го разряда нулевого интервала, соответствующего j-му столбцу.
Выделение максимальных интервалов сводится к покрытию столбцов строками таблицы различий.
В качестве примера рассмотрим нахождение минимальной ДНФ булевой функции
Страницы
- « первая
- ‹ предыдущая
- …
- 23
- 24
- 25
- 26
- 27
- …
- следующая ›
- последняя »