ДИСКРЕТНАЯ МАТЕМАТИКА (1). В. А. Ломазов р рязанов, Ю. Д. Дискретная математика учеб пособие. Ю. Д. Рязанов е изд, доп. Белгород Издво бгту, 2016. 298 с

• Название: В. А. Ломазов р рязанов, Ю. Д. Дискретная математика учеб пособие. Ю. Д. Рязанов е изд, доп. Белгород Издво бгту, 2016. 298 с
• Дата: 12.09.2022
• Размер: 4.33 Mb.
• Имя файла: ДИСКРЕТНАЯ МАТЕМАТИКА (1).pdf
• Тип: Реферат; #673155
• страница: 22 из 25

5.6. Минимизация полностью определенных булевых функций Областью определения булевой функции n аргументов является множество всех возможных двоичных наборов длины n. Если значение функции определено на всех двоичных наборах длины n, то булева функция является полностью определенной. Общая задача минимизации булевых функций может быть сформулирована следующим образом найти аналитическое выражение заданной булевой функции в форме, содержащей минимально возможное число букв (переменных и операций. В общей постановке данная задача пока не решена, однако достаточно хорошо исследована в классе дизъ- юнктивно-конъюнктивных нормальных форм.
5.6.1. Основные понятия Минимальной дизъюнктивной нормальной формой булевой функции называется ДНФ, содержащая наименьшее число букв (по отношению ко всем другим ДНФ, представляющим заданную булеву функцию. Булева функция g(x
1
, x
2
,…, x
n
) называется импликантой булевой функции f(x
1
, x
2
,…, x
n
), если для любого набора переменных, на котором
g = 1, справедливо f = 1. Пример 5.6. Булева функция f задана табл. 5.8. Там же приведены все ее импликанты. Запишем функцию f и ее импликанты в СДНФ и выполним всевозможные упрощения, применяя правило склеивания
;
;
;
;
;
;
3 2
1 3
2 1
6 3
2 3
2 1
3 2
1 5
3 2
1 4
2 1
3 2
1 3
2 1
3 3
2 1
2 3
2 1
1 7
3 2
1 3
2 1
3 2
1
x
x
x
x
x
x
g
x
x
x
x
x
x
x
x
g
x
x
x
g
x
x
x
x
x
x
x
x
g
x
x
x
g
x
x
x
g
g
x
x
x
x
x
x
x
x
x
f















Импликанта g булевой функции f, являющаяся элементарной конъюнкцией, называется простой, если никакая часть импликанты g не является импликантой функции f.

258 Из примера видно, что импликанты g
3
= x
1
x
2
и g
5
= x
2
x
3
являются простыми импликантами функции f. Импликанты g
1
, g
2
, g
4
, g
6
не являются простыми, так как и части являются импликантами функции f, например g
3
является частью g
1
. Приведем без доказательства два утверждения, полезные при получении минимальной ДНФ.
1. Дизъюнкция любого числа импликант логической функции f также является импликантой этой функции.
2. Любая булева функция f эквивалентна дизъюнкции всех своих простых импликант. Такая форма представления булевой функции называется сокращенной ДНФ. Таблица 5.8
Импликанты булевой функции
x
1
x
2
x
3
f
g
1
g
2
g
3
g
4
g
5
g
6
g
7 0
0 0
0 0
0 0
0 0
0 0
0 0
1 0
0 0
0 0
0 0
0 0
1 0
0 0
0 0
0 0
0 0
0 1
1 1
0 0
0 1
1 1
1 1
0 0
0 0
0 0
0 0
0 0
1 0
1 0
0 0
0 0
0 0
0 1
1 0
1 0
1 1
0 0
1 1
1 1
1 1
1 0
1 0
1 0
1 Перебор всех возможных импликант для булевой функции f из рассмотренного примера дает возможность убедиться, что простых импли- кант всех две g
3
и g
5
. Следовательно, сокращенная ДНФ функции f имеет вид
f= g
3

g
5
= x
1
x
2

Как видно из табл. 5.8 импликанты g
3
ив совокупности покрывают своими единицами все единицы функции f. Получение сокращенных
ДНФ является первым этапом отыскания минимальных форм булевых функций. Как уже отмечалось, в сокращенную ДНФ входят все простые инпликанты булевой функции. Иногда из сокращенной ДНФ можно убрать одну или несколько простых импликант, не нарушая эквивалентности исходной функции. Такие простые импликанты называются лишними. Исключение лишних простых импликант на сокращенных
ДНФ — второй этап минимизации. Сокращенная ДНФ булевой функции называется тупиковой, если в ней отсутствует лишние простые импликанты.

259 Устранение лишних простых импликант из сокращенной ДНФ булевой функции не является однозначным процессов, те. булева функция может иметь несколько тупиковых ДНФ. Тупиковые ДНФ булевой функции f, содержащие минимальное число букв, являются минимальными. Минимальных ДНФ тоже может быть несколько. В общем случае минимизация булевой функции производится в три этапа первый — переход от СДНФ к сокращенной ДНФ; второй — переход от сокращенной ДНФ к миникальной ДНФ; третий — переход от минимальной ДНФ к скобочной форме.
5.6.2. Получение сокращенной ДНФ булевой функции Метод Квайна Метод Квайна применим для получения сокращенной ДНФ булевой функции из СДНФ. Для этого производятся всевозможные склеивания друг с другом сначала конституент единицы, а затем всех производных элементарных конъюнкций более низкого ранга. Пусть имеется СДНФ булевой функции
4 3
2 1
4 3
2 1
4 3
2 1
4 3
2 1
4 3
2 1
4 3
2 1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
f






1 2 3 4 5 6 Пометим каждую конституенту единицы из СДНФ функции f десятичным номером (записан под конституентой). Выполняем склеивания.
Конституента 1 склеивается только с конституентой 2 попеременной) и с конституентой 3 попеременной, конституента 2 с кон- ституантой 4 и т.д. В результате получаем
;
:
4 2
;
:
3 1
;
:
2 1
4 3
1 4
3 1
4 2
1
x
x
x
x
x
x
x
x
x



:
6 5
;
:
6 4
;
:
4 3
3 2
1 4
3 2
4 Далее склеиваем полученные элементарные конъюнкции. Возможны два случая склеивания
4 1
4 3
1 4
3 1
4 1
4 2
1 4
2 с появлением одной и той же элементной конъюнкции
4 1
x
x
. Дальнейшие склеивания невозможны.

260 Не участвовавшие в склеивании конституенты единицы и элементарные конъюнкции более низкого ранга включаются в сокращенную ДНФ:
4 1
3 2
1 4
3 Метод Квайна — Мак-Класки Метод Квайна — Мак-Класки позволяет сократить количество попарных проверок на возможность склеивания по сравнению с методом
Квайна и выполняется следующим образом
1. Все конституенты единицы из СДНФ записываются их двоичными номерами.
2. Все номера разбиваются на непересекающиеся группы. Признак образования й группы i единицы в каждом двоичном номере консти- туенты единицы.
3. Склеивание производят только между номерами соседних групп. Склеиваемые номера отмечаются.
4. Склеивания производят всевозможные, как ив методе Квайна.
Неотмеченные после склеивания номера являются простыми импликан- тами. Рассмотрим метод на примере булевой функции, заданной в СДНФ:
4 3
2 1
4 3
2 1
4 3
2 1
4 3
2 1
4 3
2 1
4 3
2 1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
f






1. В СДНФ функции f заменим все конституенты единицы их двоичными номерами
f = 0001

0011

0101

0111

1110

1111 2. Образуем группы двоичных номеров. Результат заносим в таблицу Номер группы
0 1
2 3
4 0001+
0011+
0111+
1111+
0101+
1110+
3. Склеим номера из соседних групп этой таблицы. Склеиваемые номера отметим. Результаты склеивания занесем в следующую таблицу Номер группы
0 1
2 3
4 00*1+
0*11+
*111 0*01+
01*1+
111*

261 Склеим номера из соседних групп полученной таблицы. Склеиваться могут только номера, имеющие звездочки в одинаковых позициях. Склеиваемые номера отмечаем. Результаты склеивания занесем в таблицу Номер группы
0 1
2 3
4 0**1 4. Неотмеченные номера соответствуют простым импликантам:
*111, 111*, или, в другой форме 1
3 2
1 4
3 Разбиение конституент на группы позволяет уменьшить число попарных сравнений при склеивании. Метод Нельсона Метод позволяет получить сокращенную ДНФ булевой функции из ее произвольной КНФ. Суть метода заключается в использовании следующего утверждения если в произвольной КНФ булевой функции f раскрыть скобки и произвести все поглощения, тов результате будет получена сокращенная ДНФ булевой функции f. Пусть булева функция задана в произвольной КНФ:
)
)(
)(
(
3 2
1 3
1 После раскрытия скобок получаем
3 2
1 3
2 1
2 3
1 3
1 3
2 1
3 2
2 1
3 После проведения всех поглощений имеем сокращенную ДНФ:
3 2
1 3
1
x
x
x
x
x
f


5.6.3. Получение минимальной ДНФ булевой функции Для получения минимальной ДНФ необходимо убрать из сокращенной ДНФ все лишние простые импликанты. Это делается с помощью специальной импликантной матрицы Квайна. Строки такой матрицы отмечаются простыми импликантами булевой функции, те. членами сокращенной ДНФ, а столбцы — конституентами единицы, те. членами СДНФ булевой функции. Клетка импликантной матрицы на пересечении строки i и столбца j отмечается крестиком, если я импликанта покрывает ю конституенту. Простая импликанта поглощает некоторою конституенту единицы, если является ее собственной частью.

262 Минимальные ДНФ строятся по импликантной матрице следующим образом рассматриваются различные варианты выбора подмножества простых импликант, которые покроют крестиками все столбцы импли- кантной матрицы и выбираются варианты с минимальным суммарным числом букв в такой совокупности импликант. Этот метод является трудоемким, так как существует 2
n
– 1 различных вариантов выбора подмножеств простых импликант, где n — количество простых импликант. Сократить перебор можно следующим образом
1. Найти столбцы импликантной матрицы, имеющие только один крестик. Соответствующие этим крестикам простые импликанты называются базисными и составляют ядро Квайна, которое обязательно входит в минимальную ДНФ.
2. Рассмотреть различные варианты выбора подмножеств простых импликант, которые покроют крестиками остальные столбцы импли- кантной матрицы, и выбрать варианты с минимальным суммарным числом букв в таком подмножестве импликант. В этом случае существуют 2
n–r
– 1 вариантов, где r — количество базисных импликант, входящих в ядро Квайна. Метод Петрика Метод Петрика позволяет получить все тупиковые ДНФ по импли- кантной матрице. Этот метод основан на конъюнктивном представлении матрицы. Для получения конъюнктивного представления матрицы все простые импликанты обозначаются разными буквами. После этого для каждого го столбца матрицы строится дизъюнкция всех букв, обозначающих строки матрицы, пересечение которых см столбцом отмечено крестиком, конъюнктивное представление F импликантной матрицы образуется как конъюкция построенных функций для всех столбцов матрицы. После раскрытия скобок и выполнения всех возможных по- глощений получится дизъюнкция элементарных конъюнкций, каждая из которых содержит все импликанты тупиковой ДНФ. Для матрицы (табл. 5.9) конъюнктивное представление следующее
DB
D
C
C
A
B
A
F
)
)(
)(
(




. После упрощения получим
BCD
ABD
F


, что определяет две тупиковые ДНФ:
2 1
2 1
3 1
x
x
x
x
x
x
f



и
2 1
3 2
2 1
x
x
x
x
x
x
f



, первая из которых является минимальной ДНФ.

263 Таблица 5.9
Импликантная матрица Квайна Простые импликанты
Конституенты единицы
3 2
1
x
x
x
3 2
1
x
x
x
3 2
1
x
x
x
3 2
1
x
x
x
3 2
1
x
x
x
3 1
x
x
+
+
A
2 1
x
x
+
+
B
3 2
x
x
+
+
C
2 1
x
x
+
+
D Эвристический метод С целью уменьшения трудоемкости процесса нахождения минимальной ДНФ может быть использован эвристический метод, который позволяет найти тупиковую ДНФ, как правило, близкую по сложности к минимальной ДНФ, и заключается в следующим
1. Выделяется ядро Квайна и включается в искомую ДНФ.
2. Вычеркиваются строки и столбцы, покрываемые импликантами, входящими в ядро Квайна. Если в полученной матрице имеются столбцы, содержащие по одному крестику, то операцию выделения ядра
Квайна повторяют.
3. Если не все столбцы покрыты, то выбрать простую импликанту, покрывающую максимальное количество невычеркнутых столбцов. Если таких импликант несколько, то выбирается та, которая содержит минимальное количество букв. Выбранная импликанта включается вис- комую ДНФ, а покрываемые ею строка и столбцы вычеркиваются. Если все столбцы покрыты, то искомая ДНФ найдена. Эвристический метод не гарантирует нахождения действительно минимальной ДНФ и позволяет получить только приближенное решение. Степень приближенности достаточно высокая для практического использования рассмотренного метода.
5.6.4. Скобочная минимизация булевых функций Скобочная минимизация булевых функций (факторизация) в ряде случаев позволяет получить скобочную форму, значительно более простую, чем минимальная ДНФ. Процесс факторизации заключается в многократном выполнении операции вынесения за скобки общих членов. Работу факторного алгоритма рассмотрим на примере.

264 Пусть минимальная ДНФ функции f имеет вид
5 3
2 1
5 4
2 1
6 5
2 1
6 Обозначим каждую элементарную конъюнкцию буквами А, В, С, D. Тогда функцию f можно представить множеством F = (A, B, C, D). На первом этапе работы алгоритма ищутся все попарные пересечения элементов множества F. B нашем случае имеем
A

B = x
1
; A

C =
2 1
x
x
; A

D =
2 1
x
x
;
B

C = x
1
; B

D = x
1
x
5
; C

D =
2 Выбирается та пара элементов множества F, пересечение которых дает конъюнкцию наибольшей длины. Для рассматриваемого примера выберем либо пару (АС, либо (А, D), либо (C, D), что сточки зрения результатов работы алгоритма безразлично. Выберем пару (C, D) и запишем функцию f аналитически, вынося общий элемент
2 1
x
x
за скобки по отношению к C и D. Получим
)
(
5 3
5 4
2 1
6 5
2 1
6 Обозначим A
1
=
6 2
1
x
x
x
; B
1
=
6 5
2 1
x
x
x
x
; C
1
=
)
(
5 3
5 4
2 Получим F
1
=(A
1
, B
1
, C
1
). На втором этапе алгоритма ищутся все попарные пересечения элементов множества F
1
. В нашем случае имеем
A
1

B
1
= x
1
; A
1

C
1
=
2 1
x
x
; B
1

C
1
= Вновь выбирается пара элементов множества F
1
, пересечение которых дает конъюнкцию наибольшей длины. Выберем пару (A
1
, C
1
) и запишем функцию f аналитически, вынося общий элемент
2 1
x
x
за скобки по отношению к A
1
и C
1
. Получим
6 5
2 1
5 3
5 4
6 Обозначив А =
)
(
5 3
5 4
6 2
1
x
x
x
x
x
x
x


, В =
6 5
2 1
x
x
x
x
, получим множество. Ищем пересечение элементов множества F
2
. Получаем
A
2

B
2
= x
1
. Окончательно имеем
)
)
(
(
6 5
2 5
3 5
4 6
2 1
x
x
x
x
x
x
x
x
x
x
f





265
5.7. Минимизация частично определенных булевых функций Булева функция n аргументов называется частично определенной частичной, если ее значение определено не на всех двоичных наборах длины n. Минимизация частично определенных функций, также как и полностью определенных, выполняется в три этапа. Первый этап — получение сокращенной ДНФ, членами которой являются простые импликанты частичной функции. Простой импликантой частичной функции f называется элементарная конъюнкция К, если
1) она покрывает хотя бы один набор значений аргументов, на котором функция принимает единичное значение
2) не покрывает ни одного набора, на котором функция принимает нулевое значение
3) любая конъюнкция, полученная из нее вычеркиванием переменных, покрывает некоторый набор, на котором функция принимает нулевое значение. Для построения системы всех простых импликант удобно пользоваться заданием частичной функции f в виде таблиц T
1
и T
0
:
x
1
x
2
x
3
x
4
x
1
x
2
x
3
x
4 0
1 0
0 0
0 0
1 0
1 1
0 1
0 0
0 1
0 1
0 1
1 0
0 1
1 1
1 1
1 1
0 впервой из которых перечислены наборы значений аргументов, на которых функция f принимает единичное значение, а во второй — нулевое. Метод построения всех простых импликант проиллюстрирован таблицей
0 1 0 0 + 0 - 0 0 + 0 -
- 0 0 1 1 0 + 0 1 - 0 + 0 1 - -
1 0 1 0 + 0 1 0 - + 0 -
1 -
1 1 1 1 + 0 - 1 0 + - 0 1 -
0 1 1 - + - -
1 1
- 0 1 0 + - 1 - 1 1 0 1 - + 1 -
- 1
- 1 1 1 +
1 - 1 1 +
1 1 - 1 +

