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

UptoLike

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

42
кнопку, и не нажимал, если он голосует «против», и чтобы в случае, если
будет большинство человек голосовать «за», загоралась лампочка.
6. ПОЛИНОМ ЖЕГАЛКИНА.
ЛИНЕЙНЫЕ И НЕЛИНЕЙНЫЕ ФУНКЦИИ
Элементарная конъюнкция называется монотонной, если она не со-
держит отрицательных переменных.
Полиномом Жегалкина, или полиномом по модулю 2, называется
формула:
(
)
ln
KKKKxxP
Å
Å
Å
Å
=
......,,
3211
,
где
(
)
liK
i
...,,1
=
попарно различные монотонные элементарные конъ-
юнкции, составленные из переменных
n
x...,,x
1
.
Наибольший из рангов элементарных конъюнкций, входящих в по-
лином, называется степенью этого полинома. Число
l
называется длиной
полинома. При
0
=
l
полагаем
(
)
0
1
=
n
x...,,xP .
Имеет место следующее утверждение.
Для каждой булевой функции существует, и при этом единст-
венно, представление в виде полинома Жегалкина, который может
быть записан следующим образом:
1s1s
1s
1ni...iii
i,...,i О 1,...,n
Px,...,x=ax...x.
Число возможных монотонных конъюнкций
1
...
s
ii
xx
равно количе-
ству подмножеств
{
}
s
ii ,...,
1
множества
{
}
n,...,,21 , т.е.
n
2
.Коэффициенты
s
i...i
a
1
принимают значение либо 0, либо 1.
Отметим два способа построения полинома Жегалкина.
1. Метод неопределенных коэффициентов. Применяется в основном
тогда, когда булева функция
(
)
n
x...,,xf
1
задана таблицей истинности или
набором своих значений. При построении полинома Жегалкина методом
неопределенных коэффициентов:
Во-первых, выписываем общий вид полинома Жегалкина для функ-
ций от
n
переменных.
Во-вторых, исходя из того, что
(
)
n
x...,,xf
1
и искомый полином
(
)
n
x...,,xP
1
на одинаковых наборах входящих в них переменных прини-
мают одинаковые значения, составляем систему
n
2
уравнений с
n
2
неиз-
вестными
s
i...i
a
1
.
В-третьих, решаем систему, найденную на предыдущем шаге, на-
ходим коэффициенты
s
i...i
a
1
и выписываем искомый полином.