Функции алгебры логики. Стасюк В.В. - 20 стр.

UptoLike

ВУЗ: 

ДВФУ | Владивосток

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

Рубрика: 

Определение булевой
1
,..
. Представление функции
., )
nn
(
f
xxP∈
над системой
{
}
,,
x
yx y⊕
называется многочленом Жегалкина:
∧1
11
1
1 ,...,
( ,..., )
( ,..., ) ...
s
s
s
niii
ii
i
f
xx x x
α
=
⋅⋅
∑
,
де — прямая сумма, знак обозначает конъюнкцию иг
∑
⋅
{
}
1
,...,
0,1
s
ii
α
∈
.
Таки бразом, справедлива следующая м о
ия представима в виде многочлена Жегалкина и
ритом
ия функции многочленом Жегалкина следует из
Теорема 15. Всякая булева функц
п единственным образом.
Доказательство. Возможность представлен
полноты системы
{
}
,,
x
yx y⊕∧1
. Единственность такого представления рассмотрим на при-
мере функций от
n
ых. Общий вид многочлена Жегалкина для
2
2=
переменн
f
P∈
:
12 3 4
(, )
xy x y xy
α
ααα
⊕⊕⊕
=
.
Очевидно, различных многочленов Жегалкина столько же, сколько различных двоичных на-
боров
1234
(, , , )
α
ααα
, а их число равно
42
16 2 2== . Остается заметить, что булевых функций
от
2n = ровно столько же:
2
переменных
2
2
2
2P =
.
П н Жегалкина для дизъюнкции ример 34. Построим многочле
xy
∨ , пользуясь так
называ вим мемым методом неопределенных коэффициентов. Для этого соста акет многочле-
на Жегалкина
12 3 4
x
yxyxy
α
ααα
⊕⊕⊕∨=
.
Тогда при
000 0 0 0
0xy==
12341
α
ααα
⊕⊕⊕=∨= ⋅ ⋅ ⋅=
α
,
1
0
α
=
.
При
и
1010 0 1 0
0x =
1y =
2343
α
αα
⊕⊕⊕=∨= ⋅ ⋅ ⋅=
α
,
3
1
α
=
.
При
1
x
= и
110 0 110 0
0y =
242
α
αα
⊕⊕⊕=∨ = ⋅ ⋅ ⋅ =
,
2
1
α
=
.
При
1
x
= и
1 1 1 0 11 11 1 0
1y =
444
α
αα
⊕⊕⊕ ⊕
=
∨= ⋅ ⋅ ⋅= =
,
4
1
α
=
.
ведем полученные результаты в таблицу С
х у
1
α
3
α
2
α
4
α
0
0
1
1
0
1
0
1
0
1
1
1
так,
x
yxyxy⊕⊕∨=
— искомы гочлен Жега кин
Замечание. Сущ рования многочлена Жегалкина,
ываемый метод нии таблицы
й мно л а.
И
ествует упрощенный способ форми
так наз треугольника. Он состоит в построе
          Определение. Представление булевой функции                                                    f ( x1 ,..., xn ) ∈ Pn   над системой
{1, x ∧ y, x ⊕ y}   называется многочленом Жегалкина:

                                     f ( x1 ,..., xn ) =      ∑
                                                           ( i1 ,...,is )
                                                                            α i1 ,...,is xi1 ⋅ ... ⋅ xis ,


где   ∑— прямая сумма, знак ⋅ обозначает конъюнкцию и α i1 ,...,is ∈ {0,1} .
Таким образом, справедлива следующая

      Теорема 15. Всякая булева функция представима в виде многочлена Жегалкина и
притом единственным образом.

Доказательство. Возможность представления функции многочленом Жегалкина следует из
полноты системы {1, x ∧ y , x ⊕ y} . Единственность такого представления рассмотрим на при-
мере функций от n = 2 переменных. Общий вид многочлена Жегалкина для f ∈ P2 :

                                      f ( x, y ) = α1 ⊕ α 2 x ⊕ α 3 y ⊕ α 4 xy .

Очевидно, различных многочленов Жегалкина столько же, сколько различных двоичных на-
                                                             2
боров (α1 , α 2 , α 3 , α 4 ) , а их число равно 16 = 24 = 22 . Остается заметить, что булевых функций
                                                                      2
от n = 2 переменных ровно столько же: P2 = 22 .
      Пример 34. Построим многочлен Жегалкина для дизъюнкции x ∨ y , пользуясь так
называемым методом неопределенных коэффициентов. Для этого составим макет многочле-
на Жегалкина
                            x ∨ y = α1 ⊕ α 2 x ⊕ α 3 y ⊕ α 4 xy .

Тогда при x = y = 0
                           0 = 0 ∨ 0 = α1 ⊕ α 2 ⋅ 0 ⊕ α 3 ⋅ 0 ⊕ α 4 ⋅ 0 = α1 , α1 = 0 .
При x = 0 и y = 1
                            1 = 0 ∨ 1 = 0 ⊕ α 2 ⋅ 0 ⊕ α 3 ⋅1 ⊕ α 4 ⋅ 0 = α 3 , α 3 = 1 .
При x = 1 и y = 0
                             1 = 1 ∨ 0 = 0 ⊕ α 2 ⋅1 ⊕ 1 ⋅ 0 ⊕ α 4 ⋅ 0 = α 2 , α 2 = 1 .
При x = 1 и y = 1
                          1 = 1 ∨ 1 = 0 ⊕ 1 ⋅1 ⊕ 1 ⋅1 ⊕ α 4 ⋅1 = 0 ⊕ α 4 = α 4 , α 4 = 1 .

Сведем полученные результаты в таблицу

                                          х у        α1           α3             α2        α4
                                          0    0      0
                                          0    1                    1
                                          1    0                                  1
                                          1    1                                             1

Итак, x ∨ y = x ⊕ y ⊕ xy — искомый многочлен Жегалкина.
       Замечание. Существует упрощенный способ формирования многочлена Жегалкина,
так называемый метод треугольника. Он состоит в построении таблицы

Страницы