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

UptoLike

Операция замыкания . Основные замкнутые классы .
__________________________________________________________________________________________
73
Число логических множителей в э.к . и логических слагаемых в э. д . ,
называется рангом э.к. и э.д. соответственно. Считается, что константа 1
э.к. нулевого ранга , константа 0 э.д. нулевого ранга Символ & в э.к.
можно опускать для краткости
Например,
43211
xxxxK
=
э.к. 4-го ранга ;
3211
xxxD
=
э.д. 3-го ранга .
Определение. Дизъюнктивной нормальной формой (ДНФ) называ -
ется произвольная дизъюнкция различных элементарных конъюнкций, т.е.
формула вида
S
K...KKD
=
21
, где siK
i
,, 1 = э . к .
Число
S
называется длиной ДНФ. В случае
0
=
S
ДНФ называется
пустой и полагается равной нулю .
Определение. Конъюнктивной нормальной формой (КНФ) называ-
ется произвольная конъюнкция различных элементарных дизъюнкций, т.е.
формула вида
S
DDDK &...&&
21
=
,
где
S
длина КНФ , siD
i
,, 1 = э . д .
Имеют место следующие теоремы:
Теорема 1. Для каждой булевой функции
(
)
n
x,...,x,xf
21
, отличной
от тождественного нуля, существует дизъюнктивная нормальная форма
D
такая, что
(
)
Dx,...,x,xf
n
=
21
.
Теорема 2. Для каждой булевой функции
(
)
n
x,...,x,xf
21
, отличной
от тождественной единицы, существует конъюнктивная нормальная форма
K
такая, что
(
)
Kx,...,x,xf
n
=
21
.
Представление булевой функции в виде ДНФ и КНФ , вообще говоря,
неоднозначно.
Например, для функции
(
)
(
)
(
)
yxzxz,y,xf ∨= будут равносиль-
ные между собой следующие КНФ :
(
)
()()
()()()
.zxzyyxzxK
,zyyxzxK
,yxzxK
∨=
∨=
∨=
3
2
1
Рассмотрим два способа построения ДНФ и КНФ .
Способ 1. (Метод эквивалентных преобразований ). Пусть булева
функция
(
)
n
x,...,x,xf
21
задана формулой. Алгоритм построения ДНФ и
КНФ состоит в следующем :