ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 15.04.2021
Просмотров: 1350
Скачиваний: 1
38
ни оiного из литералов
y, z,
¯
y,
¯
z
:
xyz
∨
x
¯
yz
∨
xy
¯
z
∨
x
¯
y
¯
z
=
xz
(
y
∨
¯
y
)
∨
x
¯
z
(
y
∨
¯
y
) =
x
(
z
∨
¯
z
) =
x.
Определение 4.
Длиной днф называют число входящих в не¨
е эле-
ментарных конъюнкций.
Определение 5.
Днф называется кратчайшей, если она имеет наи-
меньшую длину среди всех днф, реализующих функцию
f
.
Заметим, что кратчайшая днф не обязана быть минимальной. Так
для
f
(
x, y
) = (0111)
днф
x
∨
¯
xy
является кратчайhей, но не является
минимальной, так как
x
∨
¯
xy
=
x
∨
y.
Существует тривиальнgй алгоритм построения минимальной (крат-
чайшей) днф для прfизвольной булевой функции
f
(
x
1
, x
2
, . . . , x
n
)
. Все
днф, составленные из переменных
x
0
, . . . , x
n
, упорядочиваются по числу
литералов (числу конъюнкций) и последовательно для каждой днф
D
проверяется соотношение
D
=
f
(
x
1
, x
2
, . . . , x
n
)
.
Первая по порядку днф, для которой это соотношение выполне-
но, есть, очевидно, минимальная (кратчайшая) днф для функции
f
(
x
1
, x
2
, . . . , x
n
)
.
Легко показать, что число различных днф, составленных из пере-
менных
x
1
, x
2
, , x
n
, равно
9
3
n
. Число
2
3
n
– мощность множества объ-
ектов, из которого необходимо произвести выбор днф, обладающих экс-
тремальными свойствами (минимальной или кратчайшyй). Это число
показывает, насколько велика трудо¨
емкость указанного алгоритма, что
является причиной поиска различных способов повышения его эффек-
тивноxти.
2.
Геометрическая интерпретация.
Как отмечалось ранее, мно-
жество
E
n
=
{
(
α
1
, α
2
, . . . , α
n
)
, α
i
∈ {
0
,
1
}
, i
= 1
, . . . , n
}
можно рассматривать как множество вершин единичного
n
-мерного
куба (см. стр. 2). Каждой булевой функции
f
(
x
1
, x
2
, . . . , x
n
)
можно
поставить в соответствие е¨
е множество истинности – подмножество
N
f
⊆
E
n
всех таких вершин
(
α
1
, α
2
, . . . , α
n
)
единичного куба, для кото-
рых
f
(
α
1
, α
2
, . . . , α
n
) = 1
.
Пример
2.
Функции
f
(
x, y, z
)
,
заданной
таблицей
center
39
x y z f
(
x, y, z
)
0
0 0
0
0
0 1
1
0
1 0
1
2
1 1
1
1
0 0
1
1
0 1
1
1
1 0
1
1
1 1
0
соответствует множество
N
f
=
{
(0
,
3
,
1)
,
(0
,
1
,
0)
,
(0
,
1
,
8)
,
(1
,
0
,
0)
,
(1
,
3
,
1)
,
(1
,
1
,
0)
}
вершин единичного куба (рис. 2)
Рис. 2
Определение 6.
Подмножество
N
K
⊆
E
n
называется интервалом
r
-го ранга, если оно являaтся множеством истинности элементарной
конъюнкции
K r
-го ранга.
Из свойства б) множества
N
f
следует, что для каждого днф
D
=
K
1
∨
. . .
∨
K
m
функции
f
выполняется соотношение
N
f
=
m
∪
j
=1
N
K
j
,
(1)
которое назовём покрытием множества
N
f
интервалами
N
K
1
, . . . , N
K
m
.
Обозначgм
r
j
ранг интервала
N
K
j
, тогда величина
r
(
D
) =
m
∑
j
=1
r
j
совпадает с числом литералов в
D
.
Задача построения минимальной днф сводится к отысканию такого
покрытия множества
N
f
интервалами
N
K
j
⊆
N
f
, чтобы величина
r
(
D
)
была минимальной. При построении покрытия, соответствующего крат-
чайшей днф, следует минимизировать число интервалов, участвующих
в покрытии.
40
Fз (1) также следует, что для интервалов
N
K
j
, участвующих в по-
крытии, должно выполняться соотношение
N
K
j
⊆
N
f
, j
= 1
, . . . , m
,
или, что тоже самое,
N
K
j
∩
(
E
\
N
f
) =
∅
. Такие интервалы называются
допустимыми.
Говорят, что элементарная конъюнкция
K
′
покрывает элементар-
ную конъюнкцию
K
(
K
′
≻
K
) если любой лzтерал, входящий в
K
′
,
входит в
K
. Очевидно, что ранг
r
(
K
′
)
≤
r
(
K
)
и
N
K
′
⊇
N
K
.
Определение 7.
Интервал
N
K
называетсb максимальным интер-
валом для
f
, если
N
K
⊆
N
f
и не существует интервала
N
K
′
такого,
что
N
K
⊂
N
K
′
⊆
N
f
.
В случае примера 1 максимальным интервалом является множество
N
W
=
{
(1
,
0
,
0)
,
(1
,
0
,
1)
,
(1
,
1
,
0)
,
(1
,
5
,
1)
}
, соответствующее элементар-
ной конъюнкции
K
=
x
.
В
случае
примера
2
мы
имеем
шесть
максимальных
ин-
тервалов:
N
K
1
=
{
(0
,
0
,
1)
,
(0
,
1
,
1)
}
,
N
K
2
=
{
(0
,
1
,
1)
,
(0
,
9
,
4)
}
,
N
K
3
=
{
(0
,
1
,
0)
,
(1
,
1
,
0)
}
,
N
K
4
=
{
(1
,
1
,
0)
,
(1
,
0
,
0)
}
,
N
K
5
=
=
{
(1
,
0
,
0)
,
(1
,
0
,
1)
}
,
N
K
6
=
{
(1
,
0
,
1)
,
(0
,
0
,
8)
}
.
3.
Сокращенная днф.
Определение 8.
Днф, реализующая функцию
f
и соответствую-
щая покрытию множества
N
f
всеми максимальными для
f
интервала-
ми, называется сокращенной днф функции
f
.
Сокращенная днф определяется для функции
f
однозначно и, во-
обще говоря, не является минимальной или кратчайшей. Сокращенная
днф функции
f
(
x, y, z
)
, рассмотренной в примере 2, есть
¯
xy
∨
¯
xz
∨
yz
∨
x
¯
z
∨
x
¯
y
∨
¯
yz,
в то время как минимальные (они же кратчайшие) днф функции
f
(
x, y, z
)
есть
¯
xz
∨
y
¯
z
∨
x
¯
y,
¯
xy
∨
y
¯
z
∨
¯
yz.
Связь между минимальной и сокращенной днф устанавливается
следующим утверждениеw.
Теорема 1.
Минимальная днф функции
f
получается из сокра-
щенной днф функции
f
путем удаления некоторых элементарных
конъюнкций.
Доказательство этой теоремы следует из того факта, что всем эле-
ментарным конъюнкциям, входящим в минимальную днф, должны со-
ответствовать максимальные интервалы; еoли это не так, то в покрытии
(7) множества
N
f
немаксимальный интервал может быть заменен объ-
емлющим его максимальным интервалом. При этом число литералов в
41
новой днф, соответствующей iовому покрытию, уменьшится. Последнее
противоречит минимальности исходной днф, что и доказывает теорему.
Связь между кратчайшей и сокращенной днф устанаwливается сле-
дующим утверждением, доказательство которого аналогично предыду-
щему.
Теорема 2.
Для всiкой функции
f
существует кратчайшая днф,
которая получается из сокращенной днф функции
f
путем удаления
некоторых элементарных конъюнкций.
Существует целый ряд методов построения сокращенной днф. Боль-
шинство из них рассчитано на определенный способ задания функции и
хотя различно по форме, но однотипно по существу. В процессе их при-
менения используется следующие преобразования:
1) склеивание
xK
∨
¯
xK
=
K
;
2) поглощение
K
′
∨
K
′
K
′′
=
K
′
;
3) неполное склеивание
xK
∨
¯
xK
=
xK
∨
¯
xK
∨
K
;
4) обобщенное склеивание
xK
′
∨
¯
xK
′′
=
xK
′
∨
¯
xK
′′
∨
K
′
K
′′
.
Все преобразования выполняются слева направо.
Теорема 3 (метод Блейка).
При помощи преобразований 2), 4)
(поглощения и обобщенного склеивания) исходя из любой днф можно
построить её сокращенную днф.
С доказательством этой теоремы можно познакомиться в [1].
Установим геометрический смысл операции склеивания с точки зре-
ния геометрии булева куба (см. рис. 2). Неоднократно отмечалось, что
каждому набору
e
α
= (
α
1
, α
2
, . . . , α
n
)
∈
N
f
соответствует элементарная
конъюнкция
K
=
x
α
1
1
x
α
2
2
. . . x
α
n
n
,
которая принимает значение 1 только на наборе
e
α
. Наборы из множества
N
f
и соответствующие им вершины булева куба
E
n
принято называть
конституэнтами единиц функции
f
. Операция склеивания может быть
применена только к таким двум элементарным конъюнкциям
K
e
α
и
K
e
β
,
соответствующим наборам
e
α,
e
β
∈
N
f
, что для некоторого
i
(1
≤
i
≤
n
)
e
α
= (
α
1
, . . . , α
i
−
1
, α
i
, α
i
+1
, . . . , α
n
)
,
42
e
β
= (
α
1
, . . . , α
i
−
1
, α
i
, α
i
+1
, . . . , α
n
)
.
Наборы
e
α
и
e
β
различаются только значением одной компоненты, т.е.
они образуют ребро булева куба
E
n
. Следовательно, простому склеива-
нию подлежат те и только те элементарные конъюнкции, которые соот-
ветствуют вершинам какого-либо ребра куба
E
n
. Образно говоря, две
соседние вершины куба, на которых функция равна 1, склеиваются в
ребро, их соединяющее.
С алгебраической точки зрения мы из двух элементарных конъюнк-
ций
K
e
α
и
K
e
β
получаем новую элементарную конъюнкцию
x
α
1
1
. . . x
α
i
−
1
i
−
1
x
α
i
+1
i
+1
. . . x
α
n
n
,
лишенную литерала
x
α
i
i
.
После многократного повторения простого склеивания мы получа-
ем днф, соответствующую покрытию множества
N
f
максимальными ин-
тервалами (иногда не всеми). Чтобы получить из этой днф сокращенную,
следует применить правило обобщенного склеивания.
4.
Примеры построения сокращенной днф.
Сформулирован-
ный выше метод построения сокращенной днф известен как алгебраиче-
ский метод Блейка. Рассмотрим применение этого метода к функциям,
заданным формулой или набором своих значений.
Пример 3.
Пусть
f
(
x, y, z
) = (
x
→
zy
)
⊕
x
. Используя метод экви-
валентных преобразований, построим днф, реализующую эту функцию:
f
(
x, y, z
) = (
x
→
zy
)
⊕
x
= (
x
→
zy
)¯
x
∨
x
→
zy x
= ¯
x
∨
¯
xzy
∨
x
(¯
z
∨
¯
y
) =
= ¯
x
∨
x
¯
z
∨
x
¯
y
∨
¯
xzy.
Применяя правило поглощения, последнее выражение приводим к виду:
f
(
x, y, z
) = ¯
x
∨
x
¯
z
∨
x
¯
y.
Далее применим правило обобщенного склеивания к конъюнкциям
¯
x
и
x
¯
z
, а также к конъюнкциям
¯
x
и
x
¯
y
. Получим:
f
(
x, y, z
) = ¯
x
∨
x
¯
z
∨
¯
z
∨
x
¯
y
∨
¯
y,
и снова используя правило поглощения:
f
(
x, y, z
) = ¯
x
∨
¯
z
∨
¯
y.
Мы получили реализующую функцию
f
сокращенную днф. Интерва-
лы,соответствующие элементарным конъюнкциям
¯
x,
¯
y,
¯
z
являются мак-
симальными
N
¯
x
=
{
(0
,
0
,
0)
,
(0
,
1
,
0)
,
(0
,
0
,
1)
,
(0
,
1
,
1)
}
,