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

200
Глава 6. АЛГЕБРА ЛОГИКИ
x
1
x
2
x
3
x
4 1
1 1
1 1
1 1
1 1
'
&
$
%
³
´
¶ ³
µ ´
¶
µ
³
´
¶
µ
³
´
¶
µ
³
´
¶
µ
³
´
¶
µ
Рис. 6.8
Пример 6.7.2. Простые импликанты для карты Карно, приведенной на рис. 6.7, равны x
1
x
2
, x
1
x
2
x
3
, x
1
x
3
Пример 6.7.3. На рис. 6.8 показана карта Карно, простые импликанты которой имеют вид x
2
x
3
x
4
, x
1
x
2
x
3
, x
1
x
3
x
4
, x
1
x
2
x
4
, x
2
x
3
x
4
, x
1
x
2
x
4
, x
1
x
3
. Заме- тим, что импликанты x
1
x
2
x
3
, x
1
x
2
x
3
, x
1
x
3
x
4
и x
1
x
3
x
4
не являются простыми,
так как образуемые ими 1-кубы содержатся в 2-кубе x
1
x
3
. ¤
После нахождения простых импликант задача по-
x
1
x
2
x
3
–
1
–
–
1
Рис. 6.9
строения минимальной ДНФ сводится к изучению матрицы Квайна, как показано в § 6.6. При нагляд- ном размещении простых импликант в карте Кар- но удается непосредственно находить минимальную
ДНФ, выбирая те простые импликанты, которые по- крывают все единицы и имеют наименьшее возмож- ное число вхождений переменных. Так, минималь- ной ДНФ для функции, изображенной на рис. 6.8, является формула
x
2
x
3
x
4
∨ x
1
x
3
x
4
∨ x
1
x
2
x
4
∨ x
1
x
3
Карты Карно применимы и для не всюду определенных функций. В этом случае выделяются максимальные k-кубы, покрывающие ненулевые ячейки и содержащие хотя бы одну единицу.
Пример 6.7.4. На рис. 6.9 представлена карта Карно для частичной функции f , зависящей от трех переменных x
1
, x
2
, x
3
. Сокращенная ДНФ
имеет вид x
2
x
3
∨ x
1
x
3
∨ x
1
x
2
∨ x
2
x
3
, а МДНФ — x
2
x
3
∨ x
1
x
3
∨ x
2
x
3
или
x
2
x
3
∨ x
1
x
2
∨ x
2
x
3
. ¤

