АЛГЕБРА МНОЖЕСТВ И АЛГЕБРА ЛОГИКИ

К оглавлению
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 
17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 
34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 
51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 
68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 
85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 
102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 
119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 
136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 
153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 
170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 

Алгебра чисел

В арифметике и алгебре рассматривают числа разной природы — целые числа, рациональ­ные числа (дроби) и другие. Во всех случаях с каждыми двумя числами а и b сопоставляются еще два числа a+b и ab, называемые сум­мой и произведением чисел а и b. Определение суммы и произведения двух чисел различно для чисел разной природы. Так, если a есть целое положительное число, то его можно представлять себе как число предметов

в некотором наборе. При этом сумма а + b означает число предметов, которое мы полу­чим, если объединим первый набор, содержа­щий а предметов, и второй набор, содержащий b предметов (рис. 1). Если же объединим b наборов, каждый из которых содержит по а предметов, то всего мы получим ab предметов

Более сложно определяются сумма и произведение дробей — например, так:

a1/a2+b1/b2=(a1b2+a2b1)/a2b2 и (a1/a2)(b1/b2)=a1b1/a2b2 .

Здесь числа a1, a2, b1, b2 — целые. Иные правила относятся к сложению и умножению отрицательных чисел: среди этих правил есть, скажем, такое:

(- а)(-b)=+ab.

Но независимо от природы рассматривае­мых чисел и от определения суммы и произве­дения чисел общие законы действия над чис­лами остаются одни и те же. Вот эти законы:

а+b=b+a

(коммутативный, или переместительный, закон для сложения);

ab=ba

(коммутативный, или переместительный, закон для умножения);

(а+b)+с=а+(b+с)

(ассоциативный, или сочетательный, закон для сложения);

(ab)c =а(bс)

(ассоциативный, или сочетательный, закон для умножения);

(а+b)с=ас+bc

(дистрибутивный, или распредели­тельный, закон).

При этом сразу бросает­ся в глаза, что правила, от­носящиеся к сложению чи­сел, очень похожи на правила умножения.

383

Например:

а+b=b+a и аb=bа, (а+b)+с=а+(b+с) и (аb)с= а(bс).

Это сходство между действиями сложения и умножения находит отражение и в сущест­вовании двух замечательных чисел 0 и 1 —таких, что прибавление одного из них и умно­жение на второе не меняют ни одного числа: a+0=а и a•1=а.

Следует, впрочем, заметить, что сходство между действиями сложения и умножения не простирается особенно далеко. Так, например, число 0 играет особую роль не только по отно­шению к сложению, но и по отношению к умно­жению: эта особая роль числа 0 определяется замечательным равенством а•0=0. (Из это­го равенства, в частности, вытекает, что де­лить на 0 число а¹0 нельзя.) В противо­положность этому, число 1 по отношению к опе­рации сложения не играет никакой особой роли: равенство, которое получается из равен­ства а • 0 = 0 заменой числа 0 на число 1 и операции умножения — операцией сложения:

а + 1 == 1,

почти никогда не будет верным. (Это равен­ство справедливо лишь при а =0.) Также и дистрибутивный закон:

(а+b)с=ас+bc

подчеркивает различие между действиями сложения и умножения. Если заменить в записи этого закона сложение умножением и наоборот, то получим курьезное «равенство»:

(а•b)+с=(а+с)•(b+с),

как правило, не выполняющееся: так, 1•2+3=5, а (1+3)•(2+3)=20. (Равенство (а •b)+с=(а+с)•(b+с) справедливо лишь при с=0 и при а+b+с=1.)

В математике, однако, операции сложения и умножения определяются не только для чисел. При этом иногда удается прийти к «ал­гебре», в которой сходство между операциями сложения и умножения оказывается большим, чем в обычной «числовой» алгебре. В качестве примера можно указать «алгебру множеств».

Алгебра множеств

Рассмотрим систему всевозможных мно­жеств (совокупностей) тех или иных объектов; для конкретности будем все время говорить о множествах учеников нашего класса.

