Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
Алгоритм минимизации функций в классе нормальных форм
Пусть f – функция алгебры логики. 1. Строим все МДНФ функции f. 2. Строим все МКНФ функции f. 3. Из построенных минимальных форм выбираем простейшие ( по числу букв). Пример 6. В классе нормальных форм минимизировать функцию f=(01011110). 1. Строим СДНФ для функции f: 2. Строим сокращенную ДНФ функции f: 3. Строим матрицу покрытий (таблица 3.6). Таблица 3.6
Решеточное выражение E = ( 1 Ú 2 ) 1 (3 Ú 4 ) 4 = 134 Ú 124. 4. Строим все тупиковые ДНФ функции f:
5. Обе построенные ТДНФ являются минимальными. 6. Повторяем эти этапы для функции `f. СДНФ: Сокращенная ДНФ: Строим матрицу покрытий (таблица 3.7). Таблица 3.7
Решеточный многочлен E = 112 = 12. Единственная тупиковая ДНФ (она же минимальная) для функции Минимальная КНФ функции Из построенных МДНФ и МКНФ выбираем простейшую Пример 7. В классе нормальных форм минимизировать функцию f=(11011011). 1. СДНФ: 2. Сокращенная ДНФ: = 3. Строим матрицу покрытий (таблица 3.8).
Таблица 3.8
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:
Минимизация частично определенных функций Пусть функция f(x1, …, xn) частично (не всюду) определена. Если f не определена на p наборах из 0 и 1, то существует 2p возможностей для доопределения функции f. Полностью определенная функция g (x1, …, xn) есть доопределение функции f, если g совпадает с f на тех наборах из 0 и 1, на которых f определена. Задача минимизации частично определенной функции f сводится к отысканию такого доопределения g функции f, которое имеет простейшую (по числу букв ) минимальную форму. Обозначим через f0(x1, …, xn) и f1(x1, …, xn) доопределения нулями и единицами соответсвенно частично определенной функции f(x1, …, xn). Теорема. Минимальная ДНФ частично определенной функции f(x1, …, xn) есть дизъюнкция самых коротких импликант в сокращенной ДНФ доопределения f1(x1, …, xn), которые в совкупности накрывают все конституенты единицы доопределения f0(x1, …, xn). Доказательство. Рассмотрим СДНФ некоторого доопределения g(x1, …, xn) функции f(x1, …, xn). Конституенты единицы, входящие в эту форму, войдут и в СДНФ доопределения f1. Поэтому любой простой импликант функции g будет совпадать с некоторым импликантом функции f1 или накрываться им. Самые короткие импликанты, накрывающие единицы функции f, есть импликанты функции f1. Доопределение f0 имеет минимальное количество конституент единицы в своей СДНФ, следовательно, и количество простых импликант функции f1, потребных для накрытия этих конституент, будет наименьшим. ДНФ, составленная из самых коротких простых импликант в сокращенной ДНФ функции f1 , накрывающих все конституенты единицы функции f0, будет самой короткой ДНФ, доопределяющей функцию f. Так как единицы функции f1 составлены из единиц функции f и единиц на наборах, на которых f не определена, то построенная ДНФ, накрывая все единицы функции f0 ( а, следовательно, и все единицы функции f ), совпадает с минимальной ДНФ некоторого доопределения g функции f.
Алгоритм минимизации частично определенных функций В классе ДНФ 1. Строим СДНФ функции f0 . 2. Строим сокращенную ДНФ функции f1 . 3. С помощью матрицы покрытий коституент единицы функции f0 простыми импликантами функции f1 и решеточного выражения строим все тупиковые ДНФ (для некоторых доопределений функции f ). 4. Среди полученных ТДНФ выбираем простейшие, они являются минимальными ДНФ ( для некоторых доопределений функции f ).
Алгоритм минимизации частично определенных функций В классе КНФ Построение минимальных КНФ для частично определенной функции аналогично построению минимальных КНФ для всюду определенной функции. Алгоритм минимизации частично определенных функций в классе нормальных форм аналогичен алгоритму минимизации в классе нормальных форм для всюду определенных функций. Пример 1. В классе нормальных форм минимизировать частично определенную функцию f ( x, y, z, t ) = (1---010010-01--1) Решение. Минимизируем функцию f в классе ДНФ. 1. Строим сокращенную ДНФ для доопределения единицами f1 функции f по таблице 3.9. Таблица 3.9
2. Строим матрицу покрытий коституент единицы в СДНФ для доопределения нулями f0 функции f с помощью построенной сокращенной ДНФ для f1 ( таблица 3.10). Таблица 3.10
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
3. Решеточное выражение E=5 (2 Ú 3 Ú 5) 2 (1Ú 4)(1Ú 6) = 25(1Ú 46) = 125 Ú 2446. 4. Строим две тупиковые ДНФ: и Минимальная. 5. Функция есть минимальное доопределение функции f в классе КНФ. Найденные МДНФ g1, g3 и МКНФ являются минимальными доопределениями функции f в классе нормальных форм. Техническая реализация минимальных форм для функции часто проще, а потому дешевле реализации ее СДНФ ( СКНФ ). Следовательно, этап минимизации при конструировании логических схем является одним из важнейших.
Популярное:
|
Последнее изменение этой страницы: 2016-04-09; Просмотров: 1286; Нарушение авторского права страницы