6.8. ПРИНЦИП ДВОЙСТВЕННОСТИ ДЛЯ БУЛЕВЫХ ФУНКЦИЙ
201
§ 6.8.
Принцип двойственности для булевых функций
В § 2.6 мы говорили о двойственности в классе булевых алгебр, кото- рая проявляется в том, что на множестве B со структурой булевой алгеб- ры B можно ввести структуру двойственной алгебры B
+
, в которой роль операции ∧ играет ∨, роль операции ∨ — ∧, а в качестве нуля (единицы)
используется 1 (соответственно 0). При этом между алгебрами B и B
+
име- ется изоморфизм ϕ: x 7→ x. В этом параграфе мы рассмотрим соответствие булевых функций при изоморфизме ϕ.
Функция f
+
(x
1
, . . . , x
n
) называется двойственной по отношению к функ- ции f (x
1
, . . . , x
n
), если f
+
(x
1
, . . . , x
n
) = f (x
1
, . . . , x
n
).
Двойственная функция получается из исходной при замене значений всех переменных, а также значений функции на противоположные, т. е. в таблице истинности нужно заменить 0 на 1, а 1 на 0.
Пример 6.8.1. Двойственной к функции x ∧ y является функция, соот- ветствующая формуле ¬(x ∧ y), т. е. ¬¬(x ∨ y) или x ∨ y: (x ∧ y)
+
= x ∨ y.
Аналогично (x ∨ y)
+
= x ∧ y, (x)
+
= x. ¤
Принцип двойственности. Если
f (x
1
, . . . , x
n
) = g(h
1
(x
1
, . . . , x
n
), . . . , h
m
(x
1
, . . . , x
n
)),
то
f
+
(x
1
, . . . , x
n
) = g
+
(h
+
1
(x
1
, . . . , x
n
), . . . , h
+
m
(x
1
, . . . , x
n
)).
Таким образом, функция, двойственная суперпозиции функций, есть со- ответствующая суперпозиция двойственных функций.
Принцип двойственности удобен при нахождении двойственных функ- ций, представленных формулами, содержащими лишь конъюнкции, дизъ- юнкции и отрицания. В этом случае в исходной формуле конъюнкции заме- няются на дизъюнкции, а дизъюнкции — на конъюнкции. Таким образом,
ДНФ соответствует КНФ, КНФ — ДНФ, СДНФ — СКНФ, СКНФ — СДНФ.
Пример 6.8.2. (xy ∨ x z ∨ xyz)
+
= (x ∨ y) ∧ (x ∨ z) ∧ (x ∨ y ∨ z). ¤
Отметим, что если формула ϕ эквивалентна формуле ψ: ϕ ∼ ψ, то
ϕ
+
∼ ψ
+
Функция f (x
1
, . . . , x
n
) называется самодвойственной, если
f
+
(x
1
, . . . , x
n
) = f (x
1
, . . . , x
n
).

202
Глава 6. АЛГЕБРА ЛОГИКИ
Пример 6.8.3. Покажем, что формула ϕ = xy ∨ xz ∨ yz задает самодвой- ственную функцию.
С этой целью убедимся, что на всех противоположных наборах значений переменных (δ
1
, δ
2
, δ
3
) и (1 − δ
1
, 1 − δ
2
, 1 − δ
3
) формула принимает противо- положные значения. Действительно, составив таблицу истинности
x 0 0 0 0 1 1 1 1
y
0 0 1 1 0 0 1 1
z
0 1 0 1 0 1 0 1
ϕ 0 0 0 1 0 1 1 1
,
получаем ϕ(0, 0, 0) = ϕ(1, 1, 1), ϕ(0, 0, 1) = ϕ(1, 1, 0), ϕ(0, 1, 0) = ϕ(1, 0, 1),
ϕ(0, 1, 1) = ϕ(1, 0, 0). ¤
§ 6.9.
Полные системы булевых функций
Как мы уже знаем из теоремы о функциональной полноте, любая булева функция представима в виде формулы, содержащей лишь операции ∧, ∨, ¬,
т. е. в виде терма сигнатуры {∧, ∨, ¬}. В этом параграфе будет дано описание сигнатур, позволяющих получать любые булевы функции.
Система булевых функций F = {f
1
, f
2
, . . . , f
n
} называется полной, если любая булева функция представима в виде терма сигнатуры {f
1
, f
2
, . . . , f
n
},
т. е. в виде суперпозиций функций из F.
Из сказанного выше ясно, что система {∧, ∨, ¬} является полной. Ответ на вопрос о полноте произвольной системы F дает теорема Поста, форму- лируемая ниже.
Введем определение классов Поста.
1. Класс P
0
— это класс булевых функций, сохраняющих нуль, т. е. функ- ций f (x
1
, . . . , x
n
), для которых f (0, 0, . . . , 0) = 0:
P
0
= {f | f (0, 0, . . . , 0) = 0}.
2. Класс P
1
— это класс булевых функций, сохраняющих единицу, т. е.
функций f (x
1
, . . . , x
n
), для которых f (1, 1, . . ., 1) = 1:
P
1
= {f | f (1, 1, . . . , 1) = 1}.
3. Класс S — это класс самодвойственных функций:
S = {f | f — самодвойственная функция}.

