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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

39
Классом K
с
самодвойственных булевых функций называется множе-
ство булевых функций вида:
{
),...,,(
21 ni
xxxf
/
),...,,(
21 ni
xxxf
≠
),...,,(
21 ni
xxxf
},
Другими словами, функция является самодвойственной, если на лю-
бой паре противоположных наборов она принимает противоположные
значения.
Для проверки самодвойственности булевой функции представим
её табличным способом (см. табл. 11).
Из таблицы видно, что существует пара противоположных наборов,
например 0001 и 1110, на которых значения функции равны:
(0, 0, 0, 1) = (1, 1, 1, 0) , ∉ K
с
.
Классом K
м
монотонных булевых функций называется множество
булевых функций вида:
{
),...,,(
21 ni
xxxf
/
↔σσσ≥σσσ )),...,,(),...,,((
21
**
2
*
1
nn
),...,,(
*
2
*
21
*
1 nn
σ≥σσ≥σσ≥σ↔ )},...,,(),...,,(
21
**
2
*
1
nini
ff
σσσ≥σσσ→
.
Для проверки принадлежности булевой функции f
i
(x
1
, x
2
, ..., x
n
) к
классу K
м
при небольших значениях n удобно использовать её представ-
ление гиперкубом. При этом для каждого ребра гиперкуба характерно,
что верхней его вершине соответствует двоичный набор
),...,,(
**
2
*
1
n
σσσ
, а
нижней вершине − двоичный набор
),...,,(
21 n
σσσ
. Следовательно, если
в гиперкубе найдётся хотя бы одно ребро, в котором значение функции 0
будет размещено выше значения 1, то функция не является монотонной.
Протестировать функцию на монотонность можно с помощью со-
ответствующего ей гиперкуба, представленного на рис. 17.
Таблица 11
x
1
x
2
x
3
x
4
(x
1
, x
2
, x
3
, x
4
)
x
1
x
2
x
3
x
4
(x
1
, x
2
, x
3
, x
4
)
0 0 0 0 1 1 0 0 0 0
0 0 0 1 0 1 0 0 1 0
0 0 1 0 1 1 0 1 0 0
0 0 1 1 0 1 0 1 1 0
0 1 0 0 1 1 1 0 0 1
0 1 0 1 1 1 1 0 1 1
0 1 1 0 1 1 1 1 0 0
0 1 1 1 0 1 1 1 1 0

Страницы