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

UptoLike

ВУЗ: 

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

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

Рубрика: 

()( )
(
)
(
)
12 1 2 2
(, )
1
x
xxbx bbxacabcaax
ψ
⊕⊕ ⊕⊕⊕⊕⊕⊕==
⊕
12 2 1 1 2
x
xbxaxabaxabbxabcabc⊕ ⊕ ⊕⊕ ⊕⊕ ⊕⊕⊕⊕==
12
x
x
.
Замечание. Смысл функции
ψ
в том, что на некоторые из переменных
1
x
и
2
x
наве-
иваются отрицания. Так, если, например,
1a
, то
222
1
x
ax x⊕⊕
=
=
. Кроме того, если
я
ш
1
, то отрицание навешиваетс над
ab c⊕ =
ϕ
и в конечном счете над
f
.
Пример 36. Дана функция ( , , , ) (1fxyzu 110 0101 0001 1010)
=
. Руков
нелинейн а ла составим много-
чле
одствуясь леммой о
ой функции, получим из нее конъюнкцию. С этой целью сн ча
н Жегалкина для
f
. При п многочлена Жегалкина бу-
дем использовать метод треугольника:
х у z и
остроении для заданной функции
(, ,,)
f
xyzu
0
0
0
0
1 1 1 0 0 1 0 1 0 0 0 1 1 0 1 0
0 0 1 0 1 1 1 1 0 0 1 0 1 1 1
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0 1 1 1 0 0 0 1 0 1 1 1 0 0
1 0 0 1 0 0 1 1 1 0 0 1 0
1 0 1 1 0 1 0 0 1 0 1 1
1 1 0 1 1 1 0 1 1 1 0
0 1 1 0 0 1 1 0 0 1
1 0 1 0 1 0 1 0 1
1 1 1 1 1 1 1 1
0 0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0
0 0 0 0
0 0 0
0 0
0
Единицы на левом льника соответствуют наборам значений аргументов
, , , , и . Поэтому, в многочлен Жегалки-
на
ребре треуго
(0,0,0,0) (0,0,1,1) (0,1,0,0) (0,1, 0,1) (0,1,1,1) (1,0,0,0)
войдут 1 ,
zu
,
y
,
yu
,
yzu
и
x
:
(,f y
x z u yzu yu zu x y,,) 1
=
⊕⊕⊕⊕⊕.
Из этого разложения видим, что данная функция является нелинейной. Поэтому для состав-
ения конъюнкции воспользуемся леммой о нелинейной функции. Использовать две первые
л
переменные
x
и
y
здесь нельзя, так как переменная
x
входит в многочлен Жегалкина ли-
нейно. Однако в качестве
1
x
и
2
x
можно взять любые две переменные среди
y
,
z
и
u
.
Пусть это будут
y
и
z
. Относительно этих переменных руппируем слагаемые:
г
(
)
(
)
(
)
(
)
(, ,,) 1fxyzu yzu yu y zu x⊕⊕⊕⊕=⊕ =
(
)
(
)
11yz u y u z u x⊕⊕⊕⊕⊕=⋅ ⋅
.
Здесь
0
(,)
f
xu u=
,
1
(,) 1
f
xu u⊕=
,
2
(,)
f
xu u
=
,
3
(,) 1
f
xu x
⊕
=
. остроим таблицы для найден-
ых функций.
х u
П
н
0
f
1
f
2
f
3
f
                    ψ ( x1 , x2 ) = ( x1 ⊕ b )( x2 ⊕ a ) ⊕ a ( x1 ⊕ b ) ⊕ b ( x2 ⊕ a ) ⊕ c ⊕ ab ⊕ c =
                      = x1 x2 ⊕ bx2 ⊕ ax1 ⊕ ab ⊕ ax1 ⊕ ab ⊕ bx2 ⊕ ab ⊕ c ⊕ ab ⊕ c = x1 x2 .

       Замечание. Смысл функции ψ в том, что на некоторые из переменных x1 и x2 наве-
шиваются отрицания. Так, если, например, a = 1 , то x2 ⊕ a = x2 ⊕ 1 = x2 . Кроме того, если
ab ⊕ c = 1 , то отрицание навешивается над ϕ и в конечном счете над f .
   Пример 36. Дана функция f ( x, y, z , u ) = (1110 0101 0001 1010) . Руководствуясь леммой о
нелинейной функции, получим из нее конъюнкцию. С этой целью сначала составим много-
член Жегалкина для f . При построении для заданной функции многочлена Жегалкина бу-
дем использовать метод треугольника:

                               х    у     z   и          f ( x, y , z , u )
                               0    0     0   0     1110010100011010
                               0    0     0   1     001011110010111
                               0    0     1   0      01110001011100
                               0    0     1   1      1001001110010
                               0    1     0   0       101101001011
                               0    1     0   1       11011101110
                               0    1     1   0        0110011001
                               0    1     1   1        101010101
                               1    0     0   0         11111111
                               1    0     0   1         0000000
                               1    0     1   0          000000
                               1    0     1   1           00000
                               1    1     0   0             0000
                               1    1     0   1              000
                               1    1     1   0                00
                               1    1     1   1                 0

    Единицы на левом ребре треугольника соответствуют наборам значений аргументов
(0, 0, 0, 0) , (0, 0,1,1) , (0,1, 0, 0) , (0,1, 0,1) , (0,1,1,1) и (1, 0, 0, 0) . Поэтому, в многочлен Жегалки-
на войдут 1 , zu , y , yu , yzu и x :

                                        f ( x, y, z , u ) = yzu ⊕ yu ⊕ zu ⊕ x ⊕ y ⊕ 1 .

Из этого разложения видим, что данная функция является нелинейной. Поэтому для состав-
ления конъюнкции воспользуемся леммой о нелинейной функции. Использовать две первые
переменные x и y здесь нельзя, так как переменная x входит в многочлен Жегалкина ли-
нейно. Однако в качестве x1 и x2 можно взять любые две переменные среди y , z и u .
Пусть это будут y и z . Относительно этих переменных группируем слагаемые:

                               f ( x, y, z , u ) = ( yzu ) ⊕ ( yu ⊕ y ) ⊕ ( zu ) ⊕ ( x ⊕ 1) =
                                         = yz ⋅ u ⊕ y ( u ⊕ 1) ⊕ z ⋅ u ⊕ ( x ⊕ 1) .

Здесь f 0 ( x, u ) = u , f1 ( x, u ) = u ⊕ 1 , f 2 ( x, u ) = u , f 3 ( x, u ) = x ⊕ 1 . Построим таблицы для найден-
ных функций.
                                               х u f 0 f1 f 2                     f3

Страницы