6.9. ПОЛНЫЕ СИСТЕМЫ БУЛЕВЫХ ФУНКЦИЙ
203 4. Класс M
— это класс монотонных функций. Булева функ- ция f (x
1
, . . . , x
n
) называется монотонной, если для любых наборов нулей и единиц (α
1
, . . . , α
n
) и (β
1
, . . . , β
n
) из условий α
1 6 β
1
, . . ., α
n
6 β
n
следует
f (α
1
, . . . , α
n
) 6 f (β
1
, . . . , β
n
). Таким образом,
M = {f | f — монотонная функция}.
5. Класс L — это класс линейных функций. Булева функция f (x
1
, . . . , x
n
)
называется линейной, если в булевом кольце h{0, 1}; ⊕, ¯i функция f пред- ставима в виде f (x
1
, . . . , x
n
) = c
0
⊕ c
1
x
1
⊕ c
2
x
2
⊕ . . . ⊕ c
n
x
n
, где c
0
, c
1
, c
2
,
. . ., c
n
∈ {0, 1}.
Коэффициенты c
0
, c
1
, . . ., c
n
линейной функции определяются из следу- ющих соотношений:
c
0
= f (0, 0, . . . , 0), c
0
⊕ c
1
= f (1, 0, . . . , 0),
c
0
⊕ c
2
= f (0, 1, . . . , 0), . . . , c
0
⊕ c
n
= f (0, 0, . . . , 0, 1),
т. е.
c
0
= f (0, 0, . . . , 0),
c
1
= c
0
⊕ f (1, 0, . . . , 0) , . . . , c
n
= c
0
⊕ f (0, 0, . . . , 1).
(6.1)
Таким образом, проверка линейности сводится к нахождению коэффи- циентов c
i
по формулам (6.1) и сопоставлению таблиц истинности данной формулы f (x
1
, . . . , x
n
) и полученной формулы c
0
⊕ c
1
x
1
⊕ . . . ⊕ c
n
x
n
Пример 6.9.1. Проверим, является ли линейной функция x ∨ y. Имеем
c
0
= 0 ∨ 0 = 0, c
1
= 0 ⊕ (1 ∨ 0) = 1, c
2
= 0 ⊕ (0 ∨ 1) = 1. Таким образом,
c
0
⊕ c
1
x ⊕ c
2
y = x ⊕ y. Сопоставляя таблицы истинности формул x ∨ y и x ⊕ y,
убеждаемся, что они не совпадают. Вывод: функция x ∨ y нелинейна. ¤
Линейность функции можно также определить с помощью следующей теоремы.
Теорема 6.9.1 (теорема
Жегалкина).
Всякая
булева
функция
f (x
1
, . . . , x
n
)
представима
полиномом
Жегалкина,
т.
е.
в
виде
f (x
1
, . . . , x
n
) =
L
(i
1
,...,i
k
)
x
i
1
x
i
2
. . . x
i
k
⊕ c, где в каждом наборе (i
1
, . . . , i
k
)
все i
j
различны, а суммирование ведется по некоторому множеству
таких несовпадающих наборов. Представление булевой функции в виде
полинома Жегалкина единственно с точностью до порядка слагаемых.

