Яглом И. М. Необыкновенная алгебра. — М. : Наука, 1968. — 72 с. — (Популярные лекции по математике ; вып. 45).

Популярные лекции по математике

И. М. ЯГЛОМ

НЕОБЫКНОВЕННАЯ АЛГЕБРА

ПОПУЛЯРНЫЕ ЛЕКЦИИ ПО МАТЕМАТИКЕ

ВЫПУСК 45

И. М. ЯГЛОМ

НЕОБЫКНОВЕННАЯ АЛГЕБРА

ИЗДАТЕЛЬСТВО «НАУКА»

ГЛАВНАЯ РЕДАКЦИЯ ФИЗИКО-МАТЕМАТИЧЕСКОЙ ЛИТЕРАТУРЫ

МОСКВА 1968

512 Я 29

УДК 512

АННОТАЦИЯ

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

Брошюра может быть использована в работе школьного математического кружка; она будет с интересом прочитана не только школьниками средних (7-го, 8-го) классов, но и школьниками-старшеклассниками.

2-2-2

149-08

СОДЕРЖАНИЕ

Предисловие .................. 4

§ 1. Алгебра чисел и алгебра множеств..... 5

§ 2. Алгебра Буля................ 19

§ 3. Дальнейшие свойства алгебр Буля: принцип двойственности; булевские равенства и неравенства ................... 31

§ 4. Множества и высказывания; алгебра высказываний .................... 44

§ 5. «Законы мысли» и правила вывода ..... 52

§ 6. Высказывания и контактные схемы..... 58

Приложение. Определение алгебры Буля..... 66

Литература................... 68

Ответы и указания к упражнениям....... 69

ПРЕДИСЛОВИЕ

Настоящая брошюра довольно точно воспроизводит содержание лекции, прочитанной автором 20 апреля 1966 г. учащимся 8-х классов московских школ — участникам XXIX Московской математической олимпиады. Основное отличие этой брошюры от лекции заключается в том, что здесь каждый параграф завершается (весьма, впрочем, немногочисленными) упражнениями, более трудные из которых отмечены звездочками; в конце книжки имеются ответы и указания к некоторым из упражнений. Я очень рекомендую читателю обязательно решить, если не все, то во всяком случае большинство из этих упражнений,— лишь после этого можно быть уверенным, что содержание брошюры действительно усвоено. Мелкий шрифт, как обычно, означает, что соответствующее место при первом чтении может быть пропущено; однако напечатанный мелким шрифтом § 6, по-моему, заслуживает того, чтобы каждый читатель внимательно проработал его, если не при первом, то при повторном чтении книги.

При составлении брошюры были частично использованы статьи автора: «Алгебра множеств и алгебра высказываний» (Детская энциклопедия, т. II, «Просвещение», 1964, стр. 383—396) и «Алгебры Буля» (Сборник «О некоторых вопросах современной математики и кибернетики», «Просвещение», 1965, стр. 230—324). В конце брошюры указана дополнительная литература, которая может оказаться полезной читателю, пожелавшему глубже познакомиться с алгебрами Буля.

Автор искренне благодарен С. Г. Гиндикину за полезные советы и Ф. И. Кизнер за тщательное и инициативное редактирование.

Москва, октябрь 1966

И. М. Яглом

§ 1. АЛГЕБРА ЧИСЕЛ И АЛГЕБРА МНОЖЕСТВ

В школе на уроках арифметики и алгебры изучают числа самой разной природы. В первом классе дети встречаются с целыми числами, которые не вызывают у них затруднений: большинство школьников приходят в школу, уже зная кое-что об этих числах. Но дальше появляются все новые и новые «числа»; теперь мы уже привыкли к ним и они нас не удивляют, но ведь на каждой стадии расширения понятия числа нам приходилось расставаться с теми или иными из милых сердцу иллюзий. Число (целое) отвечает на вопрос о том, сколько предметов содержит та или иная совокупность: корзина — яблок, книга — страниц или класс — мальчиков. А как же дроби? Ведь не может в классе сидеть 33-^- ученика или на столе стоять 3~ тарелки. Да, не может. Но на столе могут лежать 4 у яблока, киносеанс может длиться 1 j часа, даже в шкафу могут стоять 6 у книг (что, конечно, не свидетельствует об аккуратности хозяина этих книг, но ведь и здравому смыслу тоже не противоречит!). Только мы успели привыкнуть к тому, что предметов может быть и дробное число, как появляются числа отрицательные. Вот —3 книги в шкафу стоять никак не могут — это было бы уже совсем противоестественно. Но термометр может показывать —5°, или денег у тебя может быть —50 копеек; последнее, конечно, грустно, но только для тебя, а не для математики. Однако в старших классах появляются совсем уж «страшные» числа — сначала иррациональные, как V% (такое название эти числа получили от латинского слова «irrationnalis», что в переводе означает «неразумный», «бессмысленный»), а позже —

мнимые, как 1+2/1); сами названия показывают, как относились к таким числам люди, пока не привыкли. Возможно, что ты пока не знаешь этих чисел, что знакомство с ними тебе еще только предстоит2),— это не помешает тебе читать настоящую книгу. От первоначальной идеи о числе как о характеристике количества предметов иррациональные и мнимые числа весьма и весьма далеки, однако их тоже называют «числами».

Так что же общего имеется у всех этих видов чисел, что заставляет называть их одним и тем же именем «число»? Основное сходство между всеми типами чисел заключается в том, что все их можно складывать и умножать3). Однако сходство это тоже ведь довольно условно: хотя складывать и умножать мы можем числа всех видов, но операции эти в разных случаях имеют совершенно разный смысл. Так, сложить два целых положительных числа а и b — это значит найти число предметов в объединении двух совокупностей, первая из которых содержит а предметов, а вторая — b предметов: если в 7а классе имеется 35 учащихся, а в 76 классе — 39, то в обоих седьмых классах учатся 35+39=74 школьника (см. также рис. 1). Аналогично этому

Рис. 1. Рис. 2.

1) В настоящее время такие числа, как 1+2/, чаще называют комплексными, оставляя термин мнимые (или чисто мнимые) числа для таких чисел, как 2/или — (в противоположность этому такие числа, как 1, —2 или У2, часто называют действительными).

2) Числам разного рода посвящена хорошая элементарная книжка: А H и в е н, Числа рациональные и иррациональные, «Мир», 1966.

3) Но не вычитать или делить: если мы знаем только положительные числа, то мы не можем вычесть из числа 3 число 5, а если знаем только целые числа, то не можем разделить число 7 на число 4.

перемножить целые положительные числа а и b — это значит найти число предметов в собрании из а совокупностей по b предметов: если в школе имеется 3 седьмых класса и в каждом учится по 36 школьников, то всего школу посещают 3-36=108 семиклассников (см. также рис. 2). Однако в таком виде определения сложения и умножения невозможно распространить ни на действия с дробями, ни на действия с отрицательными числами (об иррациональных и мнимых числах мы здесь предпочитаем даже не говорить).

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

а + b = b + а и ab = ba\

коммутативный закон для сложения коммутативный закон для умножения

(a + b)+c = a + (b + c) и (ab)с = a (be);

ассоциативный закон для сложения ассоциативный закон для умножения во всех случаях также существуют два таких «особых» числа 0 и 1, что

a-f0 = a и а-1 =а

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

(а + Ь) с = ас + be,

дистрибутивный закон для умножения по отношению к сложению

где тоже а, Ь, с — числа любой природы.

Наличие в системах чисел двух операций — сложения и умножения — создает известный параллелизм, тем более заметный, что свойства сложения во многом напоминают свойства умножения. Этот параллелизм отражается,

например, в том, что в необычной «пропорции»

сложение _ умножение вычитание" ?

каждый спрошенный подставит вместо вопросительного знака «деление», не очень даже задумываясь над тем, что означает эта «пропорция»; в том, что не только школьники, но иногда даже и их родители зачастую путают термины «противоположное число» (такое число —а, сумма которого с данным числом а дает 0) и «обратное число» (такое число 1/а, произведение которого на данное число а равно 1); в сходстве свойств арифметической прогрессии (такой ряд чисел, в котором разность любых двух соседних чисел одна и та же) и геометрической прогрессии (такой ряд чисел, в котором частное любых двух соседних чисел одно и то же).

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

а-0 = 0

(отсюда, в частности, следует, что отличное от 0 число делить на 0 нельзя). Однако если заменить в последнем равенстве умножение сложением и нуль единицей, то мы придем к нелепому «равенству»

£1+1 = 1,

имеющему место лишь при а=01). Далее, заменив в дистрибутивном законе (a+b) с=ас+Ьс сложение умножением, а умножение сложением, мы получим «равенство»

ab + c = (a + c) ф + с),

с которым никто, конечно, не согласится. [Так как, очевидно,

(а + с) ф + с) = ab + ас + bc + c2 = ab + c(a + b + с),

то (а+с) (b-{-c) = ab+c лишь в том случае, еслис=0 или если а+6+с=1.]

1) Если бы равенство а-\-\= 1 имело место для каждого а, то ни от какого отличного от 1 числа отнять 1 было бы невозможно. На самом деле это, конечно, неверно; так, 3—1=2.

Но алгебра знает и иные, не числовые системы, в которых также можно определить действия сложения и умножения, более похожие одно на другое, чем сложение и умножение чисел. Рассмотрим, например, очень важную «алгебру множеств». Под множеством понимается любой набор каких угодно предметов, называемых элементами множества: можно говорить о «множестве учеников 7а класса», «множестве точек круга», «множестве точек квадрата», «множестве элементов периодической системы Менделеева», «множестве четных чисел», «множестве отметок в классном журнале», «множестве слонов в Индии», «множестве грамматических оши бок в твоем классном сочинении» и т. д. Довольно ясно, как можно определить «сложение двух множеств»: под суммой А+В множества А и множества В мы будем понимать просто объединение обоих этих множеств. Так, например, если А есть множество мальчиков твоего класса, a ß— множество девочек, то А+В — это множество всех учащихся класса; если А — множество всех четных целых положительных чисел, aß — множество чисел, делящихся на 3, то множество А + В

{2, 3, 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, ...}

состоит из тех и других чисел; если множество А состоит из точек фигуры, заштрихованной на рис. 3 горизонтальными линиями, а множество В — из точек фигуры, заштрихованной наклонными линиями, то множество А+В составляет вся заштрихованная на рис. 3 фигура. При этом ясно (см., например, рис. 3), что для каждых двух множеств А и В

А + В = В + А,

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

Рис. 3.

В и С, всегда

(А + В) + С^А + (В + С),

т. е. имеет место ассоциативный закон для сложения множеств. Множество (А + В)-+С (или А+ (ß+C)) можно обозначить просто через А + В + С без скобок: оно представляет собой объединение всех трех множеств Л, В и С (так, на рис. 4 множество А + В-\ С совпадает со всей заштрихованной на этом рисунке фигурой).

Условимся теперь называть произведением AB множеств А и В общую часть или пересечение этих множеств. Так, если А есть множество шахматистов твоего класса, aß — множество пловцов, то AB есть множество тех шахматистов, которые умеют плавать; если А есть множество четных целых положительных чисел, aß — множество чисел, делящихся на 3, то множество AB

{6, 12, 18, 24, . ..}

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

АВ = ВА

Рис. 4. Рис. 5.

(см. тот же рис. 5; понятно также, что «множество А В шахматистов, которые умеют плавать» и «множество ВА пловцов, которые умеют играть в шахматы» — это одно и то же множество). Далее, столь же очевидно, что для умножения множеств справедлив и ассоциативный закон, т. е. для любых трех множеств Л, В и С

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

Множество (АВ)С или А (ВС) можно обозначить просто через ABC без скобок; оно представляет собой общую часть или пересечение трех множеств Л, В и С (на рис. 6 множество А ВС покрыто тройной штриховкой1)).

Замечательно, что для любых трех множеств А, В и С выполняется также дистрибутивный закон:

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

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

Рис 6.

1) Вот еще один пример, иллюстрирующий ассоциативный закон для умножения множеств. Пусть А — множество целых чисел, делящихся на 2, В — множество чисел, делящихся на 3, и С — множество чисел, делящихся на 5; тогда AB — это множество чисел, делящихся на 6, и (АВ)С — множество чисел, делящихся и на 6, и на 5, т. е. делящихся на 30. С другой стороны, ВС — это множество чисел, делящихся на 15, и А(ВС) — множество четных чисел, делящихся на 15, т. е снова множество всех (целых) чисел, делящихся на 30.

умеющих плавать шахматистов и множества ВС умеющих плавать шашистов.

