Булева алгебра

Амбициозность

Активность

Безопасность

Беспристрастность

Благодарность

Быстрота

Вежливость

Вера

Вклад

Воображение

Воспитание

Гармония

Гибкость

Деятельность

Дисциплина

Добросовестность

Доброта

Достижение

Дружба

Естественность

Жизнерадостность

Заботливость

Здоровье

Знания

Зрелость

Игривость

Изобретательность

Искренность

Исполнительность

Качественность

Компетентность

Красота

Лидерство

Личностный рост

Лояльность

Любовь

Мастерство

Многосторонность

Мудрость

Мужество

Мягкость

Надежда

Надежность

Наслаждение

Независимость

Новаторство

Обслуживание клиентов

Обучение

Образование

Общительность

Оптимизм

Организованность

Оригинальность

Остроумие

Ответственность

Педантичность

Победа

Положительность

Понимание

Поощрение

Список ценностей

Порядок

Правдивость

Практичность

Предприимчивость

Привязанность

Приключение

Приспособляемость

Приятность

Прогресс

Простота

Профессионализм

Процветание

Прямота

Пунктуальность

Работа в команде

Решительность

Самоконтроль

Самореализация

Свобода

Сила

Сила воли

Симпатия

Скромность

Смелость

Совершенство

Созидательность

Сосредоточенность

Сострадание

Сотрудничество

Спокойствие

Стабильность

Статус

Счастье

Такт

Талантливость

Терпение

Теплота

Точность

Тщательность

Уважение

Уверенность в себе

Удовлетворенность

Умение

Умение прощать

Уникальность

Упорный труд

Упорство

Усердность

Услужливость

Успех

Физическая форма

Хорошие отношения

Хороший юмор

Ценность

Честность

Четкость мышления

Чувствительность

Широта мышления

Щедрость

Энергичность

Энтузиазм

Эффективность

130 ______________________________________ Брайан Трейси. «Точка фокуса»

ОБ АВТОРЕ

:.■.,■■■■... ■•

Брайан Трейси является одним из ведущих профессиональных ораторов в мире. Ежегодно он читает лекции для более 450 тысяч чело­век в Соединенных Штатах, Канаде, Европе, Австралии и Азии.

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

Ключевые темы его лекций:

Руководство в новом тысячелетии. Как стать эффективным руко­водителем во всех сферах бизнеса. Знакомство с самыми влиятельны­ми практичными стратегиями управления, предназначенными для ру­ководства, мотивировании и улучшения результатов.

Мышление XXI века. Как думать, планировать и действовать эф­фективнее, чем конкуренты. Как добиваться наилучших результатов в стремительном, постоянно меняющемся мире бизнеса.

Психология высочайшей производительности. Как думают и ве­дут себя профессионалы во всех областях личной и трудовой жизни. Знакомство с предложенными практичными, проверенными приема­ми и стратегиями для максимального успеха.

Стратегии идеальной продажи. Как научиться продавать больше, быстрее и легче, имея дело с требовательными покупателями в услови­ях современного конкурентного рынка. Как продавать дорогие товары и услуги, обходя дешевые товары конкурентов.

Вы можете посетить сайт Брайана Трейси по адресу: http://www.briantracy.com или написать по адресу: Brian Tracy In­ternational, 462 Stevens Road, Solana Beach, CA, 92075.

Оглавление

Оглавление

ВВЕДЕНИЕ.................................................................................................................... 3

ГЛАВА ПЕРВАЯ............................................................................................................ 7

Полностью раскройте свой потенциал

ГЛАВА ВТОРАЯ...................................................................................................... 21

Удвойте свою производительность

ГЛАВА ТРЕТЬЯ......................... т............................................................................... 30

Упрощайте свою жизнь

ГЛАВА ЧЕТВЕРТАЯ.................................................................................................... 38

Откройте в себе самые ценные ресурсы

ГЛАВА ПЯТАЯ......................................................................................................... 55

Практикуйте личное стратегическое планирование

ГЛАВА ШЕСТАЯ......................................................................................................... 66

Развивайте свой бизнес и карьеру