Сумму А + В двух множеств А и В определим как такое множество, которое по­лучается при объединении множеств А и В; другими словами, в множество А + В входят все те, и только те объекты, которые входят в множество А или в множество В. Так, например, если А есть множество отлич­ников из нашего класса, состоящее из учени­ков Пети, Саши, Кати, Веры и Наташи, а В —множество учеников, сидящих в первом ряду, и состоящее из школьников Ильи, Гриши, Зои, Кати, Наташи и Яши, то сумма А + В этих двух множеств состоит из учеников, которые являются отличниками или сидят в первом ряду; в нее входят ученики Петя, Саша, Катя, Вера, Наташа, Илья, Гриша, Зоя и Яша (рис. 3).

То обстоятельство, что мы назвали «сложе­нием» совершенно новую операцию, не должно нас смущать,— ведь мы и раньше каждый раз, когда переходили от чисел одной природы к числам другой природы, определяли сложение по-новому. Ясно, например, что сложение по­ложительных и отрицательных чисел — это не то же самое, что сложение одних положи­тельных чисел; так, сумма чисел 5 и (-3) — это то же самое, что разность чисел 5 и 3. Сложение дробей — не то же самое, что сложение целых чисел; рис. 1, изображающий сложение чисел, становится непригоден, когда речь заходит о дробях. Однако, называя уже знакомым нам словом «сложение» новую опе­рацию, мы каждый раз должны были лишь «доучиваться», но не «переучиваться»,— навы­ки, выработавшиеся в процессе действий с целыми числами, оказываются полезными и при действиях с дробями, правила действий над положительными числами полезны и при дей­ствиях с относительными числами и т. д. Это связано с тем, что общие законы, которым под­чиняется операция сложения целых чисел, ос­таются в силе и в дальнейшем, скажем при переходе к дробным числам; так, в обоих слу­чаях сложение коммутативно (т. е. а+b= b+а) и ассоциативно: (а+b)+с=а+(b+с).

Посмотрим теперь, сохраняют ли силу эти законы и для множеств. При этом нам удобно будет использовать специальные диаграммы, иллюстрирующие действия над множествами. Условимся обозначать весь класс (точнее гово­ря, множество всех учеников класса) квад­ратом; в этом квадрате можно расставить ряд точек, по числу учеников (рис. 4). При этом

Рис. 4.

отдельные множества учеников будут изобра­жаться частями квадрата; так, например, изоб­раженная на рис. 5, а фигура графически иллю­стрирует множество А отличников, а изобра­женная на рис. 5,б — множество В учеников, сидящих в первом ряду. Под суммой двух мно­жеств А и В понимается фигура, получаемая объединением фигур, изображающих мно­жества А и В (рис. 6).

Такие диаграммы принято называть диа­граммами Эйлера или диаграммами Венна. Они позволяют наглядно представить операцию сложения множеств и проверить ее свойства.

Ясно, например, что

А+В=В+А

(коммутативный закон для сложения множеств; рис. 7). Также ясно, что

(А+В)+С=А+(В+С)

Рис. 6. Сумма фигур — это их объединение.

(ассоциативный закон для сложения множеств; рис. 8). Сумму (А+В)+С=А+(В+С) естественно обозначать просто через А+В+С (без скобок).

Определим теперь произведение А•В или АВ двух множеств А и В как множество, получаемое в пере­сечении множеств

А и В; другими словами, в множество АВ вхо­дят те, и только те, элементы, которые входят как в множество А, так и в множество В. Так, например, если А и В — указанные выше мно­жество отличников и множество учеников, сидя­щих в классе в первом ряду, то множество АВ состоит из тех учеников, которые являются отличниками и сидят в первом ряду; оно со­стоит всего из двух учеников — Кати и Наташи (рис. 9). На рис. 10 то же множество АВ изоб­ражено на диаграмме как пересечение множеств А и В.

Использование термина «произведение» в совершенно новом смысле оправдывается тем обстоятельством, что, как и для обыкновен-

ного умножения, мы имеем: АВ=ВА (ком­мутативный закон для умножения множеств; рис. 11) и (АВ)С=А(ВС) (ассоциативный закон для умножения мно­жеств; рис. 12). Множе­ство (АВ)С=А(ВС) естественно обозначать просто через АBС (без скобок).

Проверим теперь, выполняется ли для мно­жеств дистрибутивный закон. На рис. 13, а заштрихованы множества A+В и С, при этом двойной штриховкой оказывается покрыто мно­жество (А + В) С. На рис. 13, б различно за­штрихованы АС к ВС; при этом как-то заштри­ховано множество А С + ВС. Но легко видеть, что множество, покрытое двойной штриховкой

