Файл: Учебник издание шестое Рекомендовано Министерством образования и науки Российской Федерации в качестве учебника для студентов высших технических учебных заведений.pdf

208
Глава 6. АЛГЕБРА ЛОГИКИ
-
x
5
x
4
x
3
x
2
x
1
F
f
g
Рис. 6.14
2.
Простая дизъюнктивная декомпозиция
Дизъюнктивная декомпозиция функции f (x
1
, x
2
, . . . , x
n
) вида
f (x
1
, x
2
, . . . , x
n
) = F (g(A
1
), A
2
)
называется простой.
Пример 6.10.3. На рис. 6.14 изображена реализация простой дизъюнк- тивной декомпозиции f (x
1
, x
2
, x
3
, x
4
, x
5
) = F (g(x
1
, x
2
, x
3
), x
4
, x
5
). ¤
Чтобы определить свойства булевых функций, ко-
· · ·
· · ·
A
1
A
2
Рис. 6.15
торые позволяют получать простые дизъюнктивные де- композиции в виде F (g(A
1
), A
2
), рассмотрим карту Кар- но функции f (рис. 6.15), где строки соответствуют пере- менным множества A
2
, а столбцы — переменным множе- ства A
1
(например, на рис. 6.6а изображена карта Карно с A
1
= {x
1
, x
2
} и A
2
= {x
3
}). Построенная таким образом карта Карно называется картой декомпозиции для пары
(A
1
, A
2
).
Теорема 6.10.1. Булева функция f (x
1
, x
2
, . . . , x
n
) тогда и только
тогда имеет простую дизъюнктивную декомпозицию в форме f (X) =
= F (g(A
1
), A
2
), когда карта декомпозиции функции f для пары (A
1
, A
2
)
содержит не более двух различных столбцов. ¤
Пример 6.10.4. Рассмотрим карту декомпозиции функции 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
)

6.10. ФУНКЦИОНАЛЬНАЯ ДЕКОМПОЗИЦИЯ
209 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

210
Глава 6. АЛГЕБРА ЛОГИКИ
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
. ¤

6.10. ФУНКЦИОНАЛЬНАЯ ДЕКОМПОЗИЦИЯ
211 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
),

212
Глава 6. АЛГЕБРА ЛОГИКИ
где 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
QQ
µ´
¶³
µ´
¶³
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

6.11. ЛОГИЧЕСКИЕ СЕТИ
213
Если в (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

214
Глава 6. АЛГЕБРА ЛОГИКИ
•
•
•
³³
³³
•
•
•
³³
³³
•
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)-полюсника сводится к минимизации соответствующей булевой функции.
Эффективное уменьшение числа контактов достигается с помощью на- хождения минимальной ДНФ булевой функции.

6.11. ЛОГИЧЕСКИЕ СЕТИ
215
•
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.

216
Глава 6. АЛГЕБРА ЛОГИКИ
Пример 6.11.1. На рис. 6.26а представлена схема из функциональ- ных элементов. Здесь входные символы помечены символами перемен- ных x
1
, x
2
, x
3
; ¬ — одноместный функциональный символ, соответствующий операции отрицания; & — двухместный символ, соответствующий операции конъюнкции; f
3
— некоторый двухместный символ; f
1
, f
2
, f
4
— некоторые трехместные символы. Вершины, помеченные символами f
1
, f
3
и f
4
,
являются выходными полюсами. Им соответствуют термы: f
1
(x
1
, x
2
, x
3
),
f
3
(x
1
x
2
, f
1
(x
1
, x
2
, x
3
)),
f
4
(f
3
(x
1
x
2
, f
1
(x
1
, x
2
, x
3
), x
3
), x
3
, f
2
(f
1
(x
1
, x
2
, x
3
), f
1
(x
1
, x
2
, x
3
), x
3
)).
На рис. 6.26б изображен функциональный элемент, определяемый верши- ной, помеченной символом f
4
. Ему соответствует устройство, показанное на рис. 6.26в. ¤
В примере 6.11.1 продемонстрировано, что каждый вывод схемы порож- дает некоторый терм.
Говорят, что функция f реализуется схемой Σ, если существует такой выход a схемы Σ, что функция f
a
, соответствующая терму выхода a, экви- валентна функции f .
Схемы из функциональных элементов с одним выходом, у которых вход- ные полюса помечены символами x
1
, x
2
, . . ., x
n
, а вершины, отличные от вход- ных полюсов, — символами ∨, &, ¬, называются X
n
-функциональными схе-
мами. Сложностью схемы из функциональных элементов называется чис- ло ее вершин, отличных от входных полюсов. X
n
-Функциональная схема Σ,
•³
³³
³³
³³
³
³
1•
½
½
½
½
½½
>
•
¢
¢
¢
¢
¢¢¸
•
•H
HH
j
HH
H
j
­
­
­
­
­
Á
•
©©
©©
©©
*•
?
•
- H
HH
j•H
HH
j
A
A
A
A
AAU
U
-
x
3
x
2
x
1
f
4
f
3
&
¬
f
1
f
2 1
1 1
1 2
3 3
3 2
2 1
2 1
2
•
¡
¡
¡
µ
-
@
@
@
R
f
4
f
4
а
б
в
Рис. 6.26

6.11. ЛОГИЧЕСКИЕ СЕТИ
217
•
•
•
•
•
•
¬
¬
¬
•
HH
H
j
HH
H
j
©©
©
*
•
•
©©
©©
©©
*
HH
HH
HH
HH
HH
H
H
j
XXXX
XXXX
XXXX
z
-•
-•
¡
¡
¡
µ
m
∨
&
&
&
∨
x
3
x
2
x
1
Рис. 6.27
g = z
J(y
1
,y
2
,y
3
)+1
z
1
z
2
· · ·
z
8
y
3
y
2
y
1
Рис. 6.28
реализующая функцию f , называется минимальной, если всякая другая X
n
- функциональная схема, реализующая f , имеет сложность, не меньшую, чем сложность схемы Σ. Сложность минимальной схемы, реализующей функ- цию f , называется сложностью функции f в классе схем из функциональ- ных элементов и обозначается через L(f ).
Пример 6.11.2. Сложность функции f = (x
1
∨ x
2
)x
3
∨ x
1
x
2
x
3
совпадает со сложностью X
3
-функциональной схемы, изображенной на рис. 6.27, и рав- на 8: L(f ) = 8. ¤
3.
Мультиплексоры
Мультиплексором 2
m
каналов (MUX
2
m
) называется схема с m + 2
m
вхо- дами y
1
, y
2
, . . ., y
m
, z
1
, z
2
, . . ., z
2
m
и одним выходом g, в которой при
y
1
= b
1
, . . . , y
m
= b
m
выход g принимает значение g = z
J(b
1
,...,b
m
)+1
, где
J(b
1
, . . . , b
m
) = 2 0
b
1
+ 2 1
b
2
+ . . . + 2
m−1
b
m
На рис. 6.28 показан мультиплексор MUX
8