ГЛАВА СЕДЬМАЯ....................................................................................................... 76

Улучшите семенную и личную жизнь

ГЛАВА ВОСЬМАЯ.................................................................................................. 86

Добейтесь финансовой независимости

ГЛАВА ДЕВЯТАЯ........................................................................................................ 95

Наслаждайтесь отменным здоровьем и прекрасной формой

ГЛАВА ДЕСЯТАЯ..................................................................................................... 103

Станьте тем, кем вы в состоянии стать

ГЛАВА ОДИННАДЦАТАЯ.................................................................................. 112

Измените окружающий мир

ГЛАВА ДВЕНАДЦАТАЯ...................................................................................... 119

Духовное развитие и внутренний покой

ЗАКЛЮЧЕНИЕ....................................................................................................... 126

Семь уроков XXI века

ПРИЛОЖЕНИЕ..................................................................................................... 128

Список ценностей

ОБ АВТОРЕ........................................................................................................... 130

Научно-популярное издание

ТРЕЙСИ Брайан ТОЧКА ФОКУСА

Перевод с английского - Н.И. Кароваева

Подписано в печать с готовых диапозитивов 26.11.2003

Формат 60x90 1/16. Бумага офсетная Гарнитура PetersburgC.

Печать офсетная Усл. печ. лис. 12,61 Тираж 4000 экз.

Заказ №201-83.

Издательство «Бизнесе» Лицензия АР № 381 от 14.03.03.

Республика Беларусь, 220044, г. Минск, пр. Марин Ульяновой, д. 4

Отпечатано в полном соответствии с качеством предоставленных

диапозитивов в типографии «МинскПресс».

220021, г. Минск, ул. Любавнна, 1

БУЛЕВА АЛГЕБРА

В этом параграфе будут рассмотрены представления ло­гических функций в виде суперпозиций функций И, ИЛИ, НЕ.

Разложение функций по переменным. Совершенная дизъ­юнктивная нормальная форма. Введем обозначение х⁰ = , х¹ = х. Пусть — параметр, равный 0 или 1. Тогда = 1, если х = и = 0, если х а.

¹ До сих пор все, что говорилось о формулах и суперпозициях, было справедливо не только для логических, но и для любых функций вообще (см. § 1-2). Данный же метод проверки эквивалентности годится только для функций о конечными областями определения.

Теорема 3-1. Всякая логическая функция f (х₁,..., х_n) может быть представлена в следующем виде:

f(x_1, ..., x_m, x_m+1, ..., x_n)= f(,..., , x_m+1, ..., x_n), (3–4)

,...,

где m n, а дизъюнкция берется по всем 2^m наборам зна­чений переменных x₁,..., х_m.

Это равенство называется разложением по переменным х₁,..., х_m. Например, при n = 4, m = 2 разложение (3-4) имеет вид:

f(x₁, x₂, x₃, x₄) = f(0, 0, x₃, x₄) f&(0, 1, x₃, x₄)

f(1, 0, x₃, x₄ ) f(1, 1, x₃, x₄).

Теорема доказывается подстановкой в обе части равен­ства (3-4) произвольного набора (,..., , ,..., ) всех n переменных. Так как = 1 только когда х = а, то среди 2^m конъюнкций ,..., правой части (3-4) в 1 обратится только одна — та, в которой = ,..., = . Все остальные конъюнкции равны 0.

Поэтому полу­чим: f(,..., ) = ... f(,..., , ,..., )=f(,..., ),

т. е. тождество. D

При m =1 из (3-4) получаем разложение функции по одной переменной:

f(x₁, x₂,..., x_n) = f(0, x₂,..., x_n) x₁f(1, x₂,..., x_n) (3-5)

Ясно, что аналогичное разложение справедливо для любой из n переменных.

Другой важный случай — разложение по всем n пере­менным (m = n). При этом все переменные в правой части (3-4) получают фиксированные значения и функции в конъ­юнкциях правой части становятся равными 0 или 1, что дает:

f(x₁,..., x_n) = ... , (3-6)

f(,..., )=1