на рис. 13, а,— это в точности то множество, которое заштриховано на рис. 13, б. Отсюда заключаем: в «алгебре множеств» выполняется дистрибутивный закон:(А+В)С=АС+ВС.

Алгебра правды и лжи

Всем, кто впоследствии пожелает научить правила алгебры логики, имеет смысл предварительно попрак­тиковаться в применении своеобраз­ных математических приемов вы­явления истины из поступившей ин­формации, содержащей в себе и правду, и ложь. Пусть полученная информа­ция состоит из нескольких сообщений, причем заранее известно, что правдиво только какое-то одно. Сейчас несуще­ственно — часто или редко в действи­тельности может оказаться такая ситуация.

Условимся, что эквивалентом вся­кого верного утверждения будет число 1, а всякого ложного — число 0. Тогда полученные сведения можно определенным образом закодировать (зашифровать) символами и составить из этих символов и чисел 0 и 1 неко­торые алгебраические выражения и равенства. При этом каждое ут­верждение можно представить в двух видах: как произведение и как сумму.

Пусть буквами A и B обозначены два верных утверждения, т. е. каждая буква имеет значение 1; тогда произведение АB=1; но если А или B ложно, т. е. имеет значение 0, то А•B=0. Сумму двух верных утвер­ждений (т. е. двух единиц) следует считать равной 1, A+B=1, так как в нашей алгебре нет чисел, пре­вышающих единицу; в самом деле, ведь ничто не может быть более пра­вильным, чем «верно» Однажды произошел такой разговор:

Мама. Вчера мне сказали, что Саша, сын Николая Ивановича, уже окончил институт, а ему еще толь­ко двадцать один год.

Папа. Ты что-то напутала, дорогая. Сына Николая Ивановича

зовут Костя, и ему еще только недав­но исполнилось восемнадцать.

Дочь. Я не знаю семьи Николая Ивановича, но помню, подруга утверждала, что его сыну 25 лет, и при этом называла она его другим именем, не Сашей.

При помощи вычислений опре­делите имя и возраст сына Николая Ивановича, полагая, что в каждой из полученных информаций содержат­ся верные сведения либо только о возрасте, либо только об имени. Решение на стр. 471.

 «Нуль» и «единица»

Выясним, существует ли в «алгебре мно­жеств» такой элемент 0 «нуль», что прибавление его к любому множеству А не меняет этого множества. Ясно, что последнее возможно толь­ко в том случае, если «множество 0» совсем не содержит элементов, является «пустым». Но в последнем случае не хочется даже гово­рить о «множестве», какое же это множество, состоящее из отдельных элементов, если этих элементов вовсе нет?

В учении о множествах, однако, целесооб­разнее причислять пустое множество, вовсе не содержащее элементов, к числу рас­сматриваемых множеств. Ведь в противном слу­чае мы зачастую не сможем говорить о мно­жестве, не выяснив предварительно, суще­ствует оно или нет. Так, прежде чем сказать: «Множество отличников из IX «а» класса школы № 13 Ленинграда», — нам придется пойти в школу и справиться об успеваемости учеников этого класса. Гораздо удобнее спокойно гово­рить об этом множестве, оговорив только, что оно может быть и «пустым», т. е. не содержать ни одного элемента. В ряде случаев мы можем заранее сказать, что то или иное множество не является пустым; так, не пустое, разуме­ется, множество самых высоких учеников клас­са (это множество может иногда содержать и больше одного ученика). В иных случаях мы сразу скажем, что множество, о котором идет речь,— пустое. Так, конечно, пустым является множество обучающихся в нашем классе жи­вых слонов или множество учеников, имеющих две головы. Однако в большинстве случаев лишь более тщательный анализ позволяет ука­зать, является то или иное множество пустым или нет. Так, например, множество Семенов или множество левшей из нашего класса может быть пустым или не пустым. Пустое множест­во в дальнейшем всегда будем обозначать зна­ком О. Таким образом, для каждого множества А будем иметь (рис. 14):

А+0=А.

Подобно известному правилу а•0=0 ал­гебры чисел, для любого множества А:

А•0=0.

