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

UptoLike

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

25
Разлагая данную функцию
f
по формуле (**) с учетом, что
1
1
=
Ú
D
,
D
D
=
Ú
0
, имеем
(
(
(
( )( )( )( )
( )
( )( )( )
( )( )( )
.КНФzyxzyxzyx
zyxzyxzyxzyx
zyxzyxzyxzyx
zyxzyxzyx)z,y,x(f
1
010110101111
011101001110
010100000
1
1001
011
-ÚÚÚÚÚÚ=
=ÚÚÚÚÚÚ=ÚÚÚÙ
ÙÚÚÚÚÚÚÚÚÚÚÚÚÙ
ÙÚÚÚÚÚÚÚÚÚ=
Учитывая, что
(
(
aabbababa =Ú=Ú=ÚÚ 0 , получим другую
КНФ, равносильную КНФ
1
:
(
(
(
(
(
.КНФyxzyxzzyxzyxf
2
-
Ú
Ú
Ú
=
Ú
Ú
Ú
Ú
=
Неоднозначность нормальных форм очевидна.
Таким образом, применяя различные равносильные преобразования,
мы можем прийти к различным нормальным формам, реализующих одну и
ту же функцию. В связи с этим возникает возможность выбора более
предпочтительной реализации.
ЗАДАЧИ И УПРАЖНЕНИЯ
1. По данному набору
(
n
a
a
,...,
1
значений переменных
n
xx ,...,
1
постро-
ить элементарную конъюнкцию, истинную только для этого набора значе-
ний переменных.
2. По данному набору
(
)
n
a
a
,....
1
значений переменных
n
xx ,...,
1
построить
элементарную дизъюнкцию, ложную только для этого набора значений пе-
ременных.
3. С помощью эквивалентных преобразований привести к ДНФ формулы:
1)
(
(
;zxyzx
Ú
Ú
2)
(
(
(
(
;
41431424321
xxxxxxxxxxx
Ú
Ú
®
Ú
Ú
3)
(
(
;~ yxzyzx Ú®¯
4)
(
(
;|
314321
xxxxxx
®
®
5)
(
(
.~ yxyxx Ú®Ú
4. С помощью эквивалентных преобразований привести к КНФ формулы:
1)
;
z
y
x
®
2)
(
(
;xxxxx
®
®
Å
4321
3)
(
(
;~|
41321
xxxxx
®
4)
(
(
(
;~ xyzyxyz ¯Ú
5)
(
(
(
.~ zyxzyx ®Å®ù