Дискретная математика. Элементы теории, задачи и упражнения. Часть 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
,
.