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

UptoLike

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

45
Булева функция, которой соответствует полином Жегалкина первой
степени, называется линейной. Функции, задаваемые формулами
y
~
x
,
y
x
Å
,
x
,
x
,
z
y
x
Å
Å
,
являются линейными. Множество всех линейных булевых функций обо-
значается через
L
, множество линейных функций, зависящих от
n
пере-
менных, через
nL . Для каждой функции
nLf
Î
имеет место пред-
ставление
(
)
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
~
...,,
~
~
a
a
a
1
=
и
(
)
n
~
...,,
~
~
bbb
1
= называются соседними, если
они отличаются только одной координатой. Доказать, что если функция