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

UptoLike

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

43
Пример 1. Построить полином Жегалкина для функции
(
)
(
)
.z,y,xf 11001110
=
Решение. Запишем общий вид полинома Жегалкина для функции,
зависящей от 3-х переменных:
(
)
.xyzazyaxzaxyazayaxaaz,y,xP
1232313123210
Å
Å
Å
Å
Å
Å
Å
=
Составим систему уравнений:
ï
ï
ï
ï
ï
î
ï
ï
ï
ï
ï
í
ì
=ÅÅÅÅÅÅÅ
=ÅÅÅ
=ÅÅÅ
=ÅÅÅ
=Å
=Å
=Å
=
.aaaaaaaa
;aaaa
;aaaa
;aaaa
;aa
;aa
;aa
;a
1
1
0
1
1
1
0
0
1232313123210
12210
13310
23320
30
20
10
0
Учитывая свойства операции «сложение по модулю 2»:
,;
;;
101000
110011
=Å=Å
=
Å
=
Å
находим коэффициенты полинома Жегалкина
,aaa 0
1210
=
=
=
1
123132332
=
=
=
=
=
aaaaa
и выписываем полином третьей степени:
(
)
xyzxzyzzyz,y,xP
Å
Å
Å
Å
==
.
2. Метод эквивалентных преобразований. Этот метод применяется в том
случае, когда функция
(
)
n
x...,,xf
1
задана в виде формулы алгебры логики.
Суть метода состоит в том, чтобы, исходя из свойств логических операций,
построить эквивалентную заданной формулу, содержащую только символы
операций логического умножения и сложения по модулю 2.
При этом следовать схеме:
а) построить ДНФ для заданной формулы;
б) в полученной ДНФ, выразить дизъюнкцию через конъюнкцию и
отрицание:
(
)
;wvuwvu ÚÚ (1)
в) в полученной в пункте б) формуле освободиться от отрицания, ис-
пользуя эквивалентность:
;uu 1Å=ù (2)