ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 15.04.2021
Просмотров: 1349
Скачиваний: 1
13
Для упрощения преобразований полезно использовать формулы погло-
щения и склеивания:
u
∨
uv
=
u,
uv
∨
u
¯
v
=
u.
(4
.
14)
В приведенных ниже примерах при проведении эквивалентных преобра-
зований над знаком равенства записываются номера используемых фор-
мул.
Пример 1.
Для функции
f
(
x, y, z
) = (
x
⊕
y
)
→
x
|
z
построим днф
и кнф:
(
x
⊕
y
)
→
x
|
z
(4
.
5)
=
x
⊕
y
∨
x
|
z
(4
.
8)
=
x
⊕
y
∨
¯
x
∨
¯
z
(4
.
6)
= (
x
↔
y
)
∨
¯
x
∨
¯
z
(4
.
6)
=
= ¯
x
¯
y
∨
xy
∨
¯
x
∨
¯
z
=
xy
∨
¯
x
∨
¯
z.
Применив второй дистрибутивный закон к последнему выражению, по-
лучим кнф для исходной формулы
xy
∨
¯
x
∨
¯
z
= (
x
∨
¯
x
∨
¯
z
)(
y
∨
¯
x
∨
¯
z
)
(4
.
13)
= ¯
x
∨
y
∨
¯
z.
Пример 2.
Для функции
f
(
x, y, z
) =
x
∨
z
↔
xy
построим днф и
кнф:
x
∨
z
↔
xy
(4
.
6)
=
x
∨
z xy
∨
x
∨
z xy
(4
.
9
,
4
.
12)
=
¯
x
¯
z xy
∨
(
x
∨
z
)(¯
x
∨
¯
y
)
(4
.
13)
=
= (
x
∨
z
)(¯
x
∨
¯
y
)
.
Полученное выражение представляет собой конъюнкцию различных
элементарных дизъюнкций
¯
x
∨
¯
y
и
x
∨
z
и потому является конъюнк-
тивной нормальной формой рассматриваемой функции.
Заметим, что для каждой булевой функции существует не одна
дизъюнктивная и не одна конъюнктивная нормальные формы. Произ-
водя разными способами дистрибутивные операции, мы можем прийти к
различным нормальным формам. Пусть, например, функция
φ
(
x, y, z
)
задается формулой
x
∨
yz
. Эта формула представляет собой днф. Однако
её можно привести дистрибутивными операциями и к другой нормаль-
ной форме. Применив второй дистрибутивный закон, получим кнф
K
= (
x
∨
y
)(
x
∨
z
)
.
Применив к этой формуле первый дистрибутивный закон, получим
D
=
x
∨
yx
∨
xz
∨
yz.
Эта формула также является днф функции
φ
(
x, y, z
)
. Конечно, раз-
личные нормальные формы различны лишь по виду. Все они реали-
зуют одну и ту же функцию. В случае произвольной булевой функ-
ции
f
(
x
1
, x
2
, . . . , x
n
)
её нормальные формы на наборе
(
α
1
, α
2
, . . . , α
n
)
14
принимают одно и то же значение, равное
f
(
α
1
, α
2
, . . . , α
n
)
. В следую-
щем параграфе мы выделим среди нормальных форм так называемые
совершенные нормальные формы: дизъюнктивную и конъюнктивную.
Упражнения
4.1.
По
данному
набору
(
α
1
, α
2
, . . . , α
n
)
значений
переменных
x
1
, x
2
, . . . , x
n
построить элементарную конъюнкцию, истинную
только для этого набора значений.
4.2.
По
данному
набору
(
α
1
, α
2
, . . . , α
n
)
значений
переменных
x
1
, x
2
, . . . , x
n
построить
элементарную
дизъюнкцию,
ложную
только для этого набора значений переменных.
4.3.
С помощью эквивалентных преобразований привести к днф форму-
лы:
1)
(
x
∨
y
¯
z
)(
x
∨
z
)
;
2)
((
x
1
∨
x
2
¯
x
3
x
4
)(¯
x
2
∨
x
4
)
→
x
1
x
3
x
4
)
∨
(¯
x
1
∨
x
4
)
;
3)
(
x
↓
z
)
↔
(
y
→
¯
z
)
∨
¯
xy
;
4)
(
x
1
x
2
→
x
3
x
4
)
|
(
x
1
→
¯
x
3
)
;
5)
(
x
∨
(¯
x
↔
y
))
→
x
∨
y
.
4.4.
С помощью эквивалентных преобразований привести к кнф форму-
лы:
1)
x
→
¯
yz
;
2)
((
x
1
x
2
⊕
x
3
)
→
¯
x
4
)
→
x
1
;
3)
((
x
1
|
x
2
)
→
x
3
)
↔
x
1
¯
x
4
;
4)
((
xyz
↔
(¯
y
∨
z
))
y
)
↓
x
;
5)
¬
(
x
↔
¯
yz
)
→
(¯
x
⊕
(
y
→
z
))
.
4.5.
Пусть
X
1
, . . . , X
m
, U
1
, . . . , U
n
– произвольные формулы алгебры ло-
гики. Доказать следующие эквивалентности:
1)
X
1
X
2
. . . X
m
∨
U
1
U
2
. . . U
n
=
∧
i
=1
,...,m j
=1
,...,n
(
X
i
∨
U
j
)
;
2)
(
X
1
∨
X
2
∨
. . .
∨
X
m
) (
U
1
∨
U
2
∨
. . .
∨
U
n
) =
∨
i
=1
,...,m j
=1
,...,n
X
i
U
j
.
4.6.
С помощью второго дистрибутивного закона преобразовать днф в
кнф:
1)
x
¯
y
∨
yz
∨
¯
x
¯
z
;
15
2)
xyz
∨
¯
xyz
∨
x
¯
yz
;
3)
x
1
x
2
∨
x
2
x
3
∨
x
4
¯
x
3
∨
x
2
.
§5.
Совершенные нормальные формы
В предыдущем параграфе было показано, что всякая булева функ-
ция может быть выражена в виде формулы через отрицание, дизъюнк-
цию и конъюнкцию; приведенные ниже теоремы ещё раз подтверждают
этот факт.
Теорема 1.
Для каждой булевой функции, отличной от тожде-
ственного нуля, существует и единственно (с точностью до порядка
слагаемых) следующее представление в виде дизъюнктивной нормаль-
ной формы
f
(
x
1
, x
2
, . . . , x
n
) =
∨
f
(
α
1
,α
2
,...,α
n
)=1
x
α
1
1
∧
x
α
2
2
∧
. . .
∧
x
α
n
n
.
(5
.
1)
В дальнейшем для сокращения записи формул знак конъюнкции в (5.1)
будем опускать.
Дизъюнктивная нормальная форма (5.1) называется совершенной
(сднф). Как следует из (5.1) совершенная нормальная форма отличается
от обычной днф тем, что каждое её слагаемое содержит либо переменную
x
i
, либо её отрицание
¯
x
i
для всех
i
= 1
, . . . , n
.
На основании представления (5.1) сформулируем следующий
алгоритм построения сднф, основанный на применении таблиц истинно-
сти:
– построить таблицу истинности функции
f
;
– в таблице выделить наборы, на которых функция
f
принимает зна-
чение 1;
– каждому такому набору
(
α
1
, α
2
. . . , α
n
)
поставить в соответствие
элементарную конъюнкцию
x
α
1
1
x
α
2
2
. . . x
α
n
n
,
(5
.
2)
которая только на этом наборе принимает значение 1;
– найденные элементарные конъюнкции объединить знаком дизъюнк-
ции, – полученная формула является совершенной дизъюнктивной
нормальной формой функции
f
.
16
Для тех функций, которые заданы в виде формул, сднф можно также
построить используя равенства (4.5)-(4.11) предыдущего параграфа. При
этом если какая-либо элементарная конъюнкция
K
в полученной днф не
будет содержать переменную
x
l
, её нужно заменить на две элементарные
конъюнкции
K
=
Kx
l
∨
K
¯
x
l
.
(5
.
3)
Этот процесс нужно продолжать до тех пор пока все элементарные конъ-
юнкции будут содержать все переменные
x
i
или их отрицания
¯
x
i
. После
этого удалить лишние элементарные конъюнкции, оставив из нескольких
одинаковых одну:
u
∨
u
=
u.
(5
.
4)
Теорема 2.
Для каждой булевой функции отличной от тож-
дественной 1, существует и единственно (с точностью до порядка
сомножителей) следующее представление в виде конъюнктивной нор-
мальной формы
f
(
x
1
, x
2
, . . . , x
n
) =
∧
f
(
α
1
,α
2
,...,α
n
)=0
(
x
¯
α
1
1
∨
x
¯
α
2
2
∨
. . .
∨
x
¯
α
n
n
)
.
(5
.
5)
Конъюнктивная нормальная форма (5.5) называется совершенной
(скнф).
На основании сформулированной теоремы предлагается следующий
алгоритм построения скнф с использованием таблиц истинности:
– построить таблицу истинности функции
f
;
– в таблице выделить наборы, на которых функция
f
принимает зна-
чение 0;
– каждому такому набору
(
α
1
, α
2
, . . . , α
n
)
поставить в соответствие
элементарную дизъюнкцию
x
¯
α
1
1
∨
x
¯
α
2
2
∨
. . .
∨
x
¯
α
n
n
,
(5
.
6)
которая только на этом наборе принимает значение 0;
– найденные элементарные дизъюнкции объединить знаком конъюнк-
ции, – полученная формула, согласно теореме 2, является совершен-
ной конъюнктивной нормальной формой функции
f
.
Совершенная конъюнктивная нормальная форма отличается от
обычной кнф тем, что каждый её сомножитель содержит переменную
x
i
или её отрицание
¯
x
i
для всех
i
= 1
, . . . , n
. Этот факт дает возможность
сформулировать ещё один алгоритм построения скнф (его применяют в
случае, когда функция
f
задана формулой):
17
– построить кнф функции
f
;
– если какой либо сомножитель
D
кнф не содержит переменной
x
l
его нужно заменить двумя:
D
= (
D
∨
x
l
)(
D
∨
¯
x
l
);
(5
.
7)
– этот процесс продолжать до тех пор пока все сомножители не будут
содержать все переменные
x
i
или их отрицание
¯
x
i
, i
= 1
, . . . , n
;
– из нескольких одинаковых сомножителей, полученных в результате
реализации предыдущего пункта, оставить один:
u
∧
u
=
u.
(5
.
8)
Полученный кнф будет совершенной.
Рассмотрим пример построения сднф и скнф двумя способами.
Пусть
f
(
x, y, z
) = (
x
⊕
yz
)
|
(
y
→
zx
)
.
Построим таблицу истинности.
x y z yz x
⊕
yz zx y
→
zx x
⊕
yz
)
|
(
y
→
zx
)
0
0 0
0
0
0
1
1
0
0 1
0
0
0
1
1
0
1 0
0
0
0
0
1
0
1 1
1
1
0
0
1
1
0 0
0
1
0
1
0
1
0 1
0
1
1
1
0
1
1 0
0
1
0
0
1
1
1 1
1
0
1
1
1
Выделим наборы, на которых
f
(
x, y, z
)
принимает значение 1:
(0,0,0), (0,0,1), (0,1,0), (0,1,1), (1,1,0), (1,1,1); этим наборам соответствуют
элементарные конъюнкции
¯
x
¯
y
¯
z,
¯
x
¯
yz,
¯
xy
¯
z,
¯
xyz, xy
¯
z, xyz
, объединив кото-
рые знаком дизъюнкции, получим
¯
x
¯
y
¯
z
∨
¯
x
¯
yz
∨
¯
xy
¯
z
∨
¯
xyz
∨
xy
¯
z
∨
xyz
−
сднф
.
Для построения скнф выделим наборы на которых функция
f
(
x, y, z
)
принимает значение 0: (1,0,0), (1,0,1). Им соответствуют элементарные
дизъюнкции, которые только на этих наборах принимают значение 0:
¯
x
∨
y
∨
z,
¯
x
∨
y
∨
¯
z
. Объединив их знаком конъюнкции, мы получим скнф,
реализующую данную функцию
f
:
f
= (¯
x
∨
y
∨
z
)(¯
x
∨
y
∨
¯
z
)
.