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

UptoLike

Операция замыкания . Основные замкнутые классы .
__________________________________________________________________________________________
75
Применяя 2-ой дистрибутивный закон в полученной ДНФ , построим
КНФ для данной функции.
(
)
(
)
(
)
(
)
()()()()
()() ()()
()()()()
.
,,
yyxzyxyzxxy
yzyxyzxyyzyxxy
yzyyyxxyxx
yzyxyxxyyzyxxyzyxf
∨=
==∨=
=∨∨∨∨=
=
=
=
Учитывая, что
1
1
=
=
x
y
y
x
, получим другую КНФ , равно-
сильную построенной:
(
)
(
)
(
)
(
)
zyxzyxyxzyxf ∨= ,, .
Пример 2. Построить ДНФ и КНФ для функции
(
)
11001011
=
f .
Решение. Строим таблицу истинности для функции, зависящей от
трех переменных , т.к. длина ее двоичного набора равна
(
)
.n 328
3
==
По формуле () с учетом, что
K
1
=
,
0
0
=
,имеем
(
)
.1&
1&0&0&1&
0&1&1&,,
1
111
011101001110
010100000
ÄÍÔzyxzxyzyxzyxzyxzyx
zyxzyxzyxzyx
zyxzyxzyxzyxf
=∨
∨∨
∨=
Учитывая, что
(
)
cbacaba
=
, можно получить другие ДНФ для
данной функции:
(
)
(
)
() ()
.ДНФyxzyxyx
zzxyzyxzzyx
zyxzyxyzxzyxzyxf
2
∨=
=∨=
=
=
(
)
()
()()
()
.ÄÍÔyxzxyx
yxzyx
yxzyyyx
xyzyyx
yxzyxyxf
3
∨=
∨=
∨=
=∨=
=
=
Разлагая данную функцию
f
по формуле (**)
с учетом, что
1
1
=
D
,
D
D
=
0
, имеем
(
)
(
)
(
()()()(
()
()()(
()()()
.КНФzyxzyxzyx
zyxzyxzyxzyx
y
xzyxzyxzyx
zyxzyxzyx)z,y,x(f
1
010110101111
1101001110
010100000
1
001
11
∨=
=∨∧
∨∧
∨=
x y z f
0 0 0 1
0 0 1 1
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 0
1 1 0 1
1
1
1
1