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

UptoLike

Операция замыкания . Основные замкнутые классы .
__________________________________________________________________________________________
95
Пример 2. Пусть
(
)
(
)
(
)
zyyxz,y,xf
=
. Построить полином
Жегалкина, используя метод эквивалентных преобразований.
Решение. Построим д .н .ф .
(
)
(
)
(
)
(
)
.yzzxyxzyyxzyyx
=
=
Освободимся от знака дизъюнкции
:
(
)
(
)
.yzzxyxyzzxyx =∨∨
1
Применим формулу (2):
(
)
(
)
(
)
(
)
(
)
(
)
(
)
.1111111 =∧ yzzxyxyzzxyx
Пользуясь (3), раскроем скобки в последнем выражении и приведем по -
добные , получим:
(
)
(
)
(
)
.xyxyyzyzzxzyxxy 1111
=
Описанный в пунктах а) д ) способ построения полинома Жегал-
кина применим для любой формулы. Однако в большинстве случаев суще-
ствует более краткие пути преобразования формулы в полином Жегалкина.
В предыдущем примере можно построить полином Жегалкина для каждо-
го сомножителя
x
и
z
, их произведение и дает полином Жегал-
кина для
(
)
z,y,xf . Действительно,
(
)
111 ====→ uuvvuvuvuvu ,
откуда следует
(
)
(
)
(
)
(
)
11
=
yyzxxyzyyx ,
поэтому
(
)
(
)
1
=
xyyzxyzyyx .
Для формул, содержащих символы ~ и | при построении полинома
Жегалкина, полезно использовать эквивалентности:
=
=
vuvuv~u , (5)
1== uvuvvu . (6)
Пример 3. Построим полином Жегалкина для функции
(
)
(
)
(
)
(
)
yxz~xyz,y,xf =
.
Решение.
()()
()
(
)
()()
111
65
==∨ zxxzxyzxxyzxyyxz~xy
,
.
Булева функция, которой соответствует полином Жегалкина первой
степени, называется линейной. Функции, задаваемые формулами
~
x
,
y
x
,
x
,
x
,
z
y
x
,
являются линейными. Множество всех линейных булевых функций обо -
значается через
L
, множество линейных функций, зависящих от
n
пере -
менных, через
(
)
nL
. Для каждой функции
(
)
nLf
имеет место
представление