В самом деле, множество А•0, по определению, состоит из всех элементов, принадлежащих и множеству А и множеству О. Но множество О вовсе не содержит элементов и не может со­держать элементов и множество А•0.

Теперь зададимся вопросом о «множестве 1», обладающем тем свойством, что произведение

его на любое множест­во А дает А. Последнее означает, что пересе­чение или общая часть «множества 1» и множе­ства А для любого мно­жества А совпадает с самим этим множеством. Но это возможно, разу­меется, лишь в том слу­чае, если «множество 1» содержит все вообще существующие элемен­ты. Так, если мы рассматриваем всевозможные множества учеников из нашего класса, то роль единицы будет играть множество всех обу­чающихся в классе учеников. Нетрудно понять, что, скажем, произведение этого множества и множества А будет состоять из всех отлични­ков (т. е. совпадать с А); произведение этого множества и множества В будет состоять из всех учеников, сидящих в первом ряду (т. е. будет совпадать с множеством В).

Множество, состоящее из всех элементов всех рассматриваемых множеств, называется полным, универсальным, или единич­ным; мы будем обозна­чать его знаком I. Та­ким образом, для лю­бого множества А: А•I=А.

Универсальное мно­жество I графически изображается всем квадратом, внутри кото­рого мы рисуем фигуры, изображающие различ­ные множества (рис. 15).

Удивительная алгебра

До сих пор все рассматриваемые законы действий над множествами совпадали с зако­нами действий над числами. Однако на самом деле алгебра множеств вовсе не копирует в точ­ности алгебру чисел; она обладает и многими удивительными свойствами, не имеющими ме­ста в обычной алгебре. Мы начнем со второ­го дистрибутивного закона, получаемого из первого дистрибутивного закона: (А+В)С = АС+ВС заменой сложения умножением и наоборот:

АВ+С= (А+С) (В+С).

Как уже указывалось, в алгебре чисел этот второй дистрибутивный закон, вообще говоря, места не имеет. По-другому обстоит дело с ал­геброй множеств. На рис. 16, а заштрихованы множества АВ и С, так что заштриховано на этом рисунке множество АВ+С. На рис. 16,б заштрихованы множества A+С и В+С, так что двойной штриховкой покрыто множе­ство (A+С)(В+С). Но легко видеть, что множество, покрытое на рис. 16,б двойной штриховкой, — это в точности то множество, которое заштриховано на рис. 16, а. Таким образом, для любых трех множеств А, В и С:

АВ+С= (А+С) (В+С).

Далее, выше мы отмечали курьезное равен­ство: а+1=1, получаемое из равенства а•0=0 заменой нуля единицей и умножения сложением. Но курьезным это равенство яв­ляется лишь в алгебре чисел. В алгебре же множеств, очевидно, для любого множества А:

А+I=I.

В самом деле, сумма А + I представляет собой множество, получаемое объединением универсального множества I и множества А. Но уже множество I содержит все имеющиеся в нашем распоряжении элементы, так что при­бавление к нему множества А ничего изменить не может: сумма А+I — это то же самое уни­версальное множество I!

Отметим еще необычные равенства:

А+А=А и АА=А,

также выполняющиеся для каждого множества А. В самом деле, сумма А+А представ­ляет собой объединение множества А с самим собой. Но при этом мы придем к тому же самому множеству А (рис. 17). Аналогично этому произведение АА есть пересечение множества А с самим собой, но это пере-

сечение не отличает­ся от множества А (см. тот же рис. 17).

Последние два ра­венства можно еще об­общить. Различные множества можно сравни­вать друг с другом. Ес­тественно считать, что множество А «больше» множества В, если все элементы множества В содержатся в множе­стве А. Это соотношение записывается так: AÉB или ВÌА; при этом говорят, что «мно­жество А содержит множество В» или «множе­ство В содержится в множестве А». Так, мно­жество С девочек, сидящих в первом ряду (это множество состоит из школьниц Зои, Ка­ти и Наташи), содер­жится в множестве В учеников, сидящих в первом ряду: ВÉС (рис. 18). Графически соотношение АÉВ изоб­ражается тем, что фи­гура В целиком заклю­чается в фигуре А (рис. 19) или В совпадает с А1. Ясно, что если АÉВ и ВÉС, то АÉС (рис. 20); это утверждение аналогично извест­ному свойству неравенств: если а>b и b>с, то а>с.

