Дискретная математика. Элементы теории, задачи и упражнения. Часть 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
4. Найти число булевых функций от трех переменных, которые на задан-
ных двух наборах:
        a) принимают значение 1;
        b) принимают любые заданные значения.

5. Двоичные наборы вида �d 1 ,..., d n � и �d 1 ,...,d n � называются противопо-
ложными. Найти число булевых функций от n переменных, которые на
противоположных наборах переменных принимают:
        a) противоположные значения;
        b) одинаковые значения.

6. Построить двойственную функцию для функции f , если:
        1) f � � x � y �� x � z �� y � z �;
        2) f � �01011100 �;
        3) f � �� x � y � � x �.
7. Построить двойственные функции для всех элементарных булевых
   функций.

8. Доказать или опровергнуть равенство двух функций, используя прин-
   цип двойственности:
         1) f � x � � y � z �, � � � x � y � � � x � z �;
         2) f � x � � y � z �; � � � x � y � � � x � z �;
         3) f � x � y � z �; � � xy � xz;
         4) f � x � y � z �; � � xy � xz;
         5) f � x � � y � z �; � � � x � y � � � x � z �.

9. Доказать, что f  x, y   1, если:
         1) f � � x � y � � � y � x �;
                              �
          2) f � � x � y � � x � y ;    �
          3) f � xy � � x | y �;
          4) f � x � y � � x � y �. .


      5.2 Дизъюнктивные и конъюнктивные нормальные формы

     Пусть x – булева переменная.
     Введем обозначение: x � � x � � � x � � , где параметр � � �0 ,1�. Оче-
                 � x , если � � 1
видно, что x � � �                , т. е. x 1 � x , x 0 � x .
                 � x , если � � 0
                                            21

Страницы