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

UptoLike

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

31
Определение. КНФ функции
(
)
n
x...,,xf
1
называется совершенной,
если она составлена из попарно различных элементарных дизъюнкций
ранга
n
, т.е. формул вида
(
)
( )
(
)
n
n
n
,...,,f
n
x...xxx...,,xf
s
ss
ss
ÚÚÚÙ=
=
21
1
21
0
1
, (2)
где конъюнктивное произведение берется по всем наборам
(
)
n
,...,,
s
s
s
21
,
для которых
12
,,...,.
)
n
(
f
sss
Ясно, что
(
)
1
1
¹
n
xxf ,..., .
Формулы, стоящие в правых частях равенств (1) и (2), соответствен-
но называются совершенной нормальной дизъюнктивной и конъюнк-
тивной формами (СДНФ и СКНФ). В отличие от обычных форм каждое
слагаемое СДНФ или каждый сомножитель СКНФ содержит все перемен-
ные
n
x,...,x
1
в некоторых «степенях». Рассмотрим два способа их по-
строения.
Первым способом совершенные нормальные формы для произволь-
ной булевой функции можно строить, исходя из представлений (1)(2).
Для этого достаточно построить таблицу истинности функции. Для по-
строения СДНФ нужно выделить те наборы
(
)
n
,...,,
s
s
s
21
, на которых
(
)
1
21
=
n
,...,,f
s
s
s
. Каждому такому набору ставится в соответствие эле-
ментарная конъюнкция
n
n
x&...&x&x
s
ss
21
21
. Составленная из этих конъ-
юнкций дизъюнктивная сумма и есть искомая СДНФ.
Для построения СКНФ нужно выбрать наборы
(
)
n
,...,,
s
s
s
21
, для ко-
торых
(
)
0
21
=
n
,...,,f
s
s
s
. Каждому такому набору ставится в соответст-
вие элементарная дизъюнкция
n
n
x...xx
s
ss
ÚÚÚ
21
21
. Объединяя такие дизъ-
юнкции в конъюнктивное произведение, получим СКНФ.
Пример 1. Пусть функция
(
)
z,y,x
j
принимает значение 1 тогда и
только тогда, когда большинство переменных равно нулю. Построим
СДНФ и СКНФ этой функции.
Решение. Рассмотрим таблицу истинности заданной функции (таб-
лица 1):
Функция
(
)
z,y,x
j
принимает значение 1 на наборах (000), (001),
(010), (100). Этим наборам соответствуют элементарные конъюнкции
,zyx
000
,zyx
100
,zyx
010
,zyx
001
которые с учетом (1) перепишем в виде:
,
z
y
x
,
z
y
x
,
z
y
x
.
z
y
x
Окончательно имеем СДНФ функции
(
)
z,y,x
j
:
Для построения СКНФ заметим, что рассматриваемая функция при-
нимает значение 0 на наборах (011), (101), (110) и (111).
.zyxzyxzyxzyxD
c
Ú
Ú
Ú
=