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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

32
6. СЛАБООПРЕДЕЛЁННЫЕ БУЛЕВЫ ФУНКЦИИ.
МИНИМИЗАЦИЯ В КЛАССЕ ДНФ
Под нулевым интервалом булевой функции понимают множество
двоичных наборов, на которых функция принимает значение 0 и которые
образуют гиперкуб некоторой размерности.
Слабоопределённой булевой функцией от n переменных называется
булева функция f
(x
1
, x
2
, ..., x
n
), обладающая следующими свойствами:
а) число n достаточно велико;
б) единичная и нулевая области V
1
, V
0
задаются единичными и ну-
левыми интервалами;
в) мощность объединения единичной V
1
и нулевой V
0
областей на-
много меньше, чем 2
n
.
В качестве примера слабоопределённой булевой функции рассмот-
рим семиместную булеву функцию:
f (x
1
, x
2
, ..., x
7
) =
−−−−−−−
−−−−−−−−
,01101,1000,01010интервалахна0
;0010,01011,0000интервалахна1
единичная область которой задана единичными кубами 0
–
0
–
0
−
0,
0 − − 001 − и гранью 11 − 0 − 01, а нулевая область − нулевыми гранями
10 − 0 − 01, 1101 − 0 − и кубом 00 − − 10 −. Мощность объединения единичной
и нулевой областей | V
1
∪ V
0
| равна 36, а это значительно меньше, чем 2
7
.
Таблицей различий называется двумерная таблица, каждой строке ко-
торой соответствует разряд рассматриваемого единичного интервала,
столбцу – нулевой интервал, а в ячейке (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-го нулевого интервала.
При минимизации слабоопределённых булевых функций методом
Квайна получение максимальных единичных интервалов сводится к по-
крытию столбцов строками таблицы различий, которая строится для ка-
ждого из единичных интервалов. Единица в ячейке (i, j) таблицы разли-
чий, построенной для некоторого единичного интервала, говорит о том,
что если в этом единичном интервале оставить только i-й разряд, то в по-
лученном единичном интервале не будет содержаться j-й нулевой интер-
вал. Поэтому каждое покрытие столбцов строками таблицы различий по-
рождает максимальный единичный интервал слабоопределённой булевой
функции. Заметим, что при формировании максимального единичного
интервала в него переписывают те разряды единичного интервала, кото-
рые соответствуют строкам, вошедшим в покрытие, а в оставшихся раз-

Страницы