ВУЗ:
Составители:
Рубрика:
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
Страницы
- « первая
- ‹ предыдущая
- …
- 30
- 31
- 32
- 33
- 34
- …
- следующая ›
- последняя »