Студопедия

КАТЕГОРИИ:

АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника


В классе КНФ




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

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

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

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

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

Таблица 3.10

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

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

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

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

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

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

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

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

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

Таблица 3.11

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

 

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

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

и

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

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

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

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

 


Поделиться:

Дата добавления: 2014-11-13; просмотров: 124; Мы поможем в написании вашей работы!; Нарушение авторских прав





lektsii.com - Лекции.Ком - 2014-2024 год. (0.006 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты