2015-04-01
796
По результатам предыдущего параграфа любая временная булева функция может быть представлена в виде:
φ = φ 0 τ 0 v φ 1 τ 1 v … v φ s–1 τ s–1
где φi (i = 0, 1,..., s – 1) есть функции алгебры логики. Используя тот факт, что любая функция алгебры логики может быть представлена либо в дизъюнктивной, либо в конъюнктивной совершенной нормальной форме, дадим следующие два определения.
Определение 39. Если во временной булевой функции
φ = φ 0 τ 0 v φ 1 τ 1 v … v φ s–1 τ s–1 все функции φi (i = 0, 1,..., s – 1) представлены в ДСНФ, то соответствующее выражение для φ называется дизъюнктивной совершенной нормальной формой временной булевой функции φ.
Если во временной булевой функции φ = φ 0 τ 0 v φ 1 τ 1 v … v φ s–1 τ s–1 все функции φi (i = 0, 1,..., s – 1) представлены в КСНФ, то соответствующее выражение для φ называется конъюнктивной совершенной нормальной формой временной булевой функции φ.
Из этих определений и соответствующих теорем для функций алгебры логики вытекает следующая теорема.
|
|
|
Теорема 3. Любая временная булева функция может быть представлена в ДСНФ или КСНФ.
Пример 7 - 4. Записать в ДСНФ и КСНФ следующую временную булеву функцию (см. таблицу 7-2).
Таблица 7- 2. – Табличное представление функции φ.
| x1 | x2 | x3 | t | φ (x1, х2, x3, t) | x1 | x2 | x3 | t | φ (x1, х2, x3, t | |
Составляем ДСНФ и КСНФ для φ0 и φ1:
После этого пишем ДСНФ и КСНФ данной временной булевой функции φ:
В силу вышесказанного ясно, что задача минимизации временных булевых функций может быть решена с помощью средств, подобных тем, какие рассматривались для случая минимизации функций алгебры логики.
Пример 7 - 5. Рассмотрим следующую функцию φ (х1, x2, t), (см. таблицу 7- 3).
Таблица 7- 3. – Табличное представление функции φ.
| x1 | x2 | t | φ (x1, х2, t) | x1 | x2 | t | φ (x1, х2, t | |
Согласно определению 39, получим ДСНФ этой функции:
Составим теперь минимизационную карту по методу неопределенных коэффициентов для φ, основываясь на принципе составления таких карт для функций алгебры логики, рассмотренном в гл..., и применим эту карту для минимизации данной функции φ.
Согласно этой минимизационной карте, МДНФ функции φ имеет вид:
| 
| 
| 
| 
|  
|
| |
| 
|
| 
|
|  
|
| |
|  
| 
|
|  
|
|
| |
|  
|
| 
| 
|
|
| |
|
| 
|  
|
| 
|  
| |
|
|
|  
|
|
| 
| |
 
|
| 
|
|
|
|
| |
 
|
|
|
|
|
|
|
Рисунок 7-1 Минимизационная карта к примеру 7-5
Рисунок 7-2 - Минимизационная карта к примеру 7-6.
Из приведенных примеров видно, что минимизационные карты в случае временных булевых функций достаточно громоздки и работа с ними при числе переменных х более трех или при большом количестве допустимых значений t затруднительна. В подобных случаях можно проводить неполную минимизацию. Неполная минимизация проводится следующим образом. Пусть ДСНФ временной булевой функции φ имеет вид:
|
|
|
φ = φ 0 τ 0 v φ 1 τ 1 v … v φ s–1 τ s–1
Находим по обычным правилам МДНФ для φ0, φ1, φ2,.., φs-1 и за приближенное минимальное выражение для φ берем:
где 
– МДНФ функции φi (i = 0, 1,..., s – 1). При большом (s – 1) и малом количестве аргументов х в функциях φi такой метод достаточно продуктивен.
Пример 7- 6. Применяя метод неполной минимизации для функции примера 7-5, получим:
За неполную минимальную форму ВБФ принимаем выражение
Пример 7- 7. Теперь применим метод неполной минимизациидля временной булевой функции примера 7-4:
Неполная минимальная форма для φ запишется в виде следующего выражения:
Для минимизации временных булевых функций, кроме метода минимизирующих карт, можно применять любые методы минимизации, рассмотренные для функций алгебры логики.
