Дискретная математика. Элементы теории задачи и упражнения. Часть 2. Булгакова И.Н - 50 стр.

UptoLike

Операция замыкания . Основные замкнутые классы .
__________________________________________________________________________________________
96
ставление
(
)
nnn
xcxccxxf
=
......,,
1101
, (7)
где коэффициенты
i
c принимают значения либо 0, либо 1.
Из представления (7) следует , что число всех линейных функций от
n
переменных равно
1
2
+n
. Другими словами, мощность множества
(
)
nL
равна
1
2
+n
.
Если функция
L
f
, то она называется нелинейной. Степень поли-
нома Жегалкина нелинейной функции не меньше 2. Элементарные функ-
ции
xy
,
y
x
,
y
x
, yx являются нелинейными.
Справедливо утверждение (лемма о нелинейной функции):
Если
(
)
n
x...,,xf
1
нелинейная функция, то, подставляя на места ее
переменных 0, 1,
x
,
y
,
x
,
y
, можно получить либо
xy
, либо xy.
ЗАДАЧИ И УПРАЖНЕНИЯ
1. Найти число монотонных элементарных конъюнкций ранга
r
, состав-
ленных из переменных
n
x...,,x
1
.
2. Найти число полиномов Жегалкина степени
r
над множеством пере -
менных
n
x...,,x
1
.
3. Методом неопределенных коэффициентов построить полином Жегал-
кина для следующих функций:
1)
(
)
1001
=
f ; 4)
(
)
(
)
yxy~x ↓∨ ;
2)
(
)
00010110
=
f ; 5)
(
)
yxxyz
;
3)
(
)
01001110
=
f ; 6)
(
)
(
)
.zyyx ⊕→
4. Построить полиномы Жегалкина для элементарных булевых функций.
5. При помощи эквивалентных преобразований построить полиномы Же-
галкина для следующих функций:
1)
z
x
yz
xy
D
=
; 4)
xyz
z
x
D
=
;
2)
34221
xxxxxD
=
; 5)
332121
xxxxxxD
=
;
3)
z
x
xyz
D
=
6)
x
z
y
x
D
=
.
6. Наборы
(
)
n
~
...,,
~
~
1
=
и
(
)
n
~
...,,
~
~
βββ
1
= называются соседними, если
они отличаются только одной координатой. Доказать, что если функция
(
)
n
x...,,xf
1
на двух соседних наборах принимает противоположные
значения, то она линейная. Верно ли обратное утверждение?