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

Пусть функция 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	ПИ
1					+	+
2		+
3				+	+
4		+		+
5			+
6			+

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

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

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

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

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

Минимизируем теперь функцию fв классе КНФ. Для этого проведем минимизацию функцииfв классе ДНФ Пустьh₀иh₁есть доопределение нулями и единицами соответственно функцииf.

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

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

Таблица 3.11

N	ПИ
1					+	+
2			+	+
3			+
4					+
5		+	+
6						+

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

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

и

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

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

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

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