ВУЗ: Томский государственный университет систем управления и радиоэлектроники
Категория: Учебное пособие
Дисциплина: Дискретная математика
Добавлен: 28.11.2018
Просмотров: 16677
Скачиваний: 202
101
щает конъюнкцию AC, следовательно, сумму A + AC можно заменить буквой A.
Тогда число вхождений аргументов уменьшается до пяти.
.
)
1
(
BC
B
A
A
BC
B
A
C
A
AC
BC
B
A
A
f
+
+
=
+
+
+
=
+
+
+
=
Аргумент A умножим на единицу и заменяем её дизъюнкцией
:
B
B +
.
)
(
1
BC
B
A
B
B
A
BC
B
A
A
f
+
+
+
=
+
+
⋅
=
Раскроем скобки и добавим конъюнкцию AB:
.
BC
AB
B
A
B
A
AB
f
+
+
+
+
=
Выполняем операции склеивания:
.
)
(
)
(
BC
B
A
BC
A
A
B
B
B
A
f
+
+
=
+
+
+
+
=
К сумме B + BC применима теорема поглощения:
.
)
1
(
B
C
B
BC
B
=
+
=
+
В результате получаем:
.
)
1
(
B
A
C
B
A
C
B
B
A
f
+
=
+
+
=
+
+
=
Это предел упрощения.
Заметим, что функция (5.1) зависит от трёх аргументов и имеет семь
вхождений букв, а в результате минимизации получилось выражение, содер-
жащее лишь два аргумента: A и B. От этих двух аргументов функция действи-
тельно (говорят: существенно) зависит. Аргумент C является фиктивным, от
него функция зависит несущественно (т. е. вообще не зависит).
Рассмотрим ещё два примера, иллюстрирующие алгебраическое упроще-
ние булевых формул.
· · · · · · · · · · · · · · · · · · · · · · ·
Пример 5.1
· · · · · · · · · · · · · · · · · · · · · · ·
Упростить:
.
B
A
BC
AC
C
AB
f
+
+
+
=
Сначала вынесем за скобки букву A и упростим скобочное выражение:
=
+
+
+
+
=
+
+
+
=
B
A
BC
B
B
C
C
B
A
B
A
BC
C
C
B
A
f
)]
(
[
)
(
=
+
+
+
+
+
=
B
A
BC
BC
C
B
BC
C
B
A
)
(
=
+
+
+
+
+
=
B
A
BC
B
B
C
C
C
B
A
)]
(
)
(
[
.
)
(
B
A
BC
AC
AB
B
A
BC
C
B
A
+
+
+
=
+
+
+
=
Вынесем за скобки букву С:
.
)
(
B
A
B
A
C
AB
f
+
+
+
=
Выражение в скобках – это инверсия последней конъюнкции
,
B
A
т. е.
102
.
B
A
B
A
=
+
Обозначим:
,
B
A
Q
+
=
B
A
B
A
Q
=
+
=
.
Тогда заданное выражение примет вид:
.
)
(
Q
C
Q
C
CQ
AB
C
C
Q
CQ
AB
Q
CQ
AB
f
+
+
+
=
+
+
+
=
+
+
=
Добавим к нему ещё одну конъюнкцию
Q
C
(равенство не нарушится):
=
+
+
+
+
=
f
AB
CQ
CQ
C Q
CQ
(
)
(
)
.
=
+
+
+
+
=
+ +
AB
C Q
Q
Q C
C
AB
C
Q
Подставим вместо
Q
его обозначение:
.
B
A
C
AB
f
+
+
=
Далее упростить это выражение невозможно, следовательно, оно является
минимальной формой заданной функции.
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
· · · · · · · · · · · · · · · · · · · · · · ·
Пример 5.2
· · · · · · · · · · · · · · · · · · · · · · ·
Упростить:
.
B
A
BC
C
A
f
+
+
=
Действуем, как и в случае предыдущего примера:
.
)
(
)
(
)]
(
)
(
[
)
(
]
)
(
[
)
(
)
1
(
)
(
B
C
A
A
A
B
C
A
B
A
AB
C
A
B
A
B
C
A
B
A
C
C
B
B
B
C
A
B
A
C
B
BC
C
B
C
B
A
B
A
BC
B
B
C
A
B
A
BC
C
A
B
A
ABC
C
A
C
B
A
ABC
C
A
B
A
BC
A
ABC
C
A
B
A
A
A
BC
C
A
f
+
=
=
+
+
=
+
+
=
=
+
+
=
+
+
+
+
=
=
+
+
+
+
=
=
+
+
+
=
+
+
=
=
+
+
=
+
+
+
=
=
+
+
+
=
+
+
+
=
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
Упражнения
1.
Определите число аргументов, от которых зависит функ-
ция, и число вхождений аргументов (функцию не преобразовывать):
1)
;
C
B
A
f
+
=
3)
;
A
A
A
A
f
+
+
+
=
2)
;
C
B
AB
A
f
+
+
=
4)
;
B
B
B
B
f
⋅
⋅
⋅
=
103
5)
;
B
A
B
A
AB
B
A
f
+
+
+
=
7)
;
C
C
C
D
A
f
+
+
+
+
=
6)
;
B
A
B
A
B
A
f
+
+
+
=
8)
.
A
A
A
A
f
⋅
⋅
⋅
=
2.
Найдите минимальную форму функций:
1)
;
)
(
Q
PQ
P
f
+
=
4)
;
)
(
AB
C
A
BC
B
A
f
+
+
=
2)
;
)
(
P
S
R
R
Q
Q
P
P
f
+
+
+
=
5)
;
=
+
+
f
PQ
PQ
PQ R
3)
;
Q
P
Q
f
+
=
6)
.
=
+ +
f
AC
B
AC
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
5.2 Метод Квайна
Алгебраическая минимизация обычно требует очень большой изобрета-
тельности, и с практической точки зрения интереса не представляет, за исклю-
чением простейших случаев. Поэтому многие специалисты пытались разрабо-
тать методы (алгоритмы), позволяющие найти минимальную форму булевой
функции и при этом не требующие никакой изобретательности. Главным из та-
ких методов является метод Квайна, составляющий основу всех других мето-
дов [14; 48]. Исходной формой функции для его применения является СДНФ,
т. е. перед минимизацией заданное выражение необходимо представить дизъ-
юнкцией минтермов. Проиллюстрируем метод Квайна на примере функции че-
тырёх аргументов вида:
.
D
C
B
D
B
A
BC
C
AB
f
+
+
+
=
Сначала находим СДНФ. Заданная функция зависит от четырёх аргумен-
тов A, B, C, D и содержит конъюнкции различной длины. Удлиним конъюнкции
за счёт единиц так, чтобы в каждой конъюнкции было четыре знака:
.
1
1
1
1
1
⋅
+
⋅
+
⋅
⋅
+
⋅
=
D
C
B
D
B
A
BC
C
AB
f
В первой конъюнкции отсутствует переменная D. В связи с этим единицу
заменим дизъюнкцией вида
.
D
D +
Во второй конъюнкции нет переменных A и
D. Заменяем их дизъюнкциями
A
A +
и
D
D +
соответственно. Аналогично по-
ступим и с оставшимися единицами. Тогда получим:
.)
(
)
(
)
)(
(
)
(
A
A
D
C
B
C
C
D
B
A
D
D
A
A
BC
D
D
C
AB
f
+
+
+
+
+
+
+
+
=
Раскроем скобки, при этом буквы в минтермах запишем в алфавитном
порядке, а сами минтермы расположим по возрастанию их индексов:
.
ABCD
D
ABC
D
C
AB
D
C
AB
D
C
B
A
BCD
A
D
BC
A
CD
B
A
D
C
B
A
D
C
B
A
f
+
+
+
+
+
+
+
+
+
+
=
104
Переходим к методу Квайна. Его основу составляет теорема склеивания,
применяемая к каждой паре минтермов заданной функции. Начнём с нулевого
минтерма и поочерёдно сравним его со всеми остальными. Если сравниваемые
минтермы отличаются инверсией только одного аргумента, то к ним применяем
теорему склеивания. Эти минтермы отмечаем, например, подчёркиваем, а их
общую часть запишем в отдельный список. В данном случае минтермы m
0
и m
1
,
а также m
0
и m
8
дают соответственно:
;
C
B
A
D
C
B
A
D
C
B
A
=
+
.
D
C
B
D
C
B
A
D
C
B
A
=
+
Минтермы m
0
, m
1
и m
8
подчёркиваем, при этом ранее подчёркнутый мин-
терм вторично не отмечаем:
.
ABCD
D
ABC
D
C
AB
D
C
AB
D
C
B
A
BCD
A
D
BC
A
CD
B
A
D
C
B
A
D
C
B
A
f
+
+
+
+
+
+
+
+
+
+
=
Переходим к минтерму m
1
. Сравниваем его со всеми, кроме нулевого, в
том числе и с подчёркнутыми. Получаем:
.
D
B
A
CD
B
A
D
C
B
A
=
+
Минтерм m
3
подчёркиваем. Теперь число подчёркнутых минтермов воз-
росло до четырёх:
.
ABCD
D
ABC
D
C
AB
D
C
AB
D
C
B
A
BCD
A
D
BC
A
CD
B
A
D
C
B
A
D
C
B
A
f
+
+
+
+
+
+
+
+
+
+
=
Аналогично сравниваем все остальные минтермы независимо от того,
подчёркнуты они или нет, после чего заданная функция представится в виде
дизъюнкции конъюнкций, полученных в результате склеивания минтермов:
.
ABC
ABD
C
AB
D
AB
D
C
A
BCD
BC
A
D
BC
CD
A
D
B
A
D
C
B
C
B
A
f
+
+
+
+
+
+
+
+
+
+
+
+
=
На этом заканчивается первый этап минимизации по методу Квайна.
Переходим ко второму этапу. Конъюнкции полученного выражения точ-
но так же сравниваем. Начинаем с левой конъюнкции
.
C
B
A
Она не склеивает-
ся ни с одной конъюнкцией выражения. Поэтому её не подчёркиваем и перехо-
дим к конъюнкции
.
D
C
B
Она также не склеивается ни с одной конъюнкцией.
То же самое относится и к конъюнкциям
D
B
A
и
.
CD
A
Все их не подчёркива-
ем и сравниваем конъюнкцию
:
D
BC
.
BC
BCD
D
BC
=
+
105
Конъюнкции
D
BC
и BCD подчёркиваем:
.
ABC
ABD
C
AB
D
AB
D
C
A
BCD
BC
A
D
BC
CD
A
D
B
A
D
C
B
C
B
A
f
+
+
+
+
+
+
+
+
+
+
+
+
=
Переходим к конъюнкции
:
BC
A
.
BC
ABC
BC
A
=
+
Получилась та же самая конъюнкция. Поскольку она является повторной,
то вторично её не записываем, но соответствующие конъюнкции подчёркиваем:
.
ABC
ABD
C
AB
D
AB
D
C
A
BCD
BC
A
D
BC
CD
A
D
B
A
D
C
B
C
B
A
f
+
+
+
+
+
+
+
+
+
+
+
+
=
Очередная конъюнкция
.
AC D
Её не подчёркиваем, так как она не склеи-
вается ни с одной конъюнкцией из всего выражения. За ней следуют склеива-
ющиеся конъюнкции
D
AB
и
,
ABD а также
C
AB
и
,
ABC которые дают новую
конъюнкцию AB. Конъюнкции
,
D
AB
,
ABD
C
AB
и
ABC
подчёркиваем:
.
ABC
ABD
C
AB
D
AB
D
C
A
BCD
BC
A
D
BC
CD
A
D
B
A
D
C
B
C
B
A
f
+
+
+
+
+
+
+
+
+
+
+
+
=
Таким образом, на втором этапе получили две неповторяющиеся конъ-
юнкции BC и AB. Дизъюнкция этих двух и всех неподчёркнутых конъюнкций,
полученных на первом этапе, образует выражение:
,
D
C
A
AB
BC
CD
A
D
B
A
D
C
B
C
B
A
f
+
+
+
+
+
+
=
в котором нет ни одной пары склеивающихся конъюнкций.
Выражение, полученное методом Квайна, называется сокращённой дизъ-
юнктивной нормальной формой
, а каждая его конъюнкция называется простой
импликантой.
Для всякой булевой функции существует единственная сокра-
щённая ДНФ.
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
Упражнения
1.
Представьте в СДНФ функцию:
.
)
,
,
,
(
D
C
B
A
D
C
B
A
C
B
ABC
D
B
A
D
AB
D
C
B
A
f
+
+
+
+
+
=
1) для ее СДНФ определите количество минтермов и число
букв в СДНФ;
2) выполните операции первого этапа метода Квайна, т. е.
сравните все минтермы между собой. Найдите число минтермов,
оставшихся неподчёркнутыми, и количество неповторяющихся
конъюнкций, содержащих по три аргумента;