Алгоритм минимизации функций в классе нормальных форм

Пусть f – функция алгебры логики.

1. Строим все МДНФ функции f.

2. Строим все МКНФ функции f.

3. Из построенных минимальных форм выбираем простейшие ( по числу букв).

Пример 6. В классе нормальных форм минимизировать функцию f=(01011110).

1. Строим СДНФ для функции f:

2. Строим сокращенную ДНФ функции f:

3. Строим матрицу покрытий (таблица 3.6).

Таблица 3.6

N	ПИ	`x`y z `x y z x`y`z x`y z x y`z
	`x z `y z x`y x`z	+ + + + + + + +

 

Решеточное выражение E = ( 1 Ú 2 ) 1 (3 Ú 4 ) 4 = 134 Ú 124.

4. Строим все тупиковые ДНФ функции f:

5. Обе построенные ТДНФ являются минимальными.

6. Повторяем эти этапы для функции `f.

СДНФ:

Сокращенная ДНФ:

Строим матрицу покрытий (таблица 3.7).

Таблица 3.7

N	ПИ	x`y`z `x y`z x y z
	`x`z x y z	+ + +

 

Решеточный многочлен E = 112 = 12. Единственная тупиковая ДНФ (она же минимальная) для функции Минимальная КНФ функции Из построенных МДНФ и МКНФ выбираем простейшую

Пример 7. В классе нормальных форм минимизировать функцию f=(11011011).

1. СДНФ:

2. Сокращенная ДНФ: =

3. Строим матрицу покрытий (таблица 3.8).

 

Таблица 3.8

N	ПИ	`x`y`z `x`y z `x y z x`y`z x y`z x y z
	x y x`z y`z `x z y z `x`y	+ + + + + + + + + + + +

 

E = ( 3 Ú 6 ) ( 4 Ú 6 ) ( 4 Ú 5 ) ( 2 Ú 3 ) ( 1 Ú 2 ) ( 1 Ú 5 ) = 1246 Ú 1356 Ú 134 Ú 256 Ú 2345.

4. Тупиковые ДНФ функции f:

5. Минимальные ДНФ функции f:

6. Повторяем указанные выше этапы для функции `f.

СДНФ:

Сокращенная ДНФ:

Построенная сокращенная ДНФ функции `f является для нее тупиковой и минимальной.

Минимальная КНФ функции

Построенные МДНФ и МКНФ имеют одно и то же число букв; все они составляют минимальные формы для f:

 

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

Пусть функция f(x₁, …, x_n) частично (не всюду) определена. Если f не определена на p наборах из 0 и 1, то существует 2^p возможностей для доопределения функции f. Полностью определенная функция g (x₁, …, x_n) есть доопределение функции f, если g совпадает с f на тех наборах из 0 и 1, на которых f определена.

Задача минимизации частично определенной функции f сводится к отысканию такого доопределения g функции f, которое имеет простейшую (по числу букв ) минимальную форму.

Обозначим через f₀(x₁, …, x_n) и f₁(x₁, …, x_n) доопределения нулями и единицами соответсвенно частично определенной функции f(x₁, …, x_n).

Теорема. Минимальная ДНФ частично определенной функции f(x₁, …, x_n) есть дизъюнкция самых коротких импликант в сокращенной ДНФ доопределения f₁(x₁, …, x_n), которые в совкупности накрывают все конституенты единицы доопределения f₀(x₁, …, x_n).

Доказательство. Рассмотрим СДНФ некоторого доопределения g(x₁, …, x_n) функции f(x₁, …, x_n). Конституенты единицы, входящие в эту форму, войдут и в СДНФ доопределения f₁. Поэтому любой простой импликант функции g будет совпадать с некоторым импликантом функции f₁ или накрываться им. Самые короткие импликанты, накрывающие единицы функции f, есть импликанты функции f₁. Доопределение f₀ имеет минимальное количество конституент единицы в своей СДНФ, следовательно, и количество простых импликант функции f₁, потребных для накрытия этих конституент, будет наименьшим. ДНФ, составленная из самых коротких простых импликант в сокращенной ДНФ функции f₁ , накрывающих все конституенты единицы функции f₀, будет самой короткой ДНФ, доопределяющей функцию f.

Так как единицы функции f₁ составлены из единиц функции f и единиц на наборах, на которых f не определена, то построенная ДНФ, накрывая все единицы функции f₀ ( а, следовательно, и все единицы функции f ), совпадает с минимальной ДНФ некоторого доопределения g функции f.

 

Алгоритм минимизации частично определенных функций

В классе ДНФ

1. Строим СДНФ функции f₀ .

2. Строим сокращенную ДНФ функции f₁ .

3. С помощью матрицы покрытий коституент единицы функции f₀ простыми импликантами функции f₁ и решеточного выражения строим все тупиковые ДНФ (для некоторых доопределений функции f ).

4. Среди полученных ТДНФ выбираем простейшие, они являются минимальными ДНФ ( для некоторых доопределений функции f ).

 

Алгоритм минимизации частично определенных функций

В классе КНФ

Построение минимальных КНФ для частично определенной функции аналогично построению минимальных КНФ для всюду определенной функции.

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

Пример 1. В классе нормальных форм минимизировать частично определенную функцию f ( x, y, z, t ) = (1---010010-01--1)

Решение. Минимизируем функцию f в классе ДНФ.

1. Строим сокращенную ДНФ для доопределения единицами f₁ функции f по таблице 3.9.

Таблица 3.9

x y z t	f f0 f1 `f h0 h1
0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1	1 1 1 0 0 0 - 0 1 - 0 1 - 0 1 - 0 1 - 0 1 - 0 1 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 1 1 1 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 1 1 1 - 0 1 - 0 1 0 0 0 1 1 1 1 1 1 1 1 1 - 0 1 - 0 1 - 0 1 - 0 1 1 1 1 0 0 0

2. Строим матрицу покрытий коституент единицы в СДНФ для доопределения нулями f₀ функции f с помощью построенной сокращенной ДНФ для f₁ ( таблица 3.10).

Таблица 3.10

N	ПИ
					+	+
		+
				+	+
		+		+
			+
			+

3. По таблице строим решеточный многочлен

E = (2Ú 4)(5Ú 6)(3Ú 4)(1Ú 3)1 = 145 Ú 125 Ú 146 Ú 1236.

4. Строим все тупиковые ДНФ:

5. Из построенных тупиковых ДНФ выбираем минимальные:

Функции g₁ и g₃ есть минимальные доопределения функции f в классе ДНФ.

Минимизируем теперь функцию f в классе КНФ. Для этого проведем минимизацию функции `f в классе ДНФ Пусть h<sub>0</sub> и h<sub>1</sub> есть доопределение нулями и единицами соответственно функции `f.

Сокращенная ДНФ для

Матрица покрытия конституент единицы в СДНФ для h₀ с помощью простых импликант в сокращенной ДНФ для h₁ приведена в таблице 3.11.

Таблица 3.11

N	ПИ
					+	+
			+	+
			+
					+
		+	+
						+

 

3. Решеточное выражение E=5 (2 Ú 3 Ú 5) 2 (1Ú 4)(1Ú 6) = 25(1Ú 46) = 125 Ú 2446.

4. Строим две тупиковые ДНФ:

и

Минимальная.

5. Функция есть минимальное доопределение функции f в классе КНФ.

Найденные МДНФ g₁, g₃ и МКНФ являются минимальными доопределениями функции f в классе нормальных форм.

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

 

⇐ Предыдущая3456789101112Следующая ⇒

Поделиться:

Популярное:

1. I. Морфологическая форма слова.
2. I. Поставьте предложения в отрицательную форму (Present Indefinite Tense).
3. III. Компетенции обучающегося, формируемые
4. III. Компетенции обучающегося, формируемые в результате
5. III. Поставьте глагол-сказуемое в нужной форме (Present, Past, Future Indefinite)
6. III. Этап обобщения информации
7. Iran указывает на адресное пространство и связанную с управлением памятью информацию.
8. IV.3. СОХРАНЕНИЕ ИНФОРМАЦИИ ОТ ПОКОЛЕНИЯ К ПОКОЛЕНИЮ
9. V Криминалистическое исследование видео- и фонограмм, средств видео- и звукозаписи и информации, зафиксированной с их помощью.
10. V. Bыпишите из 1-ro aбзацa npeдложение с глаголомв пассивной форме, назовите время глагола. Предложение переведите.
11. V. ПОРЯДОК ФОРМИРОВАНИЯ И ДЕЯТЕЛЬНОСТИ ОРГАНОВ ПРОФСОЮЗА
12. V1: Основы информационного права Российской Федерации