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

UptoLike

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

22
Легко видеть, что
1
=
s
x тогда и только тогда, когда
s
=
x
.
Пусть
n
x,...,x,x
21
булевы переменные.
Определение. Формулы алгебры логики вида:
n
n
iii
x&...&x&x
s
ss
2
2
1
1
и
n
n
iii
x...xx
s
ss
ÚÚÚ
2
2
1
1
,
где
{
}
n...,,,i
k
21
Î
,
{
}
10,
k
Î
s
, называются соответственно элементарной
конъюнкцией (э.к.) и элементарной дизъюнкцией (э.д.) на множестве бу-
левых переменных
{
}
n
x,...,x,x
21
.
Число логических множителей в э.к. и логических слагаемых в э.д.,
называется рангом э.к. и э.д. соответственно. Считается, что константа
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 ®Ú= будут равносиль-
ные между собой следующие КНФ: