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

UptoLike

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

24
Решение. Применяя основные равносильности и 1-й дистрибутив-
ный закон, строим ДНФ:
( ) ( ) ( ) ( )( )
( )( )
.yzyxxy
yzxyyyxxyxyzxyyx
yzxyyxyzyxyzyxz,y,xf
ÚÚ=
=ÚÚÚÚ=ÚÚÚ=
=Ú®®=Ú«=®Å=
Применяя 2-й дистрибутивный закон в
полученной ДНФ, построим КНФ для данной
функции.
(
)
(
)
(
)
(
)
( )( )( )( )
( )( ) ( )( )
( )( )( )( )
.
,,
yyxzyxyzxxy
yzyxyzxyyzyxxy
yzyyyxxyxx
yzyxyxxyyzyxxyzyxf
ÚÚÚÚÚÚÚ=
=ÚÚÚÚ=ÚÚÚ=
=ÚÚÚÚÚ=
=
Ú
Ú
Ú
=
Ú
Ú
=
Учитывая, что
1
1
=
Ú
=
Ú
Ú
x
y
y
x
, полу-
чим другую КНФ, равносильную построенной:
fx,y,z=xyxyzxyz
.
Пример 2. Построить ДНФ и КНФ для функции
(
)
11001011
=
f .
Решение. Строим таблицу истинности для функции, зависящей от
трех переменных, т.к. длина ее двоичного набора равна
(
)
.n 328
3
=
=
По формуле (*) с учетом, что
K
1
K&
=
,
0
0
K&
=
, имеем
(
)
.1&
1&0&0&1&
0&1&1&,,
1
111
011101001110
010100000
ДНФzyxzxyzyxzyxzyxzyx
zyxzyxzyxzyx
zyxzyxzyxzyxf
-ÚÚÚÚ=Ú
ÚÚÚÚÚ
ÚÚÚ=
Учитывая, что
(
)
cbacaba
Ú
=
Ú
, можно получить другие ДНФ для
данной функции:
(
)
(
)
( ) ( )
.ДНФyxzyxyx
zzxyzyxzzyx
zyxzyxyzxzyxzyxf
2
-ÚÚ=
=ÚÚÚÚ=
=
Ú
Ú
Ú
Ú
=
(
)
( )
( )( )
( )
.
3
ДНФyxzxyx
yxzyx
yxzyyyx
xyzyyx
yxzyxyxf
-ÚÚ=
ÚÚ=
ÚÚÚ=
=ÚÚ=
=
Ú
Ú
=
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