БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙУНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ
Кафедра высшей математики
РЕФЕРАТ
на тему:
«Минимизация неполностьюопределенных переключательных функций»
В ЦВМ могут использоватьсякомбинационные схемы, закон функционирования которых определен неполностью. Втаких схемах некоторые комбинации сигналов на ее входы не подаются и являютсязапрещенными.
Для запрещенных входных комбинаций выходные сигналы неопределены, т.е. могут принимать любые значения – нуль или единицу. Поэтому присинтезе схем с неполностью заданным законом функционирования можно произвольнозадать значения выходных сигналов для запрещенных комбинаций входных сигналов;нормальная работа схемы при этом не нарушается.
Выходным сигналам на запрещенных комбинациях придаюттакие значения, при которых можно построить наиболее простую схему.
Схемы с запрещенными комбинациями выходных сигналовописываются неполностью определенными переключательными функциями, т.е.функциями, значения которых определены не на всех наборах. Например, функциязаданная таблицей и диаграммой Вейча
/>
/>x1 1 1
/>x2 1 1 1 x3 1 1 1 f(x1, x2, x3) 1 1 1
определена только на шести наборах. Клетки,соответствующие наборам 1,0,0; 1,1,1 остаются пустыми.
Форма представления функции f(x1, x2, x3)существенно зависит от выбора ее значений на запрещенных наборах, Например, длязаданной функции, выбирая ее запрещенные значения равными нулю, можно получитьминимальную ДНФ в виде
/>
Если значения функции на запрещенных наборах принятьравными единице, то форма представления упрощается
/>.
Рассмотрим общую методику получения минимальных ДНФнеполностью определенных переключательных функций
Определение Пусть переключательная функция f(x1, x2,…, xn) не определена на p наборах аргументов. Тогда полностью определеннуюфункцию j(x1, x2, …, xn) будем называть эквивалентной функцииf(x1, x2, …, xn), если ее значения совпадают со значениями функции f(x1, x2, …,xn) на тех наборах, на которых эта функция f определена.
Существует 2p вариантов выбора значений функции назапрещенных наборах и, следовательно, 2р различных переключательных функций,эквивалентных функции f(x1, x2, …, xn).
Поэтому задача минимизации неполностью определеннойфункции f(x1, x2, …, xn) сводится к отысканию такой эквивалентной функции j(x1, x2, …, xn), которая имеет простейшую минимальную форму.
Введем эквивалентные функции j0(x1, x2, …, xn) и j1(x1, x2, …, xn), значения которых на всех запрещенныхнаборах функции f(x1, x2, …, xn) равны, соответственно, нулю и единице.
Теорема. Минимальная ДНФ неполностью определенной функции f(x1, x2, …, xn) совпадает с дизъюнкцией самых коротких импликантэквивалентной функции j1(x1, x2, …, xn), которые совместно поглощают всеконституенты единицы функции j0(x1, x2, …, xn) и ни одна изкоторых не является лишней.
Для доказательства теоремы рассмотрим СДНФ некоторойэквивалентной функции ji(x1, x2, …, xn). Конституенты единицы, входящие в этуформу, обязательно войдут и в СДНФ функции j1(x1, x2, …,xn). Поэтому любая простая импликанта функции ji(x1, x2, …,xn) будет совпадать с импликантой функции j1(x1, x2, …, xn) илибудет поглощаться ею. Другими словами, среди импликант функции j1(x1, x2, …, xn) всегда найдется такая, которая поглощает любуюимпликанту любой эквивалентной функции ji(x1, x2, …, xn).Следовательно, самыми короткими произведениями, накрывающими единицы функцииf(x1, x2, …, xn), будут импликанты j1(x1, x2, …, xn).
Среди всех ПФ, эквивалентных заданной, функция j0(x1, x2, …, xn) имеет минимальное количество конституент единицы.Следовательно, и количество простых импликант [из набора импликант функции j1(x1, x2, …, xn)], необходимых для поглощения конституент функции j0(x1, x2, …, xn), будет минимальным. Если составить дизъюнкции наиболеекоротких импликант функции j0(x1, x2, …, xn), которыесовместно накрывают все конституенты единицы функции j0(x1, x2, …, xn), то получим, очевидно, минимальную форму представленияфункции f(x1, x2, …, xn).
Ввиду того, что для накрытия единиц функции j0(x1, x2, …, xn) выбираются импликанты другой функции, дизъюнкция этихимпликант не равняется функции j0(x1, x2, …, xn). Однако, такаядизъюнкция обязательно равна одной из функций, эквивалентных функции f(x1, x2,…, xn).
Пример. Найти минимальную дизъюнктивную нормальнуюформу ПФ, заданной таблицей.x1 1 1 1 1 1 1 1 1 x2 1 1 1 1 1 1 1 1 x3 1 1 1 1 1 1 1 1 x4 1 1 1 1 1 1 1 1 f(x1, x2, x3, x4) 1 1 1 1 1
Полагая, что пустые клетки заполнены нулями, найдемСДНФ эквивалентной функции j0(x1, x2, x3, x4):
/>.
СНДФ функции j1(x1, x2, …, xn),полученная после заполнения пустых клеток таблицы единицами, будет
/>
Выполнив операции склеивания и поглощения, получимсокращенную ДНФ функции j1 (x1, x2, x3, x4), в которую войдут все ее простые импликанты:
/>
Составим импликантную матрицу, включив в нееконституенты единицы функции j0(x1, x2, x3, x4) иимпликанты функции j1(x1, x2, x3, x4).
Импли-
канты Конституенты
/>
/>
/>
/> x1 x2 x3 x4 x1 x2 x x
/> x
/> x x
/> x x
/> x
/> x
Импликанта x1x2 обязательнодолжна входить в мин ДНФ, т.к. только она поглощает конституенту x1x2x3x4.Импликанты x1x2/>/>совместно накрывают всеконституенты, кроме />; последняя может быть накрытаимпликантами /> или />. Поэтому минимальные ДНФфункции f(x1, x2, x3, x4) будут:
/>
/>
Пример. Найти минимальную ДНФ функции f(x1, x2, x3, x4),эквивалентая функция j0(x1, x2, x3, x4) которой имеет вид:
/>
а комбинации /> являются запрещенными.
Эквивалентную функцию j1(x1, x2, …, xn)можно получить, добавив к СДНФ функции j1(x1, x2, …, xn)запрещенные комбинации переменных:
/>
Проведя операции склеивания и поглощения, найдемпростые импликанты функции j1(x1, x2, x3, x4); x1x2x3, x1x3x4, />, />. Импликантная матрица функции f(x1, x2, x3, x4)имеет вид.
Импли-
канты Конституенты
/>
/>
/>
/>
/>
/> x x
/> х х х x1x2x3 х x1x3x4
Функция f(x1, x2, x3, x4)имеет единственную минимальную ДНФ />
В нижней строке импликантной матрицы крестикиотсутствуют и, следовательно, импликанта x1x3x4 непоглощает ни одну из конституент единицы функции j0(x1, x2, x3, x4).Это связано с тем, что данная импликанта образовалась в результате склеиванияконституент функции j1(x1, x2, x3, x4), которые в функцию j0(x1, x2, x3, x4)не входят.
Чтобы найти простейшее представление неполностьюопределенной ПФ, кроме минимальных дизъюнктивных форм следует получить минимальныеконъюнктивные нормальные формы и выбрать из них ту, которая содержит наименьшеечисло букв.
Алгоритм получения минимальных конъюнктивных формподобен рассмотренному алгоритму получения минимальной ДНФ и заключается вследующем.
Пусть задана неполностью определенная функция f(x1,x2, …, xn). Тогда для получения минимальной КНФ достаточно найти сокращеннуюКНФ эквивалентной функции j0(x1, x2, …, xn), а функцию j1(x1, x2, …, xn) записать в СКНФ. Затем следует составить ипликантнуюматрицу, включив в нее все конституенты нуля функции j1(x1, x2, …, xn) и все члены сокращенной конъюнктивной нормальной формыфункции j0(x1, x2, …, xn). По импликантной матрицерассмотренным выше способом можно получить минимальные КНФ функции f(x1, x2, …,xn).
Пример. Найти минимальную КНФ функции, записаннойтаблицей.x1 1 1 1 1 1 1 1 1 x2 1 1 1 1 1 1 1 1 x3 1 1 1 1 1 1 1 1 x4 1 1 1 1 1 1 1 1 f(x1, x2, x3, x4) 1 1 1 1 1 1 1 1
СКНФ эквивалентной функции j1(x1, x2, x3, x4):
/>/>
СКНФ функции />
/>/>
Сокращенная КНФ функции j0(x1, x2, x3, x4)
/>
Импликантная матрица имеет вид:
Импли-
канты
/>
/>
/>
/>
/> 1 2 3 4 5
/> х х х
/> х х х
/> х /> /> /> /> /> /> />
Минимальная КНФ функции f(x1, x2, x3, x4)
/>
Рассмотренная функция имеет четыре минимальные ДНФ
/>
/>
/>
/>
Здесь больше букв, чем в МКНФ.
ЛИТЕРАТУРА
1. Белоусов А.И., Ткачев С.Б. Дискретная математика: Учебник для ВУЗов /Под ред. В.С. Зарубина, А.П. Крищенко.– М.: изд-во МГТУ им. Н.Э. Баумана,2001.– 744 с. (Сер. Математика в техническом университете; Вып XIX).
2. Горбатов В.А. Фундаментальные основы дискретной математики.Информационная математика.– М.: Наука, Физматлит, 2000.– 544 с.– ISBN 5-02-015238-2.
3. Петрова В.Т. Лекции по алгебре и геометрии. Учебник для ВУЗов: в2 ч.– М.: Гуманит. изд. центр ВЛАДОС.– ч. 1 – 312 с., ч. 2 – 344 с. ISBN 5-691-00077-2. ISBN 5-691-00238-4 (I),ISBN 5-691-00239-2 (II).
4. Зарубин В.С. Математическое моделирование в технике: Учеб. дляВУЗов / Под ред. В.С. Зарубина, А.П. Крищенко.– М.: Изд-во МГТУ им. Н.Э.Баумана, 2001.– 496 с. (Сер. Математика в техническом университете; вып. XXI, заключительный).