где дизъюнкция берется по всем наборам (,..., ), на которых f = 1. Такое разложение называется совершенной дизъюнктивной нормальной формой (СДНФ) функции f.

СДНФ функции f содержит ровно столько дконъюнкций, сколько единиц в таблице f; каждому единичному набору (,..., ) соответствует конъюнкция всех переменных, в которой x_i взято с отрицанием, если = 0, и без отрица­ния, если = 1. Таким образом, существует взаимно­однозначное соответствие между таблицей функции f (x₁,..., x_n) и ее СДНФ и, следовательно, СДНФ для вся­кой логической функции единственна (как говорят в мате­матике, “единственна с точностью до порядка конъюнкций”: это означает, что ввиду коммутативности дизъюнкции и конъюнкции — см. далее (3-8) — формулы, получаемые из (3-6) перестановкой конъюнкций и букв в конъюнкции, не различаются и считаются одной и той же СДНФ). Напри­мер, функция, заданная табл. 3-1, имеет СДНФ

.

Единственная функция, не имеющая СДНФ, — это кон­станта 0.

Формулы, содержащие кроме - переменных (и, разу­меется, скобок) только знаки функций дизъюнкции, конъюн­кции и отрицания, будем называть булевыми формулами (напомним, что знак конъюнкции, как правило, опускается).

Соотношение (3-6) приводит к важной теореме.

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

Действительно, для всякой функции, кроме константы 0, таким представлением может служить ее СДНФ. Кон­станту 0 можно представить булевой формулой [см. далее равенство (3-15)]. D

Булева алгебра функций и эквивалентные преобразо­вания в ней. Пусть функция f₁ задана формулой F₁ а функ­ция f₂ — формулой F₂. Подстановка F₁ и F₂ в дизъюнкцию дает формулу . Если взять формулу , эквивалентную F₁ (т. е. тоже представляющую f₁), и , эквивалентную f₂, то получим формулу , эквива­лентную . (Доказательство эквивалентности можно провести стандартным методом (см. § 3-1); рекомендуем читателю его проделать). Таким образом, дизъюнкцию можно рассматривать как бинарную операцию на множестве логических функций, которая каждой паре функций f₁, f₂ независимо от вида формул, которыми они представлены, однозначно ставит в соответствие функцию . Анало­гично этому можно рассматривать конъюнкцию как бинарную операцию, а отрицание — как унарную операцию над функциями.

Алгебра (Р₂; , &, ) основным множеством которой является все множество логических функций, а операция­ми — дизъюнкция, конъюнкция и отрицание, называется булевой алгеброй логических функций. Операции булевой алгебры также часто называют булевыми операциями.

Фактически мы имеем дело, как правило, не с самими функциями в чистом виде, а с представляющими их формулами, т. е. с алгеброй формул, которых гораздо больше, чем функций, — ведь каждую функ­цию представляет бесконечное множество формул. Для того чтобы ал­гебра формул соответствовала алгебре функций, ей придается следую­щий вид. Элементами основного множества алгебры формул объявляются не формулы, а классы эквивалентности формул, т. е. классы формул, представляющих одну и ту же функцию. Результатом, например, дизъюнкции классов K₁ и K₂ считается класс всех формул, эквивалент­ных , где . Так определенная алгебра клас­сов формул называется алгеброй Линденбаума—Тарского. Она изоморф­на булевой алгебре функций. Этот изоморфизм настолько очевиден, что часто — особенно в прикладных работах — возникает смешение поня­тий формулы и функции. Следует ясно представлять себе, что, например, логическая схема на своем выходе реализует функцию от входов; когда же речь идет об эквивалентных преобразованиях, об упрощении и т. д., то имеются в виду преобразования формул, реализующих одну и ту же функцию.

Рассмотрим теперь основные свойства булевых опера­ций.

Ассоциативность:

a) x₁(x₂x₃) = (x₁x₂)x₃, б) (x₁ x₂) x₃ = x₁ (x₂ x₃). (3-7)

Коммутативность:

a) x₁x₂ = x₂x₁; б) x₁ x₂ = x₂ x_1. (3-8)