Возможно, что это словесное объяснение дистрибутивного закона покажется тебе громоздким. В таком случае полезно воспользоваться графической иллюстрацией. На рис. 7, а множество А + В заштриховано горизонтальными линиями, а множество С—вертикальными, так что множество (А + В)С оказывается покрытым «решеткой» линий. На рис. 7,6 множества АС и ВС заштрихованы линиями соответственно с правым и левым наклонами; при этом множество АС+ВС совпадает со всей заштрихованной на этом рисунке фигурой. Но легко видеть, что заштрихованная на рис. 7, б фигура АС+ВС не отличается от фигуры (Л + В)С, покрытой на рис. 7, а двойной штриховкой.

Нетрудно понять, какое «множество» играет в нашей «алгебре множеств» роль нуля. Ведь прибавление такого множества О (мы будем обозначать «нуль-множество» буквой О, похожей по написанию на число 0) не должно изменять ни одного множества — значит, множество О вовсе не содержит ни одного элемента, является «пустым». Тебе может захотеться исключить вовсе из рассмотрения подобное пустое множество: если множество О не содержит элементов, то это, мол, вообще не множество, а чепуха,— и нечего о нем говорить! Однако поступить так мы имеем не больше оснований, чем исключить 0 из совокупности чисел: ведь «набор» из нуля предметов также является «пустым» и говорить о «числе» содержащихся в нем предме-

Рис. 7.

тов как будто бессмысленно. Но на самом деле это не бессмысленно, а очень даже осмысленно. Если бы мы не имели числа 0, то не могли бы вычесть одно из другого каждые два числа (ибо в таком случае разность 3—3 вообще ничему бы не равнялась); нам было бы трудно записать в десятичной системе счисления, скажем, число 108 (одна сотня, восемь единиц — и вовсе никаких десятков!),— и еще многое мы не могли бы сделать: недаром возникновение идеи нуля считается одним из самых замечательных событий во всей истории арифметики. Точно также, если не причислять к числу множеств пустое множество О, то мы не могли бы указать произведение (или пересечение) любых двух множеств: так, пересечение изображенных на рис. 8 множеств А и В пусто, как пусто и пересечение множества отличников из твоего класса и множества слонов. Да и вообще, если бы мы отказались от понятия «пустое множество», то о множествах нам часто приходилось бы говорить с очень большой опаской: а вдруг «множество Андреев из пятых классов школы № 6 города Ленинграда» пусто, т. е. такого множества вовсе нет?

Ясно, что если О — это пустое множество, то для любого множества А

А + 0 = А

Не менее ясно, что, каково бы ни было множество Л, всегда

АО = 0

— ведь пересечение любого множества А и (не содержащего ни одного элемента) множества О (скажем, пересечение множества девочек из твоего класса и множества всех тех школьников, рост которых превышает 2,5 м) обязательно пусто!

Несколько сложнее обстоит дело с «множеством-единицей». Это множество / (мы будем обозначать его буквой /, похожей по написанию на число 1) должно быть таким,

Рис. 8.

чтобы произведение (т. е. пересечение) его и любого множества Л совпадало с А. Но отсюда следует, что наше множество / должно содержать все вообще элементы всех множеств А\ Ясно, что такое множество может существовать лишь в том случае, если мы ограничимся только такими множествами Л, элементы которых черпаются из какого-то определенного запаса «предметов»: множествами школьников одной определенной школы или одного класса (например, А может означать множество отличников, а В — множество шахматистов); множествами целых положительных чисел (А может означать множество четных чисел, aß — множество простых чисел, не имеющих иных делителей, кроме самого себя и единицы); множествами точек, образующими расположенные в определенном квадрате фигуры, вроде тех, которые изображались на рис. 3—8. В таком случае под / мы будем понимать «самое большое множество», содержащее все рассматриваемые нами «предметы»,— множество всех учащихся рассматриваемой школы или класса, множество всех целых положительных чисел или множество всех точек квадрата (рис. 9). Это множество / в «алгебре множеств» называется единичным или универсальным множеством. Очевидно, что для любого из «меньших» множеств А (и даже для множества Л, совпадающего с /) мы будем иметь

Л/=/,

в полном соответствии с условием, определяющим единицу.

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

Рис. 9.

Так, например, мы уже отмечали, что правило, получающееся из равенства а-0=0 заменой умножения сложением и нуля единицей, для чисел, вообще говоря, места не имеет: почти для всех чисел а имеем а-\-\ф\. А вот в алгебре множеств дело обстоит не так: здесь всегда

Л + / = /.

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

Далее, заменив в дистрибутивном законе (а+Ь) с=ас+Ьс сложение умножением и наоборот, мы получили нелепое «равенство» ab+c=(a+c) (Ь+с), для чисел почти всегда оказывающееся неправильным. По-другому обстоит дело в алгебре множеств: здесь всегда (т. е. при любых множествах Л, В и С) имеет место равенство

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

выражающее второй дистрибутивный закон (дистрибутивный закон для сложения по отношению к умножению) алгебры множеств. В самом деле, пусть опять Л — множество шахматистов, В — множество шашистов и С — множество пловцов из твоего класса. В таком случае, очевидно, пересечение AB множеств Л и В состоит из всех школьников, которые умеют играть и в шахматы, и в шашки, а объединение А В+С множеств AB и С — из зсех школьников, которые умеют играть и в шахматы, и в шашки или умеют плавать (а может быть, они умеют играть в шахматы, играть в шашки и плавать). С другой стороны, объединения Л + С и В + С множеств Л и С или В и С состоят из школьников, которые либо играют в шахматы, либо плавают (а может быть и плавают, и играют в шахматы), и из школьников, которые или играют в шашки, или плавают. Ясно, что в пересечение (А + С) (В+С) этих двух последних множеств входят все школьники, которые умеют плавать, а из неплавающих — только те, которые играют и в шахматы, и в шашки, т. е. это пересечение совпадает с множеством А В+С.

Так как такое словесное объяснение может показаться запутанным, то мы приведем еще графическую иллюстрацию второго дистрибутивного закона. На рис. 10, а штри-

ховкой с правым наклоном покрыто пересечение AB множеств А и ß, а с левым наклоном — множество С; при эгом вся заштрихованная на этом рисунке фигура изображает множество АВ+С На рис. 10,6 горизонтальными линиями заштриховано объединение А+С множеств А и С, а вертикальными — объединение В + С множеств ß и С; «сеткой» покрыто на этом рисунке пересечение (Л+С)(В + С) этих двух объединений. Но легко видеть, что фигура, покрытая на рис. 10, б сеткой из горизонтальных и вертикальных линий, в точности совпадает с заштрихованной на рис. 10, а фигурой, что и доказывает второй дистрибутивный закон В заключение мы отметим еще два закона алгебры множеств, противоречащих представлениям, приобретенным при изучении алгебры в школе. Нетрудно понять, что, каково бы ни было множество Л, объединение этого множества со вторым таким же и пересечение его с самим собой совпадут с исходным множеством А:

А + А = А и АА = А.

Эти два равенства иногда называют идемпотентными законами.

То обстоятельство, что для всех видов чисел общие за коны алгебры сохраняют один и тот же вид, весьма выгодно: благодаря ему мы при переходе от целых чисел к дробным или относительным (взятым со знаком «плюс» или «минус») можем полностью использовать полученные ранее навыки — нам приходится лишь доучиваться (в соответствии с более

Рис. 10.

богатым запасом рассматриваемых чисел), но не переучиваться. При переходе от чисел к множествам мы встречаемся с совсем иным положением дела: здесь нам частично приходится и переучиваться, поскольку ряд законов алгебры множеств для чисел места не имеет1).

Перечислим эти новые законы. К их числу относится соотношение

-4 + / = /,

определяющее глубокое отличие единичного множества / от числа 1. Возможность весьма своеобразного «раскрытия скобок» в алгебре множеств доставляет второй дистрибутивный закон

(А + С)(В + С) = АВ + С\ так, например, здесь

(А + D) (В + D) (С h D) == [ (А + D) (В + D)} (С + D) =

--=(AB + D)(CA D) = (AB)C + D = ABC + D.

1) Именно это отличие законов алгебры множеств от числовых законов является причиной того, что во многих книгах сложение и умножение множеств (т е их объединение и пересечение) обозначаются не обычными знаками + и -, а совершенно иначе: объединение множеств А и В обозначается через A \JB, а пересечение этих множеств — через A f| В Поскольку в настоящей брошюре мы будем говорить и о других алгебраических системах, в которых «сложение» и «умножение» подчиняются тем же законам, что и в алгебре множеств, то нам естественно отказаться от специфичных именно для теории множеств символов U и f]\ желание подчеркнуть близость рассматриваемых алгебр к школьной алгебре диктует использование привычных знаков сложения и умножения Все же, вероятно, уместно выписать здесь основные законы алгебры множеств и в стандартных теоретико-множественных обозначениях:

A\JB = B\JA и А(]В = В(]А)

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

(AUB) иС = Ли (SUC) и (А(]В) Г\С = А() (Bf]C);

ассоциативные законы

А[}0=А и А()1=А, А[)1 =1 и ЛПО = 0;

сЕОЙства пустого множества О и единичного множества /

(АЦВ) С\С = (А(]С) U (В Л Q и (Л Л В) L)C = (/4|JC) Л (BUQ;

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

А[)А = А и Af)A = A.

идемпотентные законы

Наконец, совершенно новыми для нас являются идемпотентные законы

А + А = А и ЛЛ-Л,

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

каковы бы ни были А и п\ потому, например,

(сравни с приведенным ниже упр. 6).

Упражнения

Докажи следующие равенства, в которых большими буквами обозначены множества (причем буква О всегда обозначает пустое множество, а буква / — единичное множество):

Пример: А(А-\-С)(В + С) = А {(А -\-С) (ß + C)] =

ассоциативность умножения

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

2-й дистрибу- коммутативность 1-й дистрибутив

тивный закон умножения ный закон

= (АА)В-\-АС = АВ-{-АС.

коммутативность идемпотентность

и ассоциативность умножения

умножения

§ 2. АЛГЕБРЫ БУЛЯ

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

А+В=В+А и АВ = ВА\

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

(А + В) + С = А + (В + С) и (AB) С = А (ВС);

ассоциaтивные законы

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

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

A -f А = А и АА = А.

идемпотентные законы

Кроме того, в алгебре множеств имеются два «особых» элемента (множества) О и / такие, что

А + 0 = А и Al = А\ А + 1=1 и /10-0.

Эти законы (правила действий) родственны привычным тебе законам алгебры чисел, но они не совпадают с этими законами; алгебра множеств — это, разумеется, тоже «алгебра», но не та, которую ты знал раньше, а новая, необычная.

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

по-прежнему называем сложением и умножением), но одинаковых по свойствам этих действий?

Ты, вероятно, уже предчувствуешь, что и алгебр, подобных алгебре множеств (т. е. алгебр, в которых действуют те же правила, что и в алгебре множеств), существует много,— и это действительно так. Прежде всего, сами алгебры множеств могут быть довольно разнообразными: можно говорить об «алгебре множеств учеников твоего класса», «алгебре множеств зверей в московском зоопарке» (это, разумеется, уже совсем другая алгебра!), «алгебре множеств (тех или других) чисел», «алгебре множеств точек квадрата» (см. рис. 3—10), «алгебре множеств книг в школьной библиотеке» или «алгебре множеств звезд на небе». Но существуют и совсем другие примеры алгебр со сходными свойствами,—и мы сейчас укажем некоторые из них.

Прежде чем перейти к этим примерам — минутку внимания. Начиная разбирать приведенные ниже примеры, ты должен твердо усвоить, что определить в каком-то множестве предметов (элементов) а, Ьу... операции сложения и умножения— это значит указать правила, по которым каждым двум предметам а и b сопоставляются еще два предмета cud, называемые суммой и произведением а и Ь:

с a + b, d = ab

Мы будем подбирать эти правила так, чтобы выполнялись все законы действий, характеризующие алгебру множеств. Но ты при этом не имеешь права спрашивать: а почему сумма а и b равна с? Ведь мы определяем сумму а+Ь именно как с, а об определениях, как известно, не спорят. Может быть, в некоторых случаях тебе наши определения покажутся странными — это естественно, так как эти определения будут новыми для тебя, а все новое, непривычное всегда кажется странным. В жизни тебя не удивляют сейчас даже такие поразительные вещи, как телевизор или телефон,— но это лишь потому, что ты к ним привык. А вот если учащемуся 2-го или 3-го класса, твердо знающему, что сумма двух чисел а и b — это число предметов в объединении совокупности а предметов и совокупности b предметов (см. рис. 1 на стр. 6), а произведение ab — это число предметов в объединении а совокупностей по b предметов в каждой (рис. 2, стр. 6), объяснить, что

