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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

44
г) раскрыть скобки в полученном выражении, пользуясь свойством ди-
стрибутивности операции
Å
относительно логического умножения
(
)
;uwuvwvu
Å
=
Å
(3)
д) привести подобные члены по правилу:
.
u
u
0
=
Å
(4)
Пример 2. Пусть
(
)
(
)
(
)
zyyxz,y,xf
=
. Построить полином
Жегалкина, используя метод эквивалентных преобразований.
Решение. Построим д.н.ф.
(
)
(
)
(
)
(
)
.yzzxyxzyyxzyyx
Ú
Ú
=
Ú
Ú
=
Освободимся от знака дизъюнкции
Ú
:
(
)
(
)
.yzzxyxyzzxyx ÙÙù=ÚÚ
1
Применим формулу (2):
(
)
(
)
(
)
(
)
(
)
(
)
(
)
.1111111 ÅÅÅÅÅÅÅ=ÙÙù yzzxyxyzzxyx
Пользуясь (3), раскроем скобки в последнем выражении и приведем по-
добные, получим:
(
)
(
)
(
)
.xyxyyzyzzxzyxxy 1111
Å
Å
Å
Å
=
Å
Å
Å
Å
Å
Å
Описанный в пунктах а)—д) способ построения полинома Жегалки-
на применим для любой формулы. Однако в большинстве случаев сущест-
вуют более краткие пути преобразования формулы в полином Жегалкина.
В предыдущем примере можно построить полином Жегалкина для каждо-
го сомножителя
y
x
®
и
z
y
®
, их произведение и дает полином Жегал-
кина для
(
)
z,y,xf . Действительно,
(
)
111 ÅÅ=ÅÅ==Ú=® uuvvuvuvuvu ,
откуда следует
(
)
(
)
(
)
(
)
11
Å
Å
Å
Å
=
yyzxxyzyyx ,
поэтому
(
)
(
)
1
Å
Å
Å
Å
=
xyyzxyzyyx .
Для формул, содержащих символы ~ и | при построении полинома
Жегалкина, полезно использовать эквивалентности:
1
ÅÅ=Å= vuvuv~u , (5)
1Å== uvuvvu . (6)
Пример 3. Построим полином Жегалкина для функции
(
)
(
)
(
)
(
)
yxz~xyz,y,xf Ú=ù .
Решение.
( ) ( )
(
)
(
)
( )( )
111
65
ÅÅÅÅ=ÅÅÅÅ=Úù zxxzxyzxxyzxyyxz~xy
,
. 
      г) раскрыть скобки в полученном выражении, пользуясь свойством ди-
      стрибутивности операции � относительно логического умножения
                           u �v � w � � uv � uw ;                    (3)
      д) привести подобные члены по правилу:
                                   u � u � 0.                        (4)

     Пример 2. Пусть f � x , y , z � � � x � y �� y � z � . Построить полином
Жегалкина, используя метод эквивалентных преобразований.
     Решение. Построим д.н.ф.
             � x � y �� y � z � � � x � y �� y � z � � x y � x z � yz .
Освободимся от знака дизъюнкции � :
                                                �            �
                                         �1 �
                             x y � x z � yz � � x y � x z � yz .
Применим формулу (2):
          �              �
       � x y � x z � yz � �� x � 1�� y � 1� � 1��� x � 1�z � 1�� yz � 1� � 1.
Пользуясь (3), раскроем скобки в последнем выражении и приведем по-
добные, получим:
         � xy � x � y �� xz � z � 1�� yz � 1� � 1 � yz � xy � y � x � 1.
      Описанный в пунктах а)—д) способ построения полинома Жегалки-
на применим для любой формулы. Однако в большинстве случаев сущест-
вуют более краткие пути преобразования формулы в полином Жегалкина.
В предыдущем примере можно построить полином Жегалкина для каждо-
го сомножителя x � y и y � z , их произведение и дает полином Жегал-
кина для f � x , y , z � . Действительно,
                 u � v � u � v � uv � u�v � 1� � 1 � uv � u � 1 ,
откуда следует
                   � x � y �� y � z � � � xy � x � 1�� yz � y � 1� ,
поэтому
                     � x � y �� y � z � � xy � yz � y � x � 1 .
     Для формул, содержащих символы ~ и | при построении полинома
Жегалкина, полезно использовать эквивалентности:
                       u ~ v � u � v � u � v �1,              (5)
                         u v � uv � uv � 1 .                  (6)

      Пример 3. Построим полином Жегалкина для функции
                      f � x , y , z � �� �� xy ~ z � � x � y ��.
      Решение.
                          �5 , 6 �
     � �� xy ~ z � � x � y �� � � xy � z � 1�� xy � x � 1� � xyz � xz � x � z � 1 .


                                            44

Страницы