Нетрудно видеть, что

если АÉВ, то А+В=А; АВ=В

(рис. 21 а, б). Так как можно считать, что АÉА, то отсюда вытекают и два выписанных ранее равенства:

А+А=А и АА=А.

Мы видим, что правила алгебры множеств во многом отличны от правил алгебры чисел. Поэтому, для того чтобы овладеть этой уди­вительной алгеброй, приходится не только «до­учиваться», но частично и «переучиваться»— отказываться от некоторых привычных пред­ставлений, связанных с опытом действий с чис­лами.

Вот, например, одно из многих необычных, с точки зрения алгебры чисел, тождеств:

(А+С)(В+С)А=АВ+СА

(рис. 22, а и б).

Укажем теперь еще одно отличие алгебры множеств от алгебры чисел, которое читатель, возможно, и не отметил. Имея дело с числами, мы можем сравнить между собой любые два числа а и b: всегда одно из них больше дру­гого (или эти числа равны). Для двух множеств А и В, однако, как правило, не будет иметь место ни одно из двух соотношений АÉВ и ВÉА. Так, в случае указанных выше множе­ства А отличников и множества В учащихся,

сидящих в первом ряду, ни одно из этих мно­жеств нельзя считать большим. Только если одно из двух множеств целиком содержится внутри другого, мы можем указать большее из них; для других же множеств А и В, гра­фически изображенных на рис. 23, а и б, ни­какое сравнение их невозможно. Таким обра­зом, лишь для некоторых пар множеств А т В можно указать, какое из этих множеств является большим.

Алгебра множеств с ее своеобразными за­конами действий, одновременно и напоминаю­щими правила действий над числами, и отлич­ными от этих правил, была впервые указана замечательным английским математиком про­шлого века Дж. Булем, отцом известной писательницы Этель Лилиан Войнич (автора романа «Овод»). По имени Буля алгебру мно­жеств часто называют «булевой алгеброй».

Основополагающее сочинение Буля, в котором впервые строилась булева алгебра, называлось «Исследование законов мысли»; оно было на­печатано в Лондоне в 1854 г., т. е. более ста лет назад. Название книги Буля сначала может показаться удивительным,— какое отношение имеет курьезная алгебра множеств к законам нашего мышления? На этот вопрос мы поста­раемся ответить ниже.

Поскольку законы действий над множест­вами отличаются от законов действий над числами, иногда считают, что эти действия нельзя обозначить теми же символами, которые используются в алгебре чисел. В математиче­ской литературе сумма множеств А и В часто обозначается через АÈВ, а произведение этих же множеств через А∩В. При этом правила дей­ствий булевой алгебры множеств записывают­ся в следующем виде:

AÈB=BÈA, А∩В=В∩А

(коммутативные законы);

389

Джордж Буль.

(AÈB) ÈC=AÈÈС), (A∩B) ∩C=A∩ (B∩C) (ассоциативные законы);

(AÈВ) ∩С=(АС) È (ВС),

(A∩B) ÈC=(AÈC)∩(BÈC)

(дистрибутивные законы);

AÈ0=A, A∩I=A,

A∩0=0, A∩= I,

АÈА=А, A∩A=A.

Мы, однако, предпочтем во всех случаях пользоваться знакомыми символами сложения и умножения.

Дополнение множества. Аналогия между сложением и умножением множеств

Вернемся к установленным выше свойствам действий алгебры множеств. Сразу бросается в глаза чрезвычайно тесная связь между за­конами, относящимися к сложению множеств, и законами умножения. Выпишем снова эти законы:

А+В=В+А, АВ=ВА;

(А+В)+С=А+(В+С), (АВ)С=А(ВС);

(А+В)С=АС+ВС, АВ+С=(А+С) (В+С);

A +0=A, AI=А;

А+I=I, А0=0;

А+А=А, АА=А

и т. д. Из этой таблицы видно, что всякое равен­ство, тождественно выполняющееся в алгебре множеств, при замене знака сложения множеств знаком умножения, и наоборот, и пустого множества О (если оно входит в наше равен­ство) универсальным множеством I, и наоборот, переходит в новое равенство, также тождест­венно выполняющееся.

