Минимизация с использованием карт Карно

Для минимизации булевых функций вручную удобно применять так называемые карты Карно. Карты Карно позволяют графически представить булеву функцию и обеспечивают наглядность процесса минимизации. На рис. 5.10 приведена карта Карно для функции трех переменных, с краев карты помечаются области, соответствующие истинным значениям некоторой переменной, остальная область соответствует ложным значениям данной переменной.

х₂

x₁

х₃

Рис. 5.10. Области карты Карно

На рис. 5.10 заштрихованная область со штрихом с наклоном влево соответствует истинным значениям х ₁, где отсутствует данная штриховка значения х ₁-ложные; заштрихованная область со штрихом с наклоном вправо соответствует истинным значениям х ₂, в остальных ячейках карты значения х ₂- ложные. Изображенная на рисунке единица соответствует вершине гиперкуба .

Карта Карно представляет прямоугольник, образованный одинаковыми ячейками. В общем случае карта строится по следующим правилам.

1. Число ячеек карты соответствует всем возможным комбинациям входных аргументов булевой функции, т.е. равно 2^k, где - число аргументов.

2. Каждая переменная делит карту на две равные непрерывные области: область истинных значений и область ложных значений. Для разных переменных области не должны совпадать. При этом считается, что края карты склеены, т.е., например, первая и последняя ячейки строки являются соседними.

При минимизации функции с помощью карт Карно поступают следующим образом.

1. Минимизируемую функцию представляют на карте Карно, для этого помечают единицами ячейки карты, соответствующие 0-кубам.

2. Отыскивают группы смежных единиц с числом единиц в группе 2, 4, 8, …, 2m, где m=1, 2, 3,…. Две смежные единицы образуют 1-куб, четыре смежные единицы – 2-куб, восемь смежных единиц 3-куб и т.д. Одна, одиночная единица соответствует 0-кубу.

3. Отдавая предпочтение группам с небольшим количеством единиц, пытаются покрыть все единицы минимальным количеством групп. Группы могут пересекаться. Следует учитывать, что края карты считаются склеенными. По найденному покрытию записывается минимальная форма как дизъюнкция -кубов, соответствующих выделенным группам смежных единиц.

Пример 5.20.

Функция трех переменных задана в СДНФ и представлена на карте Карно (рис. 5.11).

х₂

x₁

	1	1 ^-1
1 ³	²1		³1

х₃

Рис. 5.11. Определение групп смежных единиц

В данном случае можно выделить три группы по две смежные единицы, которые покрывают все вершины гиперкуба. 1-я группа соответствует истинным значениям переменных х ₁ и х ₃ (переменная х ₂ в одной единице группы истинна, в другой – ложна), следовательно, соответствует терму минимальной формы х ₁ х ₃, аналогично 2-я группа соответствует х ₂ х ₃ и 3-я группа (3-я группа построена с учетом склеивания краев карты Карно).

Пример. 5.21. (рис. 5.12).

х₂

х₁

1	1	1
			1

х₃

Рис. 5.12. «Одиночная» единица

В данном случае одна единица не имеет смежных, поэтому минимальная форма содержит 0-куб.

Пример 5.22.

Дана функция четырех переменных (рис. 5.13):

⁴

х₁

1 ¹

₃1

1 ₄

1 ²

х₄

⁴ 1

⁴1

х₃

Рис 5.13. Минимизация функции четырех переменных

Минимизируя, получим: .

Метод карт Карно обычно применяется для минимизации функций до пяти переменных. Карты Карно пяти переменных приводятся на рис. 5.14.Для данной карты помеченные области и прилегающие к ним считаются смежными (помеченная область соответствует x₂ x₃).

х₃

х₄

х₅

Рис. 5.14. Карты Карно для функции пяти переменных

Пример 5.23. Функция пяти переменных представлена на карте (рис. 5.15).

х₁

х₃

х₅

х₄

Рис. 5.15. Минимизация функции пяти переменных

