Булевы функции (стр. 6 из 7)

7.4 Карты Карно

Иногда удобно пользоваться несколько другим представлением диаграмм с цифровым кодом. Это карты Карно. Примеры карт Карно приведены на рисунке 2. По граням карты проставляются двоичные коды - коды Грея, что дает возможность легко проставлять значения функции и находить результат. Правила минимизации с применение карт Карно такие же, как и для диаграмм Вейча.

х2х3х1	00	01	11	10	х3х4х1х2	00	01	11	10
0	000	001	011	010	00	0000	0001	0011	0010
1	100	101	111	110	01	0100	0101	0111	0110
11	1100	1101	1111	1110
10	1000	1001	1011	1010
а)	б)

Рисунок 2- Карты Карно:

а) функции 3-х переменных;

б) функции 4-х переменных.

8.Особенности минимизации булевых функций большим числом переменных

Рассмотрим некоторые особенности работы с картами Карно для большого числа переменных. При числе переменных, равном или больше пяти, отобразить графически функцию в виде единой плоской карты невозможно. В таких случаях строят комбинированную карту, состоящую из совокупности более простых базовых карт, например карт для функции 4-х переменных. Процедура минимизации в этом случае состоит в том, что сначала находят минимальные формы внутри базовых карт, а затем, расширяя понятия соседних клеток, находят минимальные накрытия для совокупности карт. Соседними клетками являются клетки, совпадающие при наложении базовых карт друг на друга. Примеры карт Карно для булевых функций 5-ти и 6-ти переменных представлены на рис. 3 и 4. соответственно.

Рисунок 3-Карта Карно для булевой функции 5-ти переменных

х3х4х1х2	00	01		11	10		00		01		11	10
00
01
11
10
х5=0			х5=1

Рисунок 4- Карта Карно для булевой функции шести переменных

х3х4х1х2	00	01	11	10	00	01	11	10	00	01	11	10	00	01	11	10
00
01
11
10	(1)	(2)	(3)	(4)
х5х6	00	01	11	10

По рисунку 4 можно сделать вывод, что соседними являются для 1-й базовой карты - 2-я и 4-я; для 2-й - 1-я и 3-я; для 3-й 2-я и 4-я; для 4-й - 1-я и 3-я.

При увеличении количества переменных на одну, площадь карты увеличивается в два раза - к ней пририсовывается еще такая же карта. При этом новая переменная равняется 1 на новой карте, и 0 на той, которая была ранее.

9.Минимизация конъюнктивных нормальных форм

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

Напомним, что конституентой нуля называется функция, принимающая значение 0 на одном наборе. Она выражается дизъюнкцией всех переменных функций. Например, набору 0110 соответствует конституента нуля X1 v

v vX4

Определение. Имплицентой gбулевой функции fназывается функция, принимающая значение 0 на подмножестве нулевых наборов функции f.

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

Задачей, минимизации КНФ является определение минимальной КНФ. Эта задача также решается в два этапа— поиск сокращенной КНФ (конъюнкция всех простых имплицент) и затем нахождение минимальной КНФ. Второй этап минимизации выполняется с помощью таблицы Квайна точно так же, как при поиске минимальной ДНФ, так как возможны только два варианта: либо данная простая имплицента поглощает данную конституенту нуля, либо нет в соответствии с соотношением поглощения: (Avx)A=A

Что касается первого этапа — поиска всех простых имплицент, то практически все методы минимизации ДНФ имеют свои аналоги для КНФ. Расссмотрим это подробнее.

Соотношение склеивания по Квайну:

(Avx) (Av

) =(Avx) (Av )A=A

Метод Квайна для конъюнктивных форм:

1. Выполняются все неполные склеивания в СКНФ.

2. Выполняются все поглощения.

3. Результирующая функция проверяется на возможность дальнейшего склеивания и поглощения.

4. После получения сокращенной КНФ строится имплицентная матрица, по которой находятся “лишние” имплиценты.

По диаграмме Вейча поиск минимальной КНФ осуществляется так же просто, как в случае ДНФ. Отличие состоит лишь в том, что анализируются нулевые наборы и переменные выписываются с инверсиями (по правилам записи конституент 0).

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

х1
	0	1	1	1
	1	1	1	0

б)

В реальных задачах очень часто бывает так, что значение булевой функции на некоторых наборах не определено и может доопределяться произвольно. Выходные сигналы на этих наборах могут принимать любые значения - 0 или 1. Входные наборы, которые дают неопределенное значение функции называются запрещенными. При синтезе схем, реализующих неполностью определенные функции выходным сигналам, соответствующим запрещенным наборам, придают такие значения, при которых можно построить наиболее простую схему. В этом случае доопределение функции целесообразно производить таким образом, чтобы ее минимальная нормальная форма имела наименьшее число букв из всех возможных вариантов доопределения. Рассмотрим простой пример (рис.5,6.).

Рисунок 5

х1
	0	-	-	1
	1	1	-	0

Рисунок 6

х1
	0	0	1	1
	1	1	0	0

б)

х1
	0	0	0	1
	1	1	0	0

Функция задана диаграммой Вейча, представленной рис. 5.а. Доопределение функции на неопределенных наборах единицами (рис. 5.б) или нулями (рис. 6.а) приводит к разным минимальным ДНФ. Однако более простая минимальная ДНФ получается, если произвести доопределение так, как это сделано на диаграмме Вейча (рис. 6.б). Алгоритм поиска минимальной ДНФ частично определенной функции fможно представить следующим образом.