Сейчас мы докажем это утверждение в общем виде. Для этого нам понадобится одна свое­образная операция алгебры множеств, сопо­ставляющая новое множество не с двумя задан­ными множествами (подобно сумме А + В и произведению АВ заданных множеств), а с одним множеством А. Эта операция на­зывается образованием дополнения и обо­значается чертой, поставленной над множе­ством. А именно, через А (читается: «дополне­ние А») мы будем обозначать множество всех эле­ментов универсального множества I, не при­надлежащих множеству А. Так, если А есть множество отличников из нашего класса, то множество А состоит из всех учеников, не яв­ляющихся отличниками. На диаграмме мно­жество Ā изображается частью квадрата I, не покрытой фигурой А (рис. 24). Ясно, что А+Ā=1, А Ā =0 (см. тот же рис. 24, на кото­ром графически изображены множества А и Ā); эти два равенства можно даже принять за определение множества Ā. Отметим

еще, что =А (рис. 25). Это последнее равенство короче записывают так:

Очевидно, что I=0 и Ō=I (так как все элементы входят в универсальное множество I и ни один элемент не входит в пустое множе­ство 0). Кроме того, легко видеть, что

т.е. если множество B составляет часть мно­жества А; то дополнение А составляет часть до­полнения В (рис. 26, а, б):

Второй способ задания множества состоит в том, что мы указываем признак, харак­теризующий все элементы множества, и только эти элементы. Так, выше мы говорили: «множе­ство отличников» или «множество уча­щихся, сидящих в классе в пер­вом ряду». Такой способ задания множе­ства называется неявным или описатель­ным. Этот способ заключается в том, что мы фор­мулируем некоторое высказывание, касающееся элементов рассматриваемого уни­версального множества / («быть отлични­ком» или «сидеть в первом ряду»); далее отби­раем те, и только те, элементы множества I, которые этому высказыванию удовлетворяют.

Описательный способ задания множества связывает учение о множествах с учением о высказываниях, составляющим предмет математической логики. Высказы­ванием мы называем всякое утверждение, которое может оказаться истинным или лож­ным; при этом предполагается, что в принципе существует возможность установить, истинно данное высказывание или ложно, хотя мы, быть может, этой возможности не имеем. С этой точ­ки зрения утверждение «ровно через 100 лет в этот. день в Москве будет ясная погода» является высказыванием, поскольку через 100 лет можно будет проверить, правда это или нет. Напротив, утверждение «неделя — это большой промежуток времени» высказыва­нием не является в силу неопределенности выражения «большой промежуток времени», которое у разных лиц и в различных обстоя­тельствах может иметь совершенно разный смысл; здесь, не обладая несколькими допол­нительными сведениями, никак нельзя сказать, является это утверждение истинным или нет.

Рассмотрим теперь высказывания, относя­щиеся к элементам определенного универсаль­ного множества /; в случае, когда этим мно­жеством является множество учащихся дан­ного класса, это могут быть высказывания: «он отличник», «он сидит в первом ряду», «он выше 1 м 50 см», «он старше 50 лет», «он — это девочка», «он левша», «он имеет две головы»

и т. д. Каждому такому высказыванию отве­чает некоторое множество элементов из I, для которых это высказывание является истинным; это множество называется множеством истинности данного высказывания. Мно­жество истинности может оказаться пустым; в этом случае высказывание называется тож­дественно ложным или проти­воречивым. Так, для множества учеников данного класса тождественно ложными будут высказывания «он имеет две головы» или «ему больше 50 лет»; выше у нас фигурировало еще одно высказывание, также заведомо противо­речивое в применении к ученикам какого-либо класса: «он слон». В определенном смысле противоположный случай — это тот, когда мно­жество истинности данного высказывания сов­падает со всем универсальным множеством /; в этом случае высказывание называется тож­дественно истинным или бес­содержательным. Тождественно истин­ными являются, например, высказывания: «он (ученик определенного класса) моложе 50 лет», «он мальчик или девочка».

Алгебра множеств и алгебра высказываний

Высказывания мы будем обозначать малыми буквами латинского алфавита; отвечающие этим высказываниям множества истинности будем обозначать большими буквами. Так, выска­зываниям а — «он отличник» и b — «он сидит в первом ряду» отвечают указанные выше множества истинности А и В. Тождественно ложное высказывание всегда будем обозначать буквой о, а тождественно истинное выска­зывание — буквой i.