204
Глава 6. АЛГЕБРА ЛОГИКИ
Полином Жегалкина называется нелинейным (линейным), если он (не)
содержит произведения различных переменных.
Таким образом, линейность булевой функции равносильна линейности соответствующего полинома Жегалкина.
Для получения полинома Жегалкина булевой функции, находящейся в СДНФ, используются аксиомы булевой алгебры, аксиомы булева кольца
h{0, 1}; ⊕, ¯i и равенства, выражающие операции ∧, ∨ и ¬ через операции этого булева кольца: x∨y = x⊕y ⊕xy, x(y ⊕z) = xy ⊕xz, x = x⊕1, x⊕0 = x,
x ⊕ x = 1, xx = 0 и т. д.
Пример 6.9.2. Определим, будет ли линейной функция f (x, y, z) = x yz∨
∨ xyz ∨ xy z.
Имеем f (x, y, z) = (xyz ⊕xyz ⊕xyzxyz)∨xy z = (xyz⊕ xyz)∨xy z = xyz⊕
⊕xyz ⊕ xy z ⊕ (x yz ⊕ xyz)xy z = x yz ⊕ xyz⊕ xy z⊕ 0 = xz(y ⊕ y) ⊕ xy z =
= xz · 1 ⊕ xy z = (x ⊕ 1)z ⊕ x(y ⊕ 1)(z ⊕ 1) = xz⊕ 1· z⊕ xyz ⊕ xz ⊕ xy ⊕ x =
= x ⊕ z ⊕ xy ⊕ xyz. Полученный полином Жегалкина является нелинейным,
и, следовательно, функция f также нелинейна. ¤
Заметим, что если в эквивалентности ϕ ∨ ψ ∼ ϕ ⊕ ψ ⊕ ϕ · ψ формулы ϕ
и ψ являются различными конституентами единицы, то их произведение ϕ·ψ
равно 0, и тогда ϕ ∨ ψ ∼ ϕ ⊕ ψ. Следовательно, для получения полинома
Жегалкина из СДНФ можно сразу заменить ∨ на ⊕.
Отметим, что каждый класс Поста замкнут относительно операций заме- ны переменных и суперпозиции, т. е. с помощью этих операций из функций,
принадлежащих данному классу, можно получить только функции из этого же класса.
Пример 6.9.3. Определим, к каким классам Поста относится булева функция f (x, y) = x | y.
Так как f (0, 0) = 1, а f (1, 1) = 0, то f (x, y) /
∈ P
0
и f (x, y) /
∈ P
1
. Поскольку
f (1, 0) 6= f (0, 1), то f (x, y) /
∈ S. Так как f (0, 0) > f (1, 1), то f (x, y) /
∈ M.
Полином Жегалкина для функции f (x, y) = xy имеет вид 1 ⊕ xy в силу равенства x = 1 ⊕ x. Поэтому данная функция нелинейна. Таким образом,
можно составить следующую таблицу
Функция
Классы
P
0
P
1
S
M
L
x
|
y
нет нет нет нет нет

6.10. ФУНКЦИОНАЛЬНАЯ ДЕКОМПОЗИЦИЯ
205
Теорема 6.9.2 (теорема Поста). Система F булевых функций тогда
и только тогда является полной, когда для каждого из классов P
0
, P
1
, S,
M, L в системе F найдется функция, не принадлежащая этому классу. ¤
В силу теоремы Поста функция x | y образует полную систему, т. е.
с помощью штриха Шеффера можно получить любую булеву функцию.
В частности, x ∼ x | x, x ∧ y ∼ ¬¬(x ∧ y) ∼ ¬(x | y) ∼ (x | y) | (x | y).
Система булевых функций F называется базисом, если она полна, а для любой функции f ∈ F система F \ {f } неполна.
Теорема 6.9.3. Каждый базис содержит не более четырех булевых
функций.
Доказательство. Предположим, что существует базис F, состоящий более чем из четырех функций. По теореме Поста тогда получаем, что F
состоит ровно из пяти функций, каждая из которых не принадлежит ровно одному классу Поста. Пусть f — функция из F, не принадлежащая клас- су P
0
. Тогда, с одной стороны, f (0, 0, . . . , 0) = 1, а с другой — из f ∈ P
1
следует, что f (1, 1, . . . , 1) = 1. Это означает, что f не является самодвой- ственной функцией, что противоречит предположению. ¤
Пример 6.9.4. Следующие системы булевых функций являются бази- сами: {∧, ¬}, {∨, ¬}, {→, ¬}, {↓}, {|}, {↔, ∨, 0}, {⊕, ∧, ↔}. ¤
Широкий набор базисов открывает большие возможности при решении задач минимизации схем устройств дискретного действия, поскольку из ба- зисных схем с помощью суперпозиций можно составить схему, соответству- ющую любой булевой функции.
§ 6.10.
Функциональная декомпозиция
1.
Определение и примеры
Булева функция f (x
1
, . . ., x
n
) называется разложимой, если она может быть представлена в виде суперпозиции функций g
1
, g
2
, . . . , g
k
(k < n)
и F , каждая из которых имеет менее n переменных: f (x
1
, x
2
, . . ., x
n
) =
= F (g
1
, . . . , g
k
). При этом функция f может быть реализована с помощью устройств, соответствующих функциям g
1
, g
2
, . . ., g
k
и F , как показано на рис. 6.10. Разложение функции f в виде суперпозиции g
1
, g
2
, . . ., g
k
и F

