Минимизация частично определенных функций
Поможем в ✍️ написании учебной работы
Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой

 

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

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

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

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

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

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

 

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

В классе ДНФ

1. Cтроим CДНФ функции f0 .

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

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

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

 

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

В классе КНФ

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

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

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

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

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

 

Таблица 4.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. Cтроим матрицу покрытий конституент единицы в CДНФ для доопределения нулями f0 функции f с помощью построенной сокращенной ДНФ для f1 (табл. 4.10).

 

Таблица 4.10

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

 

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

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

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

         

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

         

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

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

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

Матрица покрытия конституент единицы в CДНФ для h0  с помощью простых импликант в сокращенной ДНФ для h1 приведена в табл. 4.11.

 

 

Таблица 4.11

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

 

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

= 25(1Ú 46) = 125 Ú 2446.

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

и

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

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

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

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

 

Дата: 2019-04-23, просмотров: 214.