266 В й колонке помещены все наборы таблицы T
1
, вой колонке содержатся всевозможные наборы, образованные из наборов й колонки заменой одного разряда прочерком и обладающие тем свойством, что они не покрывают никаких наборов таблицы T
0
(не совпадают сними вне вычеркнутых разрядах. Они могут быть найдены просмотром всех наборов из й колонки и проверкой возможности вычеркивания в каждом из них каждого из символов. Наборы й колонки, покрываемые наборами й колонки, помечаются знаком ―+‖. В й колонке находятся все наборы, полученные из наборов й колонки заменой одного разряда прочерком и не покрывающие наборов таблицы Т. Покрытые ими наборы й колонки помечаются знаком ―+‖. Из наборов й колонки уже не удается образовать наборов стремя прочерками, не покрывающих наборов из таблицы Т. На этом процедура завершается. Все непоме- ченные наборы таблицы соответствуют простым импликантам. В данном случае это
4 1
x
x
,
2 1
x
x
,
3 1
x
x
,
3 2
x
x
,
4 3
x
x
,
4 2
x
x
,
4 Второй этап минимизации — получение минимальной ДНФ. Для получения минимальной ДНФ необходимо убрать из сокращенной ДНФ все лишние простые импликанты. Это делается, как ив случае полностью определнных функций, с помощью специальной импликан- той матрицы Квайна. Строки этой матрицы отмечаются простыми им- пликантами, полученными на первом этапе, а столбцы — конституен- тами единицы, соответствующими наборам таблицы T
1
. Импликантная матрица представлена в табл. 5.10. Таблица 5.10