Импликантная матрица

Простые импли-канты	Конституенты единицы
	X	X
		X	X
			X	X
				X	X
					X	X

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

Чтобы получить минимальную дизъюнктивную нормальную форму заданной функции, достаточно найти минимальное число импликант, которые совместно накрывают крестиками все колонки импликантной матрицы.

Из табл. 2.3.1 следует, что в минимальную форму обя­зательно должны войти импликанты и , так как только они накрывают крестиками первую и шестую колонки импликантной матрицы.

Кроме того, имлликанта накрывает вторую, а импликанта — пятую колонки. Поэтому остается накрыть только третью и четвертую колонки. Для этого можно выбрать пары импликант: и ; и или одну импликанту . Если выбрать указанные выше пары импликант, то импликанты и оказываются лишними, так как импликанта одна накрывает третью и четвертую колонки таблицы. Таким образом, выбрав импликанту , получим ми­нимальную дизъюнк­тивную нормальную форму задан­ной функции.

,

которая совпадает с первой тупиковой формой. Если дополнительно к и выбрать импликанты и , то лишних импликант не оказывает­ся, а полученное выражение

,

является второй тупиковой формой заданной функ­ции.

Пример. Найти минимальные формы переключатель­ной функции

. (2.3.1)

Проводя все операции склеивания и поглощения, по­лучим сокра­щен­ную дизъюнктивную нормальную форму:

(2.3.2)

. (2.3.3)

Составим импликаитную матрицу (табл. 2.3.2), выпи­сав из выражения (2.3.1) все конституенты единицы, а из выражения (2.3.3) - все простые импликанты. При заполнении импликантной матрицы удобно пользоваться формой записи (2.3.2): следует поставить крестики в тех колонках, номера которых совпадают с числами, стоящими в левой части формы (2.3.2).

Таблица 2.3.2

Импликантная матрица

Простые импли-канты	Конституенты единицы
	X	X
	X		X
		X				X
			X	X
				X	X
					X	X

Для импликанты крестиками отмечаются первая и вторая колон­ки; для — первая и третья и т. д. Заметим, что каж­дая колонка табл. 2.3.2 отмечена двумя крестиками. По­этому из выражения (2.3.3) можно исключить любую импликанту. Минимальное количество импликант, накрывающих крестиками все колонки, равно трем:

накрывает первую и вторую колонки,

накрывает третью и четвертую колонки,

накрывает пятую и шестую колонки.

Поэтому минимальная дизъюнктивная нормальная форма заданной функции имеет вид

.

Можно накрыть все колонки табл. 3.9 и другими импликантами:

накрывает первую и третью колонки,

накрывает вторую и шестую колонки,

накрывает четвертую и пятую колонки.

Таким образом, данная функция имеет вторую минимальную форму

.

Переключательная функция имеет не­сколько других тупиковых форм, которые, однако, не являются минимальными. Например, тупиковыми будут следующие формы:

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

1. Переключательную функцию представляют в совершенной дизъюнктивной нормальной форме. При этом, если функция задана таблицей, то ее следует запи­сать «по единицам»; если же функция задана в произ­вольной аналитической форме, то совершенную дизъ­юнктивную нормальную форму можно получить, при­меняя операции развертывания, правила де Моргана и другие формулы булевой алгебры.

2. В полученной совершенной дизъюнктивной нор­мальной форме проводят все операции неполного склеивания и поглощения. В результате этого получается сокращенная дизъюнктивная нор­мальная форма заданной функции.

3. Находят минимальные дизъюнктивные нор­мальные формы по импликантной матрице. Если коли­чество импликант в сокращенной дизъюнктивной нормаль­ной форме невелико, то можно найти тупиковые формы методом испытания импликант и выбрать среди них мини­мальные.

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

Дата добавления: 2015-07-26; просмотров: 277; Нарушение авторских прав

Мы поможем в написании ваших работ!