Замечание: В ряде случаев эффективно производить минимизацию «по нулям», т.е. отделять группы смежных нулей и записать выражение для инверсии минимизируемой функции.

Пример 5.24. Функция трех переменных представлена на карте (рис 5.16).

х₁

0	0	0
			1

х₃

Рис. 5.16. Минимизация «по нулям»

Минимизация не полностью определенных булевых функций

Определение 28. Не полностью определеной булевой функцией будем называть булеву функцию, значения которой не заданы для некоторых наборов аргументов.

Пусть булева функция не определена на наборах аргументов, данной функции можно поставить в соответствие булевых функций. Полностью определенная булева функция считается эквивалентной функции в том случае, если ее значения совпадают со значениями , где определена.

Введем в рассмотрение две функции и . на тех наборах, где не определена; , где не определена. Для использования метода Квайна-Мак-Класки для минимизации не полностью определенных функций докажем теорему.

Теорема 10. Минимальная ДНФ не полностью определенной булевой функции совпадает с дизъюнкцией самых коротких импликант , которые совместно покрывают все 0-кубы функции и ни одна из которых (импликант) не является избыточной.

Доказательство: Рассмотрим какую-либо эквивалентную функцию . Очевидно, что для любой функции , т.е. любая импликанта функции будет всегда поглощать импликанты функции либо совпадать с ней. Из этого следует, что импликанты функции будут являться более короткими по длине. Так же очевидно, что из всех эквивалентных булевых функций имеем наименьшее количество 0-кубов, т.е. . Таким образом, используя для нахождения покрывающих импликант и покрывая 0-кубы из , мы найдем минимальное покрытие для функции .

Теорема доказана.

Не полностью определенная булева функция задается двумя множествами: множеством истинных значений и множеством неопределенных значений . Рассмотрим пример минимизации не полностью определенной функции методом Квайна-Мак-Класки.

Пример 5.25.

0 0 0 1 0 0 0 0

0 0 1 0

0 1 0 0

1 0 0 0 1 0 0 1

1 1 1 0

1 1 1 1

Отсюда

0 0 0 0 0

1 0 0 0 1

2 0 0 1 0

3 0 1 0 0

4 1 0 0 0

5 1 0 0 1

6 1 1 1 0

7 1 1 1 1

1 0 0 0 х 0 – 1

2 0 0 х 0 0 – 2

3 0 х 0 0 0 – 3

4 х 0 0 0 0 – 4

5 х 0 0 1 1 – 5

6 1 0 0 х 4 – 5

7 1 1 1 х 6 – 7

0 0 х 0

0 х 0 0

1 1 1 х

х 0 0 х

Таблица 5.4

	0 0 0 1	0 0 1 0	1 0 0 0	1 1 1 0	1 1 1 1
0 0 х 0		1
0 х 0 0
1 1 1 х				1	1
х 0 0 х	1		1

В данном случае вторая строка, соответствующая импликанте 0х00, вычерчивается, остальные импликанты существенные, таким образом:

0 0 х 0

1 1 1 х.

х 0 0 х

Карты Карно являются удобным средством минимизации булевых функций также для не полностью определенных функций.

Неопределенные значения наносятся на карту Карно и помечаются знаком, отличным от «0» и «1», например «–». Ячейки, соответствующие неопределенным значениям, могут быть использованы для создания групп смежных единиц (или нулей), при этом необходимо покрыть только истинные значения (или только ложные при нахождении минимальной формы по нулям). Ячейки, соответствующие неопределенным значениям, могут и не включаться в группы. Другими словами, с ячейками, помеченными «–», можно поступать как нам удобно, если удобно – включаем в группу, если нет – не включаем.

Пример 5.26. Не полностью определенная функция четырех переменных задана на карте Карно (рис. 5.17), произвести ее минимизацию.

х₁

х₃

х₄

Рис. 5.17. Минимизация не полностью определенной функции

по карте Карно

В данном случае одно неопределенное значение не входит ни в одну из групп. Данная функция не зависит от x ₄.