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

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

Импликантная матрица Квайна Простые им- пликанты
Конституенты единицы
4 3
2 1
x
x
x
x
4 3
2 1
x
x
x
x
4 3
2 1
x
x
x
x
4 3
2 1
x
x
x
x
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 1
x
x
+

267 Исключая лишние простые импликанты, получаем минимальную
ДНФ частично определенной функции. В данном случае примером минимальной ДНФ может служить
4 3
3 2
2 Трудоемкость процесса минимизации частично определенной булевой функции значительно зависит от степени определенности функции. Рассмотренный метод целесообразно использовать при минимизации слабо определенных булевых функций, когда таблицы Т и Т содержат небольшое количество строк. Если степень определенности частичной функции высока, то для минимизации функции можно использовать модифицированный метод Квайна — Мак-Класки. Модификация метода Квайна — Мак-Класки заключается в том, что частичная функция на неопределенных наборах доопределяется единичным значением. Для доопределенной функции методом Квайна — Мак-Класки находятся все простые импликации. При составлении матрицы Квайна строки отмечаются полученными простыми импликантами, а столбцы — конститу- ентами единицы частичной функции, соответствующими строкам таблицы Т. Исключая лишние простые импликанты, получаем минимальную ДНФ частично определенной функции. Используем модифицированный метод Квайна — Мак-Класки для нахождения минимальной ДНФ частичной функции, заданной таблицами Т и Т :
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 = 0100

0110

1010

1111

0000

0010

0011

0101

0111

1001

1011

1101 Процесс нахождения простых импликант методом Квайна — Мак-
Класки представлен в виде таблиц
0 0 0 0 + 0 1 0 0 + 0 1 1 0 + 0 1 1 1 + 1 1 1 1 +
0 0 1 0 + 1 0 1 0 + 1 0 1 1 +
0 0 1 1 + 1 1 0 1 +
0 1 0 1 +