Дистрибутивность конъюнкции относительно дизъюнк­ции:

x₁(x₂ x₃) = x₁x₂ x₁x₃ (3-9)

Дистрибутивность дизъюнкции относительно конъюнк­ции:

x₁ (x₂x₃) = (x₁ x₂)(x₁ x₃) (3-10)

Идемпотентность:

а) хх = х; б) x x = x. (3-11)
Двойное отрицание:

= x. (3-12)

Свойства констант:

а) x & 1 = x; б) x & 0 = 0; в) x 1 = 1; (3-13)
г) x 0 = x; д) = 1; е) = 0.

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

a) = ; б) = . (3-14)

Закон противоречия:

= 0. (3-15)

Закон “исключенного третьего”:

= 1. (3-16)

Соотношения (3-7) — (3-16) можно проверить указанным ранее стандартным методом — вычислением обеих частей равенств на всех наборах значений переменных. Ясно, что результат вычисления не зависит от того, как получены значения переменных, входящих в эти равенства, т. е. от того, являются ли эти переменные независимыми или, в свою очередь, получены в результате каких-то вычисле­ний. Поэтому равенства (3-7) — (3-16) остаются справед­ливыми при подстановке вместо переменных любых логи­ческих функций и, следовательно, любых формул, предста­вляющих эти функции. Важно лишь соблюдать следующее правило подстановки формулы вместо переменной: при под­становке формулы F вместо переменной х все вхождения переменной х в исходное соотношение должны быть одно­временно заменены формулой F. Например, соотношение = 1 полученное из (3-16), верно для любых F, а соотношение = 1 получено из (3-16) с нарушением правила подстановки и для некоторых F может оказаться неверным. Правило подстановки позволяет получать из соотношений (3-7) — (3-16) новые эквивалентные соотно­шения.

Зачем нужны эквивалентные соотношения? Во всякой алгебре (в том числе и в булевой алгебре функций) равен­ство F₁ = F₂ означает, что формулы F₁ и F₂ описывают один и тот же элемент алгебры, в данном случае одну и ту же логическую функцию f₁. Следовательно, если какая-либо формула F содержит F₁ в качестве подформулы, то замена F₁ на F₂ не изменяет элемента булевой алгебры f над которым производятся операции в формуле F; поэтому F', получен­ная из F такой заменой, эквивалентна F. Это утверждение представляет собой правило замены подформул, которое позволяет, используя эквивалентные соотношения, полу­чать формулы, эквивалентные данной.

Подчеркнем разницу между правилами подстановки и замены. При подстановке переменная заменяется на фор­мулу; формула может быть любой, но требуется одновре­менная ее подстановка вместо всех вхождений переменной. При замене подформул может быть заменена любая подфор­мула, однако не на любую другую, а только на эквивалент­ную ей. При этом замена всех вхождений исходной подфор­мулы не обязательна. Пусть имеется эквивалентность F₁ = F₂, где F₁ и F₂ содержат переменную х. Если вместо всех вхождений х в F₁ и F₂ подставить произвольную фор­мулу F, то получаются новые формулы и , причем не обязательно F₁ = ,F₂ = ; однако между собой новые формулы будут эквивалентны: = . Если же в F₁ какую-либо подформулу заменить на эквивалентную ей, то получится новая формула , эквивалентная F₁.

Пример 3-1. Возьмем первое из соотношений (3-14) и подставим вместо x₁. Получим , т. е. две формулы, неэквивалентные исходным, но эквива­лентные между собой. Если же в правой части нового соот­ношения заменить формулой , эквивалентной ей в силу (3-14), а в полученной подформуле х₁ заменить на эквивалентную ей в силу (3-12) формулу x_1, то все формулы в построенной цепи преобразований эквивалентны.

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