такое дроби, и сказать, что сумма и произведение дробей a b и -т определяются так:

то ему эти правила (тебе-то теперь уже представляющиеся совершенно естественными!), наверное, покажутся весьма странными.

Итак — вот наши примеры.

Пример 1. Алгебра двух чисел. Примем, что в нашей алгебре имеются всего только два элемента, которые мы для удобства будем называть числами и обозначать знакомыми символами 0 и 1 (однако здесь эти символы имеют совершенно новый смысл). Умножение наших чисел мы определим в точности так же, как и в обычной арифметике, т. е с помощью следующей «таблицы умножения»:

а сложение — «почти как обычно», т. е. лишь с тем отличием от обыкновенной арифметики, что сумма 1 + 1 теперь будет равна не 2 (ведь этого числа в нашей «алгебре двух чисел» вовсе нет!), а снова 1. Таким образом, «таблица сложения» для нашей алгебры имеет вид

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

а + b = b + а и ab = ba для любых а и Ь.

Нетрудно проверить, что выполняются в ней и ассоциативные законы:

(а + Ь) + с = а + (Ь + с) и (ab) с = а (be) для любых a, ft и с, причем ассоциативный закон для умножения мы можем даже

не проверять: ведь наше новое умножение полностью совпадает с умножением чисел, для которого ассоциативный закон справедлив. Легко видеть, что и идемпотентные законы здесь имеют место:

а-\-а = а и аа = а для любого а,

т. е. для а=0 и для а= 1 (вот зачем мы положили 1 + 1 = 1!). Несколько труднее проверяются дистрибутивные законы:

(a + b)c = ас + be и ab + с =■■ (а + с) (b + с) для любых а, Ь, с.

Так, например, в нашей алгебре

(1 + 1). 1 = 1-1 =1 и (Ы) + (Ы) -1 + 1 = 1; (1.0+1 = 1 + 1 = 1 и (1 + 1)(1 + 1)= 1-1 =1.

Наконец, если условиться приписывать роль элемента О нашей алгебры числу 0, а роль элемента / — числу 1, то и правила, относящиеся к «особым» элементам О и /, будут иметь место: всегда (т. е. и при а=0, и при а~\)

а + 0 = а и а-1=а; о+ 1 = 1 и а-0 = 0.

Пример 2 Алгебра четырех чисел. Вот несколько более сложный пример того же рода. Предположим, что элементами алгебры являются четыре «числа», которые мы обозначим цифрами Ом 1, буквами р и Сложение и умножение в рассматриваемой алгебре зададим следующими таблицами:

Здесь также, как нетрудно убедиться непосредственной проверкой,

а + b — b + а и ab ba для любых а, Ь\ (а + Ь) + с = а + (Ь + с) и (ab) с = а (be) для любых а, Ь, с; (а + Ь)с = ас + be и + с = (а -f с)(Ь + с) для любых а, 6, с; а + а = а и аа=а для любого а (т. е. для а = 0, р, </, 1).

Кроме того, числа 0 и 1 играют здесь роль элементов О и / алгебры множеств, ибо для любого а

а + 0=а и а-1=--а; а+1 = 1 и а-0^0.

Пример 3. Алгебра максимумов и минимумов. Примем за элементы нашей алгебры какое-то (ограниченное) множество чисел, например, условимся считать, что элементами алгебры являются какие-то (быть может, в с е!) числа ху где 0<*<1, т. е. числа, заключенные между 0 и 1, включая сами числа 0 и 1. Что же касается операций сложения и умножения, то их мы определим совершенно новым способом: для того чтобы не спутать эти операции с обычными сложением и умножением, мы будем даже обозначать их новыми значками ф (сложение) и ® (умножение). А именно, условимся считать, что сумма х®у двух чисел х и у равна наибольшему из этих чисел (любому, если х = у)\ под произведением х®у чисел х и у мы условимся понимать наименьшее из этих чисел (любое, если х=--у). Так, например, если элементами нашей алгебры являются числа О, V3, V2, 2/3 и 1, то «таблица сложения» и «таблица умножения» наших чисел выглядят так:

В математике большее из двух или нескольких чисел и, часто обозначают так: max [и, о,...,г] (от латинского слова maximum — наибольший), а наименьшее из этих чисел — символом min[w, у,...,г] (от латинского слова minimum — наименьший)1). Таким образом, в нашей

1) max [и, и,..., г] и min lu, v,..., г] можно читать соответственно как «максимум от и, v,..., г» и «минимум от и, v..... г».

«алгебре максимумов и минимумов», по определению, XЭ# = max [х, у] и х®у = т'\п [х> у].

Можно также условиться обозначать числа точками числовой прямой; при этом числа ху где 0^л:<Л, изобразятся точками горизонтального отрезка длины 1 и сумма хфу двух чисел X и у будет изображаться правой из течек х> yt а их произведение х®у — левой точкой (рис. 11).

Рис. 11.

Ясно, что наши новые операции сложения и умножения удовлетворяют коммутативным законам:

*®У = У®х и х®у = у®х.

Выполняются также, очевидно, и ассоциативные законы:

{*®y)®z^x®{y®z) и (x®y)®z = x®(y®z)\

так, число (д:фг/)фг или х(В(у®г) (его можно обозначить и просто через *®*/®г без скобок) — это max [xyy,z] (рис. 12), а число (x®y)®z или x®(y®z) (или престо

Рис. 12.

x®y®z6e3 скобок) —это minU, у, z] (см. тот же рис. 12). Не менее ясно, что и идемпотентные законы имеют здесь место:

х@х = тах [л-, х]=г-х и х®х = \тп[х9 х] = х.

Проверим, наконец, справедливость дистрибутивных законов:

[x®y)®z = (x®z)®(y®z)

и

(X®y)®Z = (X@)Z)®(y(§)Z).

Ясно, что число

(*©#)®z = min{max[.y, r/], z)

равно г, если хоть одно из чисел х, у больше г, и равно большему из этих чисел, если оба они меньше z (рис. 13, а, б). Но в точности этому же равно и число

(x®z)(B(y®z) = max {min[jc, г], min[#, z]} (см. тот же рис. 13). Аналогично этому число

(je®у)0z = max {min[a-, y],z} равно г, если хоть одно из чисел х> у ме н ь ш е г, и равно

наименьшему из чисел х, у, если оба они больше z (рис. 14, а, б). Но этому же равно и число

(х®г) ®(у®г) ==min {max [х, z],max[#, г]}

(см. тот же рис. 14).

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

алгебры множеств играют здесь наименьшее из всех рассматриваемых чисел — число 0 и наибольшее из всех чисел — число 1. В самом деле, каково бы ни было число х, где O^jc^I, всегда

х0О = тах[х, 0]=х и х® 1 = min [х, l]=x; л:01=тах[л:, 1] = 1 и х®О = min[ху 0] = 0.

Пример 4. Алгебра наименьших кратных и наибольших делителей. Пусть N — какое угодно целое положительное число; за элементы нашей новой алгебры мы примем всевозможные делители числа Л/; так, например,

Рис. 13.

Рис. 14.

если Л/=^210=2-3-5-7, то элементами рассматриваемой алгебры являются числа 1, 2, 3, 5, 6, 7, 10, 14, 15, 21, 30, 35, 42, 70, 105 и 210. Сложение и умножение наших чисел мы сейчас определим совсем по-новому: под суммой тфп чисел m и п мы будем понимать их наименьшее общее кратное — наименьшее целое (положительное) число, которое делится на оба числа m и п\ за произведение т®п чисел m и п мы примем наибольший общий делитель этих чисел — наибольшее целое число, на которое делятся и m, и п. Так, если N=6 и наша алгебра содержит всего четыре числа 1,2, 3 и 6, то сложение и умножение чисел задаются следующими таблицами:

В «высшей арифметике» (теории чисел) наименьшее общее кратное двух или нескольких чисел m, /г,..., s часто обозначают через [m, n,...,s], а наибольший общий делитель тех же чисел — через (m, az,...,s). Таким образом, в нашей алгебре, по определению,

tn Q)п ~ [т, п] и т®п = (т, п).

Например, если алгебра содержит числа 10 и 15, то

Юф 15 = [10, 15]-30 и 10(g) 15 = (10, 15) = 5.

Очевидно, что в нашей алгебре всегда

mQ)п = п(Вт и т®п = п®т.

Далее, здесь

(т®п)®р = т®{п®р) ( = [т, п, р))

(это число можно условиться обозначать просто как т®п®р без скобок) и

(т®п)® р = т®(п® р) ( = (т, л, р)) (это число можно обозначить просто через т®п®р). Не менее очевидны и идемпотентные законы:

m0m = [m, т] = т и т®т = (т, т) = т.

Несколько сложнее (как всегда) проверяются дистрибутивные законы. Число

(m©n)®p = ([m, п], р)

есть не что иное, как наибольший общий делитель числа р и наименьшего общего кратного чисел тип (вдумайся в это выражение хорошенько!); оно содержит те и только те простые множители, которые входят в состав р и одновременно в состав хоть одного из чисел m и п. Но ясно, что эти (и только эти) простые множители входят и в состав числа

(т®р)®(п®р) = [(т, р), (n, р)]; поэтому всегда

(m©Ai)®p = (m®p)©(Ai®p).

Так, например, черпая запас чисел из множества делителей числа 210, имеем

(10014)® 105 = ([10, 14], 105) = (70, 105) = 35

и

(10® 105)©(14® 105) =[(10, 105), (14, 105)] = [5, 7] = 35.

Аналогично этому число

(m®Az)0p = [(m, ai), р]

— наименьшее общее кратное числа р и наибольшего общего делителя чисел тип — содержит те и только те простые множители, которые входят либо в состав р, либо в состав обоих чисел m и п (а может быть — и в состав ру и в состав обоих чисел m и я). Но в точности эти же множители содержит и число

(т©р)® (л0р) = ([т, р), [ai, р]); поэтому всегда

(m ® п) © р - (m 0 р) ® (ai 0 р). Так, например,

(10® 14)©105 = [(10, 14), 105] = [2, 105] = 210

и

(10©105)®(14® 105) = ([10, 105], [14, 105]) =

= (210, 210) = 210.

Наконец, роль элементов О и I алгебры множеств играют здесь самое маленькое из рассматриваемого набора чисел — число 1 и самое большое — число Л/. В самом деле, очевидно (не забудь, что в нашу алгебру входят лишь делители числа /V),

тф1 1] = т и m®N = (m, N) = т\

m®N=[m, N\ = N и /я® 1 (/я, 1)=1.

Таким образом, и здесь выполняются все законы алгебры множеств.

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

Переходя теперь к изучению общих свойств всех таких алгебр, нам следует, прежде всего, дать им какое-то общее наименование. Поскольку алгебры со столь странными свойствами впервые рассматривал замечательный английский математик XIX столетия Джордж Буль1), то в настоящее время все такие алгебры принято называть алгебрами Буля2). Для основных операций алгебры Буля мы по-прежнему сохраним наименования «сложение» и «умножение» (но ты должен помнить, что это вовсе не обычное сложение и обычное умножение чисел!); однако иногда мы будем называть эти операции также булевским сложением и булевским умножением.

Сочинение Дж. Буля, в котором подробно исследовалась та необыкновенная алгебра, которой посвящена эта брошюра, впервые вышло в свет в 1854 г., т. е. больше 100 лет тому назад; называлось это сочинение так: «Исследование

1) Отец известной английской писательницы Этель Лилиан Буль (больше известной под фамилией Войнич — ее мужем был польский революционер М. Войнич), автора романа «Овод».

2) Точное определение алгебр Буля вынесено нами в Приложение (см стр. 66, 67)

Джордж Буль (1815—1864).

законов мысли» («Investigation of the laws of thought). Пока это название кажется тебе, вероятно, странным - однако, прочитав настоящую книжку, ты поймешь, какое отношение имеют рассматриваемые здесь удивительные алгебры к законам нашего мышления. Заметим только, что именно связь алгебр Буля с «законами мысли» объясняет, почему сочинение Буля, первоначально мало замеченное математиками, вызывает сегодня такой огромный интерес. В последние годы это сочинение много раз переиздавалось и переводилось на разные языки, а само понятие алгебры Буля в том или ином виде во многих странах уже вошло в школьный курс математики; в других же странах, в том числе и у нас, включение этого понятия в курс средней школы в настоящее время активно обсуждается и имеет горячих сторонников среди математиков и педагогов.

Упражнения

1. Проверь непосредственно, что для всех троек элементов «алгебры Буля с двумя числами» (пример 1, стр 21) справедливы оба дистрибутивных закона.

2. Проверь оба дистрибутивных закона для нескольких троек элементов «алгебры Буля с четырьмя числами» (пример 2, стр. 22).

3. а) Если в твоей квартире, кроме тебя, нет школьников, то все «множества школьников из твоей квартиры» таковы: множество / из одною школьника и множество О, совсем не содержащее школьников (пустое множество).Составь для «алгебры множеств школьников, проживающих в твоей квартире» (эта алгебра имеет всего два элемента, О и /) «таблицу сложения» и «таблицу умножения» и сравни ее с таблицами на стр 21; выведи отсюда, что для рассмотренной в примере 1 этого параграфа «алгебры двух чисел» действительно выполняются все законы алгебры Буля

