Дискретная математика. Кулаков Ю.В - 29 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

c
0
, c
j
= 0, 1; j = 1, 2, ..., n;
где ⊕,
∑
– знаки операции «сложение по модулю два»: 0 ⊕ 0 = 0, 0 ⊕ 1 = 1, 1 ⊕ 0 = 1, 1 ⊕ 1 = 0.
Установим, является ли булева функция (a, b, c, d) линейной.
Предположим, что она представима в виде
(a, b, c, d) = c
0
⊕ c
a
a ⊕ c
b
b ⊕ c
c
c ⊕ c
d
d,
т.е. является линейной.
Исходя из этого предположения, найдем неизвестные коэффициенты c
0
, c
a
, c
b
, c
c
, c
d
. Для определе-
ния коэффициента c
0
зафиксируем набор 0000:
(0, 0, 0, 0) = 0000 ∨ = 1 ∨ 0 = 1,
(0, 0, 0, 0) = c
0
⊕ c
a
0 ⊕ c
b
0 ⊕ c
c
0 ⊕ c
d
0 = c
0
= 1.
Аналогично найдем коэффициенты c
a
, c
b
, c
c
, c
d
, фиксируя соответственно наборы 1000, 0100, 0010,
0001:
(1, 0, 0, 0) =
0001 ∨
= 0 ∨ 0 = 0,
(1, 0, 0, 0) = 1 ⊕ c
a
1 ⊕ c
b
0 ⊕ c
c
0 ⊕ c
d
0 = 1 ⊕ c
a
= 0 → c
a
= 1;
(0, 1, 0, 0) = 0100 ∨ = 1 ∨ 1 = 1,
(0, 1, 0, 0) = 1 ⊕ 1&0 ⊕ c
b
1 ⊕ c
c
0 ⊕ c
d
0 = 1 ⊕ c
b
= 1 → c
b
= 0;
(0, 0, 1, 0) = 1000 ∨ = 1 ∨ 0 = 1,
(0, 0, 1, 0) = 1 ⊕ 1&0 ⊕ 0&0 ⊕ c
c
1 ⊕ c
d
0 = 1 ⊕ c
c
= 1 → c
c
= 0;
(0, 0, 0, 1) = 0010 ∨ = 0 ∨ 0 = 0,
(0, 0, 0, 1) = 1 ⊕ 1&0 ⊕ 0&0 ⊕ 0&0 ⊕ c
d
1 = 1 ⊕ c
d
= 0 → c
d
= 1.
Таким образом, (a, b, c, d) = 1 ⊕ a ⊕ d.
Сравним значения представлений
cbda ∨ и 1 ⊕ a ⊕ d функции
(a, b, c, d) на остальных наборах. Например, на наборе 1111 имеем:
(1, 1, 1, 1) =
1111 ∨ = 0 ∨ 0 = 0,
(1, 1, 1, 1) = 1 ⊕ 1 ⊕ 1 = 1.
Следовательно, сделанное ранее предположение о линейности функции (a, b, c, d) является не-
верным: (a, b, c, d) ∉ K
л
.
Классом K
с
самодвойственных булевых функций f
i
(x
1
, x
2
, ..., x
n
) называется множество булевых
функций вида
{ f
i
(x
1
, x
2
, ..., x
n
) / f
i
(x
1
, x
2
, ..., x
n
) = ),...,,(
21 ni
xxxf }.
Следовательно, функция является самодвойственной, если на любой паре противоположных набо-
ров функция принимает противоположные значения.
Проверим, является ли булева функция (a, b, c, d) самодвойственной. Для этого представим функ-
цию табл. 11.
Таблица 11
a
b c d
(a, b, c,
a
b c d
(a, b, c,

Страницы