ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 16.12.2020
Просмотров: 2169
Скачиваний: 53
Булевы алгебры
45
Булевы алгебры
F
В математике встречаются и другие объекты, кроме множеств,
для которых определены действия сложения и умножения, удо-
влетворяющие условиям 1)–26). Такие системы объектов изучил
в 1847 году английский математик Буль (отец писательницы Этель
Лилиан Войнич — автора знаменитой книги «Овод»). Поэтому та-
кие системы назвали
булевыми алгебрами
. Но когда это название
уже укоренилось, выяснилось, что Буль имел предшественников —
в 1685 году братья Бернулли изучали «алгебру» с теми же законами.
Совпадение интересов братьев Бернулли и Буля вполне понятно:
все они интересовались алгеброй логики, возможностью представить
в алгебраической форме рассуждения, высказывания. А булевы ал-
гебры специально приспособлены к этой цели. Высказыванием в ма-
тематической логике называют предложение, которое может быть
верно или ложно. При этом в логике не интересуются вопросом, вер-
но или ложно данное высказывание на самом деле. Там обсуждают
лишь проблему, по каким правилам можно из данных высказываний
получать более сложные и как из знания истинности или ложности
исходных высказываний выводить истинность или ложность слож-
ных высказываний.
Над высказываниями можно делать следующие операции:
1) Отрицание — замена данного высказывания
X
противополож-
ным высказыванием
X
, которое истинно, если данное выска-
зывание ложно, и ложно, если высказывание
X
истинно.
2) Конъюнкция — образование из данных двух высказываний
X
и
Y
третьего высказывания
X
∧
Y
, истинного лишь в случае,
если истинны оба высказывания
X
и
Y
.
3) Дизъюнкция — образование из данных двух высказываний
X
и
Y
третьего высказывания
X
∨
Y
, истинного в случае, когда
истинно хоть одно из данных высказываний.
4) Импликация — образование из высказываний
X
и
Y
третьего
высказывания
X
→
Y
, ложного лишь в случае, когда
X
ис-
тинно и
Y
ложно.
Во многих случаях высказывание состоит в том, что некоторый
элемент
x
принадлежит подмножеству
A
некоторого универсально-
го множества
I
. В этом случае операции 1)–4) над высказываниями
соответствуют известным нам операциям над множествами. Напри-
мер, отрицание высказывания «
x
∈
A
» есть высказывание «
x
∈
A
0
».
46
Глава I. Множества и действия над ними
Таким образом, взятию дополнения
A
соответствует отрицание вы-
сказывания «
x
∈
A
». Точно так же операции пересечения множеств
A
и
B
соответствует конъюнкция высказываний «
x
∈
A
» и «
x
∈
B
»,
операции сложения множеств — дизъюнкция высказываний и соот-
ношению
A
⊂
B
— импликация высказываний «
x
∈
A
» и «
x
∈
B
». При
этом высказывание «
x
∈
I
» всегда истинно, а высказывание «
x
∈
∅
»
всегда ложно.
Отмеченная связь делает естественным предположение, что зако-
ны 1)–26) верны не только для множеств, но и для высказываний, ес-
ли только понимать
A
∩
B
как конъюнкцию высказываний,
A
∪
B
—
как их дизъюнкцию,
A
0
— как отрицание высказывания
A
,
A
⊂
B
—
как импликацию высказываний,
I
— как всегда истинное, а
∅
—
как всегда ложное высказывание. Оказалось, что это предположение
верно — высказывания образуют булеву алгебру относительно опе-
раций 1)–4).
Но булевы алгебры можно строить не только из высказываний.
Рассмотрим, например, множество всевозможных последовательно-
стей, содержащих
n
цифр, причем каждая цифра равна нулю или
единице. Определим сложение и умножение двух таких последова-
тельностей «покоординатно», причем таблицы сложения и умноже-
ния зададим так:
+
0
1
0
0
1
1
1
1
×
0
1
0
0
0
1
0
1
логическое сложение
логическое умножение
Например,
(1
,
0
,
0
,
1) + (1
,
1
,
0
,
1) = (1
,
1
,
0
,
1);
(1
,
0
,
0
,
1)(1
,
1
,
0
,
1) = (1
,
0
,
0
,
1)
.
Положим, далее,
x
⊂
y
, где
x
= (
x
1
, . . . , x
n
)
, y
= (
y
1
, . . . , y
n
)
, если
для каждой координаты имеем
x
k
6
y
k
. Заменяя в последователь-
ности 0 на 1, а 1 на 0, получим новую последовательность, кото-
рую обозначим
x
0
. Наконец, через
∅
обозначим последовательность
(0
,
0
, . . . ,
0)
, а через
I
— последовательность
(1
,
1
, . . . ,
1)
. Предостав-
ляем читателю проверить выполнение законов 1)–26) для введенных
операций над последовательностями.
Интересный пример булевой алгебры получается, если рассмот-
реть все натуральные делители натурального числа
N
, которое
Булевы алгебры
47
является произведением нескольких различных простых чисел.
В качестве операции сложения делителей выберем образование наи-
меньшего общего кратного этих делителей, а в качестве операции
умножения — образование их наибольшего общего делителя. До-
полнением делителя
n
назовем число
n
0
=
N
n
. Наконец, скажем, что
n
⊂
m
, если
m
делится на
n
. Нетрудно проверить, что введенные
операции удовлетворяют условиям 1)–26) из пункта «Алгебра мно-
жеств», причем роль пустого множества
∅
играет число 1, а роль
универсального множества
I
— число
N
.
Если, например, взять
N
= 30
, то булева алгебра будет состоять
из чисел
{
1
,
2
,
3
,
5
,
6
,
10
,
15
,
30
}
. «Сумма» делителей 2 и 5 равна 10,
а их «произведение» равно 1. Делителем, «обратным» делителю 3,
является
10
,
3
0
= 10
. Наконец,
5
⊂
15
, так как 15 делится на 5.
Глава II. В мире чудес бесконечного
Тайны бесконечности
Не будет преувеличением сказать, что всю математику пронизы-
вает идея бесконечности. Как правило, в математике интересуются
не отдельными объектами (числами, геометрическими фигурами),
а целыми классами таких объектов: совокупностями
всех
натураль-
ных чисел,
всех
треугольников и т. д. А такие совокупности состоят
из бесчисленного множества отдельных элементов.
Поэтому математики и философы всегда интересовались поняти-
ем бесконечности. Этот интерес возник с того самого момента, когда
стало ясно, что за каждым натуральным числом идет следующее,
то есть что числовой ряд бесконечен. Но уже первые попытки изу-
чения бесконечности привели к многочисленным парадоксам.
Например, греческий философ Зенон, используя понятие беско-
нечности, доказывал невозможность движения. В самом деле, го-
ворил он, для того чтобы стрела пролетела какой-то путь, сначала
она должна сделать половину пути. Но прежде чем сделать полпу-
ти, надо пролететь четверть пути, восьмую часть пути и т. д. Так
как процесс деления пополам никогда не кончится (вот она, беско-
нечность!), то стрела никогда не сможет сдвинуться с места. Точно
так же он доказывал, что быстроногий Ахиллес никогда не догонит
медлительную черепаху.
Из-за таких парадоксов и софизмов древнегреческие математики
отказывались иметь дело с бесконечностью, изгоняли ее из матема-
тических рассуждений. Некоторые философы считали, что все гео-
метрические фигуры состоят из конечного числа мельчайших неде-
лимых частиц (атомов). Атомистическая теория легко устраняет па-
радоксы Зенона, поскольку в ней не допускается бесконечное деле-
ние — делить можно лишь до атомов, далее не делимых. Однако тут
возникли новые трудности. Нельзя разделить пополам отрезок, ес-
ли он состоит из нечетного числа неделимых (рис. 23). Круг тоже
нельзя разделить на две равные части: центр будет принадлежать
только одной из частей, а это противоречит их равенству.
Тайны бесконечности
49
Ахиллес и черепаха
Надо сказать, споры о бесконечности протекали порою довольно
остро. Так, известный греческий философ Платон с такой неприми-
римостью относился к атомистической теории Демокрита, что по-
всюду разыскивал рукописи сочинений этого автора и уничтожал
их — до изобретения книгопечатания такой метод идейной борьбы
был весьма эффективен.
Методы, в которых использовалось понятие бесконечности, поз-
волили греческим ученым получить ряд важных результатов, осо-
Рис. 23
бенно в геометрии. Однако парадоксы Зено-
на приучили их к осторожности. Например,
Евклид, формулируя свою знаменитую тео-
рему о бесконечности множества простых
чисел, выражается так: «Простых чисел
существует больше всякого предложенного
количества простых чисел». Итак, больше
всякого предложенного количества, а бес-
конечно много или нет — об этом Евклид умалчивает. Вообще,
древние греки с такой тщательностью маскировали применение ме-
тодов, в которых существенную роль играло понятие бесконечности,
что в XVI–XVII веках европейским математикам пришлось эти ме-
тоды переоткрывать.
В средние века проблемой бесконечного интересовались главным
образом в связи с рассуждениями о том, конечно или нет множество
ангелов, которое может поместиться на кончике иглы. Широкое ис-
пользование бесконечности в математике началось с XVII века, когда