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

UptoLike

Операция замыкания . Основные замкнутые классы .
__________________________________________________________________________________________
93
Наибольший из рангов элементарных конъюнкций, входящих в по -
лином, называется степенью этого полинома. Число
l
называется длиной
полинома. При
0
=
l
полагаем
(
)
0
1
=
n
x...,,xP .
Имеет место следующее утверждение.
Для каждой булевой функции существует , и при этом единст -
венно, представление в виде полинома Жегалкина , который может
быть записан следующим образом :
(
)
{}{}
.x...xax...,,xP
s
s
s
ii
n,...,i,...,i
i...in
1
1
1
1
1
=
Число возможных монотонных конъюнкций
s
ii
x...x
1
равно количест -
ву подмножеств
{
}
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
и выписываем искомый полином.
Пример 1. Построить полином Жегалкина для функции
(
)
(
)
.z,y,xf 11001110
=
Решение. Запишем общий вид полинома Жегалкина для функции,
зависящей от 3-х переменных:
(
)
.xyzazyaxzaxyazayaxaaz,y,xP
1232313123210
=
Составим систему уравнений: