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

В ЦВМ могут использоваться комбинационные схемы, закон функцио­ни­рования которых определен неполностью. В таких схемах некоторые ком­би­на­ции сигналов на ее входы не подаются и являются запрещенными. Для за­пре­щенных входных комбинаций выходные сигналы не определены, т.е. мо­гут принимать любые значения – нуль или единицу. Поэтому при синтезе схем с неполностью заданным законом функционирования можно произ­вольно задать значения выходных сигналов для запрещенных комбинаций входных сигналов; нормальная работа схемы при этом не нарушается. Поэтому выходным сигналам на запрещенных комбинациях придают такие значения, при которых можно построить наиболее простую схему.

Схемы с запрещенными комбинациями выходных сигналов описы­вают­ся неполностью определенными переключательными функциями, т.е. функ­циями, значения которых определены не на всех наборах. Например, функция, заданная таблицей истинности и диаграммой Вейча,

Минимизация неполностью определенных переключательных функций - student2.ru

определена только на шести наборах. Клетки, соответствующие наборам 1,0,0; 1,1,1, остаются пустыми.

Форма представления функции f(x1, x2, x3) существенно зависит от вы­бо­ра ее значений на запрещенных наборах, Например, для заданной функции, выбирая ее запрещенные значения равными нулю, можно получить мини­мальную ДНФ в виде

Минимизация неполностью определенных переключательных функций - student2.ru

Если значения функции на запрещенных наборах принять равными единице, то форма представления упрощается:

Минимизация неполностью определенных переключательных функций - student2.ru .

Рассмотрим общую методику получения минимальных ДНФ непол­ностью определенных переключательных функций

Определение 2.3.Пусть переключательная функция 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) равны соответственно нулю и единице.

Теорема 2.3.Минимальная ДНФ неполностью определенной функ­ции 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).

Пример 2.11. Найти минимальную дизъюнктивную нормальную форму ПФ, заданной таблицей истинности (табл. 2.6).

Таблица 2.6

Таблица истинности неполностью определенной функции

x1
x2
x3
x4
f(x1, x2, x3, x4)            


Полагая, что пустые клетки заполнены нулями, найдем СДНФ экви­ва­лентной функции j0(x1, x2, x3, x4):

Минимизация неполностью определенных переключательных функций - student2.ru .

СНДФ функции j1(x1, x2, …, xn), полученная после заполнения пустых клеток таблицы единицами, будет такой:

Минимизация неполностью определенных переключательных функций - student2.ru

Выполнив операции неполного склеивания и поглощения, получим сокра­щенную ДНФ функции j1(x1, x2, x3, x4), в которую войдут все ее простые импликанты:

Минимизация неполностью определенных переключательных функций - student2.ru .

Составим импликантную матрицу, включив в нее конституенты единицы функции j0(x1, x2, x3, x4) и импликанты функции j1(x1, x2, x3, x4) (табл. 2.7).

Таблица 2.7

Импликантная матрица

Импликанты Конституенты
Минимизация неполностью определенных переключательных функций - student2.ru Минимизация неполностью определенных переключательных функций - student2.ru Минимизация неполностью определенных переключательных функций - student2.ru Минимизация неполностью определенных переключательных функций - student2.ru x1 x2 x3 x4
x1 x2       x x
Минимизация неполностью определенных переключательных функций - student2.ru x        
Минимизация неполностью определенных переключательных функций - student2.ru     x x  
Минимизация неполностью определенных переключательных функций - student2.ru x   x    
Минимизация неполностью определенных переключательных функций - student2.ru   x      
Минимизация неполностью определенных переключательных функций - student2.ru   x      

Импликанта x1x2 обязательно должна входить в минимальную ДНФ, так как только она поглощает конституенту x1x2x3x4. Импликанты x1x2 и Минимизация неполностью определенных переключательных функций - student2.ru сов­мест­но накрывают все конституенты, кроме Минимизация неполностью определенных переключательных функций - student2.ru ; последняя может быть накрыта импликантами Минимизация неполностью определенных переключательных функций - student2.ru или Минимизация неполностью определенных переключательных функций - student2.ru . Поэтому минимальные ДНФ функции f(x1, x2, x3, x4) будут:

Минимизация неполностью определенных переключательных функций - student2.ru

Минимизация неполностью определенных переключательных функций - student2.ru

Пример 2.12. Найти минимальную ДНФ функции f(x1, x2, x3, x4), экви­валент­ная функция j0(x1, x2, x3, x4) которой имеет вид

Минимизация неполностью определенных переключательных функций - student2.ru

а комбинации Минимизация неполностью определенных переключательных функций - student2.ru являются запрещен­ными.

Эквивалентную функцию j1(x1, x2, …, xn) можно получить, добавив к СДНФ функции j1(x1, x2, …, xn) запрещенные комбинации переменных:

Минимизация неполностью определенных переключательных функций - student2.ru

Проведя операции неполного склеивания и поглощения, найдем простые импли­кан­ты функции j1(x1, x2, x3, x4): x1x2x3, x1x3x4, Минимизация неполностью определенных переключательных функций - student2.ru , Минимизация неполностью определенных переключательных функций - student2.ru . Импликантная матрица функции f(x1, x2, x3, x4) имеет вид (табл. 2.8).

Таблица 2.8

Импликантная матрица

Импликанты Конституенты
Минимизация неполностью определенных переключательных функций - student2.ru Минимизация неполностью определенных переключательных функций - student2.ru Минимизация неполностью определенных переключательных функций - student2.ru Минимизация неполностью определенных переключательных функций - student2.ru Минимизация неполностью определенных переключательных функций - student2.ru
Минимизация неполностью определенных переключательных функций - student2.ru       x x
Минимизация неполностью определенных переключательных функций - student2.ru   х х   х
x1x2x3 х        
x1x3x4          

Функция f(x1, x2, x3, x4) имеет единственную минимальную ДНФ:

Минимизация неполностью определенных переключательных функций - student2.ru

В нижней строке импликантной матрицы крестики отсутствуют и, сле­до­вательно, импликанта 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).

Пример 2.13. Найти минимальную КНФ функции, заданной таблицей (табл. 2.9).

Таблица 2.9

Таблица истинности неполностью определенной ПФ

x1
x2
x3
x4
f(x1, x2, x3, x4)      

СКНФ эквивалентной функции j1(x1, x2, x3, x4):

Минимизация неполностью определенных переключательных функций - student2.ru Минимизация неполностью определенных переключательных функций - student2.ru

СКНФ функции Минимизация неполностью определенных переключательных функций - student2.ru

Минимизация неполностью определенных переключательных функций - student2.ru

Минимизация неполностью определенных переключательных функций - student2.ru

Сокращенная КНФ функции j0(x1, x2, x3, x4):

Минимизация неполностью определенных переключательных функций - student2.ru

Импликантная матрица имеет вид (табл. 2.10).

Таблица 2.10

Импликантная матрица

Импли- канты Минимизация неполностью определенных переключательных функций - student2.ru Минимизация неполностью определенных переключательных функций - student2.ru Минимизация неполностью определенных переключательных функций - student2.ru Минимизация неполностью определенных переключательных функций - student2.ru Минимизация неполностью определенных переключательных функций - student2.ru
Минимизация неполностью определенных переключательных функций - student2.ru х х х    
Минимизация неполностью определенных переключательных функций - student2.ru х     х х
Минимизация неполностью определенных переключательных функций - student2.ru х        

Минимальная КНФ функции f(x1, x2, x3, x4):

Минимизация неполностью определенных переключательных функций - student2.ru

Рассмотренная функция имеет четыре минимальные ДНФ:

Минимизация неполностью определенных переключательных функций - student2.ru

Минимизация неполностью определенных переключательных функций - student2.ru

Минимизация неполностью определенных переключательных функций - student2.ru

Минимизация неполностью определенных переключательных функций - student2.ru

В этих формах больше букв, чем в минимальной КНФ.

ПРАКТИЧЕСКИЙ РАЗДЕЛ

Наши рекомендации