268 0 - 0 0 + 0 1 - 0 + 0 1 1 - + - 1 1 1 +
0 0 - 0 + 0 1 0 - + - 0 1 1 + 1 - 1 1 +
0 - 1 0 + 0 1 - 1 + 1 1 - 1 +
- 0 1 0 + - 1 0 1 +
0 0 1 - + 1 0 - 1 +
1 - 0 1 +
0 - - 0 0 1 - - - - 1 1
- 0 1 - - 1 - 1 0 - 1 - 1 - - 1 Последняя таблица содержит только простые импликанты. Матрица
Квайна для нахождения минимальной ДНФ частичной функции показана в таблице 5.10. Третий этап минимизации частично определенной булевой функции — переход от минимальной ДНФ к скобочной форме, не отличается от соответствующего этапа минимизации полностью определенной булевой функции.
5.8. Минимизация систем полностью определенных булевых функций Система полностью определенных булевых функций представляет собой множество полностью определенных булевых функций, имеющих общее множество аргументов. Пусть задана система полностью определенных булевых функций, представленных в ДНФ:
3 1
2 1
3 1
3 2
1 1
)
,
,
(
x
x
x
x
x
x
x
x
x
f



;
2 1
3 1
2 1
3 2
1 2
)
,
,
(
x
x
x
x
x
x
x
x
x
f



;
3 2
1 2
1 3
2 Все различные элементарные конъюнкции системы функций объединим в множество K, которое назовем полным множеством элементарных конъюнкций системы функций. В нашем случае
}
,
,
,
,
,
{
3 2
1 2
1 2
1 3
1 2
1 Система ДНФ булевых функций называется минимальной, если ее полное множество элементарных конъюнкций содержит минимальное количество буква каждая ДНФ системы включает минимальное число элементарных конъюнкций наименьшего ранга. При этом ДНФ представления булевой функции в минимальной системе в общем случае не совпадает с ее минимальной ДНФ.

269 Минимизация систем полностью определенных булевых функций может производиться по алгоритму, аналогичному алгоритму метода
Квайна с небольшими отличиями. Алгоритм минимизации следующий.
1. Построить полное множество K элементарных конъюнкций мини- мизируемой системы функций (каждая из функций системы представлена в СДНФ). Каждой конституенте единицы множества K присвоить признак, содержащий номера функций системы, в которые входит рассматриваемая конституента.
2. Произвести минимизацию СДНФ функции f, конституентами единицы которой являются все элементы множества K. При выполнении склеивания двух конституент единицы каждой вновь образуемой элементарной конъюнкции присвоить признак, состоящий из номеров функций, общих для двух склеиваемых конституент (см. примеры. Последнее справедливо и для двух склеиваемых элементарных конъюнк- ций с признаками. Если признаки склеиваемых конституент не содержат общих номеров, то склеивание не производится. Поглощение производится только для элементарных конъюнкций с одинаковыми признаками. Полученные в результате склеивания и поглощения конъюнкции называются простыми импликантами системы функций.
3. Построить импликантную матрицу функции f, аналогичную матрице Квайна, стой разницей, что для каждой конституенты единицы выделяется столько столбцов, сколько различных номеров функций содержит ее признак. Покрытие матрицы импликантами производится аналогично методу Квайна. Пусть система булевых функций задана таблицей истинности табл. 5.11). Найдем минимальную ДНФ системы булевых функций. Таблица 5.11 Таблица истинности
x
1
x
2
x
3
f
1
f
2 0
0 0
1 1
0 0
1 0
0 0
1 0
0 1
0 1
1 0
1 1
0 0
0 0
1 0
1 1
1 1
1 0
1 0
1 1
1 1
0

270 Представим каждую из функции системы в СДНФ:
3 2
1 3
2 1
3 2
1 3
2 1
1
x
x
x
x
x
x
x
x
x
x
x
x
f




;
3 2
1 3
2 1
3 2
1 3
2 1
2
x
x
x
x
x
x
x
x
x
x
x
x
f




1. Построим полное множество K элементарных конъюнкций полученной системы, приписывая каждой конституенте единицы признак вхождения в функции f
1
и f
2
:
)}
2
(
),
2
(
),
1
(
),
1
(
),
2
,
1
(
),
2
,
1
(
{
3 2
1 3
2 1
3 2
1 3
2 1
3 2
1 3
2 1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
K

2. Построим СДНФ функции f. Для удобства выполнения склеивания пронумеруем каждую конституенту единицы из СДНФ функции f ивы- полним все склеивания
)
2
(
)
2
(
)
1
(
)
1
(
)
2
,
1
(
)
2
,
1
(
3 2
1 3
2 1
3 2
1 3
2 1
3 2
1 3
2 1
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
)
2
(
)
2
(
)
2
,
1
(
:
5 1
3 1
3 2
1 3
2 1
x
x
x
x
x
x
x
x



;
)
1
(
)
1
(
)
2
,
1
(
:
4 2
3 1
3 2
1 3
2 1
x
x
x
x
x
x
x
x



;
)
1
(
)
1
(
)
1
(
:
4 3
2 1
3 2
1 3
2 1
x
x
x
x
x
x
x
x



;
)
2
(
)
2
(
)
2
(
:
6 5
2 1
3 2
1 3
2 После проведения всех поглощений, с учетом признака каждой конъюнкции, получим
)
2
(
)
1
(
)
1
(
)
2
,
1
(
)
2
(
)
2
,
1
(
2 1
2 1
3 1
3 2
1 3
1 3
2 Дальнейшие склеивания и поглощения невозможны. Получены простые импликанты минимизируемой системы булевых функций. Строим импликантную матрицу (табл. 5.12). Столбцы матрицы помечены конституентами единицы из СДНФ функции f. Для каждой конституенты единицы отводим столько столбцов матрицы, сколько различных номеров функций содержит признак конституенты. Строки матрицы помечаем простыми импликантами системы булевых функций.
Импликанты
)
2
(
),
1
(
),
2
,
1
(
),
2
,
1
(
2 1
2 1
3 2
1 3
2 1
x
x
x
x
x
x
x
x
x
x
покрывают все конститу- енты единицы из СДНФ функции f. В соответствии с этим имеем
)
2
(
)
1
(
)
2
,
1
(
)
2
,
1
(
2 1
2 1
3 2
1 3
2 Выделив для функции f
i
импликанты с признаком, включающим i, получим следующую минимальную дизъюнкцию нормальную форму системы функций
2 1
3 2
1 3
2 1
1
x
x
x
x
x
x
x
x
f



;
2 1
3 2
1 3
2 1
2
x
x
x
x
x
x
x
x
f




271 Таблица 5.12
Импликантная матрица Квайна Простые им- пликанты системы функций
Конституанты единицы функции f
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 2
1
x
x
x
1 2
1 2
1 1
2 2
3 2
1
x
x
x
(1,2)
+
+
3 1
x
x
(2)
+
+
3 2
1
x
x
x
(1,2)
+
+
3 1
x
x
(1)
+
+
2 1
x
x
(1)
+
+
2 1
x
x
(2)
+
+
5.9. Минимизация систем частично определенных булевых функций Минимизация систем частично определенных булевых функций заключается в преобразовании исходной системы к виду, содержащему минимальное число аргументов, минимальное число конъюнкций наименьшего ранга в полном множестве конъюнкций. Возможность уменьшения числа аргументов системы булевых функций появляется в том случае, если значения функций системы не изменяются при произвольных изменениях значений некоторых аргументов. Такие аргументы называются фиктивными. Для частично определенных булевых функций одни и те же аргументы могут быть фиктивными и нефиктивными. Например, для системы функций, заданной табл. 5.13, это все, кроме x
3
. Действительно, если вычеркнуть любой столбец таблицы, кроме третьего, то среди наборов значений оставшихся аргументов не найдется таких двух одинаковых наборов, на которых функции принимают различные значения. После вычеркивания некоторых столбцов отдельные аргументы могут стать нефик- тивными. Если вычеркнуть столбцы аргументов x
4
, x
5
, x
6
в табл. 5.13, то аргументы и x
2
перестают быть фиктивными, а таблица истинности сокращается до табл. 5.14 и система функций становится полностью определенной Таблица 5.13 Таблица 5.14
Система функций Система функций
№ x
1
x
2
x
3
x
4
x
5
x
6
f
1
f
2
№ x
1
x
2
x
3
f
1
f
2 1
0 0
1 0
1 1
0 1
1 0
0 1
0 1
2 0
1 1
0 0
1 1
0 2
0 1
1 1
0 3
0 0
0 1
0 0
0 0
3 0
0 0
0 0
4 0
1 0
0 0
0 1
1 4
0 1
0 1
1 5
1 0
0 0
0 1
1 1
5 1
0 0
1 1
6 1
1 0
1 0
0 0
0 6
1 1
0 0
0 7
1 0
1 0
0 1
1 0
7 1
0 1
1 0
8 1
1 1
0 0
0 0
1 8
1 1
1 0
1 Минимально возможное число аргументов системы булевых функций можно найти следующим образом. По исходной табл. 5.13 образуем все пары входных наборов, на которых хотя бы одна из функций системы принимает противоположное значение. Такими парами являются
(1, 2); (1, 3); (1, 4); (1, 5); (1, 6); (1, 7); (2, 3); (2, 4); (2, 5); (2, 6);
(2, 8); (3, 4); (3, 5); (3, 6); (3, 7); (3, 8); (4, 6); (4, 7); (4, 8); (5, 6); (5, 7);
(5, 6); (6, 7); (6, 8); (7, 8). Для каждой полученной пары наборов укажем множество тех аргументов, значениями которых различаются наборы рассматриваемой пары. Так, наборы, входящие в пару (1, 2), отмечаются значениями переменных. Сведем полученные результаты в матрицу, столбцы которой отмечаются парами наборов, а строки — аргументами системы поставим крестик, если переменная , отмечающая ю строку, имеет различные значения в паре наборов, отмечающих й столбец матрицы. Полученная матрица называется матрицей различий, а каждая ее строка — вектором различий. Для рассматриваемого примера матрица различий приведена в табл. 5.15. Таблица 5.15 Матрица различий
1 1 1 1 1 1 2 2 2 2 2 3 3 3 3 4 4 4 5 5 5 6 6 7 2 3 4 5 6 7 3 4 5 6 8 4 5 7 8 6 7 8 6 7 8 7 8 8
x
1
+ + +
+ + + + + + + + +
x
2
+ + + + +
+
+ + + + + +
x
3
+ + + + + + + +
+ + + + + + + +
x
4
+
+ +
+ + + + + +
+
+ +
x
5
+ + + + + +
x
6
+ + + + + + + + +
+ + + + +

273 Найдем минимальное покрытие столбцов матрицы строками. Для этой цели можно, например, использовать метод Петрика. Конъюнктивное представление таблицы имеет вид
).
(
)
)(
)(
(
)
)(
(
)
)(
)(
)(
(
)
)(
)(
)(
)(
(
)
)(
)(
)(
(
)
)(
)(
)(
(
4 2
4 3
6 4
3 2
6 3
2 3
6 4
2 3
1 6
3 2
1 4
1 4
3 2
1 6
4 3
1 6
4 1
4 2
6 1
6 4
3 1
3 2
1 6
3 6
4 3
2 5
1 6
5 4
3 2
1 5
3 2
6 5
3 2
6 5
4 2
5 После проведения преобразований получим
6 5
4 3
3 Следовательно, минимальным по числу строк покрытием является множество {
3 2
1
,
,
x
x
x
}. Минимальное покрытие и представляет минимально возможное число аргументов системы булевых функций. Система булевых функций от аргументов
3 2
1
,
,
x
x
x
является полностью определенной, поэтому для ее минимизации может быть использован метод минимизации систем полностью определенных булевых функций. В результате применения метода получим
;
3 2
1 3
2 1
3 2
1 3
2 1
2 2
1 2
1 Если в качестве нефиктивных аргументов принять
6 5
4 3
,
,
,
x
x
x
x
, то получим систему частично определенных булевых функций, представленную в табл. 5.16. Минимизацию системы частично определенных булевых функций выполним в три этапа
1) нахождение простых импликант системы частично определенных булевых функций
2) нахождение минимального покрытия импликантной матрицы
Квайна системы частично определенных булевых функций
3) формирование минимальной системы булевых функций. ЭТАП 1. Простой импликантой системы частично определенных булевых функций F называется конъюнкция К, если
1) она накрывает хотя бы один набора, на котором f
i
(a) = 1;
2) не накрывает ни одного набора а, на котором f
i
(a) = 0;
3) любая конъюнкция, полученная из нее вычеркиванием переменных, накрывает некоторый набора, на котором f
i
(a) = 0.