206
Глава 6. АЛГЕБРА ЛОГИКИ
-
•
-
•
x
1
x
n
•
-
-
•
-
-
g
1
g
2
g
k
-
-
-
F
-
f
Рис. 6.10
называется декомпозицией функции f , а соответствующая схема, показан- ная на рис. 6.10, — декомпозиционной реализацией функции f .
В дальнейшем будем использовать следующие обозначения логических устройств. Устройство, соответствующее функции x, будем называть ин-
вертором и обозначать, как показано на рис. 6.11а, устройство, соответ- ствующее функции f (x
1
, . . . , x
i−1
, x
i
, x
i+1
, . . . , x
n
), обозначим, как показано на рис. 6.11б, а устройство, соответствующее функции f (x
1
, x
2
, . . . , x
n
), —
на рис. 6.11в.
Пример 6.10.1. На рис. 6.12 показана декомпозиционная реализация функции f (x
1
, x
2
, x
3
, x
4
) = x
1
x
3
∨ (x
2
⊕ x
3
)x
4
∨ x
1
x
4
, где g
1
= x
1
x
3
, g
2
=
= (x
2
⊕ x
3
)x
4
, g
3
= x
1
x
4
, F (y
1
, y
2
, y
3
) = y
1
∨ y
2
∨ y
3
. ¤
x
©©
©
HH
H e x
e f
x
n
x
i+1
x
i
x
i−1
x
1
f
e
x
1
x
2
x
n
а
б
в
Рис. 6.11

6.10. ФУНКЦИОНАЛЬНАЯ ДЕКОМПОЗИЦИЯ
207
d
&
⊕
•
•
•
x
1
x
3
x
2
x
4
d d
&
&
W
-
f
g
1
g
2
g
3
F
Рис. 6.12
Пусть X = {x
1
, x
2
, . . . , x
n
} — множество входных переменных для функ- ции f (X) = F (g
1
(A
1
), g
2
(A
2
), . . . , g
k
(A
k
)), где A
i
— множества входных пере- менных, образующие разбиение множества X, т. е. A
i
6= ∅, A
i
∩ A
j
= ∅ для
i 6= j и A
1
∪ A
2
∪ . . . ∪ A
k
= X. Тогда декомпозиция функции f называется
дизъюнктивной. Недизъюнктивные декомпозиции называются нондизъюнк-
тивными.
Пример 6.10.2. На рис. 6.13 изображена реализация нондизъюнктив- ной декомпозиции f (x
1
, x
2
, x
3
, x
4
, x
5
) = F (g
1
(x
1
, x
2
, x
3
), g
2
(x
3
, x
4
, x
5
)). Здесь множества A
1
= {x
1
, x
2
, x
3
} и A
2
= {x
3
, x
4
, x
5
} не образуют разбиение мно- жества X = {x
1
, x
2
, x
3
, x
4
, x
5
}, поскольку A
1
∩ A
2
6= ∅. ¤
•
x
5
x
4
x
3
x
2
x
1
g
2
g
1
-
F
f
Рис. 6.13