б) Пусть в одной квартире живут два школьника — Петя и Катя Тогда «алгебра множеств проживающих в этой квартире школьников» содержит четыре элемента: множество / из двух школьников; два множества Р (Петя) и Q (Катя), каждое из которых состоит из одного школьника; пустое множество О. Составь «таблицу сложения» и «таблицу умножения» для этой алгебры множеств и сравни ее с таблицами на стр. 22; выведи отсюда, что для рассмотренной в примере 2 этого параграфа «алгебры четырех чисел» справедливы все законы алгебры Буля.

4. Проверь, что

5. а) Составь «таблицу сложения» и «таблицу умножения» для алгебры Буля из грех чисел 0,и 1, где хфг/=гпах \х, у] и х)£/у= min [х, у]\ проверь для этой алгебры выполнимость законов алгебры Буля.

б) Составь «таблицу сложения» и «таблицу умножения» для алгебры делителей числа 12, где тфм= [ш, п] и т®п=(т, п)\ проверь для этой алгебры выполнимость некоторых из законов алгебры Буля.

6*. Пусть разложение на простые множители (целого положительного) числа N имеет вид

тогда любые два делителя m и п этого числа можно записать в виде

т = ра1* ра2< ... pj*, где (Хя, 0<flt< Ä2.....0^ak^ Ak,

и

п = р*[*р\* ... p£\ где 0<bj < Ль 0<д2<Л2> ... , О^Ь^Л*

(некоторые из чисел ал, а2,..., ak; bx, ö2,..., bk могут быть равными нулю). Какой вид имеют в этом случае разложения на простые множители чисел [m, п] (наименьшее общее кратное чисел m и п) и (m, п) (наибольший общий делитель чисел m и л)? Воспользуйся этими разложениями для того, чтобы доказать, что множество всех делителей числа N с операциями шф/2= [m, /г] и m(g)/*=(m, я) образует алгебру Буля

§ 3. ДАЛЬНЕЙШИЕ СВОЙСТВА АЛГЕБР БУЛЯ: ПРИНЦИП ДВОЙСТВЕННОСТИ; БУЛЕВСКИЕ РАВЕНСТВА И НЕРАВЕНСТВА

Продолжим изучение необыкновенной алгебры, которую мы назвали алгеброй Буля. Прежде всего, бросается в глаза полный параллелизм свойств булевского сложения и булевского умножения: эти операции настолько похожи, что в каждой (разумеется, правильной!) формуле алгебры Буля можно заменить сложение умножением и наоборот — и равенство останется верным. Так, например, в алгебре Буля выполняется равенство

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

которое было доказано выше (см. пример, разобранный в конце упражнений к § 1, стр. 18). Заменив в этом равенстве сложение умножением и наоборот, мы получим

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

— и это равенство тоже является справедливым (см. ниже, стр. 33). Надо только иметь в виду, что если в каком-либо равенстве алгебры Буля фигурируют «особые» элементы О и I', то при замене булевского сложения булевским умножением и наоборот элемент О мы должны заменить на /, а I

— на О. Так, например, из справедливости равенства

(А + В) (А + I) + (А + В) (В + О) - А + В

(см. упр. 8 на стр. 18) следует, что имеет место также и равенство

(АВ + А0)(АВ + В1) = AB.

Сформулированное свойство алгебр Буля, позволяющее «даром» (т. е. без доказательства) получать из каждого равенства новое1), называется принципом двойственности, а равенства, которые получаются одно из другого с помощью этого принципа,— двойственными друг другу. Принцип двойственности следует из того, что список основных законов алгебры Буля, на которые мы только и имеем право опираться при доказательстве тех или иных булевских формул, совершенно «симметричен»: наряду с каждым законом в него входит также и еще один, двойственный первоначальному, т. е. получаемый из первого заменой сложения умножением и наоборот, элемента О элементом / и наоборот. Так, коммутативному закону для сложения двойственен коммутативный закон для умножения; ассоциативному закону для сложения двойственен ассоциативный закон для умножения; идемпотентному закону для сложения двойст-

1) «Новое» равенство, получающееся из какой-либо формулы алгебры Буля заменой сложения умножением и наоборот, может иногда и совпадать с первоначальным,— и в этом случае никакой выгоды наш прием не приносит. Так, например, верное равенство (упр. 6, стр. 18)

(А + В) {В + С) (С + Л)= АВ + ВС + СА при замене сложения умножением и наоборот переходит в равенство

АВ + ВС + СА =• {А + В)(В + С) (С + А), совпадающее с исходным, а равенство (упр. 7, стр. 18)

(А + В)(В + С) (C + D) = АС + ВС + BD при замене умножения сложением и наоборот переходит в равенство

AB + BC + CD = (A + C)(B+C)(B + D),

лишь несущественно отличающееся от исходного (оно переходит в исходное равенство при замене буквы В буквой С и буквы С буквой В).

венен идемпотентный закон для умножения; первому дистрибутивному закону двойственен второй дистрибутивный закон; наконец, равенствам Л+0=Л и Л + /=/ двойственны, соответственно, равенства Л/=Л и АО=0. Поэтому если при доказательстве какого-либо равенства мы пользовались теми или иными из основных законов алгебры Буля, то, используя двойственные им законы, мы сможем точно так же доказать и равенство, двойственное первоначальному.

Пример. Докажем равенство

А + АС+ ВС = {А+ В) (Л + С), двойственное равенству

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

В самом деле,

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

ассоциативность 1-й дистрибутивный

сложения закон

(А + В)С + А = [(А + В)+А\ (С+А) =

коммутативность 2-й дистрибутивный

сложения закон

= ца + А) + В](А+С) = [А+В)(А + С)

коммутативность и идемпотентность

ассоциативность сложения

сложения

(сравни с доказательством равенства Л(Л+С)(В+С)= АВ+АС на стр. 18).

Другое доказательство принципа двойственности связано с наличием в алгебре Буля специальной операции, которая переводит каждый элемент А этой алгебры в новый элемент А и при этом заменяет сложение умножением и наоборот. Другими словами, эта операция (будем называть ее операция «черта») такова, что

А + В=~АВ и ~АВ = ~А + ß.

Далее

0 = 1 и Т =0.

Наконец, элемент А операция «черта» переводит в первоначальный элемент Л, т. е. для каждого элемента А алгебры Буля

Л = ( Л) = Л.

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

Из самого определения дополнения А множества А следует, что

и что

(см. тот же рис. 15; последние два равенства могут даже служить определением множества А). Очевидно также, что

5 = /, 7=0.

Докажем, наконец, что в алгебре множеств выполняются самые важные свойства операции «черта»:

А + В = AB и АВ = Ä+ ß;

эти правила называются правилами де Моргана по имени современника и сподвижника Джорджа Буля английского

Рис. 15.

математика Аугустуса де Моргана (1806—1871). На рис. 16, а линиями с наклоном влево заштрихована фигура (множество) Л, а на рис. 16, б линиями с наклоном Вправо — ее дополнение А до полного квадрата /; горизонтальными линиями на рис. 16, а заштрихована фигура (множество) ß, а вертикальными линиями на рис. 16, б — ее дополнение ß. При этом заштрихованной на рис. 16, а оказывается фигура Л + ß, а дважды заштрихованной на рис. 16, б — фигура ÄB. Но из сравнения рис. 16, а и 16, б видно, что фигура, дважды заштрихованная на рис. 16,6, дополняет заштрихованную на рис. 16, а фигуру, что и доказывает первое правило де Моргана:

~Ä+~B = AB.

С другой стороны, двойной штриховкой на рис. 16, а покрыта фигура AB; заштрихована же на рис. 16, б фигура А-\-В. Но эти две фигуры (множества) также, очевидно, являются дополнением одна другой, т. е.

ТВ = Ä+ В.

Укажем теперь смысл операции «черта» для других рассмотренных выше примеров алгебр Буля. Так, в алгебре двух чисел (пример I на стр. 21)

0 = 1, 1=0.

Рис. 16.

При этом, очевидно, для любого элемента а этой алгебры (т. е. для а =0 и для а= 1) а—а. Далее из сравнения «таблицы сложения» и «таблицы умножения», составленной для чисел 0=1 и 1 = 0:

следует, что во всех случаях aJrb=a b. Аналогично проверяется и второе правило де Моргана: аЬ=а-{-Ь.

В алгебре четырех чисел (пример 2 на стр. 22)

0 = 1, р = <7, q=--p, Т=0.

При этом опять, очевидно, а=а для любого элемента а нашей алгебры. Для проверки соотношения a+b=a b достаточно по-прежнему сравнить две таблицы:

Аналогично проверяется и соотношение ab=aJrb.

Обратимся теперь к алгебре максимумов и минимумов, элементами которой являются такие числа х, что O^Jt^J, а булевское сложение ф и булевское умножение ® определяются так:

Xфу — max \хл у\л х®у—т'\п[ху у]. Для того чтобы в этой алгебре имели место правила де Моргана

т. е. чтобы было

max [х, у] = т\п[х, у], min [х, у] = тах [ху у],

надо только, чтобы операция «черта» обращала порядок элементов, т. е. чтобы из условия х^у следовало бы х^у (почему?). Поэтому если элементами алгебры служат все числа ху где 0^#^;1, то

можно, например, положить

х- 1 —х\

другими словами, можно считать, что точка х симметрична точке х относительно середины 1/2 отрезка [0, 1] (рис. 17). В таком случае, очевидно,

0=1, 1 = 0

и

X = X.

Разумеется, имеют место и правила де Моргана:

(см. рис. 18, а, б).

Наконец, рассмотрим алгебру наименьших кратных и наибольших делителей, элементами которой

являются всевозможные делители целого положительного числа N, а булевское сложение ф и булевское умножение® определяются так:

m п=\т, л], m (X) п = (m, п),

где [m, п] — наименьшее общее кратное чисел m и л, a (m, /г) — их наибольший общий делитель Положим здесь

- N m — — ; m

например, в разобранном выше случае N=2\0

Т = 210, 2= 105, 3 = 70, 5 = 42, 6 = 35, 7 = 30, Ш=21, Î4 = 15, 15= 14, 2Î= 10, 30 = 7, 35 = 6, 42 = 5, 70 = 3, 105 = 2. 2ÎÔ = 1. Ясно, что при этом

Т = Л/ и 7v = 1.

Кроме того, очевидно,

- N т = —— = т. N/m

Имеют здесь место и правила де Моргана:

тфп = т® п и ш0п = /пфп;

Рис. 17.

Рис. 18.

так, например,

6ф21 = [6, 21] = 42 и 6®2Ï = 35® 10-= (35, 10) = 5, а 42 = 5

и

6®21=(6, 21) = 3 и 6ф)2Г=35ф10 = [35, 10] = 70, а 3 = 70.

Полное доказательство правил де Моргана мы предоставим читателю провести самостоятельно (см., впрочем, упр 6 на стр. 43).

Пусть теперь, мы имеем какое угодно равенство, выполняющееся в любой алгебре Буля, например, знакомое уже нам равенство

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

Применив к обеим частям этого равенства операцию «черта», получим

А (А + С) (В + С) - Ло + АС. Но, в силу правил де Моргана, А(А +C)(ß+C) =ЩА+Щ(В + С) =_

= A(A+C) + B+C=A + A+ C + BC = 1+ÄC + BC

и

AB + АС = ÄB ■ АС = (А+Ъ) (А+ С).

Таким образом, окончательно имеем

Л + АС + ВС-~=(А + В) (А +С).

Но так как это равенство выполняется при любых Л, В и С, то оно останется справедливым, если элементы Л, В и С нашей алгебры Буля мы будем обозначать просто буквами Л, В и С,— а при этом мы как раз придем к равенству

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

двойственному первоначальному равенству.

Вот как из свойств операции «черта» (в первую очередь из правил де Моргана) вытекает принцип двойственности! При этом только надо не забывать, что если исходное равенство содержало «особые» элементы О или /, то, в силу равенств

0 = / и /=0,

в преобразованном (двойственном) равенстве на месте О будет стоять /, а на месте / будет стоять О.

Так, например, применив операцию «черта» к обеим частям равенства

А (А + 1)(В + 0)=АВ (см. упр. 5 на стр. 18), получим

А (А + 1)(В + 0) = АЛ

или, так как

A(A + l)(B + 0) = A{A + l) + TT+Ö=Ä+A+7 + В + 0==

= J+ Â1 + BÔ = А + АО+ BI

и

— равенство

А + АО + В1 = А + В.

Но последнее равенство (в котором ведь А и В произвольны!) равносильно следующему:

А + АО + В1 = А + В,

получаемому из первоначального равенства заменой суммы произведением и наоборот, а также заменой О на I и наоборот.

Замечательно, что принцип двойственности имеет даже еще более широкую область применимости, чем мы установили: наряду с булевскими равенствами он может применяться и к «булевским неравенствам». Однако для того, чтобы пояснить это, нам надо будет прежде ознакомиться с еще одним понятием, играющим в теории алгебр Буля очень большую роль.

В каждой алгебре Буля наряду с понятием равенства элементов этой алгебры (причем равенство А = В означает, что А и В — это просто один и тот же элемент алгебры Буля!) существует еще одно важное отношение между элементами, играющее примерно ту же роль, которую в алгебре чисел играет отношение «больше» (или «меньше»). Это отношение обозначают символом гэ (или cz) и пишут

A ZD В или В а А

(последние два соотношения имеют один и тот же смысл; заметь, что по написанию они близки к записям а>Ь или &<а); в алгебре множеств AzdB означает, что множество А содержит множество В в качестве своей части (рис. 19). Так, например, если А2 — это множество четных чисел, а Ай — множество целых чисел, делящихся на 6, то, очевидно, Л2гэЛв; точно так же если А — это множество успевающих учеников твоего класса, a В — множество отличников,

то, разумеется, AzdB. Надо только иметь в виду, что в том случае, когда множества А и В совпадают, мы тоже будем писать Aid В: ведь и в этом случае множество

В целиком содержится в множестве А \ Таким образом, отношение гэ для элементов алгебры Буля более близко не к отношению > («больше») для чисел, а к отношению ^ («больше или равно»). Ясно, что если Д d ß и S d С, io A zd С (рис. 20); подобно этому для чисел из соотношений а^Ь и Ь^с следует, что а^с. Далее,

если A ZD В и В z> А, то Л = В,

подобно тому как для чисел из соотношений а^Ь и Ь^а вытекает, что а=Ь. Наконец (и это для нас особенно важно!),

если Л:эВ, то Ad В

(рис. 21). Так, из того, что множество успевающих учеников больше множества отличников, вытекает, что множество неуспевающих учеников содержится в множестве тех учеников, которые не являются отличниками.

Рис 19. Рис. 20.

Рис. 21

До сих пор мы подчеркивали сходство отношения для множеств и отношения ^ для чисел. Укажем теперь одно существенное различие этих отношений. Любые два (действительных) числа а и b можно сравнить между собой, т. е. хоть одно из отношений а^Ь и Ь^а обязательно имеет место1). В противоположность этому для двух множеств А и ß, как правило, не выполняется ни одно из соотношений AzdB и В=эЛ (рис. 22).

Заметим еще, что для любого элемента А алгебры множеств

и что всегда (при любых А и В)

A + BzdA, АВаА (рис. 23).

Укажем смысл отношения z> для других известных нам алгебр Буля. Для «алгебры двух чисел» (пример 1 на стр. 21) это отношение устанавливается условием

1=>0,

Рис. 22.

Рис. 23.

1) Если имеют место сразу оба эти отношения, то числа а и b равны.

а для «алгебры четырех чисел» (пример 2 на стр. 22) — условиями 1з0, 1зр, 1з</. piD 0 и 730 (элементы р a q этой алгебры несравнимы, т. е. не имеет места ни одно из соотношений /?3<? и qZDp) Для «алгебры максимумов и минимумов» (пример 3 на стр 23) отношение з совпадает с отношением мы считаем, что элементы х и у этой алгебры связаны соотношением до*/, если число X не меньше числа у (так, например, здесь-i-Зу и 1з1)1)

Наконец, в «алгебре наименьших кратных и наибольших делителей» (пример 4 на стр. 25) отношение тзм означает, что число п является делителем числа т; так, например, здесь 42з6, в то время как числа 42 и 35 в этой алгебре несравнимы (т. е. не имеет места ни одно из отношений 42з35 и 42cz35). Предоставляем читателю самому проверить, что определенное таким образом отношение з в каждой из перечисленных алгебр Буля обладает всеми отмеченными нами свойствами отношения з в алгебре множеств.

Булевским неравенством естественно называть формулу, левая и правая части которой связаны отношением з (или с:) Мы при этом будем говорить лишь о тех неравенствах, которые справедливы при всех значениях, входящих в это неравенство элементов Л, ß, С,... алгебры Буля, вроде отмеченных выше неравенств /зЛ, ЛзО, A + BzdA или Лз/lß. Принцип двойственности утверждает, что, заменив в таком неравенстве сложение умножением и наоборот, элемент О (если он входил в наше неравенство) — элементом I и наоборот и поменяв знак неравенства на обрamный (т. е. заменив отношение з отношением cz), мы снова придем к верному (т. е. выполняющемуся при всех значениях входящих в него элементов алгебры Буля) неравенству. Так, например, из того, что

(А +В) (А + С) (А + /)зЛВС (см. упр. 86 на стр. 44), следует, что всегда АВ + АС+ AOœA + B+C.

Для доказательства принципа двойственности достаточно применить к обеим частям исходного неравенства операцию «черта». Так, из того, что имеет место неравенство (Л+ В)(А+С)(А+ I)z>ABC,

1) В этой алгебре Буля для любых двух элементов х и у алгебры всегда имеет место хоть одно из отношений xZDy и t/3*.