Рассмотрим некоторые основные эквивалентные преоб­разования в булевой алгебре и новые соотношения, полу­чаемые с их помощью из (3-7) — (3-16). При этом будем иметь в виду, что в булевой алгебре принято опускать скобки в следующих двух случаях: а) при последователь­ном выполнении нескольких конъюнкций или дизъюнкций (например, вместо (х₁х₂)x₃ пишут х₁х₂x₃ — это не вызывает неоднозначности ввиду ассоциативности этих операций (3-7); б) если они являются внешними скобками у конъюнкции: например, вместо (x₁ (x₂ x₃)) (x₄x₅) пишут x₁ (x₂ x₃) x₄x₅. Оба соглашения совершенно аналогичны общепри­нятому опусканию скобок для умножения в арифметиче­ских формулах ¹.

1. Упрощение формул (т. е. получение эквивалентных формул, содержащих меньшее число символов).

а) Поглощение:

x xy = x; (3-17а)

x (x y) = x. (3-176)

Докажем подробно первое равенство [для его доказатель­ства используются последовательно соотношения (3-13а), (3-9), (3-1 Зв) и (3-1 За)]:

x xy = x & 1 xy = x(1 y) = x & 1 = x.

Второе равенство доказывается с помощью (3-9), (3-11) и первого равенства:

x(x y) = xx xy = x xy = x.

б) Склеивание:

xy = x. (3-18)

Доказательство: xy = x (y ) = x & 1 = x.

в) Обобщенное склеивание:

xz xy = xz (3-19)

Доказывается с помощью расщепления, т. е. применения (3-18) в обратную сторону и поглощения (3-17): xz xy = xz xyz = xz .

г) x = x y. (3-20)

Доказательство: x = xy xy xy = x y.

д) Обобщением равенств (3-17а) и (3-20) является ра­венство

x₁ f(x_1, x₂,..., x_n) = x₁ f(0, x₂,..., x_n) (3-21)

При доказательстве используется разложение по x₁ , (3-17а) и (3-20):

x₁ f(x₁, x₂,..., x_n) = x₁ f(0, x₂,..., x_n) x₁f(1, x₂,..., x_n) = x₁ f(0, x₂,..., x_n).

__________________

¹ Внимательный читатель должен был обратить внимание на то, что эти два соглашения; а также соотношения (3-13) использованы уже в формуле (3-4).

2. Приведение к дизъюнктивной нормальной форме (в том числе к СДНФ).

Элементарными конъюнкциями называются конъюнкции переменных или их отрицаний, в которых каждая пере­менная встречается не более одного раза. Дизъюнктивной нормальной формой (ДНФ) называется формула, имеющая вид дизъюнкции элементарных конъюнкций. Соотношение (3-19) показывает, что ДНФ функции может быть не един­ственной.

Приведение к ДНФ делается так. Сначала с помощью (3-12) и правил деМоргана (3-14) все отрицания “спускают­ся" до переменных. Затем раскрываются скобки, с помощью (3-11), (3-15) и (3-16) удаляются лишние конъюнкции и повторения переменных в конъюкциях, а с помощью (3-13)
удаляются константы.

Пример 3-2.

xy (y xz) = xy = xy = xy

= xy = = xy .

Всякую ДНФ можно привести к СДНФ расщеплением конъюнкций, которые содержат не все переменные, напри­мер:

xy = xyz .

Если из формулы F₁ с помощью некоторых эквивалент­ных соотношений можно получить формулу F₂, то F₂ можно получить из F₁, используя те же эквивалентные соотноше­ния; иначе говоря, всякое эквивалентное преобразование обратимо. Это позволяет доказать следующую теорему.

Теорема 3-3. Для любых двух эквивалентных формул F₁ и F₂ существует эквивалентное преобразование F₁ в F₂ с помощью соотношений (3-7) — (3-16).

Действительно, преобразуем F₁ и F₂ в СДНФ. Поскольку F₁ и F₂ эквивалентны, то их СДНФ совпадают. Обратив второе преобразование, получим преобразование F₁ СДНФ F₂. D

Важность этой теоремы в том, что соотношений (3-7) — (3-16) оказывается достаточно для любого эквивалентного преобразования в булевой алгебре.

3. Приведение к конъюнктивной нормальной форме.

Аналогично ДНФ определяется конъюнктивная нор­мальная форма (КНФ) как конъюнкция элементарных дизъюнкций.

