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

UptoLike

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

21
4. Найти число булевых функций от трех переменных, которые на задан-
ных двух наборах:
a) принимают значение 1;
b) принимают любые заданные значения.
5. Двоичные наборы вида
(
)
n
dd ,...,
1
и
(
)
n
dd ,...,
1
называются противопо-
ложными. Найти число булевых функций от
n
переменных, которые на
противоположных наборах переменных принимают:
a) противоположные значения;
b) одинаковые значения.
6. Построить двойственную функцию для функции
f
, если:
1)
(
)
(
)
(
)
;zyzxyxf
Ú
Ú
Ú
2)
(
)
;01011100
f
3)
(
)
(
)
.xyxf
®
®
7. Построить двойственные функции для всех элементарных булевых
функций.
8. Доказать или опровергнуть равенство двух функций, используя прин-
цип двойственности:
1)
(
)
,zyxf
Å
®
=
(
)
(
)
;zxyx
®
Å
®
=
j
2)
(
)
;zyxf
®
®
=
(
)
(
)
;zxyx
®
®
®
=
j
3)
(
)
;zyxf
«
=
;
xz
xy
«
=
j
4)
(
)
;zyxf
Å
=
;
xz
xy
Å
=
j
5)
(
)
;zyxf
Ú
Å
=
(
)
(
)
.zxyx
Å
Ú
Å
=
j
9. Доказать, что
,1,
fxy
если:
1)
(
)
(
)
;xyyxf
®
Ú
®
=
2)
(
)
(
)
;yxyxf ««Å=
3)
(
)
;| yxxyf «=
4)
(
)
.yxyxf ¯«Ú= .
5.2 Дизъюнктивные и конъюнктивные нормальные формы
Пусть
булева переменная.
Введем обозначение:
s
s
s
×
Ú
×
=
xxx , где параметр
{
}
.,10
Î
s
Оче-
видно, что ,
если,x
если,x
x
î
í
ì
=
=
=
0
1
s
s
s
т. е. .xx,xx
=
=
01