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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

38
где c
0
, c
j
− коэффициенты, которые могут принимать значения 0 или 1;
⊕,
Σ
− знаки операции «сложение по модулю два»: 0 ⊕ 0 = 0, 0 ⊕ 1 = 1,
1 ⊕ 0 = 1, 1 ⊕ 1 = 0.
Определим, принадлежит ли функция к классу K
л
. Для этого полу-
чим линейное представление функции в виде:
л
(x
1
, x
2
, x
3
, x
4
) = c
0
⊕ c
1
x
1
⊕ c
2
x
2
⊕ c
3
x
3
⊕ c
4
x
4
и сравним его с функцией .
Для определения значения коэффициента c
0
вычислим значения
функций и
л
на наборе значений переменных 0000:
(0, 0, 0, 0) =
0000 ∨
= 1 ∨ 0 = 1,
л
(0, 0, 0, 0) = c
0
⊕ c
1
0 ⊕ c
2
0 ⊕ c
3
0 ⊕ c
4
0
= c
0
, c
0
= 1.
Аналогично найдём значения коэффициентов c
1
, c
2
, c
3
и c
4
, фиксируя
соответственно наборы значений переменных 1000, 0100, 0010, 0001:
(1, 0, 0, 0) =
0001 ∨
= 0 ∨ 0 = 0,
л
(1, 0, 0, 0) = 1 ⊕ c
1
1 ⊕ c
2
0 ⊕ c
3
0 ⊕ c
4
0 = 1 ⊕ c
1
,
1 ⊕ c
1
= 0, c
1
= 1;
(0, 1, 0, 0) =
0100 ∨
= 1 ∨ 1 = 1,
л
(0, 1, 0, 0) = 1 ⊕ 1&0 ⊕ c
2
1 ⊕ c
3
0 ⊕ c
4
0 = 1 ⊕ c
2
,
1 ⊕ c
2
= 1, c
2
= 0;
(0, 0, 1, 0) =
1000 ∨
= 1 ∨ 0 = 1,
л
(0, 0, 1, 0) = 1 ⊕ 1&0 ⊕ 0&0 ⊕ c
3
1 ⊕ c
4
0 = 1 ⊕ c
3
,
1 ⊕ c
3
= 1, c
3
= 0;
(0, 0, 0, 1) =
0010 ∨
= 0 ∨ 0 = 0,
л
(0, 0, 0, 1) = 1 ⊕ 1&0 ⊕ 0&0 ⊕ 0&0 ⊕ c
4
1 = 1 ⊕ c
4
,
1 ⊕ c
4
= 0, c
4
= 1.
Таким образом,
л
(x
1
, x
2
, x
3
, x
4
) = 1 ⊕ x
1
⊕ x
4
.
Сравним значения функции (x
1
, x
2
, x
3
, x
4
) =
3241
xxxx ∨
и получен-
ного линейного представления на каждом из 11 оставшихся наборов. При
этом устанавливаем существование набора, например 1111, на котором
значения функций и
л
не совпадают:
(1, 1, 1, 1) =
1
1
1
1
∨
= 0 ∨ 0 = 0,
л
(1, 1, 1, 1) = 1 ⊕ 1 ⊕ 1 = 1,
(1, 1, 1, 1) ≠
л
(1, 1, 1, 1), ∉ K
л
.

Страницы