ВУЗ: Томский государственный университет систем управления и радиоэлектроники
Категория: Учебное пособие
Дисциплина: Дискретная математика
Добавлен: 28.11.2018
Просмотров: 16669
Скачиваний: 202
76
Кроме того, можно отметить такие направления в применении теории
графов, как решение головоломок, теория игр, установка соответствий, теория
математических отношений, построение генеалогических деревьев и т. п.
Все их следовало бы отразить в данном пособии, т. е. показать, как имен-
но применяются графы, например, в решении задач лингвистики, биологии,
психологии, теории игр и др., привести примеры. Но для этого сведений только
из одной теории графов недостаточно, требуется ещё изучить соответствующие
разделы науки, т. е. лингвистику, биологию, психологию, теорию игр и др. Из-
ложить их в одной книге даже на минимально необходимом уровне совершенно
нереально. Поэтому в данном пособии применение графов показано лишь на
примерах из области синтеза дискретных структур.
77
4 Булева алгебра
4.1 Вводные понятия
В булевой алгебре, известной также под названием алгебры логики, ши-
роко применяется двоичная система счисления.
Для перевода десятичного числа в двоичную систему можно пользоваться
методом деления на 2. Проиллюстрируем это на примере числа 40:
40 – 0 – цифра младшего разряда
20 – 0
10 – 0
5 – 1
2 – 0
1 – 1 – цифра старшего разряда
Каждое следующее число, записанное в левой колонке, меньше преды-
дущего в два раза. Если число не делится на два, то оно уменьшается на едини-
цу. В колонке справа единицами отмечены нечётные числа, нулями – чётные.
Читая снизу вверх цифры правой колонки, получаем искомое двоичное число:
,
101000
40
2
10
=
где индекс 10 в выражении
10
40
говорит о том, что 40 – это десятичная запись,
а цифра 2 в числе
2
101000
обозначает: число 101000 является двоичным.
Для проверки выполним обратный перевод в десятичную систему
найденного двоичного числа 101000, воспользовавшись полиномом вида
1
2
1
0
1
2
1
0
2
2
2
2 ,
n
n
n
n
N
a
a
a
a
−
−
−
−
=
+
+
+
+
…
где n – количество знаков в двоичном числе;
0
a – цифра младшего разряда.
Из записи двоичного числа 101000 находим величины, необходимые для
применения полинома N:
.
1
;
0
;
6
5
3
4
2
1
0
=
=
=
=
=
=
=
a
a
a
a
a
a
n
Следовательно,
.
40
8
32
2
0
2
0
2
0
2
1
2
0
2
1
101000
10
0
1
2
3
4
5
2
=
+
=
⋅
+
⋅
+
⋅
+
⋅
+
⋅
+
⋅
=
В алгебре логики операции выполняются над высказываниями. Высказы-
вание – это повествовательное предложение, по смысловому содержанию кото-
рого можно сказать, истинно оно или ложно. Обычно высказывания обознача-
ются прописными буквами латинского алфавита. Например, пусть A – это
78
высказывание «Петров купил дога». Если оно истинно, то пишут А = 1. Соот-
ветственно запись A = 0 обозначает: высказывание «Петров купил дога» ложно.
Знаки 0 и 1 обычно называют константами алгебры логики.
Всякая буква, обозначающая высказывание, – это переменная величина,
принимающая одно значение из двух – либо 0, либо 1. Такую переменную
называют двоичной (высказывательной переменной, согласно [33]). Двоичная
переменная определяется аксиомами вида [23]:
A = 1, если A ≠ 0; A = 0, если A ≠ 1.
Согласно этим записям, аксиоматически принимается, что в булевой ал-
гебре никаких значений истинности, кроме «истина» и «ложь», не существует.
В булевой алгебре обычно приходится иметь дело со многими перемен-
ными, каждая из которых может принимать значения из множества {0, 1}. Их
упорядоченные последовательности условимся называть наборами значений
переменных, или просто наборами [51]. В соответствии с основным правилом
комбинаторики всего возможно
n
2 наборов. Например, в случае трёх перемен-
ных A, B и C число наборов равно 8. Запишем некоторые из них:
A = 0, B = 0, C = 0; A = 0, B = 0, C = 1; A = 1, B = 0, C = 1.
Если заранее договориться о порядке расположения букв (по алфавиту, по
возрастанию цифровых индексов и др.), то в записи наборов можно указывать
только цифры. Например, для трёх переменных перечень наборов имеет вид:
000, 001, 010, 011, 100, 101, 110, 111.
Значения переменных по сокращённой записи набора определяются од-
нозначно, например (при алфавитном порядке расположения букв):
Набор: 1 0 1
Переменные: A B C
Из этих двух записей видно, что A = 1, B = 0, C = 1.
Наборы – это упорядоченные n-значные последовательности нулей и
единиц. Их можно рассматривать как двоичные числа и записывать не только в
двоичной системе, но и в десятичной.
Из всех
n
2 наборов будем выделять:
1) нулевой набор, в нём n нулей, т. е. нет ни одной единицы;
2) единичный набор, содержащий n единиц при отсутствии нулей [12; 40].
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
Упражнения
1. Замените троеточия двоичными знаками, если набор имеет
вид 10011:
79
A = …; B = …; C = …; D = …; E = … .
2. Сколько существует наборов шести переменных, в каждом
из которых:
1) точно три единицы?
2) две единицы и четыре нуля?
3) два нуля и четыре единицы?
4) нулей столько же сколько и единиц?
3. Список переменных содержит 10 букв. Сколько существует
наборов значений этих переменных, если в каждом наборе:
1) содержится хотя бы один нуль и хотя бы одна единица?
2) содержится не менее двух нулей и не менее двух единиц?
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
4.2 Логические операции и формулы
В булевой алгебре применяются операции дизъюнкции, конъюнкции и ин-
версии, обозначаемые логическими знаками с теми же названиями.
Дизъюнкция, называемая также логическим сложением, логической сум-
мой, операцией ИЛИ, определена следующими аксиомами:
;
0
0
0
=
+
(4.1)
;
1
1
0
=
+
(4.2)
;
1
0
1
=
+
(4.3)
,
1
1
1
=
+
(4.4)
где знак «+», согласно символике Пирса [10; 21], обозначает операцию дизъ-
юнкции. В литературе для обозначения дизъюнкции нередко используется
знак «∨» из символики Пеано – Рассела, но он менее удобен в преобразованиях
булевых формул, поэтому в данной книге не применяется. При помощи опера-
ции дизъюнкции из двух простых высказываний A и B образуется новое, более
сложное, высказывание A + B. Читается запись «A или B». Согласно аксиомам
(4.1)–(4.4), дизъюнкция равна единице, если истинным является высказывание
A, или высказывание B, или оба вместе.
Конъюнкция (логическое умножение, операция И) определяется аксиома-
ми вида:
0 ⋅ 0 = 0;
(4.5)
0 ⋅ 1 = 0;
(4.6)
1 ⋅ 0 = 0;
(4.7)
80
1 ⋅ 1 = 1,
(4.8)
где точка обозначает операцию конъюнкции. Вместо точки можно ставить
знак & (амперсанд). И в этом случае из двух простых высказываний A и B обра-
зуется новое, более сложное, высказывание A⋅B. Читается: «A и B». Знак конъ-
юнкции можно не указывать. В дальнейшем будем полагать, что если между
стоящими рядом буквами нет никакого знака, то они образуют конъюнкцию:
AB = A⋅B = A & B.
Операции дизъюнкции и конъюнкции коммутативны:
;
A
B
B
A
+
=
+
,
BA
AB =
и ассоциативны:
;
)
(
)
(
C
B
A
C
B
A
+
+
=
+
+
),
(
)
(
BC
A
C
AB
=
что позволяет удалять скобки во всех случаях, когда знаками дизъюнкции или
конъюнкции соединяются более двух переменных:
(
)
; (
)
.
A
B
C
A
B C
AB C
ABC
+
+ = + +
=
Кроме того, операции дизъюнкции и конъюнкции обладают свойствами
дистрибутивности:
1) конъюнкция дистрибутивна относительно дизъюнкции:
,
)
(
AC
AB
C
B
A
+
=
+
что позволяет раскрывать скобки в выражениях, например:
,
)
(
AE
AD
AC
AB
E
D
C
B
A
+
+
+
=
+
+
+
и выносить общий множитель за скобки:
;
)
(
EF
D
C
AB
ABEF
ABD
ABC
+
+
=
+
+
2) дизъюнкция дистрибутивна относительно конъюнкции:
.)
)(
(
C
A
B
A
BC
A
+
+
=
+
Отметим ещё два свойства операций дизъюнкции и конъюнкции:
A + A = A; A
⋅
A = A.
Третья операция – инверсия (в литературе её называют также операцией
отрицания, операцией НЕ). Инверсия определяется аксиомами вида
,
0
1 =
(4.9)
,
1
0 =
(4.10)
где черта, поставленная над единицей в (4.9) и над нулём в (4.10), обозначает
операцию инверсии. Запись (4.9) читается следующим образом: отрицание ис-