и из правила: «если AzdB, то ЛсгВ» следует, что справедливо также неравенство

{А 4 В) (А + С){А -b/)cMßC.

Но, в силу правил де Моргана, учитывая, что /=0, получаем

(А + В)(А+С){А + 1) = (А + В)(А + С) + 1+1 =

= Я 7= Л В -f- А С + АО.

Аналогично

1ВС = А +В + С.

Таким образом, мы заключаем, что при любых Л, В и С имеет место неравенство

АВ + А С+АОаА + В-\ С

А так как и Л, ß, С здесь произвольны, то их можно обозначить просто через Л, £ и С- Таким путем мы и приходим к неравенству

АВ+ АС+ АОаА + В + С, двойственному первоначальному неравенству в описанном выше смысле.

Упражнения

1. Выпиши равенства, двойственные всем равенствам, доказательство которых составляет содержание упр 1 — 10 на стр 18.

2. Докажи следующие тождества алгебры множеств:

а) (А+В)(А f ß)r 4L

б) AB + iA-\-B)(A -\-В)=А + В\

в) 1ВС_1В ЛС=0; г)* Л + ЛЯ=.4 + в.

3. Докажи, что если в какое-либо равенство алгебры Буля входит операция «черга» то справедливо также равенство, в котором каждое булевское сложение заменено булевским умножением и наоборот, каждый элемент О (если он входит в наше равенство) заменен элементом / и наоборот, но операция «черта» оставлена на каждом месте, на котором она фигурирует в первом равенстве. [Пример: из тождества упр 2 в следует, что

А + В+С + Ä+B + Л + С=/,

каковы бы ни были элементы А, В, С алгебры Буля.]

4. Какие равенства получаются с помощью описанного в упр. 3 принципа двойственности из равенств упр 2 а, б, г?

5. Проверь, что в «алгебре четырех чисел» (пример 2 на стр 22) выполняется второе правило де Моргана: аЬ—а+Ь.

6* а) Пусть N=pxp» ..pÄ< где все простые числа ръ /?2,..., ^различны. Докажи, что в этом случае «алгебра наименьших кратных и наибольших делителей», элементами которой служат делители числа N (см. пример 4 на стр. 25), сводится к «алгебре подмножеств универсального множества 1—{р\,Р2.....Рь\*> выведи отсюда, что в такой

«алгебре наименьших кратных и наибольших делителей» выполняются все законы алгебры Буля, включая сюда и правила де Моргана.

б) Пусть N = рА, где р — простое число, А — целое положительное. Докажи, что в этом случае «алгебра наименьших кратных и наибольших делителей», элементами которой являются делители числа N. сводится к «алгебре максимумов и минимумов», определенной в множестве чисел 0. 1,2, ... Л. Выведи отсюда, что для такой «алгебры наименьших кратных и наибольших делителей» справедливы все законы алгебры Буля, включая и правила де Моргана

в) Пусть N=p* рА*...рА\ а/п=руа*. .р£'\ гдеОся^^, 0<я2< <^А2.....0<а,^у4.(ср упр 6 на стр 31) Какой вид имеет разложение на простые множители числа т==—? Воспользуйся полученной формулой

для доказательства правил де Моргана в общей «алгебре наименьших кратных и наибольших делителей».

7* В каких из известных тебе алгебр Буля выполняются равенства

Ai = l и Л.4 = 0,

а в каких не выполняются?

8. Докажи следующие неравенства алгебры множеств:

а) А+В+С^(А+В)(А+С)\

б) (A+B){A+C)(A+/)z:ABC\

в) {A+B)(B+C)(C+A)Z)ABC;

г) A+BZDAB+ AB.

9. Выпиши неравенства, получаемые из неравенств упр 8 а —в по принципу двойственности; докажи эти неравенства непосредственно, не обращаясь к принципу двойственности

10. Докажи, что если булевское неравенство содержит операцию «черта», то справедливо также неравенство, получаемое из исходного заменой булевскою сложения булевским умножением и наоборот, а элемента О элементом / и наоборот, но сохраняющее операцию «черта» на каждом месте, на котором стояла она в исходном неравенстве; при этом знак неравенства меняется на обратный Примени этот принцип для образования нового неравенства из неравенства упр 8 г

11. Проверь все свойства отношения з для

а) «алгебры максимумов и минимумов»;

б) «алгебры наименьших кратных и наибольших делителей». 12*. Пусть множества А и В таковы, что AzdB Упрости выражения: а) А+В\ б) АВ\ в) А+В\ г) ~ÄB

§ 4. МНОЖЕСТВА И ВЫСКАЗЫВАНИЯ; АЛГЕБРА ВЫСКАЗЫВАНИЙ

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

ный способ, при котором просто указываются все элементы рассматриваемого множества: так, можно говорить о «множестве школьников: Саша, Сеня, Миша и Катя»; о «множестве чисел: 1, 2, 3, 4, 5» или о «множестве четырех действий арифметики: сложение, вычитание, умножение и деление». В математике принято, указывая все элементы какого-либо множества, заключать их в фигурные скобки; так, можно писать

А = {Саша, Сеня, Миша, Катя}; В = {1, 2, 3, 4, 5}

или С = { + , — , X , :}

(в последней записи знаки действий символизируют сами действия)1).

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

Гораздо более распространен иной, неявный или описательный способ задания множеств, при котором мы указываем свойство, характеризующее все элементы рассматриваемого множества: так, можно говорить о «множестве всех отличников твоего класса» (возможно, что это и есть фигурирующее выше множество А) или о «множестве всех целых чисел х таких, что 0<х^5» (это и есть множество В), или о «множестве всех зверей в московском зоопарке». При этом описательный способ задания множества вполне годен и для выделения бесконечных множеств вроде «множества всех целых чисел» или «множества всех треугольников площади 1»; более того, как мы уже отмечали выше, бесконечные множества можно задавать только описательным способом.

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

1) См. также упр. 6а на стр. 43.

метов (объектов), которые нас только и интересуют (например, множество школьников твоего класса или множество целых чисел), и затем формулируем некоторое высказывание, которому удовлетворяют все элементы рассматриваемого множества и только они; если нас интересуют лишь множества школьников твоего класса, то такими высказываниями могут быть: «он отличник», «он умеет играть в шахматы»; «он сидит в первом ряду», «его зовут Андрей» и т. д.

Рис. 24.

