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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

32
Таблица 1
Номер
набора
х
у
z
(
)
z,y,x
j
1 0 0 0 1
2 0 0 1 1
3 0 1 0 1
4 0 1 1 0
5 1 0 0 1
6 1 0 1 0
7 1 1 0 0
8 1 1 1 0
Построим соответствующие этим наборам элементарные дизъюнкции:
,zyx
110
ÚÚ ,zyx
101
ÚÚ
,zyx
011
ÚÚ ,zyx
111
ÚÚ
перепишем в стандартной форме:
,
z
y
x
,
z
y
x
,
z
y
x
.
z
y
x
Конъюнктивное произведение этих дизъюнкций и есть СКНФ задан-
ной функции:
(
)
(
)
(
)
(
)
.zyxzyxzyxzyxK
c
=
Замечание. Очень часто булева функция задается набором своих
значений
(
)
n
,...,f
a
a
1
, где
(
)
n
n
E,...,
Î
a
a
1
,
{
}
10,E
=
. При этом вид набора
значений функции существенно зависит от того, как упорядочены наборы
(
)
n
,...,
a
a
1
на множестве
n
E
. Набору
(
)
n
,...,
a
a
1
поставим в соответствие
номер
nn
nn
...k
a
a
a
a
+
×
+
+
×
+
×
+
=
-
--
2221
1
2
2
1
1
(3)
В наборе значений функции на
k
-м месте запишем величину
(
)
n
,...,f
a
a
1
.
Так, функция, рассматриваемая в предыдущем примере, может быть запи-
сана в виде
(
)
(
)
00010111
=
z,y,x
j
.
Пример 2. Пусть
(
)
(
)
10010110
=
z,y,xf . Найти СДНФ и СКНФ.
Решение. Функция
f
принимает значение 1 на наборах с номерами
2, 3, 5, 8. Восстановим по формуле (3) эти наборы: (001), (010), (100), (111).
Объединим соответствующие этим наборам элементарные конъюнкции в
СДНФ: zyxzyxzyxzyxD
c
=
.
Значение 0 функция
f
принимает на наборах с номерами 1, 4, 6, 7.
Выпишем эти наборы: (000), (011), (110), (101). Конъюнкция соответст-
                                                            Таблица 1
                  Номер         х         у        z       � �x , y , z�
                  набора

                     1          0         0        0           1
                     2          0         0        1           1
                     3          0         1        0           1
                     4          0         1        1           0
                     5          1         0        0           1
                     6          1         0        1           0
                     7          1         1        0           0
                     8          1         1        1           0

Построим соответствующие этим наборам элементарные дизъюнкции:
                         x0 � y1 � z1 , x1 � y0 � z1 ,
                         x1 � y1 � z0 , x1 � y1 � z1 ,
перепишем в стандартной форме:
                x � y � z , x � y � z , x � y � z , x � y � z.
     Конъюнктивное произведение этих дизъюнкций и есть СКНФ задан-
ной функции: K c � � x � y � z �� x � y � z �� x � y � z �� x � y � z �.

          Замечание. Очень часто булева функция задается набором своих
значений f �� 1 ,...,� n � , где �� 1 ,...,� n � � E n , E � �0,1�. При этом вид набора
значений функции существенно зависит от того, как упорядочены наборы
�� 1 ,...,� n � на множестве E n . Набору �� 1 ,...,� n � поставим в соответствие
номер
                     k � 1 � � 1 � 2 n �1 � � 2 � 2 n � 2 � ... � � n �1 � 2 � � n  (3)
В наборе значений функции на k -м месте запишем величину f �� 1 ,...,� n � .
Так, функция, рассматриваемая в предыдущем примере, может быть запи-
сана в виде � � x , y , z � � �111010 0 0 � .

       Пример 2. Пусть f � x , y , z � � �011 010 01� . Найти СДНФ и СКНФ.
       Решение. Функция f принимает значение 1 на наборах с номерами
2, 3, 5, 8. Восстановим по формуле (3) эти наборы: (001), (010), (100), (111).
Объединим соответствующие этим наборам элементарные конъюнкции в
СДНФ: Dc � x y z � x y z � x y z � x y z .
       Значение 0 функция f принимает на наборах с номерами 1, 4, 6, 7.
Выпишем эти наборы: (000), (011), (110), (101). Конъюнкция соответст-

                                          32

Страницы