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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

Операция замыкания . Основные замкнутые классы .
__________________________________________________________________________________________
83
Построим соответствующие этим наборам элементарные дизъюнк-
ции:
,zyx
110
∨∨ ,zyx
101
∨∨ ,zyx
011
∨∨ ,zyx
111
∨∨
перепишем в стандартной форме:
,
z
y
x
∨
∨
,
z
y
x
∨
∨
,
z
y
x
∨
∨
.
z
y
x
∨
∨
Конъюнктивное произведение этих дизъюнкций и есть СКНФ задан-
ной функции:
(
)
(
)
(
)
(
)
.zyxzyxzyxzyxK
c
∨
∨
∨
∨
∨
∨
∨
∨
=
Замечание. Очень часто булева функция задается набором своих
значений
(
)
n
,...,f
1
, где
(
)
n
n
E,..., ∈αα
1
,
{
}
10 ,E
=
. При этом вид набора
значений функции существенно зависит от того , как упорядочены наборы
(
)
n
,...,
1
на множестве
n
E
. Набору
(
)
n
,...,
1
поставим в соответствие
номер
nn
nn
...k αααα +⋅++⋅+⋅+=
−
−−
2221
1
2
2
1
1
(3)
В наборе значений функции на
k
-м месте запишем величину
(
)
n
,...,f
1
.
Так, функция, рассматриваемая в предыдущем примере , может быть запи -
сана в виде
(
)
(
)
00010111
=
z,y,x
.
Пример 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). Конъюнкция соответст -
вующих этим наборам элементарных дизъюнкций является СКНФ задан-
ной функции:
(
)
(
)
(
)
(
)
.zyxzyxzyxzyxK
c
∨
∨
∨
∨
∨
∨
∨
∨
=
Рассмотренные примеры являются иллюстрацией к первому способу
построения СКНФ и СДНФ , основанному на представлениях (1) и (2).
Применяется он , как правило, для функций, заданных таблицей истинно-
сти или набором значений. Если же функция задана аналитически, т.е. при
помощи формулы, то для нее нужно сначала построить таблицу истинно-
сти, а затем применять описанный метод .
Второй способ построения СДНФ и СКНФ состоит в эквивалентном
преобразовании формулы, реализующей функцию , к виду (1) или (2). Как
уже отмечалось, совершенные дизъюнктивная или конъюнктивная нор-
мальные формы функции
(
)
n
x...,,xf
1
отличаются от обычных тем, что
каждое слагаемое СДНФ и каждый сомножитель СКНФ содержит все пе -

Страницы