Множество А всех таких элементов рассматриваемого универсального множества / (множества школьников, множества чисел и т. д.), которые удовлетворяют свойству, составляющему содержание данного высказывания а, называется множеством истинности данного высказывания (см. например, рис. 24)1).

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

1) Высказывания мы всегда будем обозначать малыми буквами латинского алфавита, а отвечающие им множества истинности — предпочтительно теми же самыми большими буквами латинского алфавита.

такое утверждение, о котором можно судить, истинно ли оно (в применении к определенному элементу рассматриваемого универсального множества) или ложно, Таким образом, фразы «он имеет две головы и шестнадцать рук» или «2x3=6» являются высказываниями (вторая из этих фраз даже вообще не зависит от выбора универсального множества /), а лозунг «Да здравствует Первое мая!» или междометие «Ох!», разумеется, высказываниями не являются.

Поскольку высказывания интересуют нас только с точки зрения описываемых ими множеств, то два высказывания, а и ft, которым отвечает одной то же множество истинности, мы не будем различать, будем считать одинаковыми. Если высказывания а и b (например, «он — отличник» и «он имеет только отличные оценки» или «число х нечетно» и «число х при делении 2 дает остаток 1») являются одинаковыми, то мы будем писать

а = Ь.

При этом одинаковыми придется считать все тождественно истинные (или бессодержательные) высказывания, т. е. высказывания, которые являются истинными всегда, независимо от того, какой элемент множества / мы рассматриваем: так, тождественно истинными являются высказывания «2x3=6», «он (ученик твоего класса) — мальчик или девочка», «его (ученика) рост не превосходит 3 ж» и т. д. Все истинные высказывания мы условимся обозначать буквой /. Одинаковыми мы будем считать и все тождественно ложные (или противоречивые) высказывания, не имеющие места никогда, т. е. высказывания, множество истинности которых пусто. Примерами таких высказываний, которые мы будем обозначать буквой о, могут служить следующие высказывания: «2x2=6», «он (ученик твоего класса) умеет летать», «его рост превосходит 4 м», «оно (число) больше 3 и меньше 2».

Связь между множествами и высказываниями позволяет определить для высказываний своеобразные алгебраические операции, родственные введенным выше операциям алгебры множеств. А именно, суммой двух высказываний а и b мы назовем высказывание, множество истинности которого совпадаете суммой множества истинности А высказывания а и множества истинности В высказывания Ь\ это высказывание мы условимся обозначать

символом a+b1). Но ведь сумма двух множеств — это просто объединение всех входящих в оба множества элементов; поэтому сумма высказываний а и b — это высказывание «а или 6», где предлог «или» означает, что справедливо либо высказывание а, либо высказывание Ь, либо, наконец, оба эти высказывания вместе. Так, например, если высказывание а гласит: «он умеет играть в шахматы» — и в твогм классе этому высказыванию отвечает множество истинности

А = {Саша, Сема, Миша, Андрюша, Катя, Шура, Лена},

а высказывание b гласит: «он умеет играть в шашки» — и имеет множество истинности

В= {Саша, Миша, Петя, Игорь, Катя, Света},

то a+fc — это высказывание «он умеет играть в шахматы или он умеет играть в шашки» (короче, «он умеет играть в шахматы или в шашки») — и этому высказыванию отвечает множество истинности

A -f В — {Саша, Сема, Миша, Андрюша, Петя, Игорь, Катя, Шура, Лена, Света}.

Если универсальное множество — это множество изображенных на рис. 24 фигур и высказывания cud имеют смысл: «она (фигура) круглая» и «она заштрихованная», то высказывание c+d гласит: «она (фигура) круглая или заштрихованная» (рис. 25).

Рис. 25.

1) В математической логике сумма двух высказываний а и b обычно называется дизъюнкцией этих высказываний и обозначается символом а\/Ь (сравни с обозначением A\JB для суммы множеств Л и В).

Аналогично этому произведением ab высказываний aube множествами истинности А и В мы будем называть такое высказывание, множество истинности которого совпадает с произведением А В множеств А и В1). Но произведение двух множеств А и В — это их пересечение или общая часть, содержащая те и только те элементы, которые входят в оба множества А и В; поэтому произведение ab высказываний aw b — это высказывание «а и Ь», где предлог «и», как всегда, означает, что истинны оба высказывания: и а, и Ь. Так, например, если высказывания а и Ь, касающиеся школьников твсего класса, имеют тот же смысл, что и выше, то высказывание ab гласит: «он умеет играть в шахматы и он умеет играть в шашки» (короче, «он умеет играть в шахматы и в шашки») — и этому высказыванию отвечает множество истинности

ЛВ^{Саша, Миша, Катя}.

Если относящиеся к изображенному на рис. 24 множеству фигур высказывания cud имеют смысл «она (фигура) круглая» и «она заштрихованная», то высказывание cd означает, что «она (фигура) круглая и заштрихованная» (рис. 25).

Связь между множествами и высказываниями позволяет перенести на высказывания все правила алгебры множеств:

а-\-Ь — Ь + а, ab = ba;

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

(а + Ь) + с = а + (Ь + с), (ab) с = а (Ьс)\

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

(а + Ь) с = ас + be, ab + c=-(a + с) (b + с);

дистрибутивные законы алгебры высказываний

а-\- а — а, аа — а.

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

Кроме того, если / — тождественно истинное высказывание, а о — тождественно ложное высказывание, то всегда (т. е. при любом высказывании а)

а-{-о = а, ai = a;

a + i = i, ао — о.

1) В математической логике произведение высказываний а и b чаще называют конъюнкцией этих высказываний и обозначают символом а/\Ь (сравни с обозначением А(]В для произведения множеств А и В).

Так, например, высказывание «он отличник или он имеет две головы» равносильно высказыванию «он отличник», а высказывание «он умеет плавать и он моложе 200 лет» — высказыванию «он умеет плавать»1).

Для того чтобы понять, каким образом правила алгебры высказываний выводятся из правил алгебры множеств, рассмотрим, например, второй дистрибутивный закон. Так как множество истинности суммы двух высказываний представляет собой сумму множеств истинности этих высказываний, а множество истинности произведения высказываний — произведение их множеств истинности, то множество истинности сложного высказывания ab-\-c — высказывания «имеют место „а и Ь"или с»— есть АВ\С, где Л, В и С — соответственно множества истинности высказываний a, b и с. Аналогично этому множество истинности (сложного) высказывания (а-\-с)(Ь-\-с) —это множество (Л+С)(В+С). Но, в силу второго дистрибутивного закона алгебры множеств,

Таким образом, множества истинности высказываний ab-\-c и (а-\-с)(Ь~гс) совпадают — но это и означает, что высказывания ab-\-c и (а+с)(Ь-\-с) одинаковы! [См. также стр. 15, где мы указывали, что высказывания «он умеет играть в шахматы и в шашки или умеет плавать» и «он умеет играть в шахматы или умеет плавать, а также умеет играть в шашки или умеет плавать» имеют один и тот же смысл, т. е. что

где высказывания a, b и с имеют смысл: «он умеет играть в шахматы», «он умеет играть в шашки» и «он умеет плавать».]

Наряду с операциями сложения и умножения множеств можно перенести в алгебру высказываний и операцию «черта». При этом под а следует понимать высказывание, множеством истинности которого является множество Л, где А — множество истинности высказывания а. Другими словами, условию а должны удовлетворять те и только те элементы универсального множества /, которые не входят

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

гз множество А, т. е. те, которые не удовлетворяют условию а. Так, например, если высказывание а гласит: «он имеет неудовлетворительные оценки», то высказывание а означает: «он не имеет неудовлетворительных отметок» («он успевает по всем предметам»); если универсальное множество / состоит из изображенных на рис. 24 фигур и высказывание b гласит: «она (фигура) треугольная», то высказывание b имеет смысл «она не треугольная» (рис. 26).

Рис. 26.

Вообще высказывание а имеет смысл «не а»; поэтому операция «черта» алгебры высказываний называется образованием отрицания или просто отрицанием.

Перечислим теперь правила алгебры высказываний, связанные с операцией отрицания:

а = а\ a-\-a = i и аа = о\ о = i и i = о; a+b^ab и ab = a + b.

В самом деле, отрицание тождественно ложного высказывания (например, «2x2 не равно 5» или «этот ученик не имеет двух голов») всегда будет высказыванием тождественно истинным, а отрицание тождественно истинного высказывания («этот ученик не моложе 120 лет») — тождественно ложным. Легко проверить и все другие законы (сделай это!); впрочем, они не нуждаются в специальной проверке, так как вытекают из соответствующих правил алгебры множеств 1).

_1) Так, например, поскольку множества истинности высказываний а+Ь и ab равны А+В и А В, где А и В — множества истинности выска. зыванийаиб, и А+ В— AB, то, по определению равенства (совпадения) высказываний, a+b=ab.

Упражнения

1. Приведи три примера тождественно истинных высказываний; два примера тождественно ложных высказываний.

2. Пусть высказывание а имеет смысл:

а) «2X2=4»;

б) «он — мальчик»;

в) «слон — насекомое»;

г) «он умеет летать».

Какой смысл имеет во всех этих случаях высказывание а? Является ли это высказывание тождественно истинным? Является ли оно тождественно ложным?

3. Пусть высказывание а имеет смысл «он умеет играть в шахматы», а высказывание b — «он умеет играть в шашки». Какой смысл имеют высказывания:

а) а+Ь; б) ab; в) а+6; г) а+Ь; д) а+Ь; е) ab; ж) ab; з) а Ь?

4. Пусть высказывание а означает: «он (школьник) отличник», b — «он брюнет», с — «он умеет плавать». Какой смысл имеют высказывания

а) (а-\-Ь)с и ас-\-Ьс\

б) аЬ+с и (а+с)(Ь+с)?

5. Пусть высказывания а и b имеют смысл, «оно (целое положительное число) четно» и «оно простое». Какой смысл имеют высказывания

а) ab; б) а-\-Ь; и) ab; г) ab; д) а-\-Ь?

Каковы множества истинности этих высказываний?

6. Пусть высказывания а и b имеют смысл: «он (ученик) участвует в математическом кружке» и «он поет в хоре». Какой смысл имеют высказывания

а) а-\-Ь и а Ь;

б) ab и а+Ь?

§ 5. «ЗАКОНЫ МЫСЛИ» И ПРАВИЛА ВЫВОДА

Теперь мы можем ответить на вопрос о том, почему Дж. Буль назвал свое сочинение, в котором строилась рассматриваемая в настоящей книжке «необыкновенная алгебра», «Исследование законов мысли». В самом деле, ведь алгебра высказываний имеет самое непосредственное отношение к правилам, которыми руководствуется человек в процессе мышления, так как определенные выше сумма и произведение высказываний обозначают не что иное, как логические связки «или» и «и», операция «черта» имеет

смысл отрицания, а законы алгебры высказываний описывают основные свойства этих логических операций, которыми руководствуются все люди. Конечно, лишь очень немногие воспринимают эти свойства как математические законы мысли, но свободно используют их уже и маленькие дети. В самом деле, ведь никто, разумеется, не сомневается, что сказать: «он быстро бегает и высоко прыгает» — это то же самое, что сказать: «он высоко прыгает и быстро бегает»; другими словами, все знают (хоть и не все сознают это), что высказывания ab и Ьа имеют один и тот же смысл, «равны» между собой.

Теперь мы можем объяснить причины столь возросшего в наши дни интереса к исследованиям Дж. Буля, к математической трактовке законов логики в виде своеобразных «правил алгебры». До тех пор, пока область мысли составляла абсолютную прерогативу человеческого разума, мы могли не заботиться о формализованном описании «законов мысли»: ведь люди всегда руководствовались этими законами, даже не отдавая себе полного отчета в их содержании. Но за последние десятилетия положение резко изменилось, и сегодня мы стремимся поручать нашим «электронным помощникам», электронным вычислительным машинам те функции, которые ранее выполнялись только сознательными людьми: управление производством и составление графиков движения транспорта, решение математических задач и перевод книг с одного языка на другой, планирование экономики и отыскание интересующих нас данных в обширной научной литературе; даже в шахматы ныне играют электронные машины! Но для того чтобы «обучить» машины всему этому, нам, естественно, потребовалось четко сформулировать те «правила игры», те «законы мысли», которым должны следовать созданные человеком «умные» машины: если сам человек следует правилам логики инстинктивно, то для машины эти правила надо четко сформулировать, причем сформулировать на том единственном «языке», который только и может «понять» математическая машина — на языке математики1).