От ДНФ к КНФ перейдем следующим образом. Пусть ДНФ F имеет вид , где k₁,..., k_m — элементарные конъюнкции. Формулу приведем к ДНФ . Тогда . По правилу де Моргана от­рицания элементарных конъюнкций преобразуются в эле­ментарные дизъюнкции, что и даст КНФ.

Пример 3-3.

.

Аналогом СДНФ является СКНФ — совершенная конъ­юнктивная нормальная форма, каждая элементарная дизъ­юнкция которой содержит все переменные. Единственная функция, не имеющая СКНФ, — константа 1.

Двойственность. Функция f₁ (x₁,..., х_n) называется двойственной к функции f₂ (х₁,..., х_n), если f₁ (x₁,..., x_n) = f₂(,..., ). Беря отрицание над обеими частями равен­ства и подставляя ,..., вместо x₁,..., х_n получаем (,..., ) = (,..., ) = f₂ (x₁,..., x_n), т. е. f₂ двой­ственна к f₁. Таким образом, отношение двойственности между функциями симметрично. Из определения двойствен­ности ясно, что для любой функции двойственная функция определяется однозначно. В частности, может оказаться, что функция двойственна самой себе. В этом случае она называется самодвойственной.

Пример 3-4. Дизъюнкция двойственна конъюнкции (в силу правил де Моргана); константа 1 двойственна 0; отрицание самодвойственно. Еще один традиционный при­мер самодвойственной функции — ху хz yz.

Пользуясь определением двойственности, нетрудно (пря­мой выкладкой) доказать следующее утверждение, называе­мое принципом двойственности: если в формуле F, представляющей функцию f, все знаки функций заменить соответственно на знаки двойственных функций, то полу-ченнаяформула F* будетпредставлять функцию f*, двойственную f. В булевой алгебре принцип двойственности имеет более конкретный вид, вытекающий из ранее приведенных примеров: если в формуле F, представляющей функцию f все конъюнкции заменить на дизъюнкции, дизъюнкции — на конъюнкции, 1 на 0, 0 на 1, то получим формулу F*, представляющую функцию f*, двойственную f.

Если функции равны, то и двойственные им функции также равны. Это позволяет с помощью принципа двойст­венности получать новые эквивалентные соотношения, пе­реходя от равенства F₁ = F₂ с помощью указанных замен к равенству F₁* = F₂*. Примером пары соотношений, полу­чаемых друг из друга по принципу двойственности, яв­ляются два равенства (3-17).

Булева алгебра и теория множеств. В примере 2-1, п. 3 были опи­саны булевы алгебры множеств. Общий термин “булева алгебра” для алгебр множеств и логических функций не случаен.

Всякая алгебра типа (2, 2, 1) называется булевой алгеброй, если ее операции удовлетворяют соотношениям (3-7) — (3-16). В алгебре множеств элементами являются подмножества фиксированного (“уни­версального”) множества U (напомним, что система всех подмножеств U обозначается через B(U)), операции & соответствует пересечение, операции — объединение, операции соответствует дополнение; еди­ницей является само множество U, нулем — пустое множество. Спра­ведливость соотношений (3-7) — (3-16) для алгебры множеств можно показать непосредственной их проверкой. Для этого нужно рассмотреть переменные в них как множества, знаки &, заменить на , и пока­зать, что если какой-либо элемент принадлежит множеству из левой части равенства, то он принадлежит правой части, и наоборот. Эту проверку мы предоставляем читателю.

В предыдущих главах уже отмечалось и использовалось (см. тео­рему 1-2) взаимно-однозначное соответствие Г между множеством B(U), где U = {a₁,..., а_n}, и множеством В_n двоичных векторов длины n: каждому подмножеству М U соответствует двоичный вектор F (М) = = (,..., ), где = 1, если a_i M, и = 0, если a_i M. Булева алгебра (В_n; , &, ) на множестве В_n определяется следующим образом: для любых векторов = (,..., ) и = (,..., )

= ( , ,..., );

& = ( & , & ,..., & ); (3-22)
= (, ,..., ).

