ВУЗ: Томский государственный университет систем управления и радиоэлектроники
Категория: Учебное пособие
Дисциплина: Дискретная математика
Добавлен: 28.11.2018
Просмотров: 16676
Скачиваний: 202
96
Если формула содержит только знаки дизъюнкции или только знаки
конъюнкции, то такие выражения относятся к формам первого порядка, напри-
мер:
,
F
E
C
A
+
+
+
.
F
E
C
A
Формула вида
)
(
1
C
D
AD
f
+
=
имеет второй порядок. Первый порядок
образует конъюнкция вне скобок, второй – дизъюнкция в скобках.
В формуле
)
(
2
CE
D
AD
f
+
=
первый порядок образует операция конъ-
юнкции вне скобок, второй – дизъюнкция, третий – конъюнкция в скобках.
Следовательно, эта формула имеет третий порядок.
Выражение
F
E
C
B
A
C
D
A
f
)
(
)
(
3
+
+
+
=
записано в форме четвёртого
порядка: первый – дизъюнкция между скобками, второй – конъюнкция пере-
менной F и скобочного выражения, третий – дизъюнкция в правых скобках,
четвёртый – конъюнкция в правых скобках.
Выражение
F
E
C
B
A
L
K
C
D
D
A
f
)
](
)
(
[
4
+
+
+
=
имеет пятый порядок:
первый – конъюнкция между квадратными и круглыми скобками, второй –
дизъюнкция в квадратных скобках (но не в круглых), третий – конъюнкция пе-
ременной C и выражения в круглых скобках, четвёртый – дизъюнкция в левых
круглых скобках, пятый – конъюнкция в левых круглых скобках.
Очевидно, что порядок ДНФ и КНФ не может быть выше второго. Но ес-
ли функция имеет второй порядок, то она не всегда является нормальной. При-
мерами могут служить функции Пирса (Вебба, согласно [14, с. 185]) и Шеффе-
ра, имеющие вид соответственно:
;
C
D
B
A
f
+
+
+
=
ABDC
f =
.
Это формулы второго порядка, но они не являются ни ДНФ, ни КНФ.
В настоящее время хорошо изучены только ДНФ и КНФ, имеющие боль-
шое практическое значение. Но исследователей привлекают и формы высших
порядков, так как путём повышения порядка функции, представленной в мини-
мальной ДНФ (или КНФ), число входящих в неё букв можно ещё уменьшить.
Например, в формуле
D
C
B
A
D
BC
A
D
C
B
A
D
C
B
A
f
+
+
+
=
в классе ДНФ уменьшить число букв не удаётся. В ней 16 вхождений букв.
А если порядок повысить до третьего, то число букв уменьшится в два раза:
).
)(
(
D
C
D
C
B
A
B
A
f
+
+
=
97
В связи с этим возникает вопрос о существовании алгоритма, позволяю-
щего для произвольной ДНФ найти абсолютно минимальную форму, т. е. та-
кую, в которой содержалось бы наименьшее число вхождений переменных по
сравнению с любыми другими формами. Абхъянкаром был предложен такой
алгоритм [40, с. 131], однако даже при четырёх переменных число операций m
оценивается неравенством вида
257
65536
2
2
.
m
≤ ≤
Так что алгоритм Абхъянкара имеет только теоретическое значение, а на
практике задачу уменьшения числа вхождений переменных приходится решать
в основном методом перебора.
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
Упражнения
1.
Определите порядок следующих функций:
1) f = [(AB + C)D + E]PQ;
2) f = [(A + B + C + EF)(A + B + CDE) + K + L]AB;
3) f = [(AB + C)D + E]P + [Q(R + ST) + T]M;
4) f = [(A + BC + EF)(A + B + CDE) + KL]AB;
5) f = [(ABC + AC)AB + C]B + C.
2.
Даны три функции:
;
)
(
1
CE
D
AD
f
+
=
;
)
(
)
(
2
F
E
C
A
C
D
A
f
+
+
+
=
.
)
](
)
(
[
3
F
C
B
A
L
K
C
D
D
A
f
+
+
+
=
Определить порядок следующих выражений:
1) f
1
+ f
2
+ f
3
;
2) ( f
1
+ f
2
) f
3
;
3) f
1
+ f
2
f
3
;
4) f
1
f
2
f
3
;
5) f
1
f
2
+f
1
f
3
;
6) f
1
f
2
+f
1
f
3
+ f
2
f
3
.
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
4.10 Понятие суперпозиции
Согласно [12], суперпозиция в булевой алгебре – это «подстановка одних
булевых функций вместо аргументов в другие булевы функции» [12, с. 197].
Аналогично понятие суперпозиции определяется в [11; 14; 25; 32; 33].
Операцию суперпозиции поясним на примерах. Пусть дана функция
f(A,B,C,D) = (1, 2, 3, 6, 9, 10, 11, 14, 15),
(4.29)
в аналитической записи имеющая вид (минимальная ДНФ):
.
D
B
D
C
AC
f
+
+
=
(4.30)
98
Вместо её букв можно подставлять любые булевы функции, например:
f
1
= A; f
2
= AВ + С; f
3
= A + E; f
4
= 1; f
5
= Q; f
6
= 0,
и т. д. Для определённости воспользуемся конъюнкцией ABC и выясним, изме-
нится ли функция (4.29), если в ней переменную C заменить выражением ABC.
Переменная С в (4.30) встречается два раза. В таких случаях подстановка
выполняется дважды:
.
)
(
)
(
D
B
D
ABC
ABC
A
f
+
+
=
После преобразований получаем:
.
D
B
ABC
f
+
=
Её СДНФ имеет вид:
f(A,B,C,D) = (1, 3, 9, 11, 14, 15),
что не совпадает с выражением (4.29).
Таким образом, в данном случае применение операции суперпозиции
привело к изменению заданной функции. При других же подстановках функция
может оказаться неизменной. Например, если в формуле (4.30) переменную A
заменить конъюнкцией ABC, то функция не изменится.
4.11 О неоднозначности обозначений в булевой алгебре
Символика и терминология дискретной математики в настоящее время не
являются устоявшимися. Одним и тем же понятиям авторы публикаций дают
различные названия, применяют для них различные обозначения. Одни из тер-
минов и обозначений получили большее распространение, другие – меньшее.
В данном параграфе отметим некоторые из них.
Операция дизъюнкции во многих публикациях обозначается знаком «∨»,
относящимся к символике Пеано – Рассела, а также Гильберта:
.
∨
A
B
Как показывает анализ публикаций, этот знак получил значительное рас-
пространение. Примерами могут служить источники [1; 4; 11; 14; 25; 29; 32; 38;
51]. В подобных изданиях материал излагается почти полностью с теоретиче-
ских позиций, то есть вопросы применения булевой алгебры если и упомина-
ются, то лишь вскользь на уровне третьестепенной важности. Кроме того, буле-
вы формулы, приводимые в этих публикациях, как правило, особой
сложностью не отличаются. В таких случаях безразлично, как обозначать
дизъюнкцию.
С прикладной же точки зрения, когда приходится иметь дело с большим
числом не самых простых формул, далеко не всё равно, какие применяются
99
знаки. Булева формула должна быть представлена так, чтобы её структура
схватывалась взглядом мгновенно, с наименьшими усилиями. Этим требовани-
ям полностью удовлетворяет символика Пирса (точнее Шредера – Пирса), где
для обозначения дизъюнкции применяется знак «+» [10, с. 69; 21, с. 219]. По
этой причине знак «+» принят в данном пособии. Знак «+» для обозначения
дизъюнкции применяется в публикациях [13; 15; 20; 23; 37; 48].
Конъюнкцию (логическое умножение, логическое произведение, операция
И) многие авторы обозначают знаком «∧». Но в применении этот знак не очень
удобен. Конъюнкция – «родня» арифметическому умножению двоичных чисел,
поэтому в данной книге вместо знака «∧» принято ставить точку из символики
Пирса:
,
B
A ⋅
а большей частью – не указывать никакого знака:
.
AB
B
A
B
A
=
⋅
=
∧
Инверсия, т. е. операция отрицания, в литературных источниках обозна-
чается также различными знаками. Например, в [19; 20; 45; 53] применяется
знак «~A»; в [23] – «
A′
»; в [20; 22; 24; 27; 35; 37] – «¬
A
»; в [54] – «!A».
Нормальные формы в [20, с. 207] называются строками термов.
Минтермы нередко называют конституентами единицы [1; 6; 12; 39; 40],
конституентами функции [14, с. 146], первыми совершенными формами [20,
с. 186], членами стандартной суммы [23], элементарными конъюнкциями [4],
полными правильными элементарными конъюнкциями (сокращённо ППЭК)
[38] и т. д., а макстермы – конституентами нуля [6], элементарными суммами
[15], вторыми совершенными формами [20], полными правильными элементар-
ными дизъюнкциями (сокращённо ППЭД) [38] и др.
С. К. Клини использует химическую терминологию: логические перемен-
ные называет атомами, а их дизъюнкции и конъюнкции – молекулами [22].
Проблема неоднозначности символики в булевой алгебре возникла давно.
Например, М. Фистер ещё в 1957 г. отмечал: «К сожалению, до настоящего
времени общепринятых обозначений [булевых операций] нет. Обычно каждый
автор использует свои собственные обозначения» [48, с. 58]. С тех пор прошло
60 лет, а проблема неоднозначности остаётся на том же уровне. Будет ли в
дальнейшем устранена эта неоднозначность, трудно предсказать. Но не исклю-
чено, что со временем в теоретических работах могут остаться обозначения
«∨», для дизъюнкции, и «¬», для инверсии; прикладники же, возможно, дизъ-
юнкцию будут обозначать знаком Пирса «+», а инверсию – чертой над буквой.
100
5 Минимизация ДНФ логических формул
5.1 Алгебраическое упрощение булевых формул
В предыдущей главе термин «упрощение» уже упоминался, но без его
толкования. Предполагалось, что интуитивного представления об упрощении
булева выражения вполне достаточно. Однако при освещении вопросов прак-
тического применения булевых функций такое понятие, как «упрощение»,
необходимо уточнить, так как упрощать можно по различным критериям.
Прежде всего, отметим, что многие авторы, говоря об упрощении, приме-
няют термин «минимизация булевых функций» [1; 6; 8; 12; 14; 23; 40; 48; 57].
Это не совсем корректный термин, так как если функция задана, например при
помощи таблицы истинности, где указано, на каких наборах функция равна
единице и на каких – нулю (и, возможно, не определена), то применение к ней
терминов «упрощение» и «минимизация» лишено смысла. Очевидно, что авто-
ры, когда пишут о минимизации, имеют в виду не таблицу истинности, а фор-
мулу, при помощи которой представлена функция. В связи с этим и в данном
пособии под упрощением булевой функции будем понимать тождественные пре-
образования ее формулы, которые приводят к уменьшению числа вхождений
аргументов по сравнению с исходной формулой. Цель этих преобразований со-
стоит в нахождении минимальной формы булева выражения как предела упро-
щения по числу вхождений аргументов.
Уточним, что такое число вхождений аргументов и в чем его отличие от
числа переменных, от которых зависит функция. Рассмотрим пример:
.
D
C
A
B
A
f
+
=
Эта функция зависит от четырёх аргументов A, B, C, D, но содержит пять
вхождений аргументов. Функция
AC
BC
B
A
A
f
+
+
+
=
(5.1)
зависит от трёх аргументов, а число её вхождений аргументов равно семи.
Таким образом, число вхождений аргументов – это общее число букв в
записи булева выражения. При этом если какая-либо буква встречается в фор-
муле несколько раз, то столько же раз она учитывается при подсчёте числа
вхождений аргументов.
Рассмотрим формулу (5.1). Нетрудно заметить, что к ней применимы тео-
ремы поглощения и склеивания, т. е. её можно упростить. Слагаемое A погло-