Дискретная математика. Элементы теории, задачи и упражнения. Часть 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). Конъюнкция соответст-