Рассмотрим теперь две операции, позволяю­щие по двум высказываниям строить новые, составные высказывания. В математической логике эти операции называются латинскими терминами «дизъюнкция» и «конъ­юнкция» и обозначаются специальными значками Ú и Ù так, а Ú b означает дизъюнк­цию высказываний а и b, аÙb — конъюнкцию (сравним с обозначениями суммы и произведе­ния, или объединения и пересечения, мно­жеств, указанными на стр. 389). Мы здесь для простоты почти не будем употреблять этих сложных терминов и символов; вместо этого будем говорить о сумме а+b и произ­ведении аb высказываний а и b.

Под суммой (дизъюнкцией) вы­сказываний а и b понимается высказывание, которое мы получим, если объединим высказы­вания а и b союзом «или». Например, если а есть высказывание «он отличник», a b — вы­сказывание «он сидит в первом ряду», то через a+b будем обозначать высказывание «он является отличником или сидит в первом ря­ду». При этом частичку «или» мы будем всегда понимать в смысле: «или первое, или второе, или то и другое вместе». Ясно, что если А есть множество истинности высказывания a, а В — множество истинности высказывания 6, то множеством истинности высказывания а+b будет А+В (рис. 28). Так, в рассматривае­мом примере множество истинности высказы­вания а состоит из школьников Пети, Саши, Кати, Веры и Наташи, а множество истинности высказывания b — из школьников Ильи, Гри­ши, Зои, Кати, Наташи и Яши; множество же истинности высказывания а+b образуют де­вять школьников: Петя, Саша, Катя, Вера, Наташа, Илья, Гриша, Зоя и Яша.

Под произведением (конъюнк­цией) высказываний а и b мы будем понимать высказывание ab, получаемое, если объеди­нить высказывания а и b, связав их союзом «и». Итак, множеством истинности высказывания ab является произведение (пересечение) множеств истинности высказываний а и b (рис. 29). В нашем примере это множество ab состоит из двух учениц — Кати и Наташи.

Условимся еще называть два высказывания одинаковыми, или эквивалентными, если им отвечает одно и то же множество истинности. Эквивалентность высказываний будем обозначать обычным знаком равенства. Равенство а=b означает, что содержащиеся в высказываниях а и b признаки, выделяющие определенную часть универсального множе­ства, равнозначны, имеют один и тот же смысл, разнятся только своей формой. При изучении высказываний естественно не различать между собой эквивалентные высказывания, например «он отличник» и «он имеет отличные оценки».

Мы установили, что множество истинности суммы двух высказываний совпадает с суммой множеств истинности этих высказываний; мно­жество истинности произведения двух высказы­ваний совпадает с произведением множеств

истинности этих высказываний. Отсюда сле­дует, что все известные нам правила алгебры множеств можно перевести на язык алгебры высказываний. Так, например:

а+b=b+a, ab=ba;

(a+b)+c=a+(b+с), (ab)c= a(bc);

(a+b)c=ас+bc, ab+с=(а+c)(b+c); a+0=a, aI=a;

a0=0, a+I=I;

a+a=a, aa=а и т. д.

Докажем для примера первый дистрибутив­ный закон для высказываний, т. е. равенство:

(а+b)с=ас+bc.

В соответствии с нашим условием множества истинности высказываний a, b и с обозначаются через А, В и С. При этом высказывание (а+b)с имеет своим множеством истинности (А+В)С; высказывание ас+bc имеет своим множеством истинности АС+ВС. Но множе­ства (А+В)С и АС+ВС совпадают; это значит, что высказывания (a+b)c и ас+bc эквивалентны.

Запишем еще законы алгебры высказыва­ний в той форме, в которой они приводятся в книгах по математической логике:

aÚb=bÚа,

Úb) Úс=аÚ (bÚс),

Úb)Ùс=(аÙс) Ú (bÙс),

аÙb=bÙa,

Ùb) Ùс=аÙ (bÙс),

Ùb) Úс=(аÚс) Ù (bÚс).

аÚ0=а, аÙI=а,

аÙ0=0, аÚI= I,

аÚа=а, аÙа=а.

393

394

395

396

С симметрией прихо­дится иметь дело не только физикам и кристаллографам, но и художникам, рабо­тающим в области прикладного искус­ства.