1) Нам не хотелось бы только, чтобы читатель вывел из сказанного заключение, что элементарная алгебра высказываний, которой только и посвящена эта книга, уже представляет собой аппарат, позволяющий конструировать сложные вычислительные машины или ставить задачи в той форме, в какой их решение можно «передоверять» электронным машинам.

Но вернемся к самим «законам мысли». Наиболее интересны из них правила, связанные с логической операцией отрицания; многие из них имеют в логике специальные названия. Например, правило

а + а = i

выражает так называемый закон исключенного третьего: либо имеет место высказывание а, либо высказывание а — третьего не дано, и поэтому высказывание a-fa, т. е. «а или не а», всегда истинно. Так, ничего не зная о «самом высоком ученике 7а класса школы № 12 г. Ленинграда», мы с уверенностью можем утверждать, что этот ученик «или отличник или не отличник», что он «или умеет играть в шахматы, или не умеет играть в шахматы» Правило

аа = о

носит название закона противоречия; этот закон утверждает, что высказывания a и а, т. е. a и «не а» никогда не могут иметь места одновременно, т. е. что произведение этих высказываний всегда ложно. Так, если какой-либо ученик является отличником, то высказывание «он не отличник» для него, разумеется, неверно; если (целое) число п четно, то для него неверно высказывание «оно нечетно». Правило

а = а

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

a+b=ab и ab = a + b

для высказываний, словесная формулировка которых несколько более сложна (см., впрочем, ниже упр. 1). Также и все другие правила алгебры высказываний, вроде дистри-

бутивных законов

(а + b) с =■■ асbe и ab + с = (а + с) (Ь + с)

или идемпотентных законов

а -\- а = а и аа = ау

являются определенными «законами мысли», правилами логики, управляющими выводом новых умозаключений из уже известных.

Особое место занимают правила, связанные с логическим отношением г>. Мы до сих пор не рассматривали этого отношения; однако установленная выше «двусторонняя связь» между множествами и высказываниями позволяет без труда перенести отношение =э алгебры множеств (отношение включения) в область алгебры высказываний. А именно, мы будем писать

и говорить, что высказывание а следует из высказывания b (или а является следствием Ь), если множество истинности А высказывания а содержит множество истинности В высказывания 6, т. е. если

Так, например, поскольку множество В отличников твоего класса, очевидно, содержится в множестве А всех успевающих учеников, то высказывание а: «он (ученик твоего класса) успевает по всем предметам» — является следствием высказывания Ь: «он отличник». Аналогично этому множество

ЛвН6, 12, 18,

делящихся на 6 (целых положительных) чисел содержится в множестве

Л2 = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20, . . .}

четных чисел; поэтому высказывание «оно (число) четное» является следствием высказывания «оно делится на 6»1).

1) Если az)b, то говорят также, что высказывание b является достаточным условием для а (для того чтобы школьник успевал по всем предметам, разумеется, достаточно, чтобы он был отличником), а высказывание а — необходимым условием для b (для того чтобы школьник был отличником, конечно, необходимо, чтобы он успевал по всем предметам).

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

так, например, характер вывода имеют, как правило, доказательства математических теорем: требуется установить, что из условия b теоремы (например, «угол Р треугольника MNP — прямой», рис. 27) следует ее заключение а («УИ Р2 + NР2=M Л'2»; в этом случае запись azDb равносильна теореме Пифагора). При выводах (например, при доказательстве теорем) мы систематически пользуемся (иногда не отдавая себе в этом отчета) основными свойствами отношения з1):

аза;

если аз/? и йза, то а = Ь; если азЬ и бзс, то ûdc; /за и азо для любого а; a + bzDa и aiDüb при любых а и ft; если аз ft, то b за.

Так, например, мы знаем, что если у четырехугольника диагонали в точке пересечения делятся пополам (высказывание fc), то этот четырехугольник — параллелограмм (высказывание а)2); с другой стороны, у параллелограмма противоположные углы равны (высказывание с). Таким образом, имеем

азб и сза;

поэтому

об,

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

Рис. 27.

1) Правило: если aZDb и Ьза, то а—Ь иногда формулируют так: если Ъ является необходимым и достаточным условием для а, то высказывания а и b равносильны (с принятой здесь точки зрения — одинаковы, равны).

2) В данном случае мы даже имеем азЬ и toa, т. е. а=Ь.

Остановимся еще на использовании правила: если azDb, то bzz>a Это правило лежит в основе так называемых доказательств от противного. Пусть нам требуется доказать, что имеет место соотношение aiDb: из высказывания b следует высказывание а. Часто легче оказывается доказать, что если а не имеет места, то не может выполняться и ft, т. е. что из высказывания «не а» (высказывания а) вытекает высказывание «не ft» (высказывание ft).

Вот пример этого: докажем, что если (целое) число я, большее 3, простое (высказывание ft), то п имеет вид 6&чь1 (где k—целое), т. е. п дает при делении на 6 остаток +1 или остаток—1 (высказывание а). Доказать это прямо, не опираясь на правило: «если aoft, то ftida», довольно трудно; попробуем поэтому воспользоваться доказательством от противного. Предположим, что имеет место высказывание а, т. е. что (целое и большее 3) число п не имеет вида 6&+1. Поскольку каждое целое число п дает при делении на 6 либо остаток 0 (число п делится на 6), либо остаток 1, либо остаток 2, либо остаток 3, либо остаток 4, либо остаток 5 (или, что то же самое, остаток — 1), то предположение à означает, что число п при делении на 6 дает либо остаток О (т. е. делится на 6), либо остаток 2, либо остаток 3, либо остаток 4. Но число, делящееся на 6, заведомо не является простым; если целое число я>3 дает при делении на 6 остаток 2 или 4, го оно четно и, значит, не может быть простым; если п дает при делении на 6 остаток 3, го оно делится на 3 и гоже не может быть простым Итак, из а следует b (в символической записи: bzDd)\ отсюда и вытекает, что

— а это нам и требовалось доказать1).

Упражнения

1. Сформулируй словами правила де Моргана алгебры высказываний: a+b—ab и ab=a+b.

2. Придумай пример, иллюстрирующий

а) закон исключенного третьего;

б) закон противоречия;

в) закон двойного отрицания

1) Более точным является следующее рассуждение: из доказанного соотношения bz^a следует (а)3(6) или aZDb; но, 1ак как в силу закона двойного отрицания а=а и b=b, имеем oö,

3. Придумай по одному примеру для иллюстрации каждого из перечисленных на стр. 56 свойств отношения Z) (отношения следования) высказываний.

4. Вспомни знакомый тебе пример доказательства от противного и запиши его в символической форме.

5. Пусть aZDb. Упрости сумму a-f b высказываний а и Ь\ произведение ab этих высказываний.

§ 6. ВЫСКАЗЫВАНИЯ И КОНТАКТНЫЕ СХЕМЫ

В заключение настоящей брошюры укажем еще один пример алгебры Буля, который, вероятно, покажется тебе довольно неожиданным. В качестве элементов нашей алгебры мы будем рассматривать всевозможные контактные схемы, т. е. электрические цепи, разорванные рядом контактных выключателей. Отдельные участки такой цепи, подобные изображенному на рис. 28, мы будем обозначать большими русскими буквами; они и явятся элементами рассматриваемой своеобразной алгебры.

Рис. 28.

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

Рис. 29.

сложение и умножение участков электрической цепи коммутативны:

А + Б = Б + А, АБ = БА и ассоциативны:

(А + Б) + В = А + (Б + В) ( = А + Б + В), (АБ) В = А (БВ) ( = АБВ) (см. рис. 30, а, б, на котором изображены «тройная сумма» А+Б-\-В трех контактов и их «тройное произведение» А Б В). Они также удовлетворяют идемпотентным законам:

А + А = А, АА = А,

поскольку последовательное или параллельное включение двух одинаковых (т. е. замкнутых или разомкнутых одновременно) контактов дает такой же результат, как один-единственный контакт. Несколько сложнее проверяется выполнимость в нашей «алгебре контактных схем» двух дистрибутивных законов:

(А+Б)В = АВ + БВ и АБ+В = (А + В)(Б + В);

однако и эти законы, как можно усмотреть из рис. 31 и 32, имеют здесь место (нетрудно проверить, что схема, изображенная на рис. 31,а «равна» в нашем смысле схеме рис. 31, б, а схема рис. 32, а — схеме рис. 32, б).

Условимся, наконец, обозначать через И всегда замкнутый (запаянный) контакт (рис. 33, a), a через О — постоянно разомкнутый контакт (разрыв сети; рис. 33, б). При этом, очевидно, А + 0 = А и АН = А (рис. 34);

А + И = И и АО = 0

(рис. 35); таким образом, роль «особых» элементов / и О нашей алгебры Буля играют контакты И и О.

Договоримся еще обозначать через А и А такую пару контактов, что, когда контакт А замкнут, контакт А обязательно разомкнут', технически такую пару контактов осуществить весьма нетрудно (рис. 36). Очевидно, что

А = А, Й==0 и 0 = И,

а также

А\А=И и ЛЛ=0

Рис. 30.

Рис. 31

Рис. 32.

Рис. 33.

Рис. 34.

Рис. 35.

Рис. 36.

Рис. 37.

(рис. 37, а, б). Более сложно доказываются правила де Моргана:

А + £ = Л Б и ЛБ = Л +£,

но и они имеют здесь место (см. рис. 38, а, б, где, скажем, участки цепи А-\- Б и Л + £ определяются тем условием, что если цепь А + Б пропускает ток, то цепь Л + ß его не пропускает, и наоборот).

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

d — cbc + abc,

где a, b w с — какие-то «простые» высказывания, а сложение и умножение высказываний и операция «черта» обозначают, как обычно, логические связки «или», «и» и отрицание Сопоставим высказываниям a, b и с контакты Л, Б и Ц\ в таком случае наше сложное высказывание d изобразится схемой рис. 39, отвечающей комбинации

Д=АЬЦ+АБЦ

Рис. 38.

Рис. 39.

контактов А, Б, Ц. При этом, для того чтобы проверить, будет ли истинно высказывание d, когда, скажем, высказывания а и b истинны, а высказывание с ложно, надо лишь замкнуть контакты А и Б схемы Д и разомкнуть контакт Ц (рис. 40). Если при этом схема Д будет пропускать ток, то значит она отвечает истинному высказыванию i (т. е. пропускающей ток схеме //), другими словами, в этом случае высказывание d истинно. Если же схема Д при наших условиях тока не пропускает («равна» схеме О), то высказывание d при наших условиях равносильно высказыванию о, т. е. ложно.

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

Пример 1. Требуется спроектировать электрическую цепь для спальни с одной электрической лампочкой, где желательно иметь два выключателя: один — у двери и второй — над постелью; при этом поворот каждого выключателя независимо от состояния второго выключателя должен размыкать цепь, если до этого она была замкнута, и замыкать, если ранее она была разомкнута.

Решение. Обозначим два отвечающих выключателям контакта буквами А и Б; в таком случае задача заключается в составлении такой (отвечающей электрической цепи в спальне) комбинации Ц контактов А и Б (а также, возможно, А и Б), что изменение состояния любого из этих двух контактов изменяет и состояние всей цепи Ц (т. е. превращает пропускающую ток цепь в разомкнутую и наоборот). Иначе говоря, наша задача состоит в составлении такой комбинации с каких-то высказываний а и Ь, что замена истинного высказывания а на ложное или наоборот меняет характер («истинно»; «ложно») всего высказывания с и то же самое относится к высказыванию Ь. Этому условию удовлетворяет высказывание с, истинное, когда оба высказывания а и b истинны или оба они ложны, и ложное в остальных случаях (когда истинно одно из двух высказываний a, b, а второе ложно). Употребление в этом описании частицы «или» подсказывает мысль о возможности представления высказывания с в виде суммы двух высказываний, одно из которых истинно когда истинны а и b, а второе — когда истинны а и b (т. е. когда а и b ложны). Обратив теперь внимание на частицу «и» в описании двух слагаемых искомой суммы, мы придем к выводу о том, что эти слагаемые таковы:

ab и ab.

Рис. 40.

Таким образом, окончательно имеем

c^cb + a Ь,

— и действительно нетрудно видеть, что это высказывание с удовлетворяет перечисленным выше условиям.

Переходя теперь обратно от высказываний к контактным схемам, мы заключаем, что интересующая нас электрическая цепь Ц выражается формулой

ц^аб + а В;

ясно, что техническая реализация подобной схемы (рис. 41) трудности не представляет.

Рис. 41.

Пример 21). Надо спроектировать электрическую цепь управления лифтом, где мы, для простоты, предполагаем число этажей равным двум. Цепь должна содержать два контакта, управление которыми осуществляется нажимом кнопок, расположенных в кабине лифта (кнопка спуска) и у двери лифта на первом этаже (кнопка вызова); дополнительные контакты связаны с дверями лифта на первом и на втором этажах, с внутренней дверью кабины, а также с полом лифта, на который оказывает давление находящийся в кабине пассажир. Электрическая цепь, управляющая движением лифта вниз2), должна включаться лишь, если кабина находится на втором этаже и кроме того, выполнены следующие условия:

