Алгоритм минимизации функций в классе нормальных форм
Пусть 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 :
Дата добавления: 2016-03-27; просмотров: 1303;