Свойства диаграмм Вейча

С помощью диаграмм Вейча можно находить:

1. минимальную форму по СКНФ
2. минимальную форму по ДНФ и КНФ функции
3. все одинаково минимальные формы
4. минимальную форму неполностью определенных функций.

Пусть f(x₁x₂x₃) задана не в виде СДНФ, а в ДНФ:

f(x₁x₂x₃) = x₁x₂ x₁x₂x₃ x₁x₂

Заполним соответствующую диаграмму:

Так как x₁x₂ = x₁x₂ (x₃ x₃) = x₁x₂x₃ x₁x₂x₃, то в соответствующие клетки диаграммы поставлены единицы.

Поэтому: f_min(x₁,x₂,x₃) = x₂x₃ x₁x₂ x₁x₂

Преимущество метода: простота и наглядность для небольшого числа аргументов.

Недостатки: неприменяемость метода для большого числа аргументов (> 6) вследствие сложности диаграмм и потери наглядности.

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

Страницы: 1 | 2 | 3 | вопросы |»

| учебники | для печати и PDA | ZIP

Если Вы заметили ошибку - сообщите нам, или выделите ее и нажмите Ctrl+Enter

В лекции представлена минимизация неполностью определенных функций, дан синтез функций в базисах штрих Шеффера и стрелка Пирса, даны подходы к минимизации конъюнктивных форм.

Очень часто, если не в большинстве случаев, работа конкретного устройства описывается с помощью неполностью определенной функции, так как некоторые комбинации входных сигналов не подаются или являются запрещенными. Определение. Неполностью определенной функцией является такая переключательная функция, значения которой на некоторых наборах аргументов могут быть произвольными (т.е. равными "0" или "1"). Определение. Пусть функция f(x₁,x₂,...x_n) не определена на "р" наборах аргументов. Тогда полностью определенную функцию (x₁,x₂,...x_n) будем считать эквивалентной к f(x₁,x₂,...x_n), если ее значения на тех наборах, на которых f(x₁,x₂,...x_n) определена, совпадают. Очевидно, существует 2^р различных функций, эквивалентных f(x₁,x₂,...x_n). Задача минимизации f(x₁,x₂,...x_n) состоит в выборе такой эквивалентной (x₁,x₂,...x_n), которая имеет простейшую форму. Введем две вспомогательные эквивалентные функции ₀(x₁,x₂,...x_n), ₁(x₁,x₂,...x_n), которые принимают на запрещенных наборах аргументов значения 0 и 1 соответственно. ТЕОРЕМА. МДНФ неполностью определенной f(x₁,x₂,...x_n) совпадает с дизъюнкцией самых коротких импликант ₁(x₁,x₂,...x_n), которые совместно накрывают все конституенты единицы ₀(x₁,x₂,...x_n), и ни одна из которых не является лишней. Пример: Пусть задана f(x₁,x₂,...x_n) в виде следующей таблицы:

f(x1,x2,...xn)

-

-

-

-

-

-

Числовые эквиваленты наборов

Тогда

₀(x₁x₂x₃x₄) = 0 5 8 12 15 = x₁x₂x₃x₄ x₁x₂x₃x₄ x₁x₂x₃x₄ x₁x₂x₃x₄ x₁x₂x₃x₄ = 0000 0101 1000 1100 1111,

а

₁(x₁x₂x₃x₄) = 0 1 2 3 5 8 10 12 13 14 15 = 0000 0001 0010 0011 0101 1000 1010 1100 1101 1110 1111

Найдем простые импликанты ₁(x₁x₂x₃x₄)

Конституенты единицы 1	Отметки о склейке	Импликанты	Отметки о склейке	Импликанты
	*	000- 00-0 -000	*	00- - 00- - -0-0
	*	*
*	*
*	00-1 0-01 001- -010 1-00	*
	*	-
*	*	1- -0
*	*
*	*
	*	-101 1-10 110- 11-0	-
*
*	-	11- -
-
	*	111-	*

Простые импликанты ₁(x₁x₂x₃x₄)

₁(x₁x₂x₃x₄) = 0-01 -101 110- 11-0 00- - -0-0 1- -0 11- -

Построим импликантную матрицу.

Конституенты единицы0
Простые импликанты 1
0-01		+
-101		+
110-				+
11-0				+
00--	+
-0-0	+		+
1--0			+	+
11--				+	+

Выполним оптимальное покрытие конституент единицы ₀ простыми импликантами ₁ и получаем минимальную форму функции f(x₁x₂ x₃ x₄)

f¹_min(x₁x₂ x₃ x₄) = 11- - -0-0 -101 = x₁x₂ x₂x₄ x₂x₃x₄

f²_min(x₁x₂ x₃ x₄) = 11- - -0-0 0-01 = x₁x₂ x₂x₄ x₁x₃x₄

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

Пример:

Рассмотрим функцию f(x₁x₂ x₃ x₄) и найдем ее минимальную форму. Заполнить диаграмму Вейча по следующим правилам: в клетки диаграммы поставим единицы, которые соответствуют конституентам единицы, нули – для отсутствующих конституент и символ неопределенности – "*" (звездочка) – в остальные.

Видно, что в клетки для конституент: x₁x₂x₃x₄, x₁x₂x₃x₄, x₁x₂x₃x₄ целесообразно "поставить" единицы вместо символов неопределенности, так как в этом случае образуется правильная конфигурация 2-го ранга, которая покрывается произведением x₂x₃.

Аналогично и в клетку x₁x₂x₃x₄ нужно "поставить" единицу.

Итак, f_min(x₁x₂ x₃ x₄) = x₂x₃ x₁x₄ x₃x₄ x₁x₂.

Замечание. Все, что было сказано относительно минимизации функции, представленной в СДНФ или ДНФ справедливо для функции, заданной в СКНФ или КНФ.

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

Дата добавления: 2014-01-06