Лекции по дискретной математике. Математическая логика. Зарипова Э.Р - 39 стр.

UptoLike

ВУЗ: 

РУДН | Москва

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

Рубрика: 

39
полином Жегалкина.
Доказательство
. Возьмем полином Жегалкина для нелинейной
функции f:
s1
s1
s1
ii
ii
iin1
xxxxf ...),...,(
),...,(
...
∑
=
α
.
В силу нелинейности полинома в нем найдется член,
содержащий не менее двух множителей. Пусть это x
1
и x
2
. Тогда
полином можно записать следующим образом
),...,(),...,(
),...,(),...,(...
),...,(
...
n34n332
ii
n321n3121iiii
xxfxxfx
xxfxxxfxxxx
s1
s1s1
⊕⊕
⊕⊕=
∑
α
,
причем 0xxf
n31
≡
/
),...,(.
Выберем такие ,,...,
n3
α
α
чтобы 1f
n31
=
),...,(
α
α
. Тогда
,),...,,,(),(
γ
β
α
α
α
ϕ
=
=
2121n32121
xxxxxxfxx
где
γ
β
α
,, - константы, равные 0 или 1.
Рассмотрим функцию
),(
21
xx
ψ
, получаемую из
),(
21
xx
ϕ
следующим образом:
.),(),(
γ
αβ
α
β
ϕ
ψ
=
2121
xxxx
Воспользуемся явным выражением для функции
),(
21
xx
ϕ
,
чтобы вычислить
212
121212
12121
xxx
xxxxxx
xxxxx
=++++
++++++=+++⊕
⊕⊕⊕⊕⊕=++++
γαβγαββ
αβααββαγαβγαβ
βααβγαβαβϕ
)(
)())((),(
.
Следовательно,
2121
xxxx
=
),(
ψ
.
В заключение отметим, что классы T
0
,T
1
,S,M и L попарно
различны, что видно из таблицы.
T
0
T
1
S M L
0 + - - + +
1 - + - + +
x - - + - +

Страницы