Дискретная математика. Элементы теории задачи и упражнения. Часть 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
⊕
⊕
⊕
⊕
⊕
⊕
⊕
=
Составим систему уравнений: 
                                             93
Операция замыкания. Основные замкнутые классы.
__________________________________________________________________________________________
     Наибольший из рангов элементарных конъюнкций, входящих в по-
лином, называется степенью этого полинома. Число l называется длиной
полинома. При l =0 полагаем P (x1 , ..., x n ) =0 .
     Имеет место следующее утверждение.
     Для каждой булевой функции существует, и при этом единст-
венно, представление в виде полинома Жегалкина, который может
быть записан следующим образом:
                    P (x1 , ..., x n ) = ∑ a i ...i x i ... x i .
                                                                1       s   1   s
                                           {i1 ,...,i s }∈{1 ,...,n }
       Число возможных монотонных конъюнкций xi ...x i равно количест-              1   s


ву подмножеств {i1 ,..., i s } множества {1,2 ,..., n}, т.е. 2 .Коэффициенты a i ...i
                                                                                    n
                                                                                            1   s


принимают значение либо 0, либо 1.
         Отметим два способа построения полинома Жегалкина.
1.       Метод неопределенных коэффициентов. Применяется в основном
тогда, когда булева функция f ( x1 , ..., x n ) задана таблицей истинности или
набором своих значений. При построении полинома Жегалкина методом
неопределенных коэффициентов:
         Во-первых, выписываем общий вид полинома Жегалкина для функ-
ций от n переменных;
         Во-вторых, исходя из того, что f ( x1 , ..., x n ) и искомый полином
P ( x1 , ..., x n ) на одинаковых наборах входящих в них переменных прини-
мают одинаковые значения, составляем систему 2 n уравнений с 2 n неиз-
вестными a i ...i .
              1   s


     В-третьих, решаем систему, найденную на предыдущем шаге, на-
ходим коэффициенты a i ...i и выписываем искомый полином.
                             1   s




          Пример 1. Построить полином Жегалкина для функции
 f ( x , y , z ) =(01110 011).
          Решение. Запишем общий вид полинома Жегалкина для функции,
зависящей от 3-х переменных:
         P (x , y , z ) =a 0 ⊕ a1 x ⊕ a 2 y ⊕ a 3 z ⊕ a12 xy ⊕ a13 xz ⊕ a 23 zy ⊕ a123 xyz .
          Составим систему уравнений:

Страницы