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

UptoLike

Операция замыкания . Основные замкнутые классы .
__________________________________________________________________________________________
82
(
)
()
(
)
n
n
n
,...,,f
n
x...xxx...,,xf
σσσ
σσ
∧=
=
21
1
21
0
1
, (2)
где конъюнктивное произведение берется по всем наборам
(
)
n
,...,,
σ
σ
σ
21
,
для которых
(
)
0
21
=
n
,...,,f
σ
σ
σ
.Ясно, что
(
)
1
1
n
xxf ,...,
Формулы, стоящие в правых частях равенств (1) и (2), соответствен -
но называются совершенной нормальной дизъюнктивной и конъюнк-
тивной формами (СДНФ и СКНФ ). В отличие от обычных форм каждое
слагаемое СДНФ или каждый сомножитель СКНФ содержит все перемен -
ные
n
x,...,x
1
в некоторых «степенях» . Рассмотрим два способа их по -
строения.
Первым способом совершенные нормальные формы для произволь-
ной булевой функции можно строить, исходя из представлений (1) (2).
Для этого достаточно построить таблицу истинности функции. Для по -
строения СДНФ нужно выделить те наборы
(
)
n
,...,,
σ
σ
σ
21
, на которых
(
)
1
21
=
n
,...,,f
σ
σ
σ
. Каждому такому набору ставится в соответствие эле-
ментарная конъюнкция
n
n
x&...&x&x
σσσ
21
21
. Составленная из этих конъ-
юнкций дизъюнктивная сумма и есть искомая СДНФ .
Для построения СКНФ нужно выбрать наборы
(
)
n
,...,,
σ
σ
σ
21
, для ко-
торых
(
)
0
21
=
n
,...,,f
σ
σ
σ
. Каждому такому набору ставится в соответст -
вие элементарная дизъюнкция
n
n
x...xx
σσσ
∨∨
21
21
. Объединяя такие дизъ -
юнкции в конъюнктивное произведение, получим СКНФ .
Пример 1. Пусть функция
(
)
z,y,x
ϕ
принимает значение 1 тогда и
только тогда, когда большинство переменных равно нулю . Построим
СДНФ и СКНФ этой функции.
Решение. Рассмотрим таблицу истинности заданной функции (таб-
лица 1):
Функция
(
)
z,y,x
ϕ
принимает значение 1 на наборах (000), (001),
(010), (100). Этим наборам соответствуют элементарные конъюнкции
,zyx
000
,zyx
100
,zyx
010
,zyx
001
которые с учетом (1) перепишем в виде:
,
z
x
,
z
x
,
z
x
.
z
x
Окончательно имеем СДНФ функ-
ции
(
)
z,y,x
ϕ
:
Для построения СКНФ заме-
тим, что рассматриваемая функция
принимает значение 0 на наборах
(011), (101), (110) и (111).
но -
мер
набора
x
z
(
)
z,y,x
ϕ
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
Таблица 1
.zyxzyxzyxzyxD
c
=