Имеем три простые импликанты: -111, 111-, 0--1

4. Имеем три простые импликанты: -111, 111-, 0--1.

Таблица 11  Таблица 12 Таблица 13

Номер группы	Двоичные номера кон-ституент 1		Номер группы	Двоичные номера импликант		Номер группы	Двоичные номера импликант
0	-		1 (1-2)	00-1 *		1	0--1
1	0001 *			0-01 *			0--1
2	0011 *		2 (2-3)	0-11 *		2	-111
	0101 *			01-1 *			111-
3	0111 *		3 (3-4)	-111
	1110 *			111-
4	1111 *

Таблица 14

Простые	Конституенты единицы
импликанты
(0--1)	Х	Х	Х	Х
(-111)				Х		Х
(111-)					Х	Х

5. Строим импликантную матрицу (табл. 14). По таблице определяем совокупность простых импликант - 0--1 и 111-, соответствующую минимальной ДНФ. Для восстановления буквенного вида простой импликанты достаточно выписать произведения тех переменных, которые соответствуют сохранившимся двоичным цифрам:

fmin=Ú

Заметим, что разбиение конституент на группы позволяет уменьшить число попарных сравнений при склеивании.

7.3 Метод диаграмм Вейча

 

Метод позволяет быстро получать минимальные ДНФ булевой функции f небольшого числа переменных. В основе метода лежит задание булевых функций диаграммами некоторого специального вида, получившими название диаграмм Вейча. Для булевой функции двух переменных диаграмма Вейча имеет вид (табл. 15). Каждая клетка диаграммы соответствует набору переменных булевой функции в ее таблице истинности. В табл.15. это соответствие показано. В клетке диаграммы Вейча ставится единица, если булева функция принимает единичное значение на соответствующем наборе. Нулевые значения булевой функции в диаграмме Вейча не ставятся. Для булевой функции трех переменных диаграмма Вейча имеет следующий вид (табл. 16). Добавление к ней еще такой же таблицы дает диаграмму для функции 4-х переменных (табл. 17). Таким же образом, т. е. приписыванием еще одной диаграммы 4-х переменных, к только что рассмотренной, можно получить диаграмму для функции 5-ти переменных и т. д., однако диаграммы для функций с числом переменных больше 4-х используются редко.

Для приведенных диаграмм характерно следующее:

1)  каждой клетке диаграммы соответствует свой набор;

Таблица 15. Таблица 16.

	11	01			110	111	011	010
	10	00			100	101	001	000

Таблица 17.  Таблица 18.

								х1
х1	1100	1101	1001	1000				1	1		1
х1	1110	1111	1011	1010	х3						1
	0110	0111	0011	0010	х3
	0100	0101	0001	0000
		х4	х4

2) соседние наборы расположены рядом в строке либо в столбце. Соседними наборами называются наборы, отличающиеся одной компонентой. Напомним, что конституенты, соответствующие таким наборам, склеиваются (см. метод Квайна-Мак-Класки). Например, для функции, заданной табл. 18, конституенты, соответствующие паре единиц в левой части таблицы, склеиваются и порождают элементарное произведение из двух букв:

=

О паре единиц в правой части диаграммы можно сказать то же самое: =.

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

Еще одно важное замечание: столбцы, расположенные по краям диаграммы, тоже считаются соседними. Для нашего примера это означает, что имеет место еще одно склеивание, в результате которого, следуя указанному правилу, получаем элементарное произведение . Из рассмотренных ранее методов нам известно, что возможно дальнейшее склеивание получаемых элементарных произведений. На диаграммах Вейча они тоже располагаются рядом. Общее правило склеивания на диаграммах Вейча можно сформулировать следующим образом: склеиванию подлежат прямоугольные конфигурации, заполненные единицами и содержащие число клеток, являющееся степенью 2. Получающееся новое элементарное произведение определяется как произведение переменных, не меняющих своего значения на всех склеиваемых наборах. Число m оставшихся переменных в элементарном произведении определяется легко:

m=n-log2M,

где n- число переменных,

M - число склеиваемых наборов.

Метод широко используется на практике, благодаря простоте и удобству. После небольшой тренировки достигается элементарный навык определения минимальной ДНФ по диаграмме «с первого взгляда».

Минимизация булевой функции заключается в нахождении минимального покрытия всех единиц диаграммы Вейча блоками из единиц (указанной конфигурации), расположенных в соседних клетках диаграммы. При этом всегда считается, что левый край диаграммы Вейча 4-х переменных примыкает к ее правому краю, а верхний край диаграммы примыкает к нижнему ее краю. Для удобства можно предположить, что диаграмма сворачивается в цилиндр как по горизонтали, так и по вертикали. После получения минимального покрытия всех единиц диаграммы Вейча, минимальная ДНФ булевой функции записывается как дизъюнкция элементарных конъюнкций, соответствующих выделенным блокам единиц в диаграмме.

В диаграмме Вейча необходимо и достаточно, чтобы каждая единичная клетка участвовала в склейке хотя бы один раз.

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

Вся диаграмма должна быть покрыта наименьшим количеством склеек. В склейку может входить 2n соседних клеток (2, 4, 8, 16. и т.д.).

Рассмотрим несколько примеров.

Таблица 19  Таблица 20

  X4 X3

х1						х1		1	1
х1	1	1			х3	х1	1	1	1	1	х3
		1	1		х3		1	1	1	1	х3
		1	1					1	1
		х4	х4					х4	х4

f1=v f2= X4 v X3

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  v X4

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

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

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

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

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

(A v x) (A v ) =(A v x) (A v )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 можно представить следующим образом.