1) обе двери лифта и дверь кабины закрыты; пассажир находится в лифте и нажимает кнопку спуска или

2) обе двери лифта закрыты (а дверь кабины закрыта или открыта); пассажира в кабине нет; человек внизу нажимает кнопку вызова.

Решение. Обозначим контактные выключатели, регулирующие включение цепи, следующим образом: В — выключатель, замыкающийся лишь в том случае, когда кабина находится на Втором этаже; Дг и Д2 — выключатели, замыкающиеся при закрывании Дверей лифта на 1-м и 2-м этажах; Дк — аналогичный выключатель, связанный с Дверью Кабины; П — выключатель, связанный с полом кабины и замыкающийся от тяжести Пассажира; Кс и Кв — выключатели, связанные с Кнопкой Спуска в кабине лифта и с Кнопкой Вызова у дверей лифта на 1-м

1) Этот пример заимствован из книги: И.А.Полетаев, Сигнал, Сов. радио, 1958, стр. 214.

2) Мы здесь рассматриваем лишь устройство цепи, управляющей движением лифта вниз; совершенно аналогично может быть разобрано и устройство цепи, двигающей лифт вверх (см. упр. 6 на стр. 65).

этаже. Согласно условию задачи искомая цепь Цс управления Спуском лифта должна включаться (пропускать ток) лишь в том случае, если:

1) контакт В замкнут и контакт Дх замкнут, и контакт Д2 замкнут, и контакт Дк замкнут, и контакт П замкнут, и контакт Кс замкнут

или

2) контакт В замкнут, и контакт Дх замкнут, и контакт Д2 замкнут, и контакт Дк замкнут или разомкнут, и контакт Кв замкнут, и контакт П разомкнут.

Учитывая, что логическая операция «и» отвечав! произведению высказываний (контактов), а логическая операция «или» — их сумме, мы без труда получаем

цс=вдхдгдкпкс+вдхд2 (дк + дк)квп.

Используя равенство

ДК+ДК = И

и свойство контакта И {АИ—А для любого контакта А), а также коммутативный закон для умножения и дистрибутивный закон, полученное выражение можно упростить:

Цс = ВДхД2(ПДкКс + ПКв). Нетрудно понять как осуществить технически такую сеть (рис. 42).

Упражнения

1. Изобрази контактные схемы, отвечающие сложным высказываниям

а) (a+b)(c+d);

б) abc-\-ab-{-а\

в) abc+abc+abc\

г) (a+b)(â+b)+ab+âb.

2. Изобрази контактные схемы, отвечающие высказываниям

(a-\-c)(b + c)(a + d)(b-\-d) и ab + cd

проверьте «равенство» этих схем.

3*. Построй электрическую цепь Цу включающую контакты Л, Б, В Yi Г (и, может быть, контакты Л, Б, В. Г), такую, что

а) цепь Ц замыкается лишь в том случае, если замкнуты все кон такты Л, 5, В и Г или ни один из этих контактов.

Рис. 42.

б) Цепь Ц замыкается лишь в том случае, если замкнуты некоторые из контактов Л, 5, В и Г, но не все эти контакты.

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

б) Построй аналогичную сеть для комитета, состоящего из председателя и пяти членов,— здесь лампочка должна зажигаться лишь в том случае, если предложение собрало большинство голосов или если голоса разделились поровну и за предложение подан голос председателя.

5*. Спроектируй электрическую цепь, позволяющую зажигать и тушить лампочку с помощью

а) трех независимых переключателей (ср. с примером 1 на стр. 62);

б) п независимых переключателей.

6. В условиях примера 2 на стр. 63 спроектируй цепь, управляющую движением лифта вверх.

ПРИЛОЖЕНИЕ

ОПРЕДЕЛЕНИЕ АЛГЕБРЫ БУЛЯ

Алгеброй Буля называется произвольное множество элементов а, ß, у»-» Для которых определены две операции — сложение и умножение, сопоставляющие каждым двум элементам а и ß их сумму oc+ß и произведение aß1) определена операция «черта», сопоставляющая каждому элементу a новый элемента2); имеются два «особых» элемента о и i и выполняются следующие правила:

Правила, относящиеся Правила, относящиеся к операции сложения к операции умножения

1) a + ß = ß-f-a, la) aß = ßa;

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

2) (<x + ß) + Y = a+(ß + Y), 2а) (aß) v = aфу);

ассоциативные законы

3) a-|-a = a, За) aa = a.

идемпотентные законы Правила, связывающие сложение и умножение

4) (a + ß)Y = <xY + ßY, 4а) aß + Y = (a + Y) Ф + У)

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

Правила, относящиеся к элементам о и t

5) a + o = a, 5а) ai = a;

6) a-f-i = l. 6а) ao = o.

1) Сравни со сказанным на стр. 20.

2) Ученые математики говорят по этому поводу, что в алгебре Буля имеются две бинарные операции (сложение и умножение), сопоставляющие каждым двум элементам a и ß алгебры Буля новый элемент a+ß, соответственно aß, и одна унарная операция, сопоставляющая новый элемент a одному элементу a алгебры Буля.

Правила, относящиеся к операции «черта» 7) а = ое;

8) о = 1, 8а) Г=о.

Правила, связывающие операцию «черта» со сложением и умножением

9) cc + ß=aß, 9a)öß = ä+ß.

Правила де Моргана

В определении алгебры Буля можно не требовать наличия отношения Z): включение ooß можно определить любым из условий a+ß—а или aß=ß, откуда можно вывести все свойства отношения Z):

аза;

если alDß и ßz>a, то a=ß; если az)ß и ßz>Y> то азу, Юа и aiDo; a-f ßiDa и aiDaß; если aZ)ß, то ßz)a

(выведи их!). Более того, в определении алгебры Буля можно не требовать наличия одной из операций сложения или умножения, а лишь второй из этих операций и операции «черта»; так, например, имея операции «сложение» и «черта», мы можем определить умножение с помощью правила де Моргана:

aß=^fp.

Однако только наличие операций сложения и умножения (без операции «черта») алгебру Буля еще не задает.

Приведенное выше определение алгебры Буля является весьма «неэкономным»: многие из перечисленных свойств могут быть выведены из других, так что требовать их выполнения не обязательно. По этому поводу см., например, книги [2], [4] или статью [8] из приведенного ниже списка литературы.

ЛИТЕРАТУРА

1. Дж. Т. Кальбертсон, Математика и логика цифровых устройств, «Просвещение», 1965.

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

2. Э. Беркли, Символическая логика и разумные машины, ИЛ, 1961.

Эта книга во многих отношениях близка к предыдущей; однако алгебрам Буля здесь отведено несколько меньше места за счет более широкого освещения проблематики, связанной с математическими машинами.

3. Дж. Кемени, Дж. Снелл, Д ж. Томпсон, Введение в конечную математику, ИЛ, 1963.

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

4. Р. Курант и Г. Роббинс, Что такое математика, «Просвещение», 1967.

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

5. А. Кофман, Р. Фор, Займемся исследованием операций, «Мир», 1966.

Одна из глав этой очень интересной книги, рассчитанной на мало под готовленного читателя, посвящена алгебрам Буля

6. Р. Столл, Множества, логика и аксиоматические теории, «Просвещение», 1967

Эта книга несколько серьезнее предшествующих; однако для более опыт ного читателя она будет весьма интересна

7. Л. А. Калужнин. Что такое математическая логика, «Наука», 1964.

Небольшая брошюра близкая по характеру к книге 161.

8. И. М. Яглом, Алгебры Буля, сб. «О некоторых вопросах современной математики и кибернетики», «Просвещение», 1965, стр. 230— 324.

ОТВЕТЫ И УКАЗАНИЯ К УПРАЖНЕНИЯМ

§ 1

3. а)

§ 2

б)

§ 3

3. Примени к обеим частям рассматриваемого равенства операцию «черта»; воспользуйся тем, что А—А.

4. АВ+АВ=А (см. упр. 2а); (А + В)(АВ+ АВ)=АВ (см. упр. 26); А (А+В)=АВ (см. упр. 2г).

6. а) Каждому делителю m числа N отвечает некоторое подмножество множества / = р2>"-> Р^} простых делителей числа N — множество тех из этих делителей, которые одновременно являются и делителями т;при этом если числам тип отвечают подмножества Л и В множества /, то числам mQ)n= [m, ai], т®п=(т, п) и m = — отвечают множества Л+ В, А В и А . б) Если т= ра, п= рь, то m(f/г= [m, n] =

7. Эти равенства не выполняются в «алгебре максимумов и минимумов» (за исключением того случая, когда элементами алгебры являются всего два числа) и в «алгебре наименьших кратных и наибольших делителей» (за исключением того случая, когда все простые делители plt р2,..., р. числа N попарно различны; ср.с упр. 6а).

Рис. 43.

Рис. 41

Рис. 45.

5. а) «оно четно и оно простое»; множество истинности — {2J; б) «оно нечетно или оно простое»; множество истинности {1,2, 3, 5, /, 9, 11, 13, 15, 17,...} отличается от множества нечетных чисел добавлением числа 2; в) «оно нечетно и оно простое»; множество истинности {3, 5, 7, 11, 13, 17, 19,...} отличается от множества всех простых чисел исключением числа 2; г) «оно четно и оно не простое»; множество истинности {4, 6, 8, 10, 12, 14, 16,...} отличается от множества всех четных чисел исключением числа 2; д) «оно нечетно или оно не простое»; множество истинности {1, 3, 4, 5, 6, 7, 8, 9, 10, 11,...} есть множество всех целых положительных чисел, кроме числа 2.

§ 5

5. a-\-b=a\ ab=b.

§ 6

I. а) См. рис. 43; б) см. рис. 44. 3. а) См. рис. 45, а\ б) см. рис. 45,6. 4. а) С=АБ+АВ+БВ\

Исаак Моисеевич Яглом

НЕОБЫКНОВЕННАЯ АЛГЕБРА

М., 1968 г., 72 стр. с илл.

(Серия: «Популярные лекции по математике»)

Редактор Ф. И. Кизнер

Техн. редактор А. А. Благовещенская Корректор В П. Сорокина

Сдано в набор 25/IX 1967 г. Подписано к печати 21 /XII 1967 г. Бумага 84X108V32 тип. № 2. Физ. печ. л. 2,25. Условн. печ. л. 3,78. Уч.-изд. л. 3,48. Тираж 240.000 (120.000) экз. Т-16060. Цена 10 коп. Заказ № 2006.

Издательство «Наука» Главная редакция физико-математической литературы. Москва, В-71, Ленинский проспект, 15.

Ордена Трудового Красного Знамени Первая Образцовая типография имени А. А. Жданова Главполиграфпрома Комитета по печати при Совете Министров СССР. Москва, Ж-54, Валовая, 28.

Отпечатано в типографии Газетно-журнального изд-ва. Вильнюс, ул. Тесос, 1. Зак. No 1282.

Цена 12 коп., вместо 10 коп.

Бумага № 1 вместо № 2

Цена 12 коп.

ПОПУЛЯРНЫЕ ЛЕКЦИИ ПО МАТЕМАТИКЕ:

Вып. 1. А. И. Маркушевич. Возвратные последовательности.

Вып. 2. И. П. Натансон. Простейшие задачи на максимум и минимум.

Вып. 3. И. С. Соминский. Метод математической индукции.

Вып. 4. А. И. Маркушевич. Замечательные кривые.

Вып. 5. П. П. Коровкин. Неравенства.

Вып. 6. H. Н. Воробьев. Числа Фибоначчи.

Вып. 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. H. Н. Воробьев. Признаки делимости.

Вып. 40. С. В. Фомин. Системы счисления.

Выи. 41. Б. Ю. Коган. Приложение механики к геометрии.

Вып. 42. Ю. И. Любич и л. А. Шор. Кинематический метод в геометрических задачах.

Вып. 43, в. А. Успенский. Треугольник Паскаля.

Выи. 44. И. Я. Бакельман. Инверсия.

Вып. 45. И. М. Яглом. Необыкновенная алгебра.