ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 15.04.2021
Просмотров: 1355
Скачиваний: 1
43
N
¯
y
=
{
(0
,
0
,
0)
,
(1
,
0
,
0)
,
(0
,
0
,
1)
,
(1
,
0
,
1)
}
,
N
¯
z
=
{
(0
,
0
,
0)
,
(0
,
1
,
0)
,
(1
,
0
,
0)
,
(1
,
1
,
0)
}
.
Пример 4.
Мажоритарной функцией или функцией голосования
принято называть функцию, зависящую от нечетного числа переменных,
которая принимает значение 1, если большинство её переменных равны
1. В случае, когда
f
зависит от 3-х переменных, сднф мажоритарной
функции записывается в виде
f
(
x, y, z
) =
xyz
∨
¯
xyz
∨
x
¯
yz
∨
xy
¯
z.
Построение сокращенной днф по методу Блейка для этой функции
состоит из следующих этапов:
-
применение правила обобщенного склеивания:
f
(
x, y, z
) = (
xyz
∨
xy
¯
z
)
∨
(
xyz
∨
¯
xyz
)
∨
(
xyz
∨
x
¯
yz
) =
=
xyz
∨
xy
¯
z
∨
xy
∨
xyz
∨
¯
xyz
∨
yz
∨
xyz
∨
x
¯
yz
∨
xz
;
-
применение правила поглощения:
f
(
x, y, z
) =
xy
∨
yz
∨
xz.
Дальнейшее применение этих правил не приводит к появлению но-
вых элементарных конъюнкций. Интервалы
N
xy
,
N
yz
и
N
xz
являются
максимальными
N
xy
=
{
(1
,
1
,
0)
,
(1
,
1
,
1)
}
,
N
yz
=
{
(0
,
1
,
1)
,
(1
,
1
,
1)
}
,
N
xz
=
{
(1
,
0
,
1)
,
(1
,
1
,
1)
}
.
Построенная днф является сокращенной, а также минимальной и крат-
чайшей для функции
f
.
Замечание.
Следует отметить, что применение правила обобщенно-
го склеивания к элементарным конъюнкциям вида
xK
и
¯
xK
и последу-
ющее за этим применение правила поглощения равносильно применению
к этим конъюнкциям правила простого склеивания. Это упрощает опе-
рацию по построению сокращенной днф, что будет продемонстрировано
ниже.
В рассматриваемом ранее примере 2 применение метода Блейка при-
водит к образованию сокращенной днф, состоящей из шести элементар-
ных конъюнкций:
f
(
x, y, z
) = (¯
x
¯
yz
∨
¯
xyz
)
∨
(¯
xy
¯
z
∨
xy
¯
z
)
∨
(
x
¯
y
¯
z
∨
x
¯
yz
) = ¯
xz
∨
y
¯
z
∨
x
¯
y
=
44
= (¯
xz
∨
x
¯
y
)
∨
(
y
¯
z
∨
x
¯
y
) = ¯
xz
∨
x
¯
y
∨
¯
yz
∨
y
¯
z
∨
x
¯
z
= (¯
xz
∨
y
¯
z
)
∨
x
¯
y
∨
¯
yz
∨
x
¯
z
=
= ¯
xy
∨
x
¯
y
∨
¯
yz
∨
y
¯
z
∨
x
¯
z
∨
¯
xz.
Здесь в первой строке в скобки объединяются слагаемые, к которым
в последующем применяется правило простого склеивания, во второй
строке к объединенным в скобкам элементарным конъюнкциям приме-
няется правило обобщенного склеивания.
Пример
5.
Рассмотрим
функцию
f
,
зависящая
от
4-х
переменных
и
заданную
набором
своих
значений:
f
(
x
1
, x
2
, x
3
, x
4
) = (0111011110101000)
. Её сднф, что легко проверить,
имеет вид:
f
(
x
1
, x
2
, x
3
, x
4
) = ¯
x
1
¯
x
2
¯
x
3
x
4
∨
¯
x
1
x
2
¯
x
3
x
4
∨
¯
x
1
¯
x
2
x
3
¯
x
4
∨
¯
x
1
¯
x
2
x
3
x
4
∨
∨
¯
x
1
x
2
x
3
¯
x
4
∨
¯
x
1
x
2
x
3
x
4
∨
x
1
¯
x
2
¯
x
3
¯
x
4
∨
x
1
¯
x
2
x
3
¯
x
4
∨
x
1
x
2
¯
x
3
¯
x
4
.
После попарного склеивания элементарных конъюнкций в сднф по-
лучаем:
f
(
x
1
, x
2
, x
3
, x
4
) = ¯
x
1
¯
x
3
x
4
∨
¯
x
1
¯
x
2
x
3
∨
¯
x
1
x
2
x
3
∨
x
1
¯
x
2
¯
x
4
∨
x
1
¯
x
3
¯
x
4
=
= ¯
x
1
¯
x
3
x
4
∨
¯
x
1
x
3
∨
x
1
¯
x
2
¯
x
4
∨
x
1
¯
x
3
¯
x
4
Согласно правилам обобщенного склеивания и поглощения имеем:
¯
x
1
¯
x
3
x
4
∨
¯
x
1
x
3
= ¯
x
1
¯
x
3
x
4
∨
¯
x
1
x
3
∨
¯
x
1
x
4
= ¯
x
1
x
3
∨
¯
x
1
x
4
,
поэтому
f
(
x
1
, x
2
, x
3
, x
4
) = ¯
x
1
x
3
∨
¯
x
1
x
4
∨
x
1
¯
x
2
¯
x
4
∨
x
1
¯
x
3
¯
x
4
(
∨
x
3
¯
x
2
¯
x
4
.
)
Дальнейшее применение метода Блейка не приводит к образованию но-
вых конъюнкций. Поэтому построенная днф является сокращенной для
рассматриваемой функции
f
.
5.
Тупиковая днф.
После того, как сокращенная днф построена,
для получения минимальной (кратчайшей) днф можно воспользоваться
тривиальным алгоритмом. Очевидно, что в этом случае его эффектив-
ность повышается, но и здесь приходится рассматривать большое число
днф, чтобы среди них найти минимальную (кратчайшую) и реализую-
щую функцию
f
.
Определение 9.
Покрытие множества
N
f
⊂
E
n
максимальными
интервалами называется неприводимым, если, после удаления из него
любого интервала, оно перестает быть покрытием.
Определение 10.
Днф функции
f
называется тупиковой, если ей
соответствует неприводимое покрытие множества
N
f
.
45
Очевидно, что всякая минимальная (кратчайшая) днф является ту-
пиковой.
Пример 6.
Рассмотрим функцию
f
(
x, y, z
)
, заданную набором сво-
их значений
f
= (11100111)
. Её сднф имеет вид:
f
(
x, y, z
) = ¯
x
¯
y
¯
z
∨
¯
x
¯
yz
∨
¯
xy
¯
z
∨
x
¯
yz
∨
xy
¯
z
∨
xyz.
Множество истинности этой функции изображено на рис.3.
Рис. 3
Сокращенной днф этой функции являются
f
(
x, y, z
) =
x
¯
y
∨
¯
yz
∨
xz
∨
xy
∨
y
¯
z
∨
¯
x
¯
z.
Пользуясь этим изображением, нетрудно установить, что тупиковая
днф рассматриваемой функции является
D
1
=
xy
∨
¯
x
¯
z
∨
¯
yz,
D
2
=
y
¯
z
∨
¯
x
¯
y
∨
xz,
D
3
= ¯
x
¯
y
∨
xy
∨
¯
yz
∨
y
¯
z,
D
4
= ¯
x
¯
y
∨
xz
∨
xy
∨
¯
x
¯
z,
D
5
= ¯
yz
∨
xz
∨
y
¯
z
∨
¯
x
¯
z.
Дизъюнктивные нормальные формы
D
1
и
D
2
являются минимальными
и кратчайшими для функции
f
(
x, y, z
)
;
D
3
,
D
4
являются тупиковыми
днф, но не являются ни минимальными, ни кратчайшими.
Аналогично находятся тупиковые днф в примере 2. Среди них от-
метим минимальные и кратчайшие:
D
1
= ¯
xy
∨
y
¯
z
∨
x
¯
y,
D
2
= ¯
xy
∨
x
¯
z
∨
¯
yz.
46
Таким образом, если сокращенная днф строится однозначно для
каждой булевой функции, то процесс перехода от сокращенной днф к ту-
пиковой неоднозначен и не каждая тупиковая днф является минималь-
ной или кратчайшей днф. Алгоритм построения минимальной и крат-
чайшей днф может быть изображен в виде следующей схемы:
Таким образом, построение минимальных и кратчайших днф состоит из
следующих этапов:
1. Построение множества истинности
N
f
функции
f
.
2. Выделение всех максимальных интервалов и построение сокращен-
ной днф.
3. Построение тупиковых днф.
4. Выделение всех минимальных и кратчайших днф среди тупиковых.
Тупиковую днф можно построить с помощью так называемой таб-
лицы Квайна [1]. Столбцы этой таблицы соответствуют элементарным
конъюнкциям исходной днф, а строки простым импликантам (элемен-
тарным конъюнкциям) сокращенной днф. На пересечении строки и
столбца проставляется знак +(плюс), если простая импликанта данной
строки покрывает элементарную конъюнкцию данного столбца. Постро-
им таблицу Квайна в случае примера 5. Она имеет следующий вид:
0001 0011 0010 0101 0111 0110 1100 1000 1010
0
× ×
1
+
+
+
+
0
×
1
×
+
+
+
+
1 0
×
0
+
+
×
0 1 0
+
+
1
×
0 0
+
+
Из построенной таблицы следует, что любая тупиковая днф в рас-
сматриваемом случае с необходимостью включает элементарные конъ-
юнкции
¯
x
1
x
4
(первая строка),
¯
x
1
x
3
(вторая строка),
x
1
¯
x
3
¯
x
4
(последняя
47
строка). Для покрытия набора
(1010)
∈
N
f
достаточно взять одну из
элементарных конъюнкций
x
1
¯
x
2
¯
x
4
или
¯
x
2
x
3
¯
x
4
. Таким образом, мы име-
ем две тупиковые днф:
f
(
x
1
, x
2
, x
3
, x
4
) = ¯
x
1
x
4
∨
¯
x
1
x
3
∨
x
1
¯
x
3
¯
x
4
∨
x
1
¯
x
2
¯
x
4
,
f
(
x
1
, x
2
, x
3
, x
4
) = ¯
x
1
x
4
∨
¯
x
1
x
3
∨
x
1
¯
x
3
¯
x
4
∨
¯
x
2
x
3
¯
x
4
.
Обе эти днф являются минимальными и кратчайшими.
Упражнения.
13.1.
Построить минимальные и кратчайшие днф для следующих функ-
ций:
1)
(
x
→
y
)
⊕
z
;
2)
(
xy
⊕
z
)
|
(¯
x
∨
y
)
;
3)
(
x
↓
z
)
→
(
y
⊕
¯
z
)
;
4)
(
x
1
x
2
∨
x
3
)
→
(
x
4
⊕
¯
x
1
)
;
5)
x
1
x
2
x
3
⊕
x
1
x
4
⊕
x
3
;
6)
xy
⊕
z
⊕
1
;
7)
((
x
|
y
)
|
z
)
→
(
x
⊕
y
)
;
8)
(
z
↓
y
)
↔
(
y
→
x
)
;
9)
(
x
1
|
(
x
3
⊕
x
4
))
↔
x
2
;
10)
(
x
2
↔
x
1
x
3
)
↓
x
4
.