274 Здесь i

{1, 2, …, n}, где n — количество функций в системе. Для нахождения всех простых импликант удобно пользоваться представлением системы частично определенных булевых функций в виде таблиц Т и Т (табл. 5.17), впервой из которых перечислены наборы аргументов, на которых хотя бы одна из функций системы принимает единичное значение, а во второй — наборы аргументов, на которых хотя бы одна из функций системы принимает нулевое значение. Наборы таблицы Т отмечены номерами функций, которые на этих наборах принимают единичное значение. Наборы таблицы Т отмечены номерами функций, которые на этих наборах принимают нулевое значение.
Таблица 5.16 Таблица 5.17 Система функций Таблицы Т и Т системы функций
x
3
x
4
x
5
x
6
f
1
f
2
x
3
x
4
x
5
x
6
x
3
x
4
x
5
x
6
1 0
1 1
0 1
1 0
1 1
(2)
1 0
1 1
(1)
1 0
0 1
1 0
1 0
0 1
(1)
1 0
0 1
(2)
0 1
0 0
0 0
0 0
0 0
(1,2)
0 1
0 0
(1, 2)
0 0
0 0
1 1
0 0
0 1
(1, 2)
1 0
0 0
(1)
0 0
0 1
1 1
1 0
0 0
(2)
1 0
0 0
0 1 Процесс нахождения всех простых импликант системы частично определенных булевых функций проиллюстрирован таблицей
+1 0 1 1
(2)
+ - 0 1 1
(2)
+ - - 1 1
(2)
-
- 1 -
(2)
+1 0 0 1
(1)
+ 1 - 1 1
(2)
+ - 0 1 -
(2)
+0 0 0 0
(1, 2)
+ 1 0 1 -
(2)
+ 1 - 1 -
(2)
+0 0 0 1
(1, 2)
+ - 0 0 1
(1)
- - 0 1
(1)
+1 0 0 0
+ 1 - 0 1
(1)
0 0 -
-
(1, 2)
+ 0 0 - 0
(1, 2)
0 -
- 1
(1, 2)
+ 0 0 0 -
(1, 2)
- 0 - 0
(2)
+ 0 - 0 1
(1, 2)
1 -
- 0
(2)
+ 0 0 - 1
(1, 2)
+ - 0 0 0
(2)
+ - 0 0 0
(2)
+ 1 0 - 0
(2) Впервой колонке помещены все наборы таблицы Т с признаками. Во второй колонке содержатся всевозможные наборы, образованные из наборов первой колонки заменой одного разряда прочерком и обладающие тем свойством, что они не покрывают ни одного набора из таблицы Т, имеющего хотя бы один общий признак с полученным набором. При замене разряда прочерком признак набора не изменяется. В наборе 1011
(2) нельзя поставить прочерк в третьем разряде, так как полученный

275 набор 10-1 (2) покрывает набор 1001 (2) из таблицы Т, но можно поставить прочерк во втором разряде, несмотря на то, что полученный набор
1-11 (2) покрывает набор 1011 (1) из таблицы Т. Это покрытие не имеет значения, так как признаки наборов 1-11(2) и 1011(1) не пересекаются. Наборы первой колонки, покрываемые наборами второй, помечаются знаком ―+‖, аналогично заполняются третья и четвертая колонки. В четвертой колонке нельзя вычеркнуть ни одного разряда, и процесс завершается. Все помеченные наборы таблицы соответствуют простым им- пликантам системы частично определенных булевых функций. ЭТАП 2. Строим импликантную матрицу Квайна системы частично определенных булевых функций. Столбцы матрицы помечаем наборами таблицы Т. Для каждого набора отводим столько столбцов матрицы, сколько различных номеров функций содержит его признак. Строки матрицы помечаем простыми импликантами. Матрицу заполняем с учетом признаков. Матрица Квайна представлена в табл. 5.18. Таблица 5.18