Судопланов. Судоплатов С.В., Овчинникова Е.В. Дискретная математика 2016. Редакционная коллегия серии учебники нгту
 Скачать 2.01 Mb.
|
|
f (x 1 , x 2 , x 3 , x 4 , x 5 ), показанную на рис. 6.16. Так как имеются только два различных столбца, то существует простая дизъюнктивная декомпозиция функции f в форме f = F (g(x 1 , x 2 , x 3 ), x 4 , x 5 ). Для нахождения функции g(x 1 , x 2 , x 3 ) 212 Глава 6. АЛГЕБРА ЛОГИКИ 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 0 0 0 1 1 0 0 x 4 x 2 x 5 x 3 x 3 x 1 Рис. 6.16 выберем строку карты, в ячейках которой содержатся как нули, так и едини- цы, например 4-ю строку (рис. 6.17). По выбранной строке составим функ- цию g с соответствующей таблицей истинности, показанной на рис. 6.18: g = x 1 x 2 x 3 ∨ x 1 x 2 x 3 ∨ x 1 x 2 x 3 Приведя полученную формулу к минимальной ДНФ, получаем g = = x 1 x 2 x 3 ∨ x 1 x 2 . Теперь для нахождения функции F заметим, что по выбору строки карты декомпозиции имеем g = 0 для столбца (1 1 1 0) T и g = 1 для столбца (1 0 0 1) T . Таким образом, мы получаем карту Карно функции F от переменных g, x 4 , x 5 в виде, изображенном на рис. 6.19. По карте Карно находим минимальную ДНФ функции F (g, x 4 , x 5 ) = gx 5 ∨ x 4 x 5 ∨ gx 5 . ¤ Если все столбцы карты декомпозиции идентичны, то функция не за- висит от переменных множества A 1 и декомпозиция является тривиальной. Если карта содержит два различных столбца, но комбинации цифр в них содержат либо все нули, либо все единицы, то функция не зависит от пере- менных множества A 2 1 0 0 0 1 1 0 0 x 2 x 3 x 3 x 1 Рис. 6.17 6.10. ФУНКЦИОНАЛЬНАЯ ДЕКОМПОЗИЦИЯ 213 x 1 0 0 0 0 1 1 1 1 x 2 0 0 1 1 0 0 1 1 x 3 0 1 0 1 0 1 0 1 g 1 0 0 0 1 1 0 0 1 1 1 0 1 1 0 0 x 4 x 5 g Рис. 6.18 Рис. 6.19 3. Сложные дизъюнктивные декомпозиции Дизъюнктивная декомпозиция, не являющаяся простой, называется сложной. Рассмотрим два вида сложных декомпозиций: итеративную и мно- жественную. Итеративная функциональная декомпозиция представлена в следующей общей форме: f (X) = F (g m (. . . g 3 (g 2 (g 1 (A 1 ), A 2 ), A 3 ), . . . , A m ) (6.2) и основана на повторении простой дизъюнктивной декомпозиции по пере- менным A 1 , A 2 , . . ., A m Множественная функциональная декомпозиция имеет вид f (X) = F (g 1 (A 1 ), g 2 (A 2 ), . . . , g m (A m )). (6.3) Связь между сложными и простыми дизъюнктивными декомпозициями дается следующими теоремами. Теорема 6.10.2. Для данной булевой функции f (X) тогда и только то- гда существует итеративная дизъюнктивная декомпозиция вида (6.2), ко- гда существует простая дизъюнктивная декомпозиция вида f (X) = F m (g 0 m (A 1 , A 2 , . . . , A m−1 ), A m ), простая дизъюнктивная декомпозиция функции g 0 m g 0 m = F m−1 (g 0 m−1 (A 1 , A 2 , . . . , A m−2 ), A m−1 ), простая дизъюнктивная декомпозиция функции g 0 m−1 и т. д. до m = 1. При этом F = F m , g m = F m−1 , g m−1 = F m−2 , . . . , g 2 = F 1 , g 1 = g 0 1 . ¤ 214 Глава 6. АЛГЕБРА ЛОГИКИ 0 0 0 1 1 1 0 0 0 1 1 1 0 0 1 1 x 4 x 2 x 3 x 3 x 1 1 1 1 1 1 1 0 0 x 3 x 2 x 1 а б Рис. 6.20 Теорема 6.10.3. Для данной булевой функции f (X) тогда и только то- гда существует множественная дизъюнктивная декомпозиция вида (6.3), когда существуют простые дизъюнктивные декомпозиции вида f (X) = F 1 (g 1 (A 1 ), A 2 , A 3 , . . . , A m ), f (X) = F 2 (g 2 (A 2 ), A 1 , A 3 , . . . , A m ), f (X) = F m (g m (A m ), A 1 , A 2 , . . . , A m−1 ). ¤ Пример 6.10.5. Пусть f = x 1 x 2 x 3 x 4 ∨x 1 x 2 x 3 x 4 ∨x 3 x 4 ∨ ∨ x 1 x 2 x 4 ∨x 1 x 2 x 4 Из карты декомпозиции, показанной на рис. 6.20а, получим простую дизъюнктивную декомпозицию f = F (g 1 (x 1 , x 2 , x 3 ), x 4 ), где g 1 = x 3 ∨ x 1 x 2 ∨ ∨x 1 x 2 и F = g 1 x 4 ∨ g 1 x 4 1 1 1 1 1 1 x 1 x 2 x 3 x 4 Рис. 6.21 Теперь рассмотрим функцию g 1 . Из карты, приведенной на рис. 6.20б, получим простую дизъ- юнктивную декомпозицию g 1 = F 1 (g 2 (x 1 , x 2 ), x 3 ), где g 2 = x 1 x 2 ∨ x 1 x 2 и F 1 = g 2 ∨ x 3 Эти две простые дизъюнктивные декомпозиции дают вместе итеративную дизъюнктивную декомпо- зицию f = F (F 1 (g 2 (x 1 , x 2 ), x 3 ), x 4 ). ¤ Пример 6.10.6. Пусть f = x 1 x 2 x 3 ∨ x 1 x 2 x 4 ∨ ∨ x 1 x 2 x 3 ∨ x 1 x 2 x 4 . Карта декомпозиции, показанная на рис. 6.21, имеет две различные строки и два различных столбца и, следовательно, дает следую- щие две декомпозиции функции f : f = F 1 (g 1 (x 1 , x 2 ), x 3 , x 4 ), где g 1 (x 1 , x 2 ) = x 1 x 2 ∨ x 1 x 2 , F 1 (g 1 , x 3 , x 4 ) = g 1 x 3 ∨ g 1 x 4 , f = F 2 (g 2 (x 3 , x 4 ), x 1 , x 2 ), 6.11. ЛОГИЧЕСКИЕ СЕТИ 215 где g 2 = x 3 ∨x 4 , F 2 = g 2 x 1 x 2 ∨g 2 x 1 x 2 . В соответствии с теоремой 6.10.3 су- ществует множественная дизъюнктивная декомпозиция f = F (g 1 (x 1 , x 2 ), g 2 (x 3 , x 4 )). Для нахождения функции F составим ее таблицу истинности, определя- емую всевозможными комбинациями значений g 1 и g 2 и соответствующими значениями функции f : g 1 (x 1 , x 2 ) g 2 (x 3 , x 4 ) F 0 0 0 0 1 0 1 0 0 1 1 1 Из таблицы истинности находим, что F = g 1 · g 2 . ¤ § 6.11. Логические сети 1. Определение и реализация булевых функций Мультиграф G = hM, U, Ri, в котором выделено k вершин (полюсов), на- зывается k-полюсной сетью. Сеть G, задаваемая неориентированным муль- тиграфом с k полюсами, в которой каждое ребро помечено буквой из алфа- вита X = {x 1 , x 2 , . . . , x n , x 1 , x 2 , . . . , x n }, называется k-полюсной контактной схемой. На рис. 6.22 приведен пример контактной схемы с двумя полюса- ми a 1 и a 6 • • • • • • HH HH HH ©© ©© ©© ````` ````` ````` Q Q Q Q Q Q Q µ´ ¶³ µ´ ¶³ a 1 a 2 a 3 a 4 a 5 a 6 x 1 x 2 x 3 x 1 x 2 x 1 x 2 x 3 x 3 Рис. 6.22 216 Глава 6. АЛГЕБРА ЛОГИКИ Если в (k + 1)-полюсной схеме S один полюс выделен (он называется входным), а остальные полюса (выходные) равноправны, то S называется (1, k)-полюсником. Таким образом, если в приведенной на рис. 6.22 двухпо- люсной схеме рассматривать, например, полюс a 1 как входной, а полюс a 6 как выходной, то получаем (1, 1)-полюсник . Ребра контактной схемы называются контактами. Контакт, соответ- ствующий логической переменной x i , называется замыкающим и обозна- чается через ∅ −c b− ∅ . Замыкающий контакт пропускает ток при x i = 1. Кон- такт, соответствующий литере x i , называется размыкающим и обозначается как ∅ −c b − ∅ . Через него ток проходит при x i = 0. Таким образом, значение 1 интерпретируется как состояние переключателя “ток проходит”, а 0 — “ток не проходит”. Функции x i ∧ x j соответствует последовательное соединение контактов ∅ −c b−c b− ∅ , а функции x i ∨ x j — параллельное соединение кон- тактов a− c b − − c b −` Нетрудно заметить, что схеме, показанной на рис. 6.22, соответствуют электрическая схема, приведенная на рис. 6.23, а также схема контактов, изображенная на рис. 6.24. На последнем рисунке показаны контакты, зави- сящие от значений переменных x 1 , x 2 , x 3 , а также схема соединений контак- тов. Пусть a, b — полюса контактной схемы Σ, [a; b] — некоторая цепь из a в b, K [a;b] — конъюнкция литер, приписанных ребрам цепи [a; b]. Функция f a,b (X), определяемая формулой f a,b (X) = W [a;b] K [a;b] , в которой дизъюнкция берется по всем простым цепям схемы, соединяющим полюса a и b, назы- вается функцией проводимости между полюсами a и b схемы Σ. Говорят, • • x 1 x 2 x 1 • • x 1 x 2 x 2 • x 3 - x 3 x 3 • Рис. 6.23 6.11. ЛОГИЧЕСКИЕ СЕТИ 217 • • • ³³ ³³ • • • ³³ ³³ • a 1 a 6 x 1 x 2 x 3 Рис. 6.24 что функция g(X) реализуется (1, k)-полюсником, если существует такой выходной полюс b i , что f a,b i (X) = g(X), где a — входной полюс. (1, 1)- Полюсники называются эквивалентными, если они реализуют одну и ту же булеву функцию. Сложностью (1, 1)-полюсника называется число контак- тов. (1, 1)-полюсник, имеющий наименьшую сложность среди эквивалент- ных ему схем, называется минимальным. Сложность минимального (1, 1)- полюсника, реализующего функцию f , называется сложностью функции f в классе (1, 1)-полюсников и обозначается через L π (f ). Заметим, что задача нахождения минимального (1, 1)-полюсника среди эквивалентных данному (1, 1)-полюснику Σ равносильна нахождению сре- ди функций, реализуемых схемой Σ, функции, имеющей наименьшее чис- ло вхождений переменных. Действительно, функцию, реализуемую (1, 1)- полюсником, нетрудно представить в виде формулы, которая строится из ли- тер в соответствии с контактной схемой и имеет ровно столько вхожде- ний переменных, сколько контактов имеет схема. Например, изображенной на рис. 6.23 схеме соответствует булева функция f (x 1 , x 2 , x 3 ) = (x 1 ∨ x 2 ) · ((x 1 ∨ x 2 ) · x 3 ∨ x 3 ) ∨ x 1 x 2 x 3 . (6.4) Таким образом, задача нахождения минимального (1, 1)-полюсника сводится к минимизации соответствующей булевой функции. Эффективное уменьшение числа контактов достигается с помощью на- хождения минимальной ДНФ булевой функции. 218 Глава 6. АЛГЕБРА ЛОГИКИ • x 1 x 2 x 1 x 2 x 3 x 3 x 3 - • • x 1 x 2 x 1 x 2 • x 3 x 3 - • а б Рис. 6.25 Найдем минимальную ДНФ функции (6.4), реализуемой схемой рис. 6.23. Придавая логическим переменным x 1 , x 2 , x 3 всевозможные значения, по схе- ме или формуле (6.4) получаем таблицу истинности: x 1 0 0 0 0 1 1 1 1 x 2 0 0 1 1 0 0 1 1 x 3 0 1 0 1 0 1 0 1 f 1 0 1 0 1 0 0 1 , по которой определим совершенную ДНФ: x 1 x 2 x 3 ∨ x 1 x 2 x 3 ∨ x 1 x 2 x 3 ∨ x 1 x 2 x 3 Используя один из методов нахождения минимальной ДНФ, получаем фор- мулу x 1 x 3 ∨ x 2 x 3 ∨ x 1 x 2 x 3 , эквивалентную формуле (6.4) и соответствующую схеме, состоящей из семи контактов (рис. 6.25а). Отметим, что схема, изображенная на рис. 6.25а, допускает упрощение, соответствующее формуле (x 1 ∨ x 2 )x 3 ∨ x 1 x 2 x 3 , которое приведено на рис. 6.25б и является минимальной схемой. Сложность минимальной схемы рав- на 6: L π (f ) = 6. 2. Схемы из функциональных элементов Ориентированная бесконтурная сеть, в которой полюса делятся на вход- ные (входы) и выходные (выходы), называется схемой из функциональных элементов. Входные полюса помечаются символами переменных, а каждая вершина, отличная от входного полюса, — некоторым функциональным символом. При этом должны выполняться следующие условия: • если a — входной полюс, то полустепень захода вершины a равна нулю: deg − (a) = 0; • если вершина a не является полюсом и помечена n-местным функцио- нальным символом f , то deg − (a) = n и дуги, входящие в a, перенумерованы от 1 до n. Функциональным элементом называется всякий подмультиграф схемы, состоящий из невходного полюса a, помеченного соответствующим симво- лом f , и вершины, из которых исходят дуги в вершину a. 6.11. ЛОГИЧЕСКИЕ СЕТИ 219 Пример 6.11.1. На рис. 6.26а представлена схема из функциональ- ных элементов. Здесь входные символы помечены символами перемен- ных x 1 , x 2 , x 3 ; ¬ — одноместный функциональный символ, соответствующий операции отрицания; & — двухместный символ, соответствующий операции конъюнкции; f 3 — некоторый двухместный символ; f 1 , f 2 , f 4 — некоторые трехместные символы. Вершины, помеченные символами |