Поскольку компоненты (разряды) и векторов и принимают значения 0 и 1, то указанные операции над компонентами — это просто логические операции над двоичными переменными; операции над век­торами естественно назвать покомпонентными (поразрядными) логи­
ческими операциями над двоичными векторами. Такие операции (наряду с логическими операциями над переменными) входят, в частности, в систему команд любой современной ЭВМ. Выполнение их очень просто: вектор содержит единицы во всех разрядах, в которых есть 1 либо в , либо в , вектор & — в тех разрядах, в которых 1 есть и в , и в ; вектор содержит единицы в тех разрядах, в которых содержит нули. Например, если = 01011, = 11010, то = 11011, & = 01010, = 10100.

Теорема 3-4. Если |U| = n, то булева алгебра (B(U); , , ) изоморфна булевой алгебре (B_n; , &, ).

Взаимно-однозначное соответствие Г между подмножествами U и векторами из В_n было описано ранее. Остается показать, что Г — изоморфизм, т. е. что для него выполнено условие (2-1), которое в данном случае сводится к трем равенствам: если Г (M₁) = , а Г (М₂) = , то

Г(M₁ M₂) = ;

Г(M₁ M₂) = & ; (3-23)
Г(M₁) = .

Справедливость их вытекает непосредственно из (3-22): если a_i M₁ М_2, то i-й разряд вектора Г (М₁ М₂) = 1; с другой сто­роны, это означает, что a_i M₁ или a_i M₂, т. е. = 1 или = 1 и, следовательно, i-й разряд вектора равен 1. Если же a_i M₁ М₂, то i-й разряд Г (M₁ M₂) равен 0. Но тогда a_i M₁ и a_i М₂, следовательно, i-й разряд также равен 0. Аналогично доказы­ваются остальные два равенства. D

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

Рассмотрим теперь множество Р₂(m) всех логических функций m переменных х₁,..., х_m. Оно замкнуто относительно операций &, , (результат их применения к функциям из P₂(m) снова дает функцию из Р₂ (m)) и, следовательно, образует конечную булеву алгебру (Р₂(m); , &, ), являющуюся подалгеброй булевой алгебры логических функций.

Теорема 3-5. Если |U| = 2^m, то булева алгебра множеств (B(U); , , ) изоморфна булевой алгебре функций (Р₂(m); , &, ).

Прежде всего отметим, что эти две алгебры равномощны и содер­жат элементов. Кроме того, поскольку все множества U одинаковой мощности порождают изоморфные булевы алгебры множеств (см. при­мер 2-2, п. 5), то теорему достаточно доказать для какого-либо конкрет­ного U, удовлетворяющего условию |U| = 2^m. В качестве такого U возьмем множество В_m и, следовательно, будем доказывать изоморфизм между

(B (В_m); , , ) и (Р₂(m); , &, ).

Обозначим через M_f множество единичных наборов функции f; тогда набор из В_m принадлежит M_f, если и только если f() = 1. Соответствие Г (f) = M_f между функциями и их единичными множест­вами является взаимно-однозначным соответствием между Р₂(m) и B(В_m), поскольку различным функциям соответствуют различные множества, и наоборот. (Функцию f, единичным множеством которой служит М, называют характеристической функцией множества М.) Покажем, что Г является изоморфизмом. Для этого достаточно прове­рить услойие (2-1), которое в данном случае сводится к трем равенствам

Г(f g) = M_f M_g;

Г(f&g) = M_f M_g;

Г() =

для любых функций f и g m переменных. Докажем первое из них. Пусть Г (f g). Тогда f () g () = 1, следовательно, f () = 1 или g () = 1 и, значит, M_f или М_g; откуда следует, что (M_f M_g). Обратный случай (M_f M_g). Тогда M_f или М_g и, следовательно, f () = 1 или g () = 1. Поэтому f () g () = 1 и Г (f g). Аналогично доказываются и остальные два равенства. D

Замечание. Во избежание путаницы обращаем внимание читателя на различия объектов в доказанных нами теоремах.

1. В теореме 3-4 фигурировали алгебры со следующими основными множествами:

U ={a₁,.