eng
Содержание
Cодержание
Глава 1. Теория множеств .......................................................................................... 6
1.0.
Введение ....................................................................................................... 6
1.1.
Множество и его элементы .......................................................................... 6
1.2.
Универсальное множество и пустое множество .......................................... 8
1.3.
Подмножества .............................................................................................. 9
1.4.
Диаграммы Венна ....................................................................................... 10
1.5.
Операции над множествами ...................................................................... 12
1.6.
Фундаментальное произведение множеств ............................................... 15
1.7.
Классы множеств, степенные множества и разбиения ............................ 17
1.8.
Алгебра множеств и двойственность ......................................................... 18
1.9.
Доказательство тождеств с множествами ................................................. 20
1.10.
Математическая индукция ....................................................................... 25
1.11.
Представление множеств формулами ..................................................... 26
1.12.
Многочлены алгебры множеств ............................................................... 29
1.13.
Полные нормальные формы .................................................................... 31
1.14.
Определение минимальных форм ........................................................... 34
1.15.
Представление формул алгебры множеств графами ............................... 37
1.16.
Минимизация формул алгебры множеств на графе ............................... 39
1.17.
Решенные задачи ...................................................................................... 44
Глава 2. Отношения ................................................................................................. 68
2.0.
Введение ..................................................................................................... 68
2.1.
Декартово произведение множеств ........................................................... 68
2.2.
Отношения ................................................................................................. 69
2.3.
Представление отношений ........................................................................ 71
2.4.
Композиция отношений ............................................................................ 73
2.5.
Свойства отношений .................................................................................. 75
2.6.
Замыкание свойств ..................................................................................... 78
2.7.
Отношение эквивалентности .................................................................... 79
2.8.
Отношение частичного порядка ................................................................ 81
2.9.
Решенные задачи ........................................................................................ 81
Глава 3. Упорядоченные множества и решетки ..................................................... 93
3.0.
Введение ..................................................................................................... 93
3.1.
Упорядоченные множества ........................................................................ 93
3.2.
Диаграммы Хассе ....................................................................................... 96
3.3.
Супремум и инфимум ................................................................................ 98
3.4.
Изоморфизм упорядоченных множеств .................................................... 99
3.5.
Решетки .....................................................................................................100
3.6.
Нижняя грань 0 и верхняя грань I ............................................................102
3.7.
Дистрибутивные решетки .........................................................................105
3.8.
Решенные задачи .......................................................................................107
4
Содержание
Глава 4. Теория графов ...........................................................................................114
4.0.
Введение ....................................................................................................114
4.1.
Определения ..............................................................................................115
4.2.
Подграфы. Изоморфизм и гомеоморфизм графов ..................................118
4.3.
Дополнение графа .....................................................................................119
4.4.
Маршруты, цепи, циклы ...........................................................................122
4.5.
Расстояние в графе ....................................................................................123
4.6.
Двудольные и k-дольные графы ...............................................................126
4.7.
Операции над графами ..............................................................................129
4.8.
Многомерный куб как произведение графа K2 ........................................130
4.9.
Связность графов ......................................................................................133
4.10.
Деревья .....................................................................................................139
4.11.
Векторные пространства циклов и разрезов графа ................................142
4.12.
Представления графов. Матрицы и списки смежности графов ............150
4.13.
Покрытия, независимость и паросочетания ..........................................159
4.14.
Раскрашивание графов ............................................................................164
4.15.
Метод Магу для определения доминирующих
и независимых подмножеств вершин графа, а также
паросочетаний .........................................................................................167
4.16.
Эйлеровы и гамильтоновы графы ...........................................................172
4.17.
Планарность ............................................................................................176
4.18.
Ориентированные графы ........................................................................178
4.19.
Решенные задачи .....................................................................................185
Глава 5. Сети ...........................................................................................................228
5.0.
Введение ....................................................................................................228
5.1.
Алгоритмы построения остовных деревьев ..............................................228
5.2.
Алгоритмы поиска кратчайших путей на сети .........................................230
5.3.
Задача коммивояжера ...............................................................................235
5.4.
Потоки в сетях ...........................................................................................242
5.5.
Алгоритм Форда – Фалкерсона (алгоритм расстановки меток) .............248
5.6.
Решенные задачи .......................................................................................250
Глава 6. Логика и исчисление высказываний .......................................................259
6.0.
Введение ....................................................................................................259
6.1.
Высказывания и составные высказывания ..............................................261
6.2.
Логические операции ................................................................................262
6.3.
Таблицы истинности для высказываний ..................................................264
6.4.
Тавтологии и контрадикции .....................................................................265
6.5.
Логическая тождественность ....................................................................267
6.6.
Условные высказывания ...........................................................................268
6.7.
Алгебра высказываний ..............................................................................270
6.8.
Построение выводов в исчислении высказываний .................................272
6.9.
Исчисление предикатов ............................................................................273
6.10.
Решенные задачи .....................................................................................275
Содержание 5
Глава 7. Языки, автоматы, машины Тьюринга ......................................................288
7.0.
Введение ....................................................................................................288
7.1.
Алфавит и слова .........................................................................................288
7.2.
Языки .........................................................................................................289
7.3.
Регулярные выражения и языки ...............................................................290
7.4.
Конечные автоматы FSA (finite state automata) ........................................291
7.5.
Конечные автоматы FSM (finite state machines) .......................................297
7.6.
Машины Тьюринга ....................................................................................301
7.7.
Решенные задачи .......................................................................................306
Глава 8. Кодирование в повседневной жизни .......................................................311
8.0.
Введение ....................................................................................................311
8.1.
Коды Брайля и Морзе ...............................................................................311
8.2.
Контрольные цифры .................................................................................312
8.3.
Штрих-коды (Bar codes) ............................................................................313
8.4.
Компьютерные коды .................................................................................317
8.5.
Решенные задачи .......................................................................................319
Глава 9. Разностные уравнения .............................................................................321
9.0.
Введение ....................................................................................................321
9.1.
Рекурсии ....................................................................................................324
9.2.
Итерации ...................................................................................................325
9.3.
Разностные уравнения первого порядка ..................................................327
9.4.
Банковские кредиты ..................................................................................329
9.5.
Разностные уравнения второго порядка ..................................................330
9.6.
Решенные задачи .......................................................................................333
Предметный указатель ............................................................................................339
Литература ..............................................................................................................342
ÃËÀÂÀ 1
ÒÅÎÐÈß ÌÍÎÆÅÑÒÂ
1.0. Введение
Понятие множества используется во всех математических дисциплинах. Сама идея
о существовании соотношения между величинами различной природы возникла,
по-видимому, во времена античности, однако потребовалось много столетий,
чтобы это первоначальное представление привело к современному теоретико-
множественному понятию отображения, которое каждому элементу одного мно-
жества ставит в соответствие элемент другого множества. Античные математики
использовали различные таблицы, например, астрономические таблицы Птолемея,
но эти таблицы понимались как соотношения между конечными дискретными
множествами постоянных величин и предназначались только для вычисления
числовых значений. В многочисленных трудах греческих математиков, включая и
Архимеда, не используется идея функциональной зависимости. Эта идея сформи-
ровалась лишь в начале 17-го века, когда научились представлять функциональные
зависимости с помощью формул. В работах Декарта, Ньютона, Лейбница, Эйлера
для записи различных зависимостей стали использовать не громоздкие таблицы,
а компактные алгебраические выражения. Эти работы привели к значительным
успехам в математике и благодаря им в 18-м веке главным объектом становится
не число, а функция.
Понятия, связанные с множествами, введены немецким математиком Дедекин-
дом в 1871 году в работе по теории алгебраических чисел и теории полей. Общие
принципы множеств, или совокупностей, сформулированы Георгом Кантором
в эти же годы, однако его основные работы посвящены свойствам бесконечных
множеств. Кантор показал, что свойства бесконечных и конечных множеств зна-
чительно различаются.
1.1. Множество и его элементы
Понятие множества не имеет строгого определения. Оно выведено из понятия
совокупности, образованной из конечного числа предметов, которые необходимо
рассмотреть, как единое целое. Например, можно говорить о множестве различ-
ных студентов, которых объединяет то, что они учатся в одной учебной группе,
или о множестве граждан одной страны, или о множестве всех точек, лежащих на
одной прямой. При этом чтобы выделить эти предметы, необходимо указать свой-
ства, которыми они обладают, а также указать признаки, по которым можно будет
отличить предметы одной совокупности от другой. В 1872 году Кантор определил
множество как «объединение в одно целое объектов, хорошо различимых нашей
1.1. Множество и его элементы 7
интуицией». В книге Бурбаки «Теория множеств», изданной в 1939 году, имеется
такое определение: «множество образуется из элементов, обладающих некоторыми
свойствами и находящихся в некоторых отношениях между собой или с элементами
других множеств».
Объекты, из которых образованы множества, называют элементами множеств.
По так называемой наивной точке зрения, элементами множеств могут быть объ-
екты любой природы. Множество образовано из различных элементов, но это еди-
ный, самостоятельный объект, его можно представить в виде оболочки, в которую
заключены его элементы и в которой нет ничего, кроме них.
Множество однозначно задано, если определены его элементы.
Для обозначения множеств обычно используются большие латинские бук-
вы A, B, С, X, Y, …, а элементы обозначаются строчными буквами a, b, с, x, y, …
Утверждение «x является элементом A», или « x принадлежит A» записывается как
x ∈ A.
Если x не является элементом A, тогда пишут
x ∉ A.
Определение. Два множества А и В равны, если они состоят из одних и тех же
элементов.
Запись A = B означает, что множество А равно множеству В, а запись A ≠ B означает,
что они не равны. Каждый элемент в одном множестве является элементом только
один раз, даже если он и повторяется в записи множества многократно. Элементы
одного множества принято заключать в фигурные скобки. Например, множество
букв {ТЕОРИЯ МНОЖЕСТВ} и множество букв {ВИНЕР МОНЖ СМИТ ЯН} рав-
ны, поскольку они задают одно и то же множество букв {В Е Ж И М Н О Р С Т Я},
однако если рассматривать в качестве элементов не буквы, а слова, тогда это будет
два различных множества.
Перестановка элементов списка не меняет самого множества, так, множество
{a, b, c, d} и множество {d, c, b, a} равны. Очень часто в приложениях используются
числовые множества, для обозначения которых выделены специальные символы
N = {1, 2, 3,}, множество натуральных чисел.
Z = {…, –2, –1, 0, 1, 2, …}, множество целых чисел.
Q = {множество рациональных чисел}.
R = {множество вещественных чисел}.
С = {множество комплексных чисел}.
Чтобы задать множество, можно просто перечислить все его элементы, однако
на практике составить такой список обычно довольно сложно. Например, если мы
хотим составить список всех, живущих в данном городе, рост которых превышает
2 метра, то теоретически это вполне возможно, но в реальности получение списка
для такого множества вызовет непреодолимые проблемы. Список можно приме-
нять, когда число элементов сравнительно небольшое. Еще один способ задания
множества основан на так называемом принципе абстракции, который формулиру-
ется следующим образом:
8 Глава 1. Теория множеств
для любого множества Х и любого свойства Р имеется множество А, такое, что
элементы А являются элементами Х и обладают свойством Р.
В этом случае множество можно задать, указав некоторое свойство, позволяю-
щее выделить элементы множества из элементов основного множества.
Пример 1.1
(а) М = {x: x – нечетное целое число и x > 1}.
Здесь М является множеством, состоящим из положительных целых чисел,
которые больше 1 и нечетные.
(b) А = {x: x – гласная буква английского алфавита}.
Здесь, a ∈ A, e ∈ A, но b ∉ A. Нетрудно заметить, что это множество можно
задать и перечислением его элементов, т.е. А = {a, e, i, o, u, y}.
(с) Пусть В = {x: x2 + x – 2 = 0},
C = {–2, 1}, D = {–2, –2, 1, 1}.
В этом случае все три множества равны, т.е. B = C = D, поскольку множество
не зависит ни от того, в каком порядке показаны его элементы, ни от того, сколько
раз они повторяются, ни от того, как они получены.
(d) Пусть A = {2, 3, 4, 5} B = {5, 7, 8} C = {A, B}
Множества А и В являются числовыми, а элементами множества С являются
уже не числа, а множества, т.е. С является множеством множеств и состоит из двух
элементов. Элемент 2 ∉ С, несмотря на то, что 2 ∈ A и A ∈ C.
Кроме этого, множество можно задать, определяя каждый его элемент по
некоторому уже известному множеству. Например, N = {1, 2, 3, …} – множество
натуральных чисел. Определим новое множество, как множество степеней числа 3
{31, 32, 33, …}.
Множество может быть также задано при помощи операций над множествами.
1.2. Универсальное множество и пустое множество
При задании множества в любом приложении теории множеств обычно приходится
сталкиваться с вопросом, к какому основному или универсальному множеству при-
надлежит рассматриваемое множество. Например, когда мы говорим о множестве
студентов какой-либо группы, то универсальным множеством может быть как
множество всех студентов университета, в котором учатся студенты этой группы,
так и множество всех людей на планете. Это определяется целями конкретной за-
дачи. Если надо найти некоторое множество точек на плоскости, то универсальным
множеством будет множество всех точек плоскости. Универсальное множество
обычно обозначается символом
U.
Множество, в котором нет ни одного элемента, называется пустым или несу-
ществующим множеством и обозначается
∅.
Для любого элемента x можно сказать, что пустое множество обладает свой-
ством x ∉ ∅. Пустое множество может возникнуть при задании множества U и
1.3. Подмножества 9
некоторого свойства A, такого, что в U нет ни одного элемента со свойством A,
например, множество
М = {x: x натуральное число, для которого ex < 2x}
не имеет ни одного элемента, т.е. является пустым. Имеется только одно пустое
множество, и если М и S пустые множества, то М = S, поскольку они состоят из
одних и тех же элементов, а именно – из никаких элементов.
1.3. Подмножества
Выбирая из множества М какие-либо элементы, можно получить новое множе-
ство S, которое будет частью множества М или, как еще говорят, подмножеством
множества М. Иначе говоря, множество S является подмножеством множества М,
если каждый элемент S является также и элементом М. Это отношение записыва-
ется так
S ⊆ M или M ⊇ S,
что иногда читают, как S содержится в М или М содержит S.
Обычно принято считать, что часть «меньше» целого, однако в теории множеств
это не так, поскольку каждое множество является подмножеством самого себя,
т.е.M ⊆ M, это свойство называют рефлексивностью.
Пример 1.2
(а) Рассмотрим множества
Х = {1, 2, 3, 4, 7, 8} Y = {2, 3, 8, 9} Z = {2, 8}.
Здесь Z ⊆ X и Z ⊆ Y, но Y не является подмножеством Х, поскольку имеет
элемент 9, которого нет в множестве Х. Кроме того, поскольку эти множества
определяют одну и ту же задачу, то все они должны принадлежать к универсальному
множеству U и это множество U должно содержать, по крайней мере, следующие
элементы {1, 2, 3, 4, 7, 8, 9}.
(b) Пусть N, Z, Q, R множества, о которых упоминалось в параграфе 1.1. Тогда
N ⊆ Z ⊆ Q ⊆ R.
(с) Каждое множество Х является подмножеством универсального множества U,
поэтому, по определению, все элементы Х принадлежат U. Пустое множество ∅
также является подмножеством Х.
(d) Если каждый элемент А принадлежит множеству В, а каждый элемент В
принадлежит множеству С, тогда каждый элемент А принадлежит С, т.е. если A ⊆ B
и B ⊆ C, тогда A ⊆ C.
(e) Если A ⊆ B и B ⊆ A, тогда А и В имеют те же самые элементы и А = В. Об-
ратно, если А = В, тогда A ⊆ B и B ⊆ A, т.к. каждое множество является подмно-
жеством самого себя.
10 Глава 1. Теория множеств
Формально последние три случая определяют следующие условия:
1. Для любого множества А всегда ∅ ⊆ A ⊆ U.
2. Для любого множества А выполняется A ⊆ A.
3. Если A ⊆ B и B ⊆ C, тогда A ⊆ C.
4. A = B, только если A ⊆ B и B ⊆ A.
Если A ⊆ B и A = B, то A называют несобственным подмножеством B. Когда
A ⊆ B и A ≠ B, т.е. в B содержится по крайней мере один элемент, которого нет
в A, то A называют собственным подмножеством B и пишут A ⊂ B. Пусть, например,
A = {1, 2} B = {1, 2, 3, 4, 5} C = {5, 4, 3, 2, 1}.
Здесь A и B являются подмножествами C, но A – собственное подмножество,
а B – несобственное подмножество C.
1.4. Диаграммы Венна
Диаграмма Венна позволяет получить визуальное представление множеств в виде
замкнутых областей на плоскости. Универсальное множество представляется вну-
тренними точками прямоугольника, а другие множества представляются точками
кругов (или каких-либо других областей, ограниченных замкнутыми кривыми),
лежащих внутри этого прямоугольника. Фактически эти множества являются под-
множествами универсального множества и поэтому между ними может существо-
вать взаимосвязь в том смысле, что они имеют общие элементы. Например, для
двух множеств A и B возможны три случая взаимосвязи по отношению включения.
Если эти множества не имеют общих элементов, т.е множества не пересекаются,
тогда диск, представляющий A, будет отделен от диска, представляющего B, как
на рис. 1.1а. Если A ⊂ B, т.е. все элементы A являются также и элементами B, тог-
да диск, представляющий A, будет полностью лежать внутри диска для B как на
рис. 1.1b.(В случае, когда A ⊆ B и A = B, диск, представляющий A, будет совпадать
с диском для B.)
Третий случай взаимосвязи множеств A и B показан на рис. 1.1с, при этом:
– некоторые элементы имеются в A, но их нет в B,
– есть элементы B, которых нет в А,
– есть элементы, которые принадлежат и A и B одновременно,
– есть элементы, которых нет ни в A, ни в B.
а) b) c)
А и В не пересекаются А ⊂ В
A В
B
A
A B
Рис. 1.1
1.4. Диаграммы Венна 11
Вывод и диаграммы Венна
Аргументация в логике представляет собой полное или частичное обоснование
какого-либо утверждения (заключения) с помощью других утверждений (по-
сылок). Под выводом понимается утверждение того, что заключение следует из
посылок. Вывод называется правильным тогда и только тогда, когда из конъюнк-
ции посылок следует заключение, т.е. во всех случаях, когда посылки истинны,
заключение тоже является истинным. Поскольку словесные утверждения по су-
ществу являются утверждениями о множествах, то поэтому их можно описывать
диаграммами Венна.
Следовательно, диаграммы Венна можно использовать для проверки правиль-
ности выводов.
Пример 1.3
Показать, что следующий аргумент правильный:
A: Компьютеры, которые установлены на кафедре программирования, имеют
LCD-дисплеи.
В: Компьютеры университета, которые используются в учебном процессе, со-
единены с интернетом.
С: Ни один компьютер кафедры программирования не соединен с интернетом.
D: Все компьютеры, которые используются в учебном процессе, не имеют
LCD-дисплеев.
Здесь утверждения А, В и С означают посылки, а утверждение D ниже линии
означает заключение. Вывод правильный, если заключение D логически следует
из утверждений А, В и С.
Из утверждения А компьютеры с LCD-дисплеями входят в множество ком-
пьютеров университета, а из утверждения С следует, что множество компьютеров
кафедры программирования и множество компьютеров, которые соединены с ин-
тернетом, не пересекаются.
Из утверждения В следует, что компьютеры, которые используются в учебном
процессе, образуют подмножество компьютеров, которые соединены с интернетом,
как это показано на рис. 1.2.
Вывод является правильным, что видно из диаграммы Венна, поскольку множе-
ство компьютеров, используемых в учебном процессе, не пересекается с множеством
компьютеров с LCD-дисплеями.
Необходимо заметить, что поскольку речь идет о проверке правильности вывода,
истинность заключения при этом не рассматривается. Истинность заключения не
является ни необходимым, ни достаточным условием правильности вывода. Если
все посылки истинны, то заключение истинно. Но если хотя бы одна из посылок
ложна, то заключение может быть как истинным, так и ложным, т.е. правильность
вывода зависит от того, что представляют собой его посылки, и, фактически, опре-
деляется только его формой.
12 Глава 1. Теория множеств
1.5. Операции над множествами
Операции над множествами позволяют получать из исходных множеств новые
множества. При этом предполагается, что и сами исходные множества, и вновь
полученное множество являются подмножествами одного и того же универсаль-
ного множества.
Операция объединения множеств
Объединением двух множеств А и В, обозначается A B, называется множество
всех элементов, которые принадлежат к А или к В, т.е.
A B = {x: x ∈ A или x ∈ B}.
Здесь союз «или» используется в смысле и / или. На рис. 1.3 объединение A B
представлено на диаграммах Венна заштрихованной областью. Если А и В непу-
стые множества и А не совпадает с В, то возможны три различные диаграммы для
объединения, рис. 1.3.
Пример 1.4
Пусть А = {1, 2, 3, 4, 5}, B = {1, 3, 7, 8}, A B = {1, 2, 3, 4, 5, 7, 9}.
Этот случай показан на рис. 1.3а, множества имеют общие элементы {1, 3}.
Если А = {1, 2, 3, 4, 5}, B = {7, 8, 9}, то здесь множества А и В не имеют общих
элементов, как показано на рис. 1.3b, A B = {1, 2, 3, 4, 5, 7, 8, 9}.
Если А = {1, 2, 3, 4, 5, 6,}, B = {1, 2, 3}, A B = {1, 2, 3, 4, 5, 6}, то в этом случае
B ⊂ A, т.е. A B = A, как на рис. 1.3с.
Компьютеры кафедры
программирования
Компьютеры,
соединенные
с интернетом
Компьютеры
с LCD]дисплеем Компьютеры,
используемые
в учебном процессе
Рис. 1.2
1.5. Операции над множествами 13
Операция пересечения множеств
Пересечением двух множеств А и В, обозначается A B, называется множество
элементов, которые принадлежат и А и В, т.е.
A B = {x: x ∈ A и x ∈ B}.
Пересечение представлено на диаграммах Венна заштрихованной областью,
рис. 1.4. Здесь, как и в случае с операцией объединения, также имеется три случая.
Если А = {1, 2, 3, 4, 5}, B = {2, 3, 6, 7, 8}, A B ={2, 3}, рис. 1.4a.
Если A = {1, 2, 3, 4}, B ={6, 7, 8, 9}, A B = ∅, т.е. множества А и В не пере-
секаются, рис. 1.4b.
Если А = {1, 2, 3, 4, 5, 6}, B ={4, 5,6}, A B =B ={4, 5,6}, рис. 1.4с.
A В A В A В
а) b) c)
Рис. 1.3
В
A
A В
В
A
а) b) c)
Рис. 1.4
Теорема 1.1. Следующие соотношения эквивалентны:
A ⊂ В, A B = A, и A B = B.
Следует заметить, что вопрос о том, является ли А собственным или несоб-
ственным подмножеством В, в общем, не существенен и поэтому можно записать
теорему следующим образом:
A ⊆ B, A B = A и A B = B.
14 Глава 1. Теория множеств
Операция дополнения множеств
Если все множества рассматривается в некоторое определенное время и являются
подмножествами фиксированного универсального множества U, тогда можно опре-
делить универсальное дополнение, или просто дополнение множества А, обозначается
Ас, как множество элементов, которые принадлежат U, но не принадлежат А, т.е.
Ас ={x: x ∈ U, x ∉ A}.
В некоторых текстах дополнение A обозначается как A’ или На рис. 1.5а до-
полнение Ас показано заштрихованной областью.
Операция разности множеств
Если подобным же образом рассматривать дополнение множества В до другого
множества А, то можно получить операцию разности множеств А и В, обозначаемую
как А \ В, которая задает множество элементов, принадлежащих А, но не принад-
лежащих В, т.е.
А \ В = {x: x ∈ A, x ∉ B}.
Иногда множество А \ В читается как «А минус В» и обозначается А – В. На
рис. 1.5b разность А \ В заштрихована.
A
Ас заштриховано А \ В заштриховано
AС
A В
а) b)
Рис. 1.5
Нетрудно заметить, что для любых двух множеств А и В выполняется тождество
А \ В =А ∩ ВС.
Пример 1.5
Пусть универсальное множество U = N ={1, 2, 3, 4,…} является множеством
натуральных чисел и пусть
А = {1, 2, 3, 4, 5}, B = {4, 5, 6, 7, 8}, C = {7, 8, 9}
и пусть D={1, 3, 5, 7, 9,…} множество нечетных чисел. Тогда дополнения
Ас ={6, 7, 8, 9, …}, Bc = {1, 2, 3, 9, 10, 11, …}, Cc = {1, 2, 3, 4, 5, 6, 10, 11, …},
1.6. Фундаментальное произведение множеств 15
и разности множеств
А \ В = {1, 2, 3}, А \ C = {1, 2, 3, 4, 5}, B \ C = {4, 5, 6}, C \ B = {9},
B \ A={6, 7, 8}, A \ D ={2, 4}, Dc = {2, 4, 6, 8, 10,…}, множество четных чисел.
Симметрическая разность множеств
Симметрической разностью множеств А и В, обозначается А ⊕ В, называется
множество, которое состоит из элементов либо А, либо В, но не входящих в оба
эти множества одновременно. Иначе говоря, это объединение этих множеств, из
которого удалено их пересечение
А ⊕ В = (А В) \ (А В).
Можно также показать, что
А ⊕ В = (А \ В) (В \ А).
Например, пусть А = (1, 2, 3, 4, 5, 6}, B = {4, 5, 6, 7, 8}. Тогда
А \ В ={1, 2, 3}, B \ A={7, 8} и тогда А ⊕ В = {1, 2, 3, 7, 8}.
На рис. 1.6 на диаграмме Венна множество А ⊕ В заштриховано.
В
А ⊕ В заштриховано
A
Рис. 1.6
1.6. Фундаментальное произведение множеств
Операции над множествами позволяют образовывать из исходных множеств новые
множества. При этом операция пересечения множеств применяется для различных
практических задач, таких как классификация каких-либо объектов, анализ различ-
ного рода социологических опросов или исследований, анализ данных, из которых
необходимо выбрать данные, характеризуемые заданными свойствами. Рассмотрим
следующий пример. Пусть имеется список студентов группы, успешно решивших
первую задачу контрольной работы (обозначим множество их фамилий как А). Пусть
также имеется список всех тех, кто успешно решил вторую задачу (множество В), и
16 Глава 1. Теория множеств
всех тех, кто решил третью (множество С). Если теперь потребуются сведения о тех,
кто успешно решил и первую и вторую задачи одновременно, то необходимо будет
выбрать тех, кто входит одновременно и в первый, и во второй списки. Для этого
надо найти новое множество, являющееся пересечением исходных множеств А и
В, т.е. найти множество А ∩ В. Однако это множество не содержит информации
о том, решили или нет данные студенты третью задачу. Ясно, что для этого потре-
буется найти еще одно множество, являющееся пересечением всех трех множеств,
т.е. множество А ∩ В ∩ С.
Предположим теперь, что необходимо составить такой список, в котором при-
сутствуют фамилии студентов, которые решили первую и вторую задачи, но не
решили третьей. В этом случае надо найти множество А ∩ В ∩ Сс.
Рассмотрение подобных случаев приводит к понятию фундаментального про-
изведения множеств.
Пусть имеется n различных множеств А1, А2, А3, …, Аn. Фундаментальным про-
изведением множеств называется множество вида
А1
* ∩ А2
* ∩ А3
* ∩ …∩ Аn
*,
где Аi
* это либо Аi, либо Аi
c. Заметим также, что
(1) Имеется точно 2n таких фундаментальных произведений.
(2) Любые два таких фундаментальных произведения не пересекаются.
(3) Универсальное множество является объединением всех таких фундамен-
тальных произведений.
Рассмотрим пример из трех множеств А, В и С и дадим геометрическую интер-
претацию их фундаментальных произведений, pис. 1.7.
U
А
В
С
P6
P5
P7
P3
P1
P4 P2
P0
Рис. 1.7
1.7. Классы множеств, степенные множества и разбиения 17
А = {1, 2, 3, 6, 7}
B = {3, 4, 5, 6}
C = {5, 6, 7, 8}
U = {1, 2, 3, 4, 5, 6, 7, 8, 9}.
Имеется ровно восемь фундаментальных произведений из трех множеств:
P0 = Ac ∩ Bc ∩ Cc = {9} P1 = Ac ∩ Bc ∩ C = {8} P2 = Ac ∩ B ∩ Cc = {4}
P3 = Ac ∩ B ∩ C ={5} P4 = A ∩ Bc ∩ Cc = {1, 2} P5 = A ∩ Bc ∩ C = {7}
P6 = A ∩ B ∩ Cc ={3} P7 = A ∩ B ∩ C = {6}.
1.7. Классы множеств, степенные множества
и разбиения
Для данного множества S можно рассматривать множество всех его подмножеств.
При этом придется рассматривать множество, элементами которого будут также
множества, т.е. множество множеств. Чтобы избегать путаницы, часто бывает более
удобно говорить о классе множеств или о семействе множеств. Если необходимо
рассмотреть множества из данного класса, то можно говорить о подклассе или
подсемействе. Например, рассмотрим множество S = {a, b, c, d}. Пусть А класс под-
множеств S из трех элементов. Тогда
А = [{a, b, c}, {a, b, d}, {a, c, d}, {d, c, d}].
Элементами класса А являются множества {a, b, c}, {a, b, d}, {a, c, d} и {b, c, d}.
Пусть теперь В класс подмножеств S, который содержит элемент а и два других
элемента из S. Тогда
В = {{a, b, c}, {a, b, d}, {a, c, d}].
Элементами В являются множества{a, b, c}, {a, b, d} и {a, c, d}]. Поэтому В яв-
ляется подклассом класса А.
Для данного множества S можно говорить о классе всех подмножеств S. Этот
класс называют степенным множеством S и обозначают 2S. Если n(S) – число элемен-
тов множества S, то число элементов степенного множества n(2S) представляет собой
степень 2 и равно n(2S) = 2n(S). Например, если S = {a, b, c}, то степенное множество
2S = [∅, , , , {a, b},{a, c}, {b, c}, S].
Заметим, что пустое множество ∅ принадлежит к 2S, т.к. пустое множество
является подмножеством S и само S принадлежит 2S, поэтому число элементов
n(2S) = 23 = 8.
Рассмотрим теперь еще одно важное понятие, которое называется разбиением
множества S. Разбиением множества S называется семейство {Аi} непустых под-
множеств S, для которых:
1. Каждый элемент х из S принадлежит к одному из подмножеств Аi.
2. Подмножества из {Аi} взаимно не пересекаются, т.е., если Аi ≠ Аj тогда
Аi ∩ Аj = ∅.
18 Глава 1. Теория множеств
Подмножества в разбиении иногда называют клетками или блоками. На pис. 1.8
представлена диаграмма Венна, изображающая разбиение прямоугольного множе-
ства точек S, на пять клеток А1, А2, А3, А4, А5.
Фундаментальные произведения также представляют собой разбиение уни-
версального множества.
Операции объединения и пересечения могут быть распространены на любое
количество множеств. Объединение состоит из таких элементов, которые принад-
лежат по крайней мере к одному из множеств, а пересечение – из таких элементов,
которые принадлежат ко всем множествам.
1.8. Алгебра множеств и двойственность
Абстрактная алгебра занимается изучением операций, производимых над некото-
рыми элементами. К настоящему времени идеи абстрактной алгебры используются
не только для математических методов, но и позволяют получать практические
результаты. Операции объединения, пересечения и дополнения, производимые
над множествами, удовлетворяют определенным законам (или тождествам) и
образуют алгебру множеств. Поскольку числовая алгебра появилась раньше, то
возникает вопрос, какая из операций (пересечение или объединение) «похожа» на
операцию сложения чисел и какая – на операцию умножения. Ответить на этот
вопрос едва ли возможно. Для чисел, например, выполняется только дистрибутив-
ность умножения относительно сложения, а в алгебре множеств рассматривают два
закона дистрибутивности: пересечения относительно объединения и объединения
относительно пересечения.
Важным при выполнении операций является их приоритет. Сначала выполня-
ется операция дополнения, затем пересечения и затем объединения.
Множества удовлетворяют следующим законам (или тождествам):
1 A ∩ B = B ∩ A A ∪ B = B ∪ A
Коммутативность – означает, что
любые два элемента можно менять
местами
2
(A ∩ B) ∩ C =
= A ∩ (B ∩ C)
(A ∪ B) ∪ C =
= A ∪ (B ∪ C)
Ассоциативность – результат опе-
рации не зависит от порядка ее
выполнения
А1
А2 А3
А4
А5
Рис. 1.8
1.8. Алгебра множеств и двойственность 19
3 A ∩ A = A A ∪ A = A
Идемпотентность – формулы алге-
бры множеств не имеют ни степе-
ней, ни коэффициентов
4
A ∩ (B ∩ C) =
= (A ∩ B) ∪ (A ∩ C)
A ∪ (B ∩ C) =
= (A ∪ B) ∩ (A ∪ C)
Дистрибутивность – раскрытие ско-
бок и вынесение общего элемента
5 A ∩ (A ∪ B) = A A ∪ (A ∩ B) = A
Законы поглощения – большее по
числу переменных пересечение
(или объединение) поглощается
меньшим
6 (A ∩ B)С = AC ∪ BC (A ∪ B)C = АC ∩ ВC
Законы де Моргана – дополнение
пересечения (объединения) не-
скольких множеств заменяется на
объединение (пересечение) допол-
нений каждого из этих множеств
7 (AC)C = A
Инволюция – дополнение допол-
нения множества дает исходное
множество
8
A ∩ AC = ∅
∅C = U
A ∪ AC = U
UC = ∅
Законы дополнения
9
A ∩ U = A
A ∩ ∅ = ∅
A ∪ ∅ = A
A ∪ U =U
Законы тождества
Принцип двойственности алгебры множеств
Нетрудно заметить, что тождества в таблице располагаются парами, например,
первое тождество A ∩ B = B ∩ A имеет парное A ∪ B = B ∪ A, и это выполняется
для всех остальных законов алгебры множеств.
Принцип двойственности состоит в том, что если верно какое либо тождество, то
тождество, полученное из него путем замены каждой из операций ∪, ∩, а также U
и ∅ на операции ∪, ∩, ∅ и U соответственно, будет также верно. Поэтому у любого
тождества есть его «двойник», отличающийся тем, что у него каждая операция заме-
нена на парную ей (объединение – на пересечение, а пересечение – на объединение)
и при этом пустое множество заменяется на универсальное, а универсальное на
пустое. Принцип двойственности очень важен, поскольку если доказана истинность
какого-либо выражения, то истинность двойственного ему можно не доказывать –
оно будет истинно вследствие данного принципа. Например, для верного тождества
A = (A ∩ BC ∩ CC) ∪ (A ∩ (B ∪ C)),
двойственное ему будет также верным тождеством
A = (A ∪ BC ∪ CC) ∩ (A ∪ (B ∩ C)).
Или для верного тождества
A = (A ∩ U) ∪ (A ∩ B ∩ C),
двойственное ему тождество A = (A ∪ ∅) ∪ (A ∪ B ∪ C).
20 Глава 1. Теория множеств
1.9. Доказательство тождеств с множествами
Для доказательства равенства тождеств обычно используются четыре метода:
1. Элементный метод.
2. Диаграммы Венна.
3. Табличный метод.
4. Алгебраический метод.
Элементный метод основан на том, что для произвольно выбранного элемента x
из множества, заданного в левой части тождества, доказывается, что этот элемент
принадлежит и множеству правой части этого тождества. Затем выбирается про-
извольный элемент из правой части и показывается, что он входит и в левую часть.
Вместе это доказывает, что оба множества состоят из одних и тех же элементов.
Докажем далее законы алгебры множеств.
Доказательство коммутативности (или переместительного свойства) операций
объединения и пересечения самоочевидно, поскольку ни в определении пересече-
ния, ни в определении объединения ничего не говорится о порядке подмножеств.
Ассоциативность (или сочетательный закон) также просто доказывается. Пока-
жем, что (A ∩ B) ∩ C ⊆ A ∩ (B ∩ C). Если x ∈ (A ∩ B) ∩ C, то x ∈ (A ∩ B) и x ∈ С, из
x ∈ (A ∩ B) следует, что x ∈ А и x ∈ B, т.е. x принадлежит всем трем множествам A,
B и C. Следовательно, x ∈ (B ∩ C) и x ∈ A ∩ (B ∩ C). Обратное включение пока-
зывается аналогично, поскольку множество в правой части тождества также обра-
зовано из элементов (и только из таких), которые входят в каждое из множеств A,
B и C. Ассоциативность для операции объединения следует из того, что элементы
в множестве левой части тождества и элементы в множестве правой части, состоят
из таких и только таких элементов, которые принадлежат, по крайней мере, одному
из подмножеств A, B и C.
Идемпотентность означает, что если x ∈ A ∩ A, то значит x принадлежит пере-
сечению множества A с самим собой, т.е. x принадлежит самому множеству A. Если
элемент x ∈ A ∪ A, то x принадлежит объединению множества A с самим собой,
т.е. и в этом случае он принадлежит только множеству A.
Докажем дистрибутивность пересечения относительно объединения.
A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C).
Необходимо убедиться, что множества, стоящие в левой и правой частях этого
тождества, состоят из одних и тех же элементов. Сначала покажем, что множество
левой части включается в множество правой части.
A ∩ (B ∪ C) ⊆ (A ∩ B) ∪ (A ∩ C).
Пусть x ∈ A ∩ (B ∪ C). Тогда по определению операции пересечения x ∈ A и
x ∈ (B ∪ C). Если x ∈ B, то тогда x принадлежит и A и B и поэтому он принадлежит
и их пересечению x ∈ (A ∩ B). Но поскольку x принадлежит объединению B и C, то
он может принадлежать не только B, но и С и даже обоим этим множествам. Если
x ∈ С, тогда он принадлежит и пересечению А и С, т.е. x ∈ (A ∩ C). Но отсюда можно
видеть, что в любом из этих случаев x принадлежит к какому-то из множеств – либо
1.9. Доказательство тождеств с множествами 21
(A ∩ B), либо (A ∩ C), и тогда, в соответствии с определением операции объедине-
ния, x принадлежит и объединению этих множеств x ∈ (A ∩ B) ∪ (A ∩ C) и поэтому
A ∩ (B ∪ C) ⊆ (A ∩ B) ∪ (A ∩ C).
Теперь покажем, что множество из правой части включается в множество левой.
Пусть x ∈ (A ∩ B) ∪ (A ∩ C). Если x ∈ (A ∩ B), то отсюда x ∈ A и x ∈ В. Но
поскольку x ∈ В, то он принадлежит и объединению множества В с любым другим
множеством, в частности и с множеством С, т.е. x ∈ (B ∪ C). В связи с тем, что x
входит в множество A и в множество (B ∪ C), то он входит и в их пресечение. Если
же x ∈ (A ∩ C), то тогда x ∈ A и x ∈ С. Но поскольку x ∈ С, то он принадлежит и
объединению В с любым другим множеством, т.е. x ∪ (B ∪ C). Поскольку и в этом
случае x входит в оба множества и в А и в (B ∪ C), то он входит и в их пресечение
x ∈ A ∩ (B ∪ C), поэтому(A ∩ B) ∪ (A ∩ C) ⊆ A ∩ (B ∪ C).
Докажем теперь двойственное тождество, т.е. дистрибутивность объединения
относительно пересечения A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C). Для этого надо по-
казать, что всякий элемент x множества A ∪ (B ∩ C) принадлежит и множеству
(A ∪ B) ∩ (A ∪ C). Если элемент x принадлежит множеству А, то он принадлежит
и множеству A ∪ (B ∩ C), потому что оно содержит множество А. В то же время,
если x ∈ A, то он входит и в пересечение (A ∪ B) ∩ (A ∪ C). Допустим x не является
элементом множества А. Тогда он должен принадлежать пересечению (B ∩ C), а
также каждому из множеств B и C в отдельности. Тогда по определению операции
объединения x ∈ (A ∪ B) и x ∈ (A ∪ С). Из этого следует, что x принадлежит и пере-
сечению этих множеств (A ∪ B) ∪ (A ∪ C). И в том и в другом случае x из левого
множества входит и в правое. Пусть x принадлежит правому множеству. Тогда, если
он принадлежит множеству А, то он принадлежит и множеству A ∪ (B ∩ C) по
определению объединения. Если он не принадлежит А, то тогда он принадлежит
и В и С в отдельности, а значит, он принадлежит и пересечению (B ∪ C) и поэто-
му в каждом из этих случаев любой элемент из правого множества входит в левое
множество, что и требовалось доказать.
Докажем законы поглощения.
A ∩ (A ∪ B) = A,
A ∪ (A ∩ B) = A.
Доказательство обоих законов очевидно. Пусть, например, x ∈ A ∩ (А ∪ В). Тогда
x ∈ A и x ∈ (А ∪ В). Если допустить, что поскольку x принадлежит объединению
А и В, то он принадлежит множеству В, но не принадлежит множеству А, но это
приводит к противоречию, поскольку по определению пересечения x ∈ A. Другими
словами, любой элемент левого множества может быть только из множества А.
Для доказательства закона де Моргана (A ∩ B)С = AC ∪ BC покажем сначала,
что левое множество включается в правое (A ∩ B)С ⊆ AC ∪ BC. Пусть x ∈ (A ∩ B)С.
Тогда x ∉ A ∩ B. Из этого следует, что х не входит в оба множества одновременно,
т.е. он не входит либо в А, либо в В. Если он не входит в А, то тогда он входит в АС,
а если он не входит в В, то тогда он входит в ВС. Отсюда следует, что х ∈ AC ∪ BC и
поэтому (A ∩ B)С ⊆ AC ∪ BC.
Докажем теперь, что всякий элемент х из множества AC ∪ BC принадлежит и
множеству (A ∩ B)С. Если x ∈ AС, то тогда x ∉ A, и поэтому х не может принад-
22 Глава 1. Теория множеств
лежать пересечению x ∉ A ∩ B. Если x ∈ ВС, то тогда x ∉ В, и поэтому х также не
может принадлежать пересечению x ∉ A ∩ B. В любом из этих случаев x ∉ A ∩ B
и потому x ∈ (A ∩ B)С.
Докажем двойственный закон де Моргана (A ∪ B)C = АC ∩ ВC. Поскольку
элемент х принадлежит множеству (A ∪ B)C тогда и только тогда, когда он не при-
надлежит ни множеству А, ни множеству В, то из этого следует, что он должен
входить и в множество АC, и в множество ВC, т.е. в их пересечение АC ∩ ВC. С другой
стороны, если х входит в пересечение АC ∩ ВC, то он не может входить ни в А, ни
в В, потому что в пересечении дополнений множеств ни могут находиться элемен-
ты самих этих множеств. Но тогда х входит в дополнение к их объединению, т.е.
x ∈ (A ∪ B)С, что и требовалось доказать.
Доказательство закона инволюции (AC)C = A следует из того факта, что любой
элемент из U принадлежит либо А, либо AC. Поэтому когда берется дополнение
к множеству А, то получается множество АС, а когда берется дополнение к АС, то
снова получается множество А.
Законы дополнения и тождества очевидны и не требуют доказательства.
Второй метод доказательства равенства тождеств состоит в использовании
диаграмм Венна. Однако здесь иногда приходится рассматривать всевозможные
случаи, при которых множества не имеют общих элементов, пересекаются или
вкладываются друг в друга.
Докажем, например, закон де Моргана (A ∩ B)С = AC ∪ BC. На рис. 1.9 пред-
ставлены три случая (а) – когда А и В не пересекаются, (b) – когда А включается
в В, и (с) – когда в пересечение входят элементы и из А и из В (имеется и случай,
когда В включается в А, но он аналогичен случаю (b)). На рис 1.9d, e и f показаны
их дополнения. Далее на (а1), (b1) и (с1) показаны множества AC ∪ BC для каждого
из этих случаев. Можно видеть, что на каждом рисунке области для множества
(A ∩ B)С и множества AC ∪ BC одинаковые во всех трех случаях и поэтому эти
множества равны.
Рассмотрим табличный метод доказательства равенства множеств. Докажем
ассоциативность пересечения (A ∩ B) ∩ C = A ∩ (B ∩ C). Пусть имеется диаграмма
Венна для трех множеств A, B и С из универсального множества U на рис. 1.10. Три
овальные области представляют собой множества A, B и С. Прямоугольная область
определяет множество U, и она разбита на восемь областей, которые помечены
цифрами от 0 до 7. Можно видеть, что область разбиения 7 определяет множество
A ∩ B ∩ C, область 6 – множество A ∩ B ∩ CС и т.д. Чтобы по диаграмме Венна
проверить ассоциативность пересечения, можно использовать следующую идею.
Заменим множества A, B и С и их пересечения на соответствующие им множества
из областей разбиения на этой диаграмме. Множество А заменяется на {4, 5, 6, 7},
В – на {2, 3, 6, 7}, и С – на {1, 3, 5, 7}, A ∩ B – на {6, 7}, B ∩ C – на {3, 7}
Несмотря на то что множества А, В и С могут быть какими угодно, доказать
любое тождество для этих множеств можно, сведя доказательство к проверке этого
тождества на уменьшенных множествах разбиения.
(A ∩ B) ∩ C = A ∩ (B ∩ C).
{6, 7} ∩ {1, 3, 5, 7} = {4, 5, 6, 7} ∩ {3, 7}.
1.9. Доказательство тождеств с множествами 23
а) b) c)
d) e) f)
А ∩ В = ∅ А ∩ В = А А ∩ В заштриховано
(А ∩ В)С = U (А ∩ В)С = AС (А ∩ В)С заштриховано
(АС ∪ ВС) = U АС ∪ ВС = AС АС ∪ ВС заштриховано
а1) b1) c1)
А
А
А
А А
А
А А А
В
В
В
В В
В
В В В
18
Рис. 1.9
А
В
С
6
7
5
2
3
1
4
U
0
Рис. 1.10
24 Глава 1. Теория множеств
Не трудно видеть, что и левое, и правое множества этого тождества состоят из
одного единственного элемента 7, что и доказывает ассоциативность пересечения
множеств.
Докажем то же самое, используя табличный метод. Для этого построим таблицу,
столбцы которой соответствуют различным множествам тождества, а каждая строка
соответствует одному из множеств разбиения (строк 8, поскольку разбиение со-
стоит из 8 множеств в соответствии с рис 1.10). Строки содержат ответы на вопрос:
входит ли соответствующее данной строке множество разбиения во множество
доказываемого тождества или нет. Три первые столбца таблицы дают ответы, вхо-
дит ли соответствующее множество разбиения во множество А, во множество В и
во множество С. Столбец «Левая часть» соответствует левой части доказываемого
тождества (A ∩ B) ∩ C, столбец «Правая часть» – правой части A ∩ (B ∩ C).
А В С
Множество
разбиения
A ∩ B
Левая
часть
B ∩ C
Правая
часть
нет нет нет 0 нет нет нет нет
нет нет да 1 нет нет нет нет
нет да нет 2 нет нет нет нет
нет да да 3 нет нет да нет
да нет нет 4 нет нет нет нет
да нет да 5 нет нет нет нет
да да нет 6 да нет нет нет
да да да 7 да да да да
Поскольку ответы для всех строк «Левой части» те же самые, что и для «Правой
части», тождество является доказанным. Табличный метод особенно удобен при
построении доказательств с использованием компьютера.
Алгебраический метод основывается на идее разбиения доказательства на шаги,
при этом переход от одного шага к следующему осуществляется за счет примене-
ния какого-либо закона алгебры множеств (например, закона ассоциативности,
дистрибутивности, поглощения и т.д.). Доказательство требует хорошего знания
базисных законов алгебры множеств, а также определенного опыта их применения.
Рассмотрим метод на следующем примере. Пусть требуется доказать, что
(A ∩ C) \ (A ∩ B ∩ C) = A ∩ ВС ∩ C.
При переходе от одного шага к другому будем указывать (в правой части соот-
ветствующей строки) причины, позволяющие делать такие переходы
(A ∩ C) \ (A ∩ B ∩ C) = (A ∩ C) ∩ (A ∩ B ∩ C)С = поскольку А \ В = А ∩ ВС
= (A ∩ C) ∩ (AС ∪ BС ∪ C С) = по закону Де Моргана
= (A ∩ C) ∩ AС) ∪ (A ∩ C) ∩ ВС) ∪ (A ∩ C) ∩ СС) = по закону дистрибутивности
= ((A ∩ AС) ∩ C) ∪ (A ∩ ВС ∩ C)) ∪ (A ∩ (C ∩ СС)) = по закону ассоциативности
= (∅ ∩ C) ∪ (A ∩ ВС ∩ C)) ∪ (A ∩ ∅) = поскольку (A ∩ AС) = ∅
= ∅ ∪ (A ∩ ВС ∩ C) ∪ ∅ = поскольку (A ∩ ∅) = ∅
= A ∩ ВС ∩ C. поскольку A ∪ ∅ = А
1.10. Математическая индукция 25
В этом примере левое выражение преобразовано в правое. Это преобразование
облегчается тем обстоятельством, что известно, какое выражение должно быть
получено. В то же время можно и правое выражение привести к левому. Чтобы
понять, как это сделать, достаточно просмотреть первое преобразование от конца
к началу. Какой путь легче, не всегда бывает сразу ясно, поэтому иногда необходимо
попробовать оба способа, чтобы добиться правильного результата.
1.10. Математическая индукция
Имеется следующее существенное свойство множества натуральных чисел
N = {1, 2, 3, …}, которое используется при построении различных доказательств.
Принцип математической индукции
Пусть Р – некоторое утверждение, определенное на положительных целых N, т.е.
утверждение Р(n) либо истинно, либо ложно для каждого n из N. Если для Р вы-
полняются два следующих свойства:
1. P(1) истинно.
2. P(n + 1) истинно, если истинно P(n).
Тогда Р истинно для каждого положительного целого.
Обычно этот принцип используется как аксиома для доказательства других
результатов. Используем его для доказательства следующего результата:
Путь Р будет утверждением, что сумма первых n натуральных чисел, возведен-
ных в куб, равна т.е.
Р(n): 13 + 23 +33 + … + n3 =
Легко видеть, что P(n) истинно при n = 1, т.е. P(1) : 13 =
Допустим теперь, что P(n) истинно и докажем, что P(n + 1) также будет истинно.
Для этого прибавим к обеим частям выражения для P(n) следующее слагаемое (n + 1)3
13 + 23 +33 + …+n3 + (n + 1)3 = + (n + 1)3.
Преобразуем далее правую часть
P(n + 1): 13 + 23 +33 + …+ n3 + (n + 1)3 =
Таким образом, P(n + 1) истинно, когда истинно P(n). Теперь по принципу
математической индукции утверждение Р истинно для всех n. Иногда принцип
26 Глава 1. Теория множеств
математической индукции записывают в более удобном для использования
виде
1. P(1) истинно.
2. P(n + 1) истинно, если истинно P k) для всех 1 ≤ k < n.
Тогда Р истинно для каждого положительного целого.
1.11. Представление множеств формулами
При построении дискретной модели часто необходимо разбивать множества на
некоторые его части, чтобы исследовать те или иные свойства исходной модели.
Подобные задачи возникают как при разработке телекоммуникационных техно-
логий, так и в различных бизнес-приложениях. Рассмотрим такой пример. Пусть
элементами множества являются зоны торгового зала большого супермаркета и не-
обходимо разбить это множество на подмножества так, чтобы каждое подмножество
представляло собой совокупность зон, просматриваемых одной видеокамерой, при
условии, что видеокамер должно быть как можно меньше. Если зоны выбраны так,
что они покрывают все помещение зала, то при этом выбранные подмножества не
должны накладываться друг на друга, поскольку это приведет к неоптимальному
использованию видеокамер. Кроме того, возможно, что требуется просматривать не
всю площадь зала, а только некоторые ее части. Во всех таких случаях приходится
рассматривать некоторое множество, представляющее собой определенную сово-
купность подмножеств заданного множества.
Для универсального множества U всегда можно построить его разбиение, из
множеств которого легко получать требуемые совокупности. Наиболее конструк-
тивным разбиением для этих целей является система множеств, порождаемая
фундаментальными произведениями. Из 1.7 следует, что для любых n множеств
можно построить разбиение S универсального множества U на 2n подмножеств,
называемых фундаментальными произведениям.
Определение
Любое множество или совокупность множеств разбиения S можно представит
как объединение пересечений, каждое из которых является фундаментальным
произведением. Обратно, каждое непустое выражение из объединения фундамен-
тальных произведений задает некоторое множество или совокупность множеств
разбиения и такое задание однозначно определяет это множество.
Если рассматривать операцию объединения как сложение, а операцию пере-
сечения как умножение, то подобные выражения часто называют многочленами.
Эти многочлены можно преобразовывать, используя алгебраические методы.
Многочлен, образованный из фундаментальных произведений, единственным
образом задает любое подмножество разбиения. Будем называть такой много-
член каноническим. Осуществляя эквивалентные преобразования выражения для
многочлена в каноническом виде, при котором сохраняется множество, которое
он определяет, можно получать более простые выражения для аналитического за-
дания данного множества. Если многочлен для заданного множества не допускает
дальнейшего упрощения, то такой многочлен называется минимальным.
1.11. Представление множеств формулами 27
Рассмотрим пример использования многочленов.
Пример 1.6
Предположим, что в некотором университете проведена выборочная про-
верка посещаемости занятий девяти студентов по трем предметам: математике,
информатике и английскому языку. Обозначим через А множество тех студентов,
которые имеют, по крайней мере, один пропуск по математике. Тогда АС будет
представлять собой множество студентов, которые не имеют ни одного пропуска
по математике. Пусть В – множество студентов, которые имеют, по крайней
мере, один пропуск по информатике, и С – по крайней мере, один пропуск по
английскому языку.
В деканат поступили следующие сведения:
– список студентов, которые не имеют пропусков занятий ни по одному из
предметов, AС ∩ BС ∩ CС = ∅;
– список студентов, которые не имеют пропусков ни по математике, ни по
информатике, но имеют по английскому языку (В списке вместо фамилий
будем для простоты указывать номера студентов), AС ∩ BС ∩ C = {9};
– список студентов, которые не имеют пропусков по математике и английскому
языку, но имеют – по информатике, AС ∩ B ∩ CС = {8};
– список студентов, которые не имеют пропусков по математике, но имеют по
информатике и английскому языку, AС ∩ B ∩ C = ∅;
– список студентов, которые имеют пропуски по математике, но не имеют по
информатике и английскому языку, (A ∩ BС ∩ CС) = {1, 6};
– список студентов, которые имеют пропуски по математике и английскому
языку, но не имеют по информатике, A ∩ BС ∩ C = {2, 7};
– список студентов, которые не имеют пропусков ни по математике, ни по
информатике, но имеют по английскому языку, A ∩ B ∩ CС = {3};
– список студентов, которые имеют пропуски по всем трем предметам,
A ∩ B ∩ C = {4, 5}.
Получив эти данные, деканат хотел бы составить списки тех студентов, ко-
торые:
1. Имеют пропуски по математике, но не имеют по информатике.
2. Имеют пропуски по математике и информатике.
3. Имеют, по крайней мере, один пропуск по математике.
Для того чтобы ответить на вопрос первого пункта, т.е найти множество тех
студентов, которые имеют пропуски по математике, но не имеют по информатике,
надо составить многочлен из тех фундаментальных произведений, которые включают
в себя множество A ∩ BС. Таких фундаментальных произведений два. Их объединение
и дает искомый многочлен (A ∩ BС ∩ CС) ∪ (A ∩ BС ∩ C) = {1, 6} ∪ {2, 7} = {1, 2, 6, 7}.
Это легко доказать, если выполнить упрощение данной формулы:
(A ∩ BС ∩ CС) ∪ (A ∩ BС ∩ C) = (A ∩ BС) ∩ (C ∪ СС) = по закону дистрибутивности
= (A ∩ BС) ∩ U = поскольку (C ∪ СС) = U
= A ∩ BС по закону тождества
A ∩ U = А.
28 Глава 1. Теория множеств
Аналогичное рассуждение можно применить и для второго пункта
(A ∩ B ∩ C) ∪ (A ∩ B ∩ CС) = {4, 5} ∪ {3} = {3, 4, 5}, т.к.
(A ∩ B ∩ C) ∪ (A ∩ B ∩ CС) = (A ∩ B) ∩ (C ∪ СС) = по закону дистрибутивности
= (A ∩ B) ∩ U = поскольку (C ∪ СС) = U
= A ∩ B по закону тождества
A ∩ U = А.
Для ответа на третий пункт, т.е. для определения множества А, надо составить
многочлен из четырех фундаментальных произведений, содержащих множество А.
Этот многочлен имеет вид
(A ∩ BС ∩ CС) ∪ (A ∩ BС ∩ C) ∪ (A ∩ B ∩ C) ∪ (A ∩ B ∩ CC) =
= {1, 6} ∪ {2, 7} ∪ {3} ∪ {4, 5} = {1, 2, 3, 4, 5, 6, 7}.
Многочлен можно упростить
(A ∩ BС) ∩ (С ∪ СС) ∪ (A ∩ B) ∩ (С ∩ CС) = по закону дистрибутивности
(A ∩ BС) ∩ U ∪ (A ∩ B) ∩ U = поскольку (C ∪ СС) = U
(A ∩ BС) ∪ (A ∩ B) = по закону тождества
A ∩ (BС ∪ B) = по закону дистрибутивности
A ∩ U = A по закону тождества.
Решение задачи можно получить и при помощи диаграммы Венна, показанной
на рис. 1.11.
U
A ∩ B ∩ CС
{3}
AС ∩ BС ∩ C
{9}
A ∩ BС ∩ CC
{1, 6}
AС ∩ B ∩ CC
{8}
A ∩ BС ∩ C
{2, 7}
A ∩ B ∩ C
{4, 5}
AС ∩ B ∩ C
{∅}
AС ∩ BС ∩ C C
{∅}
А
В
С
Рис. 1.11
1.12. Многочлены алгебры множеств 29
Поскольку мы имеем все 8 комбинаций из трех исходных множеств и их до-
полнений, т.е. имеем все 8 фундаментальных произведений для трех множеств, то
к решению данной задачи можно подойти и иначе. Допустим, нам надо выполнить
первый пункт задачи, т.е. найти множество тех студентов, которые имеют пропу-
ски по математике, но не имеют их по информатике. Фактически нам надо найти
пересечение двух множеств: множества А (имеющих пропуски по математике) и
множества ВС (не имеющих пропусков по информатике), т.е. множество A ∩ BС.
Для того чтобы найти элементы этого множества, нам нужно выразить множества
A ∩ BС через фундаментальные произведения. Сделать это можно с помощью ис-
кусственного приема, который позволяет вводить в любое пересечение множеств
те множества, которые в нем отсутствуют, приводя его, тем самым, к объединению
фундаментальных произведений.
A ∩ BС = (A ∩ BС) ∩ (С ∪ СС) = поскольку С ∪ СС = U, а (A ∩ BС) ∩ U = (A ∩ BС)
= (A ∩ BС ∩ С) ∪ (A ∩ BС ∩ СC) по закону дистрибутивности.
Это решение по сути дела представляет собой действия, произведенные при
решении задачи в первом случае, но выполненные в обратном порядке. Этот же
способ позволяет выразить любое множество через фундаментальные произведения.
1.12. Многочлены алгебры множеств
Множества с операциями пересечения, объединения и дополнения, удовлетворя-
ющие абстрактным законам, введенным в 1.8, образуют алгебраическую систему,
называемую алгеброй множеств. Эта алгебра является булевой алгеброй и поэтому
часто использует идеи и терминологию булевой алгебры, однако следует отметить,
что эта терминология не вполне стандартизирована, что иногда приводит к раз-
личным названиям одних и тех же понятий. Рассмотрим некоторые понятия более
подробно.
Пусть имеется n переменных, каждая из которых определяет некоторое мно-
жество. Выражением алгебры множеств Е (или формулой) называется выражение,
составленное из этих переменных, соединенных при помощи операций объедине-
ния, пересечения и дополнения, например
Е1 = A ∩ (BС ∩ С)С ∪ (A ∩ BС ∩ СC)С,
Е2 = A ∩ (BС ∩ С) ∪ (A ∩ BС ∩ СC),
Е3 = (A ∩ BС ∩ С) ∪ (A ∩ BС ∩ СC),
Е4 = (AC ∪ BC) ∩ (AC ∪ BC ∪ С) ∩ (BC ∪ С),
Е5 = (AC ∪ B ∪ С) ∩ (A ∪ BC ∪ С) ∩ (AC ∪ BC ∪ С)
являются выражениями из трех переменных А, В и С.
Литералом называется переменная или дополнение переменной, например А,
АС, ВС и т.д. Произведением называется литерал или пересечение двух или более
литералов, таких, что ни одна пара из них не содержит одной и той же переменной.
Например, BС ∩ С, A ∩ BС ∩ СC, А, СC – являются произведениями, а выражения
30 Глава 1. Теория множеств
A ∩ BС ∩ АС и A ∩ BС ∩ BС – нет. Заметим, что любое пересечение литералов всегда
приводится либо к ∅, либо к произведению. Так, например, A ∩ BС ∩ АС = ∅, по-
тому что A ∩ АС = ∅ (по закону дополнения), а пересечение A ∩ BС ∩ BС = A ∩ BС,
потому что BС ∩ BС = BС (по закону идемпотентности).
Если при n переменных произведение состоит из n литералов, то его называют
фундаментальным произведением (некоторые авторы называют любое произведение
фундаментальным произведением).
Выражение, представляющее собой объединение различных произведений,
если в нем нет ни одного произведения, которое включается в другое произведение,
называют суммой произведений, или нормальной формой объединения пересечений,
или многочленом в нормальной форме. Из предыдущего примера Е1 является просто
выражением, Е2 и Е3 – являются выражениями в нормальной форме объединения
пересечений.
Если выражение состоит из объединения фундаментальных произведений, то
такое выражение называют полной нормальной формой объединения пересечений
или многочленом в канонической форме. Многочлен Е3, кроме того, что он имеет
нормальную форму объединения пересечений, является еще и многочленом, име-
ющим полную нормальную форму объединения пересечений.
Аналогично, если при n переменных объединение состоит из n литералов,
то его называют фундаментальным объединением и, если заменить операции
объединения на операции пересечения, а операции пересечения на операции
объединения, то можно получить нормальную форму пересечения объединений и
полную нормальную форму пересечения объединений. Выражение Е4 имеет нор-
мальную форму пересечения объединений, а Е5 – полную нормальную форму
пересечения объединений.
Любое выражение может быть преобразовано к эквивалентному выражению,
имеющему нормальную форму. Одно из отличий нормальной формы в том, что
в таком выражении операция дополнения применяется только к переменным.
Чтобы избавиться от дополнений, применяемых к выражениям, надо применять
закон Де Моргана.
Алгоритм 1.1 для преобразования выражения к нормальной форме объединения
пересечений.
Пусть имеется исходное выражение алгебры множеств Е.
Шаг 1. Используя законы Де Моргана и инволюции, приведем каждую скобку,
к которой применяется операция дополнения, к виду, в котором операция допол-
нения применяется только к переменным.
Шаг 2. Используя закон дистрибутивности объединения относительно пере-
сечения, раскроем скобки, содержащие объединения литералов, относительно
операций пересечения.
Шаг 3. Используя законы ассоциативности, дополнения и идемпотентности,
преобразуем каждое пересечение литералов либо в ∅, либо в произведение.
Шаг 4. Используя законы поглощения и тождества, упростим выражение Е, и
если оно состоит из объединения пересечений, то нормальная форма получена,
если же нет, то переходим к шагу 2.
1.13. Полные нормальные формы 31
Пример 1.7
Применим данный алгоритм для преобразования к нормальной форме следу-
ющего выражения
Е = ((А ∩ ВС) ∪ (В ∩ СС)С) ∩ (((В ∩ С) ∪ (АС ∩ С))С ∪ (А ∩ В)).
Шаг 1. Используя законы Де Моргана и инволюции, получим
Е = ((А ∩ ВС) ∪ ВС ∪ С) ∩ ((ВС ∪ СС) ∩ (А ∪ СС) ∪ (А ∩ В)).
Шаг 2. Используя закон дистрибутивности, раскроем скобки в правой части
выражения
Е = ((А ∩ ВС) ∪ ВС ∪ С) ∩ ((А ∩ ВС) ∪ (ВС ∩ СС) ∪ (А ∩ СС) ∪ (СС ∩ СС) ∪ (А ∩ В)).
Шаг 3. Преобразуем пересечение литералов в произведение
Е = ((А ∩ ВС) ∪ ВС ∪ С) ∩ ((А ∩ ВС) ∪ (ВС ∩ СС) ∪ (А ∩ СС) ∪ СС ∪ (А ∩ В)).
Шаг 4. Поскольку ВС включается в А ∩ ВС, то А ∩ ВС поглощается, также СС
включается в ВС ∩ СС и А ∩ СС, поэтому оба эти пересечения поглощаются и вы-
ражение Е принимает следующий вид
Е = (ВС ∪ С) ∩ ((А ∩ ВС) ∪ СС ∪ (А ∩ В)).
Здесь снова надо раскрывать скобки, поэтому переходим к Шагу 2.
Шаг 2. Раскроем скобки и получим
Е = (А ∩ ВС ∩ ВС) ∪ (ВС ∩ СС) ∪ (А ∩ В ∩ ВС) ∪ (А ∩ ВС ∩ С) ∪
∪ (С ∩ СС) ∪ (А ∩ В ∩ С).
Шаг 3. Преобразуем пересечение литералов в произведение
Е = (А ∩ ВС) ∪ (ВС ∩ СС) ∪ ∅ ∪ (А ∩ ВС ∩ С) ∪ ∅ ∪ (А ∩ В ∩ С).
Шаг 4. Пересечение А ∩ ВС включается в А ∩ ВС ∩ С, поэтому последнее по-
глощается и нормальная форма для Е имеет вид
Е = (А ∩ ВС) ∪ (ВС ∩ СС) ∪ (А ∩ В ∩ С).
1.13. Полные нормальные формы
Следует отметить, что терминология этого раздела не стандартизирована, так, по
аналогии с булевой алгеброй полные нормальные формы иногда называют со-
вершенными нормальными формами. Рассмотрим выражение Е = Е(x1, x2, …xn),
состоящее из объединения произведений, т.е. представленное в нормальной форме.
Если каждое произведение состоит точно из n литералов, то такое выражение на-
зывается полной нормальной формой объединения пересечений.
32 Глава 1. Теория множеств
Теорема 1.2. Любое выражение алгебры множеств может быть преобразовано
к эквивалентному ему выражению в полной нормальной форме, и такое представ-
ление является единственным.
В предыдущем разделе было показано, как преобразовать любое выражение
алгебры множеств к эквивалентному выражению в нормальной форме. Далее рас-
смотрим алгоритм, позволяющий трансформировать это выражение в эквивалент-
ное ему выражение в полной нормальной форме. Идея этого алгоритма состоит в
том, что если какое-то произведение Р в выражении Е не содержит i-й переменной,
то ее можно вести в Е, образуя произведение Р ∩ (xi ∪ xi
c) при i ≤ n.
Алгоритм 1.2 для преобразования выражения к полной нормальной форме объ-
единения пересечений.
Шаг 1. Пусть имеется выражение Е = Е(x1, x2, … xn), представленное в нормаль-
ной форме. Найдем произведение Р в выражении Е, которое не содержит i-й пере-
менной, и образуем произведение Р ∩ (xi ∪ xi
c). Это не нарушает эквивалентности
выражения, поскольку (xi ∪ xi
c) = U, а Р ∩ U = Р. Удалим повторяющиеся произ-
ведения (это возможно, поскольку Р ∪ Р = Р).
Шаг 2. Повторяем Шаг 1 до тех пор, пока каждое произведение в Е не станет
фундаментальным произведением, т.е. каждое произведение не будет включать
в себя все n переменных.
Пример 1.8
Применим данный алгоритм для выражения Е в нормальной форме, получен-
ного в Примере 1.7, чтобы преобразовать его к полной нормальной форме.
Е = (А ∩ ВС) ∪ (ВС ∩ СС) ∪ (А ∩ В ∩ С).
Шаг 1. Находим произведение А ∩ ВС, которое не содержит переменной С, и
образуем произведение (А ∩ ВС) ∩ (С ∪ СС), получим
Е = (А ∩ ВС) ∩ (С ∪ СС) ∪ (ВС ∩ СС) ∪ (А ∩ В ∩ С) =
= (А ∩ ВС ∩ С) ∪ (А ∩ ВС ∩ СС) ∪ (ВС ∩ СС) ∪ (А ∩ В ∩ С).
Шаг 2. Поскольку в Е имеется произведение ВС ∩ СС, которое не содер-
жит переменной А, то снова переходим к Шагу 1 и образуем произведение
(ВС ∩ СС) ∩ (А ∪ АС),
Е = (А ∩ ВС ∩ С) ∪ (А ∩ ВС ∩ СС) ∪ (ВС ∩ СС) ∩ (А ∪ АС) ∪ (А ∩ В ∩ С).
После раскрытия скобок в Е образуется два одинаковых фундаментальных про-
изведения А ∩ ВС ∩ СС. Одно из них необходимо удалить. Теперь Е представлено
в полной нормальной форме:
Е = (А ∩ ВС ∩ С) ∪ (А ∩ ВС ∩ СС) ∪ (АС ∩ ВС ∩ СС) ∪ (А ∩ В ∩ С).
Таким образом, если имеется выражение, представленное в нормальной форме,
то данный алгоритм позволяет алгебраическими преобразованиями привести его
к полной нормальной форме. Однако этот способ не единственный. Для этой же
цели можно также использовать и диаграммы Венна.
1.13. Полные нормальные формы 33
Рассмотрим пример. Пусть имеется разбиение множества U, показанное на
рис. 1.10. Выделим множество, которое задается формулой (нормальной формой
объединения пересечений) А ∪ (ВС ∩ С). Она задает объединение двух множеств:
А = {4, 5, 6, 7} и множества, представляющего собой пересечение множеств ВС и
С, т.е. множества ВС ∩ С = {1, 5}. Поэтому множество А ∪ (ВС ∩ С) = {1, 4, 5, 6, 7}.
На рис. 1.12 это множество заштриховано. Из диаграммы видно, что множество
А ∪ (ВС ∩ С) задается объединением пяти фундаментальных произведений:
множеству {4} соответствует фундаментальное произведение А ∩ ВС ∩ СС, множе-
ству {6} – А ∩ В ∩ СС, множеству {7} – А ∩ В ∩ С, множеству {5} – А ∩ ВC ∩ С, и
множеству {1} – АC ∩ ВС ∩ С. Объединение этих фундаментальных произведений
и дает полную нормальную форму
(А ∩ ВС ∩ СС) ∪ (А ∩ В ∩ СС) ∪ (А ∩ В ∩ С) ∪ (А ∩ ВС ∩ С) ∪ (АС ∩ ВС ∩ С).
U
A 6
4
5
7
2 B
3
C
1
Рис. 1.12
Заметим, что для любого множества существует не только единственная полная
нормальная форма объединения пересечений, но и единственная полная нормальная
форма пресечения объединений. Эту форму также можно найти двумя способами.
Так, для множества из предыдущего примера А ∪ (ВС ∩ С) раскроем скобки и полу-
чим выражение в нормальной форме пересечения объединений (А ∪ ВС) ∩ (А ∪ С).
В первой скобке нет переменной С, а во второй – переменной В. Поскольку выра-
жение (С ∩ СС) = ∅, то следующее выражение эквивалентно исходному
((А ∪ ВС) ∪ (С ∩ СС)) ∩ ((А ∪ С) ∪ (В ∩ ВС)) =
= (А ∪ ВС ∪ С) ∩ (А ∪ ВС ∪ СС) ∩ (А ∪ В ∪ С) ∩ (А ∪ ВС ∪ С)
= (А ∪ ВС ∪ С) ∩ (А ∪ ВС ∪ СС) ∩ (А ∪ В ∪ С) .
34 Глава 1. Теория множеств
Последнее выражение и будет полной нормальной формой пересечения объ-
единений для исходной формулы.
Найти данное выражение можно также и при помощи диаграммы Венна.
Поскольку в исходное множество {1, 4, 5, 6, 7} не вошли элементы {0, 2, 3}, то не-
обходимо образовать пересечение таких объединений, которые не содержат эти
три множества. Объединение А ∪ В ∪ С не содержит элемента {0}, объединение
А ∪ ВС ∪ С не содержит элемента {2}, и объединение А ∪ ВС ∪ СС не содержит
элемента {3}. Отсюда, образовав из них пересечение, можно получить полную
нормальную форму пересечения объединений
(А ∪ В ∪ С) ∩ (А ∪ ВС ∪ С) ∩ (А ∪ ВС ∪ СС).
Более подробно эти формы будут рассмотрены в упражнениях.
1.14. Определение минимальных форм
Множество можно задавать различными формулами. Хотя эти формулы выглядят
по-разному, но все они эквивалентны в том смысле, что они определяют одни и те
же элементы данного множества. Например, пусть имеется два выражения в нор-
мальной форме
Е1 = (В ∩ С) ∪ (АС ∩ СС),
Е2 = (В ∩ С) ∪ (АС ∩ В) ∪ (АС ∩ ВС ∩ СС).
Эти формулы эквивалентны, что нетрудно проверить, если преобразовать каж-
дую из них к полной нормальной форме, которая и для Е1, и для Е2 одна и та же:
(А ∩ В ∩ С) ∪ (АС ∩ В ∩ С) ∪ (АС ∩ В ∩ СС) ∪ (АС ∩ ВС ∩ СС).
Для того чтобы определить, какая из эквивалентных формул «проще», введем
следующие обозначения. Пусть Е – выражение в нормальной форме, и пусть
L(E) – количество литералов в этом выражении (считаются все вхождения), и
F(E) – количество произведений, из которых образовано Е. Так, для Е1 значение
L(E1) = 2 + 2 = 4 и F(E1) = 2, а L(Е2) = 2 + 2 + 3 = 7 и F(E2) = 3.
Пусть Е1 и Е2 эквивалентные выражения в нормальной форме. Тогда Е1 проще
Е2, если
L(E1) < L(Е2) и F(E1) ≤ L(Е2) или
L(E1) ≤ L(Е2) и F(E1) < L(Е2).
Выражение Е, представленное в нормальной форме, называется минимальным,
если не существует никакого другого эквивалентного ему выражения, которое про-
ще, чем Е. Следует заметить, что может существовать более одного эквивалентного
минимального выражения.
Произведение Р называется простым импликантом, для выражения Е, если
Р ∪ Е = Е
1.14. Определение минимальных форм 35
и нет никакого другого произведения, содержащегося в Р, которое обладает этим
свойством. Например, пусть
Е = (А ∩ С) ∪ (ВС ∩ С) ∪ (АС ∩ В ∩ С).
Можно показать, что выражение
(АС ∩ В) ∪ Е = Е, но АС ∪ Е ≠ Е и В ∪ Е ≠ Е.
Поэтому АС ∩ В является простым импликантом Е.
Теорема 1.3. Любое выражение Е, представленное в минимальной форме, яв-
ляется объединением простых импликантов Е.
Методы определения минимальных форм обычно базируются на алгоритмах,
которые позволяют находить простых импликантов и выбирать из них те, которые
и дают выражения в минимальной форме. Для определения простых импликантов
имеется метод соседства (его также называют методом консенсуса), который со-
стоит в следующем. Пусть Pi и Pj два произведения такие, что одно из них содержит
литерал Х, а другое ХС (т.е. какая-то переменная в одно произведение входит без
дополнения, а в другое – с дополнением, и других переменных с этим свойством в
данных произведениях нет). Тогда соседством Pi и Pj будет называться произведение
(без повторений), составленное из литералов Pi и Pj, из которых удалены Х и ХС, а
сами Pi и Pj называются соседними. Соседство не определено, если Pi = X и Pj = XC.
Из определения соседства следует следующее утверждение:
Если S является соседством Pi и Pj, то тогда
Pi ∪ Pj ∪ S = Pi ∪ Pj.
Пример 1.9. Найти соседство S для P1 и Р2.
1. P1 = (А ∩ В) и Р2 = (ВС ∩ СС), удалим В и ВС и образуем пересечение P1 и Р2
получим S = А ∩ СС.
2. P1 = АС ∩ ВС ∩ С и Р2 = ВС ∩ СС, удалим С и СС, получим без повторений
S = АС ∩ ВС.
3. P1 = В и Р2 = ВС ∩ СС, удаление В и ВС дает S = СС.
4. P1 = АС ∩ ВС ∩ С и Р2 = В ∩ С ∩ D, удаление ВС и В дает S = АС ∩ С ∩ D.
5. P1 = АС ∩ ВС ∩ С и Р2 = В ∩ СС, здесь две переменные В и С имеют дополне-
ния и поэтому P1 и Р2 не имеют соседства.
6. P1 = АС ∩ ВС ∩ С и Р2 = ВС ∩ С здесь нет переменой без дополнения и с до-
полнением и поэтому P1 и Р2 также не имеют соседства.
Метод соседства позволяет находить все простые импликанты для любой фор-
мулы в нормальной форме.
Алгоритм 1.3 для нахождения простых импликантов (метод соседства).
Пусть имеется исходное выражение алгебры множеств Е, представленное
в нормальной форме.
Шаг 1. Используя закон поглощения, удалим произведение Pi, которое включает
в себя произведение Pj.
Шаг 2. Если имеются два соседних произведения Pi и Pj, то добавим к Е сосед-
ство S, которое они определяют.
Шаг 3. Повторяем Шаг 1 и Шаг 2, пока они могут быть применены.
36 Глава 1. Теория множеств
Теорема 1.4. Когда метод соседства прекращает работу, тогда выражение Е пред-
ставляет собой объединение простых импликантов.
Пример 1.10
Найти все простые импликанты для выражения Е
Е = (А ∩ ВС ∩ СС) ∪ (АС ∩ ВС ∩ СС) ∪ (AC ∩ С) ∪ (АС ∩ ВС ∩ С) ∪ (А ∩ В ∩ С)
(удалено АС ∩ ВС ∩ С поглощаемое AC ∩ С)
= (А ∩ ВС ∩ СС) ∪ (АС ∩ ВС ∩ СС) ∪ (AC ∩ С) ∪ (А ∩ В ∩ С)
(для соседних произведений (А ∩ ВС ∩ СС) и (АС ∩ ВС ∩ СС) добавлено (ВС ∩ СС))
= (ВС ∩ СС) ∪ (А ∩ ВС ∩ СС) ∪ (АС ∩ ВС ∩ СС) ∪ (AC ∩ С) ∪ (А ∩ В ∩ С)
(удалены (А ∩ ВС ∩ СС) и (АС ∩ ВС ∩ СС) поглощаемые (ВС ∩ СС))
= (ВС ∩ СС) ∪ (AC ∩ С) ∪ (А ∩ В ∩ С)
(для соседних произведений (ВС ∩ СС) и (AC ∩ С) добавлено (AC ∩ ВС))
= (AC ∩ ВС) ∪ (ВС ∩ СС) ∪ (AC ∩ С)
(для соседних произведений (AC ∩ С) и (А ∩ В ∩ С) добавлено (В ∩ С))
= (AC ∩ ВС) ∪ (ВС ∩ СС) ∪ (AC ∩ С) ∪ (А ∩ В ∩ С) ∪ (В ∩ С)
(удалено (А ∩ В ∩ С) поглощаемое (В ∩ С))
= (AC ∩ ВС) ∪ (ВС ∩ СС) ∪ (AC ∩ С) ∪ (В ∩ С).
Поскольку ни одного нового импликанта образовать нельзя, алгоритм прекращает
свою работу и Е представлено в виде объединения четырех простых импликантов
= (AC ∩ ВС), (ВС ∩ СС), (AC ∩ С) и (В ∩ С).
Хотя метод соседства и дает все простые импликанты, он не отвечает на вопрос –
как для данного выражения выглядит эквивалентная ему минимальная форма, и
тем более, сколько для него имеется эквивалентных минимальных форм. Чтобы
найти минимальную форму, применим следующий алгоритм
Алгоритм 1.4 для нахождения минимальной формы в выражении, представля-
ющем собой объединение простых импликантов.
Пусть имеется исходное выражение алгебры множеств Е, представленное в нор-
мальной форме в виде объединения всех простых импликантов Е.
Шаг 1. Представим каждый простой импликант в виде объединения фундамен-
тальных произведений (используя алгоритм преобразования выражения к полной
нормальной форме объединения пересечений).
Шаг 2. Последовательно удалим из Е каждый такой имликант, все фундамен-
тальные произведения которого имеются среди фундаментальных произведений
остающегося выражения.
Пример 1.11. Применим этот алгоритм для выражения, полученного в При-
мере 1.10.
Е = (AC ∩ ВС) ∪ (ВС ∩ СС) ∪ (AC ∩ С) ∪ (В ∩ С).
Выразим каждый простой импликант в виде объединения фундаментальных
произведений
1.15. Представление формул алгебры множеств графами 37
AC ∩ ВС = (АС ∩ ВС ∩ С) ∪ (АС ∩ ВС ∩ СС)
ВС ∩ СС = (АС ∩ ВС ∩ СС) ∪ (А ∩ ВС ∩ СС)
AC ∩ С = (АС ∩ В ∩ С) ∪ (АС ∩ ВС ∩ С)
В ∩ С = (А ∩ В ∩ С) ∪ (АС ∩ В ∩ С).
Удалим импликант AC ∩ ВС, поскольку его фундаментальное произведение
(АС ∩ ВС ∩ С) входит в выражение для третьего импликанта, а (АС ∩ ВС ∩ СС)
входит в выражение для второго импликанта. Из оставшихся трех импликантов
ни один этим свойством не обладает, поэтому алгоритм прекращает свою работу и
минимальная форма для Е выглядит следующим образом
Е = (ВС ∩ СС) ∪ (AC ∩ С) ∪ (В ∩ С).
Заметим также, что метод соседних произведений можно использовать и при эк-
вивалентных преобразованиях выражений, чтобы уменьшить число произведений,
входящих в упрощаемый многочлен. Это можно сделать при помощи следующих
правил, называемых правилами соседства
(А ∩ В) ∪ (АС ∩ С) ∪ (В ∩ С) = (А ∩ В) ∪ (АС ∩ С)
(А ∪ В) ∩ (АС ∪ С) ∩ (В ∪ С) = (А ∪ В) ∩ (АС ∪ С).
Доказательство этих правил, использующее граф, рассмотрено далее.
1.15. Представление формул алгебры множеств
графами
Многочлену в полной нормальной форме можно взаимно однозначно поставить
в соответствие неориентированный двудольный граф. Как следует из парагра-
фа 1.13, каждое множество имеет единственную полную нормальную форму
объединения пересечений, а также единственную полную нормальную форму
пресечения объединений. Отсюда следует, что каждому множеству можно поста-
вить в соответствие единственный граф, задаваемый полной нормальной формой
объединения пересечений, и единственный граф, задаваемый полной нормальной
формой пересечения объединений. Заметим, что существуют множества, для
которых эти графы могут быть изоморфны. Из сказанного также следует, что име-
ются задачи, связанные с множествами, которые можно решить методами теории
графов.
Сначала необходимо определить понятие смежных произведений. Оно основано
на той же идее, которая используется при введении понятия соседства в парагра-
фе 1.14. Два фундаментальных произведения Pi и Pj называются смежными, если они
состоят из тех же самых переменных и различаются точно в одном литерале. Другими
словами, имеется какая-то переменная, которая в одно из этих фундаментальных
произведений входит без дополнения, а в другое – с дополнением. В частности,
объединение двух смежных фундаментальных произведений представляет собой
произведение, в котором на один литерал меньше.
ÒÅÎÐÈß ÌÍÎÆÅÑÒÂ
1.0. Введение
Понятие множества используется во всех математических дисциплинах. Сама идея
о существовании соотношения между величинами различной природы возникла,
по-видимому, во времена античности, однако потребовалось много столетий,
чтобы это первоначальное представление привело к современному теоретико-
множественному понятию отображения, которое каждому элементу одного мно-
жества ставит в соответствие элемент другого множества. Античные математики
использовали различные таблицы, например, астрономические таблицы Птолемея,
но эти таблицы понимались как соотношения между конечными дискретными
множествами постоянных величин и предназначались только для вычисления
числовых значений. В многочисленных трудах греческих математиков, включая и
Архимеда, не используется идея функциональной зависимости. Эта идея сформи-
ровалась лишь в начале 17-го века, когда научились представлять функциональные
зависимости с помощью формул. В работах Декарта, Ньютона, Лейбница, Эйлера
для записи различных зависимостей стали использовать не громоздкие таблицы,
а компактные алгебраические выражения. Эти работы привели к значительным
успехам в математике и благодаря им в 18-м веке главным объектом становится
не число, а функция.
Понятия, связанные с множествами, введены немецким математиком Дедекин-
дом в 1871 году в работе по теории алгебраических чисел и теории полей. Общие
принципы множеств, или совокупностей, сформулированы Георгом Кантором
в эти же годы, однако его основные работы посвящены свойствам бесконечных
множеств. Кантор показал, что свойства бесконечных и конечных множеств зна-
чительно различаются.
1.1. Множество и его элементы
Понятие множества не имеет строгого определения. Оно выведено из понятия
совокупности, образованной из конечного числа предметов, которые необходимо
рассмотреть, как единое целое. Например, можно говорить о множестве различ-
ных студентов, которых объединяет то, что они учатся в одной учебной группе,
или о множестве граждан одной страны, или о множестве всех точек, лежащих на
одной прямой. При этом чтобы выделить эти предметы, необходимо указать свой-
ства, которыми они обладают, а также указать признаки, по которым можно будет
отличить предметы одной совокупности от другой. В 1872 году Кантор определил
множество как «объединение в одно целое объектов, хорошо различимых нашей
1.1. Множество и его элементы 7
интуицией». В книге Бурбаки «Теория множеств», изданной в 1939 году, имеется
такое определение: «множество образуется из элементов, обладающих некоторыми
свойствами и находящихся в некоторых отношениях между собой или с элементами
других множеств».
Объекты, из которых образованы множества, называют элементами множеств.
По так называемой наивной точке зрения, элементами множеств могут быть объ-
екты любой природы. Множество образовано из различных элементов, но это еди-
ный, самостоятельный объект, его можно представить в виде оболочки, в которую
заключены его элементы и в которой нет ничего, кроме них.
Множество однозначно задано, если определены его элементы.
Для обозначения множеств обычно используются большие латинские бук-
вы A, B, С, X, Y, …, а элементы обозначаются строчными буквами a, b, с, x, y, …
Утверждение «x является элементом A», или « x принадлежит A» записывается как
x ∈ A.
Если x не является элементом A, тогда пишут
x ∉ A.
Определение. Два множества А и В равны, если они состоят из одних и тех же
элементов.
Запись A = B означает, что множество А равно множеству В, а запись A ≠ B означает,
что они не равны. Каждый элемент в одном множестве является элементом только
один раз, даже если он и повторяется в записи множества многократно. Элементы
одного множества принято заключать в фигурные скобки. Например, множество
букв {ТЕОРИЯ МНОЖЕСТВ} и множество букв {ВИНЕР МОНЖ СМИТ ЯН} рав-
ны, поскольку они задают одно и то же множество букв {В Е Ж И М Н О Р С Т Я},
однако если рассматривать в качестве элементов не буквы, а слова, тогда это будет
два различных множества.
Перестановка элементов списка не меняет самого множества, так, множество
{a, b, c, d} и множество {d, c, b, a} равны. Очень часто в приложениях используются
числовые множества, для обозначения которых выделены специальные символы
N = {1, 2, 3,}, множество натуральных чисел.
Z = {…, –2, –1, 0, 1, 2, …}, множество целых чисел.
Q = {множество рациональных чисел}.
R = {множество вещественных чисел}.
С = {множество комплексных чисел}.
Чтобы задать множество, можно просто перечислить все его элементы, однако
на практике составить такой список обычно довольно сложно. Например, если мы
хотим составить список всех, живущих в данном городе, рост которых превышает
2 метра, то теоретически это вполне возможно, но в реальности получение списка
для такого множества вызовет непреодолимые проблемы. Список можно приме-
нять, когда число элементов сравнительно небольшое. Еще один способ задания
множества основан на так называемом принципе абстракции, который формулиру-
ется следующим образом:
8 Глава 1. Теория множеств
для любого множества Х и любого свойства Р имеется множество А, такое, что
элементы А являются элементами Х и обладают свойством Р.
В этом случае множество можно задать, указав некоторое свойство, позволяю-
щее выделить элементы множества из элементов основного множества.
Пример 1.1
(а) М = {x: x – нечетное целое число и x > 1}.
Здесь М является множеством, состоящим из положительных целых чисел,
которые больше 1 и нечетные.
(b) А = {x: x – гласная буква английского алфавита}.
Здесь, a ∈ A, e ∈ A, но b ∉ A. Нетрудно заметить, что это множество можно
задать и перечислением его элементов, т.е. А = {a, e, i, o, u, y}.
(с) Пусть В = {x: x2 + x – 2 = 0},
C = {–2, 1}, D = {–2, –2, 1, 1}.
В этом случае все три множества равны, т.е. B = C = D, поскольку множество
не зависит ни от того, в каком порядке показаны его элементы, ни от того, сколько
раз они повторяются, ни от того, как они получены.
(d) Пусть A = {2, 3, 4, 5} B = {5, 7, 8} C = {A, B}
Множества А и В являются числовыми, а элементами множества С являются
уже не числа, а множества, т.е. С является множеством множеств и состоит из двух
элементов. Элемент 2 ∉ С, несмотря на то, что 2 ∈ A и A ∈ C.
Кроме этого, множество можно задать, определяя каждый его элемент по
некоторому уже известному множеству. Например, N = {1, 2, 3, …} – множество
натуральных чисел. Определим новое множество, как множество степеней числа 3
{31, 32, 33, …}.
Множество может быть также задано при помощи операций над множествами.
1.2. Универсальное множество и пустое множество
При задании множества в любом приложении теории множеств обычно приходится
сталкиваться с вопросом, к какому основному или универсальному множеству при-
надлежит рассматриваемое множество. Например, когда мы говорим о множестве
студентов какой-либо группы, то универсальным множеством может быть как
множество всех студентов университета, в котором учатся студенты этой группы,
так и множество всех людей на планете. Это определяется целями конкретной за-
дачи. Если надо найти некоторое множество точек на плоскости, то универсальным
множеством будет множество всех точек плоскости. Универсальное множество
обычно обозначается символом
U.
Множество, в котором нет ни одного элемента, называется пустым или несу-
ществующим множеством и обозначается
∅.
Для любого элемента x можно сказать, что пустое множество обладает свой-
ством x ∉ ∅. Пустое множество может возникнуть при задании множества U и
1.3. Подмножества 9
некоторого свойства A, такого, что в U нет ни одного элемента со свойством A,
например, множество
М = {x: x натуральное число, для которого ex < 2x}
не имеет ни одного элемента, т.е. является пустым. Имеется только одно пустое
множество, и если М и S пустые множества, то М = S, поскольку они состоят из
одних и тех же элементов, а именно – из никаких элементов.
1.3. Подмножества
Выбирая из множества М какие-либо элементы, можно получить новое множе-
ство S, которое будет частью множества М или, как еще говорят, подмножеством
множества М. Иначе говоря, множество S является подмножеством множества М,
если каждый элемент S является также и элементом М. Это отношение записыва-
ется так
S ⊆ M или M ⊇ S,
что иногда читают, как S содержится в М или М содержит S.
Обычно принято считать, что часть «меньше» целого, однако в теории множеств
это не так, поскольку каждое множество является подмножеством самого себя,
т.е.M ⊆ M, это свойство называют рефлексивностью.
Пример 1.2
(а) Рассмотрим множества
Х = {1, 2, 3, 4, 7, 8} Y = {2, 3, 8, 9} Z = {2, 8}.
Здесь Z ⊆ X и Z ⊆ Y, но Y не является подмножеством Х, поскольку имеет
элемент 9, которого нет в множестве Х. Кроме того, поскольку эти множества
определяют одну и ту же задачу, то все они должны принадлежать к универсальному
множеству U и это множество U должно содержать, по крайней мере, следующие
элементы {1, 2, 3, 4, 7, 8, 9}.
(b) Пусть N, Z, Q, R множества, о которых упоминалось в параграфе 1.1. Тогда
N ⊆ Z ⊆ Q ⊆ R.
(с) Каждое множество Х является подмножеством универсального множества U,
поэтому, по определению, все элементы Х принадлежат U. Пустое множество ∅
также является подмножеством Х.
(d) Если каждый элемент А принадлежит множеству В, а каждый элемент В
принадлежит множеству С, тогда каждый элемент А принадлежит С, т.е. если A ⊆ B
и B ⊆ C, тогда A ⊆ C.
(e) Если A ⊆ B и B ⊆ A, тогда А и В имеют те же самые элементы и А = В. Об-
ратно, если А = В, тогда A ⊆ B и B ⊆ A, т.к. каждое множество является подмно-
жеством самого себя.
10 Глава 1. Теория множеств
Формально последние три случая определяют следующие условия:
1. Для любого множества А всегда ∅ ⊆ A ⊆ U.
2. Для любого множества А выполняется A ⊆ A.
3. Если A ⊆ B и B ⊆ C, тогда A ⊆ C.
4. A = B, только если A ⊆ B и B ⊆ A.
Если A ⊆ B и A = B, то A называют несобственным подмножеством B. Когда
A ⊆ B и A ≠ B, т.е. в B содержится по крайней мере один элемент, которого нет
в A, то A называют собственным подмножеством B и пишут A ⊂ B. Пусть, например,
A = {1, 2} B = {1, 2, 3, 4, 5} C = {5, 4, 3, 2, 1}.
Здесь A и B являются подмножествами C, но A – собственное подмножество,
а B – несобственное подмножество C.
1.4. Диаграммы Венна
Диаграмма Венна позволяет получить визуальное представление множеств в виде
замкнутых областей на плоскости. Универсальное множество представляется вну-
тренними точками прямоугольника, а другие множества представляются точками
кругов (или каких-либо других областей, ограниченных замкнутыми кривыми),
лежащих внутри этого прямоугольника. Фактически эти множества являются под-
множествами универсального множества и поэтому между ними может существо-
вать взаимосвязь в том смысле, что они имеют общие элементы. Например, для
двух множеств A и B возможны три случая взаимосвязи по отношению включения.
Если эти множества не имеют общих элементов, т.е множества не пересекаются,
тогда диск, представляющий A, будет отделен от диска, представляющего B, как
на рис. 1.1а. Если A ⊂ B, т.е. все элементы A являются также и элементами B, тог-
да диск, представляющий A, будет полностью лежать внутри диска для B как на
рис. 1.1b.(В случае, когда A ⊆ B и A = B, диск, представляющий A, будет совпадать
с диском для B.)
Третий случай взаимосвязи множеств A и B показан на рис. 1.1с, при этом:
– некоторые элементы имеются в A, но их нет в B,
– есть элементы B, которых нет в А,
– есть элементы, которые принадлежат и A и B одновременно,
– есть элементы, которых нет ни в A, ни в B.
а) b) c)
А и В не пересекаются А ⊂ В
A В
B
A
A B
Рис. 1.1
1.4. Диаграммы Венна 11
Вывод и диаграммы Венна
Аргументация в логике представляет собой полное или частичное обоснование
какого-либо утверждения (заключения) с помощью других утверждений (по-
сылок). Под выводом понимается утверждение того, что заключение следует из
посылок. Вывод называется правильным тогда и только тогда, когда из конъюнк-
ции посылок следует заключение, т.е. во всех случаях, когда посылки истинны,
заключение тоже является истинным. Поскольку словесные утверждения по су-
ществу являются утверждениями о множествах, то поэтому их можно описывать
диаграммами Венна.
Следовательно, диаграммы Венна можно использовать для проверки правиль-
ности выводов.
Пример 1.3
Показать, что следующий аргумент правильный:
A: Компьютеры, которые установлены на кафедре программирования, имеют
LCD-дисплеи.
В: Компьютеры университета, которые используются в учебном процессе, со-
единены с интернетом.
С: Ни один компьютер кафедры программирования не соединен с интернетом.
D: Все компьютеры, которые используются в учебном процессе, не имеют
LCD-дисплеев.
Здесь утверждения А, В и С означают посылки, а утверждение D ниже линии
означает заключение. Вывод правильный, если заключение D логически следует
из утверждений А, В и С.
Из утверждения А компьютеры с LCD-дисплеями входят в множество ком-
пьютеров университета, а из утверждения С следует, что множество компьютеров
кафедры программирования и множество компьютеров, которые соединены с ин-
тернетом, не пересекаются.
Из утверждения В следует, что компьютеры, которые используются в учебном
процессе, образуют подмножество компьютеров, которые соединены с интернетом,
как это показано на рис. 1.2.
Вывод является правильным, что видно из диаграммы Венна, поскольку множе-
ство компьютеров, используемых в учебном процессе, не пересекается с множеством
компьютеров с LCD-дисплеями.
Необходимо заметить, что поскольку речь идет о проверке правильности вывода,
истинность заключения при этом не рассматривается. Истинность заключения не
является ни необходимым, ни достаточным условием правильности вывода. Если
все посылки истинны, то заключение истинно. Но если хотя бы одна из посылок
ложна, то заключение может быть как истинным, так и ложным, т.е. правильность
вывода зависит от того, что представляют собой его посылки, и, фактически, опре-
деляется только его формой.
12 Глава 1. Теория множеств
1.5. Операции над множествами
Операции над множествами позволяют получать из исходных множеств новые
множества. При этом предполагается, что и сами исходные множества, и вновь
полученное множество являются подмножествами одного и того же универсаль-
ного множества.
Операция объединения множеств
Объединением двух множеств А и В, обозначается A B, называется множество
всех элементов, которые принадлежат к А или к В, т.е.
A B = {x: x ∈ A или x ∈ B}.
Здесь союз «или» используется в смысле и / или. На рис. 1.3 объединение A B
представлено на диаграммах Венна заштрихованной областью. Если А и В непу-
стые множества и А не совпадает с В, то возможны три различные диаграммы для
объединения, рис. 1.3.
Пример 1.4
Пусть А = {1, 2, 3, 4, 5}, B = {1, 3, 7, 8}, A B = {1, 2, 3, 4, 5, 7, 9}.
Этот случай показан на рис. 1.3а, множества имеют общие элементы {1, 3}.
Если А = {1, 2, 3, 4, 5}, B = {7, 8, 9}, то здесь множества А и В не имеют общих
элементов, как показано на рис. 1.3b, A B = {1, 2, 3, 4, 5, 7, 8, 9}.
Если А = {1, 2, 3, 4, 5, 6,}, B = {1, 2, 3}, A B = {1, 2, 3, 4, 5, 6}, то в этом случае
B ⊂ A, т.е. A B = A, как на рис. 1.3с.
Компьютеры кафедры
программирования
Компьютеры,
соединенные
с интернетом
Компьютеры
с LCD]дисплеем Компьютеры,
используемые
в учебном процессе
Рис. 1.2
1.5. Операции над множествами 13
Операция пересечения множеств
Пересечением двух множеств А и В, обозначается A B, называется множество
элементов, которые принадлежат и А и В, т.е.
A B = {x: x ∈ A и x ∈ B}.
Пересечение представлено на диаграммах Венна заштрихованной областью,
рис. 1.4. Здесь, как и в случае с операцией объединения, также имеется три случая.
Если А = {1, 2, 3, 4, 5}, B = {2, 3, 6, 7, 8}, A B ={2, 3}, рис. 1.4a.
Если A = {1, 2, 3, 4}, B ={6, 7, 8, 9}, A B = ∅, т.е. множества А и В не пере-
секаются, рис. 1.4b.
Если А = {1, 2, 3, 4, 5, 6}, B ={4, 5,6}, A B =B ={4, 5,6}, рис. 1.4с.
A В A В A В
а) b) c)
Рис. 1.3
В
A
A В
В
A
а) b) c)
Рис. 1.4
Теорема 1.1. Следующие соотношения эквивалентны:
A ⊂ В, A B = A, и A B = B.
Следует заметить, что вопрос о том, является ли А собственным или несоб-
ственным подмножеством В, в общем, не существенен и поэтому можно записать
теорему следующим образом:
A ⊆ B, A B = A и A B = B.
14 Глава 1. Теория множеств
Операция дополнения множеств
Если все множества рассматривается в некоторое определенное время и являются
подмножествами фиксированного универсального множества U, тогда можно опре-
делить универсальное дополнение, или просто дополнение множества А, обозначается
Ас, как множество элементов, которые принадлежат U, но не принадлежат А, т.е.
Ас ={x: x ∈ U, x ∉ A}.
В некоторых текстах дополнение A обозначается как A’ или На рис. 1.5а до-
полнение Ас показано заштрихованной областью.
Операция разности множеств
Если подобным же образом рассматривать дополнение множества В до другого
множества А, то можно получить операцию разности множеств А и В, обозначаемую
как А \ В, которая задает множество элементов, принадлежащих А, но не принад-
лежащих В, т.е.
А \ В = {x: x ∈ A, x ∉ B}.
Иногда множество А \ В читается как «А минус В» и обозначается А – В. На
рис. 1.5b разность А \ В заштрихована.
A
Ас заштриховано А \ В заштриховано
AС
A В
а) b)
Рис. 1.5
Нетрудно заметить, что для любых двух множеств А и В выполняется тождество
А \ В =А ∩ ВС.
Пример 1.5
Пусть универсальное множество U = N ={1, 2, 3, 4,…} является множеством
натуральных чисел и пусть
А = {1, 2, 3, 4, 5}, B = {4, 5, 6, 7, 8}, C = {7, 8, 9}
и пусть D={1, 3, 5, 7, 9,…} множество нечетных чисел. Тогда дополнения
Ас ={6, 7, 8, 9, …}, Bc = {1, 2, 3, 9, 10, 11, …}, Cc = {1, 2, 3, 4, 5, 6, 10, 11, …},
1.6. Фундаментальное произведение множеств 15
и разности множеств
А \ В = {1, 2, 3}, А \ C = {1, 2, 3, 4, 5}, B \ C = {4, 5, 6}, C \ B = {9},
B \ A={6, 7, 8}, A \ D ={2, 4}, Dc = {2, 4, 6, 8, 10,…}, множество четных чисел.
Симметрическая разность множеств
Симметрической разностью множеств А и В, обозначается А ⊕ В, называется
множество, которое состоит из элементов либо А, либо В, но не входящих в оба
эти множества одновременно. Иначе говоря, это объединение этих множеств, из
которого удалено их пересечение
А ⊕ В = (А В) \ (А В).
Можно также показать, что
А ⊕ В = (А \ В) (В \ А).
Например, пусть А = (1, 2, 3, 4, 5, 6}, B = {4, 5, 6, 7, 8}. Тогда
А \ В ={1, 2, 3}, B \ A={7, 8} и тогда А ⊕ В = {1, 2, 3, 7, 8}.
На рис. 1.6 на диаграмме Венна множество А ⊕ В заштриховано.
В
А ⊕ В заштриховано
A
Рис. 1.6
1.6. Фундаментальное произведение множеств
Операции над множествами позволяют образовывать из исходных множеств новые
множества. При этом операция пересечения множеств применяется для различных
практических задач, таких как классификация каких-либо объектов, анализ различ-
ного рода социологических опросов или исследований, анализ данных, из которых
необходимо выбрать данные, характеризуемые заданными свойствами. Рассмотрим
следующий пример. Пусть имеется список студентов группы, успешно решивших
первую задачу контрольной работы (обозначим множество их фамилий как А). Пусть
также имеется список всех тех, кто успешно решил вторую задачу (множество В), и
16 Глава 1. Теория множеств
всех тех, кто решил третью (множество С). Если теперь потребуются сведения о тех,
кто успешно решил и первую и вторую задачи одновременно, то необходимо будет
выбрать тех, кто входит одновременно и в первый, и во второй списки. Для этого
надо найти новое множество, являющееся пересечением исходных множеств А и
В, т.е. найти множество А ∩ В. Однако это множество не содержит информации
о том, решили или нет данные студенты третью задачу. Ясно, что для этого потре-
буется найти еще одно множество, являющееся пересечением всех трех множеств,
т.е. множество А ∩ В ∩ С.
Предположим теперь, что необходимо составить такой список, в котором при-
сутствуют фамилии студентов, которые решили первую и вторую задачи, но не
решили третьей. В этом случае надо найти множество А ∩ В ∩ Сс.
Рассмотрение подобных случаев приводит к понятию фундаментального про-
изведения множеств.
Пусть имеется n различных множеств А1, А2, А3, …, Аn. Фундаментальным про-
изведением множеств называется множество вида
А1
* ∩ А2
* ∩ А3
* ∩ …∩ Аn
*,
где Аi
* это либо Аi, либо Аi
c. Заметим также, что
(1) Имеется точно 2n таких фундаментальных произведений.
(2) Любые два таких фундаментальных произведения не пересекаются.
(3) Универсальное множество является объединением всех таких фундамен-
тальных произведений.
Рассмотрим пример из трех множеств А, В и С и дадим геометрическую интер-
претацию их фундаментальных произведений, pис. 1.7.
U
А
В
С
P6
P5
P7
P3
P1
P4 P2
P0
Рис. 1.7
1.7. Классы множеств, степенные множества и разбиения 17
А = {1, 2, 3, 6, 7}
B = {3, 4, 5, 6}
C = {5, 6, 7, 8}
U = {1, 2, 3, 4, 5, 6, 7, 8, 9}.
Имеется ровно восемь фундаментальных произведений из трех множеств:
P0 = Ac ∩ Bc ∩ Cc = {9} P1 = Ac ∩ Bc ∩ C = {8} P2 = Ac ∩ B ∩ Cc = {4}
P3 = Ac ∩ B ∩ C ={5} P4 = A ∩ Bc ∩ Cc = {1, 2} P5 = A ∩ Bc ∩ C = {7}
P6 = A ∩ B ∩ Cc ={3} P7 = A ∩ B ∩ C = {6}.
1.7. Классы множеств, степенные множества
и разбиения
Для данного множества S можно рассматривать множество всех его подмножеств.
При этом придется рассматривать множество, элементами которого будут также
множества, т.е. множество множеств. Чтобы избегать путаницы, часто бывает более
удобно говорить о классе множеств или о семействе множеств. Если необходимо
рассмотреть множества из данного класса, то можно говорить о подклассе или
подсемействе. Например, рассмотрим множество S = {a, b, c, d}. Пусть А класс под-
множеств S из трех элементов. Тогда
А = [{a, b, c}, {a, b, d}, {a, c, d}, {d, c, d}].
Элементами класса А являются множества {a, b, c}, {a, b, d}, {a, c, d} и {b, c, d}.
Пусть теперь В класс подмножеств S, который содержит элемент а и два других
элемента из S. Тогда
В = {{a, b, c}, {a, b, d}, {a, c, d}].
Элементами В являются множества{a, b, c}, {a, b, d} и {a, c, d}]. Поэтому В яв-
ляется подклассом класса А.
Для данного множества S можно говорить о классе всех подмножеств S. Этот
класс называют степенным множеством S и обозначают 2S. Если n(S) – число элемен-
тов множества S, то число элементов степенного множества n(2S) представляет собой
степень 2 и равно n(2S) = 2n(S). Например, если S = {a, b, c}, то степенное множество
2S = [∅, , , , {a, b},{a, c}, {b, c}, S].
Заметим, что пустое множество ∅ принадлежит к 2S, т.к. пустое множество
является подмножеством S и само S принадлежит 2S, поэтому число элементов
n(2S) = 23 = 8.
Рассмотрим теперь еще одно важное понятие, которое называется разбиением
множества S. Разбиением множества S называется семейство {Аi} непустых под-
множеств S, для которых:
1. Каждый элемент х из S принадлежит к одному из подмножеств Аi.
2. Подмножества из {Аi} взаимно не пересекаются, т.е., если Аi ≠ Аj тогда
Аi ∩ Аj = ∅.
18 Глава 1. Теория множеств
Подмножества в разбиении иногда называют клетками или блоками. На pис. 1.8
представлена диаграмма Венна, изображающая разбиение прямоугольного множе-
ства точек S, на пять клеток А1, А2, А3, А4, А5.
Фундаментальные произведения также представляют собой разбиение уни-
версального множества.
Операции объединения и пересечения могут быть распространены на любое
количество множеств. Объединение состоит из таких элементов, которые принад-
лежат по крайней мере к одному из множеств, а пересечение – из таких элементов,
которые принадлежат ко всем множествам.
1.8. Алгебра множеств и двойственность
Абстрактная алгебра занимается изучением операций, производимых над некото-
рыми элементами. К настоящему времени идеи абстрактной алгебры используются
не только для математических методов, но и позволяют получать практические
результаты. Операции объединения, пересечения и дополнения, производимые
над множествами, удовлетворяют определенным законам (или тождествам) и
образуют алгебру множеств. Поскольку числовая алгебра появилась раньше, то
возникает вопрос, какая из операций (пересечение или объединение) «похожа» на
операцию сложения чисел и какая – на операцию умножения. Ответить на этот
вопрос едва ли возможно. Для чисел, например, выполняется только дистрибутив-
ность умножения относительно сложения, а в алгебре множеств рассматривают два
закона дистрибутивности: пересечения относительно объединения и объединения
относительно пересечения.
Важным при выполнении операций является их приоритет. Сначала выполня-
ется операция дополнения, затем пересечения и затем объединения.
Множества удовлетворяют следующим законам (или тождествам):
1 A ∩ B = B ∩ A A ∪ B = B ∪ A
Коммутативность – означает, что
любые два элемента можно менять
местами
2
(A ∩ B) ∩ C =
= A ∩ (B ∩ C)
(A ∪ B) ∪ C =
= A ∪ (B ∪ C)
Ассоциативность – результат опе-
рации не зависит от порядка ее
выполнения
А1
А2 А3
А4
А5
Рис. 1.8
1.8. Алгебра множеств и двойственность 19
3 A ∩ A = A A ∪ A = A
Идемпотентность – формулы алге-
бры множеств не имеют ни степе-
ней, ни коэффициентов
4
A ∩ (B ∩ C) =
= (A ∩ B) ∪ (A ∩ C)
A ∪ (B ∩ C) =
= (A ∪ B) ∩ (A ∪ C)
Дистрибутивность – раскрытие ско-
бок и вынесение общего элемента
5 A ∩ (A ∪ B) = A A ∪ (A ∩ B) = A
Законы поглощения – большее по
числу переменных пересечение
(или объединение) поглощается
меньшим
6 (A ∩ B)С = AC ∪ BC (A ∪ B)C = АC ∩ ВC
Законы де Моргана – дополнение
пересечения (объединения) не-
скольких множеств заменяется на
объединение (пересечение) допол-
нений каждого из этих множеств
7 (AC)C = A
Инволюция – дополнение допол-
нения множества дает исходное
множество
8
A ∩ AC = ∅
∅C = U
A ∪ AC = U
UC = ∅
Законы дополнения
9
A ∩ U = A
A ∩ ∅ = ∅
A ∪ ∅ = A
A ∪ U =U
Законы тождества
Принцип двойственности алгебры множеств
Нетрудно заметить, что тождества в таблице располагаются парами, например,
первое тождество A ∩ B = B ∩ A имеет парное A ∪ B = B ∪ A, и это выполняется
для всех остальных законов алгебры множеств.
Принцип двойственности состоит в том, что если верно какое либо тождество, то
тождество, полученное из него путем замены каждой из операций ∪, ∩, а также U
и ∅ на операции ∪, ∩, ∅ и U соответственно, будет также верно. Поэтому у любого
тождества есть его «двойник», отличающийся тем, что у него каждая операция заме-
нена на парную ей (объединение – на пересечение, а пересечение – на объединение)
и при этом пустое множество заменяется на универсальное, а универсальное на
пустое. Принцип двойственности очень важен, поскольку если доказана истинность
какого-либо выражения, то истинность двойственного ему можно не доказывать –
оно будет истинно вследствие данного принципа. Например, для верного тождества
A = (A ∩ BC ∩ CC) ∪ (A ∩ (B ∪ C)),
двойственное ему будет также верным тождеством
A = (A ∪ BC ∪ CC) ∩ (A ∪ (B ∩ C)).
Или для верного тождества
A = (A ∩ U) ∪ (A ∩ B ∩ C),
двойственное ему тождество A = (A ∪ ∅) ∪ (A ∪ B ∪ C).
20 Глава 1. Теория множеств
1.9. Доказательство тождеств с множествами
Для доказательства равенства тождеств обычно используются четыре метода:
1. Элементный метод.
2. Диаграммы Венна.
3. Табличный метод.
4. Алгебраический метод.
Элементный метод основан на том, что для произвольно выбранного элемента x
из множества, заданного в левой части тождества, доказывается, что этот элемент
принадлежит и множеству правой части этого тождества. Затем выбирается про-
извольный элемент из правой части и показывается, что он входит и в левую часть.
Вместе это доказывает, что оба множества состоят из одних и тех же элементов.
Докажем далее законы алгебры множеств.
Доказательство коммутативности (или переместительного свойства) операций
объединения и пересечения самоочевидно, поскольку ни в определении пересече-
ния, ни в определении объединения ничего не говорится о порядке подмножеств.
Ассоциативность (или сочетательный закон) также просто доказывается. Пока-
жем, что (A ∩ B) ∩ C ⊆ A ∩ (B ∩ C). Если x ∈ (A ∩ B) ∩ C, то x ∈ (A ∩ B) и x ∈ С, из
x ∈ (A ∩ B) следует, что x ∈ А и x ∈ B, т.е. x принадлежит всем трем множествам A,
B и C. Следовательно, x ∈ (B ∩ C) и x ∈ A ∩ (B ∩ C). Обратное включение пока-
зывается аналогично, поскольку множество в правой части тождества также обра-
зовано из элементов (и только из таких), которые входят в каждое из множеств A,
B и C. Ассоциативность для операции объединения следует из того, что элементы
в множестве левой части тождества и элементы в множестве правой части, состоят
из таких и только таких элементов, которые принадлежат, по крайней мере, одному
из подмножеств A, B и C.
Идемпотентность означает, что если x ∈ A ∩ A, то значит x принадлежит пере-
сечению множества A с самим собой, т.е. x принадлежит самому множеству A. Если
элемент x ∈ A ∪ A, то x принадлежит объединению множества A с самим собой,
т.е. и в этом случае он принадлежит только множеству A.
Докажем дистрибутивность пересечения относительно объединения.
A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C).
Необходимо убедиться, что множества, стоящие в левой и правой частях этого
тождества, состоят из одних и тех же элементов. Сначала покажем, что множество
левой части включается в множество правой части.
A ∩ (B ∪ C) ⊆ (A ∩ B) ∪ (A ∩ C).
Пусть x ∈ A ∩ (B ∪ C). Тогда по определению операции пересечения x ∈ A и
x ∈ (B ∪ C). Если x ∈ B, то тогда x принадлежит и A и B и поэтому он принадлежит
и их пересечению x ∈ (A ∩ B). Но поскольку x принадлежит объединению B и C, то
он может принадлежать не только B, но и С и даже обоим этим множествам. Если
x ∈ С, тогда он принадлежит и пересечению А и С, т.е. x ∈ (A ∩ C). Но отсюда можно
видеть, что в любом из этих случаев x принадлежит к какому-то из множеств – либо
1.9. Доказательство тождеств с множествами 21
(A ∩ B), либо (A ∩ C), и тогда, в соответствии с определением операции объедине-
ния, x принадлежит и объединению этих множеств x ∈ (A ∩ B) ∪ (A ∩ C) и поэтому
A ∩ (B ∪ C) ⊆ (A ∩ B) ∪ (A ∩ C).
Теперь покажем, что множество из правой части включается в множество левой.
Пусть x ∈ (A ∩ B) ∪ (A ∩ C). Если x ∈ (A ∩ B), то отсюда x ∈ A и x ∈ В. Но
поскольку x ∈ В, то он принадлежит и объединению множества В с любым другим
множеством, в частности и с множеством С, т.е. x ∈ (B ∪ C). В связи с тем, что x
входит в множество A и в множество (B ∪ C), то он входит и в их пресечение. Если
же x ∈ (A ∩ C), то тогда x ∈ A и x ∈ С. Но поскольку x ∈ С, то он принадлежит и
объединению В с любым другим множеством, т.е. x ∪ (B ∪ C). Поскольку и в этом
случае x входит в оба множества и в А и в (B ∪ C), то он входит и в их пресечение
x ∈ A ∩ (B ∪ C), поэтому(A ∩ B) ∪ (A ∩ C) ⊆ A ∩ (B ∪ C).
Докажем теперь двойственное тождество, т.е. дистрибутивность объединения
относительно пересечения A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C). Для этого надо по-
казать, что всякий элемент x множества A ∪ (B ∩ C) принадлежит и множеству
(A ∪ B) ∩ (A ∪ C). Если элемент x принадлежит множеству А, то он принадлежит
и множеству A ∪ (B ∩ C), потому что оно содержит множество А. В то же время,
если x ∈ A, то он входит и в пересечение (A ∪ B) ∩ (A ∪ C). Допустим x не является
элементом множества А. Тогда он должен принадлежать пересечению (B ∩ C), а
также каждому из множеств B и C в отдельности. Тогда по определению операции
объединения x ∈ (A ∪ B) и x ∈ (A ∪ С). Из этого следует, что x принадлежит и пере-
сечению этих множеств (A ∪ B) ∪ (A ∪ C). И в том и в другом случае x из левого
множества входит и в правое. Пусть x принадлежит правому множеству. Тогда, если
он принадлежит множеству А, то он принадлежит и множеству A ∪ (B ∩ C) по
определению объединения. Если он не принадлежит А, то тогда он принадлежит
и В и С в отдельности, а значит, он принадлежит и пересечению (B ∪ C) и поэто-
му в каждом из этих случаев любой элемент из правого множества входит в левое
множество, что и требовалось доказать.
Докажем законы поглощения.
A ∩ (A ∪ B) = A,
A ∪ (A ∩ B) = A.
Доказательство обоих законов очевидно. Пусть, например, x ∈ A ∩ (А ∪ В). Тогда
x ∈ A и x ∈ (А ∪ В). Если допустить, что поскольку x принадлежит объединению
А и В, то он принадлежит множеству В, но не принадлежит множеству А, но это
приводит к противоречию, поскольку по определению пересечения x ∈ A. Другими
словами, любой элемент левого множества может быть только из множества А.
Для доказательства закона де Моргана (A ∩ B)С = AC ∪ BC покажем сначала,
что левое множество включается в правое (A ∩ B)С ⊆ AC ∪ BC. Пусть x ∈ (A ∩ B)С.
Тогда x ∉ A ∩ B. Из этого следует, что х не входит в оба множества одновременно,
т.е. он не входит либо в А, либо в В. Если он не входит в А, то тогда он входит в АС,
а если он не входит в В, то тогда он входит в ВС. Отсюда следует, что х ∈ AC ∪ BC и
поэтому (A ∩ B)С ⊆ AC ∪ BC.
Докажем теперь, что всякий элемент х из множества AC ∪ BC принадлежит и
множеству (A ∩ B)С. Если x ∈ AС, то тогда x ∉ A, и поэтому х не может принад-
22 Глава 1. Теория множеств
лежать пересечению x ∉ A ∩ B. Если x ∈ ВС, то тогда x ∉ В, и поэтому х также не
может принадлежать пересечению x ∉ A ∩ B. В любом из этих случаев x ∉ A ∩ B
и потому x ∈ (A ∩ B)С.
Докажем двойственный закон де Моргана (A ∪ B)C = АC ∩ ВC. Поскольку
элемент х принадлежит множеству (A ∪ B)C тогда и только тогда, когда он не при-
надлежит ни множеству А, ни множеству В, то из этого следует, что он должен
входить и в множество АC, и в множество ВC, т.е. в их пересечение АC ∩ ВC. С другой
стороны, если х входит в пересечение АC ∩ ВC, то он не может входить ни в А, ни
в В, потому что в пересечении дополнений множеств ни могут находиться элемен-
ты самих этих множеств. Но тогда х входит в дополнение к их объединению, т.е.
x ∈ (A ∪ B)С, что и требовалось доказать.
Доказательство закона инволюции (AC)C = A следует из того факта, что любой
элемент из U принадлежит либо А, либо AC. Поэтому когда берется дополнение
к множеству А, то получается множество АС, а когда берется дополнение к АС, то
снова получается множество А.
Законы дополнения и тождества очевидны и не требуют доказательства.
Второй метод доказательства равенства тождеств состоит в использовании
диаграмм Венна. Однако здесь иногда приходится рассматривать всевозможные
случаи, при которых множества не имеют общих элементов, пересекаются или
вкладываются друг в друга.
Докажем, например, закон де Моргана (A ∩ B)С = AC ∪ BC. На рис. 1.9 пред-
ставлены три случая (а) – когда А и В не пересекаются, (b) – когда А включается
в В, и (с) – когда в пересечение входят элементы и из А и из В (имеется и случай,
когда В включается в А, но он аналогичен случаю (b)). На рис 1.9d, e и f показаны
их дополнения. Далее на (а1), (b1) и (с1) показаны множества AC ∪ BC для каждого
из этих случаев. Можно видеть, что на каждом рисунке области для множества
(A ∩ B)С и множества AC ∪ BC одинаковые во всех трех случаях и поэтому эти
множества равны.
Рассмотрим табличный метод доказательства равенства множеств. Докажем
ассоциативность пересечения (A ∩ B) ∩ C = A ∩ (B ∩ C). Пусть имеется диаграмма
Венна для трех множеств A, B и С из универсального множества U на рис. 1.10. Три
овальные области представляют собой множества A, B и С. Прямоугольная область
определяет множество U, и она разбита на восемь областей, которые помечены
цифрами от 0 до 7. Можно видеть, что область разбиения 7 определяет множество
A ∩ B ∩ C, область 6 – множество A ∩ B ∩ CС и т.д. Чтобы по диаграмме Венна
проверить ассоциативность пересечения, можно использовать следующую идею.
Заменим множества A, B и С и их пересечения на соответствующие им множества
из областей разбиения на этой диаграмме. Множество А заменяется на {4, 5, 6, 7},
В – на {2, 3, 6, 7}, и С – на {1, 3, 5, 7}, A ∩ B – на {6, 7}, B ∩ C – на {3, 7}
Несмотря на то что множества А, В и С могут быть какими угодно, доказать
любое тождество для этих множеств можно, сведя доказательство к проверке этого
тождества на уменьшенных множествах разбиения.
(A ∩ B) ∩ C = A ∩ (B ∩ C).
{6, 7} ∩ {1, 3, 5, 7} = {4, 5, 6, 7} ∩ {3, 7}.
1.9. Доказательство тождеств с множествами 23
а) b) c)
d) e) f)
А ∩ В = ∅ А ∩ В = А А ∩ В заштриховано
(А ∩ В)С = U (А ∩ В)С = AС (А ∩ В)С заштриховано
(АС ∪ ВС) = U АС ∪ ВС = AС АС ∪ ВС заштриховано
а1) b1) c1)
А
А
А
А А
А
А А А
В
В
В
В В
В
В В В
18
Рис. 1.9
А
В
С
6
7
5
2
3
1
4
U
0
Рис. 1.10
24 Глава 1. Теория множеств
Не трудно видеть, что и левое, и правое множества этого тождества состоят из
одного единственного элемента 7, что и доказывает ассоциативность пересечения
множеств.
Докажем то же самое, используя табличный метод. Для этого построим таблицу,
столбцы которой соответствуют различным множествам тождества, а каждая строка
соответствует одному из множеств разбиения (строк 8, поскольку разбиение со-
стоит из 8 множеств в соответствии с рис 1.10). Строки содержат ответы на вопрос:
входит ли соответствующее данной строке множество разбиения во множество
доказываемого тождества или нет. Три первые столбца таблицы дают ответы, вхо-
дит ли соответствующее множество разбиения во множество А, во множество В и
во множество С. Столбец «Левая часть» соответствует левой части доказываемого
тождества (A ∩ B) ∩ C, столбец «Правая часть» – правой части A ∩ (B ∩ C).
А В С
Множество
разбиения
A ∩ B
Левая
часть
B ∩ C
Правая
часть
нет нет нет 0 нет нет нет нет
нет нет да 1 нет нет нет нет
нет да нет 2 нет нет нет нет
нет да да 3 нет нет да нет
да нет нет 4 нет нет нет нет
да нет да 5 нет нет нет нет
да да нет 6 да нет нет нет
да да да 7 да да да да
Поскольку ответы для всех строк «Левой части» те же самые, что и для «Правой
части», тождество является доказанным. Табличный метод особенно удобен при
построении доказательств с использованием компьютера.
Алгебраический метод основывается на идее разбиения доказательства на шаги,
при этом переход от одного шага к следующему осуществляется за счет примене-
ния какого-либо закона алгебры множеств (например, закона ассоциативности,
дистрибутивности, поглощения и т.д.). Доказательство требует хорошего знания
базисных законов алгебры множеств, а также определенного опыта их применения.
Рассмотрим метод на следующем примере. Пусть требуется доказать, что
(A ∩ C) \ (A ∩ B ∩ C) = A ∩ ВС ∩ C.
При переходе от одного шага к другому будем указывать (в правой части соот-
ветствующей строки) причины, позволяющие делать такие переходы
(A ∩ C) \ (A ∩ B ∩ C) = (A ∩ C) ∩ (A ∩ B ∩ C)С = поскольку А \ В = А ∩ ВС
= (A ∩ C) ∩ (AС ∪ BС ∪ C С) = по закону Де Моргана
= (A ∩ C) ∩ AС) ∪ (A ∩ C) ∩ ВС) ∪ (A ∩ C) ∩ СС) = по закону дистрибутивности
= ((A ∩ AС) ∩ C) ∪ (A ∩ ВС ∩ C)) ∪ (A ∩ (C ∩ СС)) = по закону ассоциативности
= (∅ ∩ C) ∪ (A ∩ ВС ∩ C)) ∪ (A ∩ ∅) = поскольку (A ∩ AС) = ∅
= ∅ ∪ (A ∩ ВС ∩ C) ∪ ∅ = поскольку (A ∩ ∅) = ∅
= A ∩ ВС ∩ C. поскольку A ∪ ∅ = А
1.10. Математическая индукция 25
В этом примере левое выражение преобразовано в правое. Это преобразование
облегчается тем обстоятельством, что известно, какое выражение должно быть
получено. В то же время можно и правое выражение привести к левому. Чтобы
понять, как это сделать, достаточно просмотреть первое преобразование от конца
к началу. Какой путь легче, не всегда бывает сразу ясно, поэтому иногда необходимо
попробовать оба способа, чтобы добиться правильного результата.
1.10. Математическая индукция
Имеется следующее существенное свойство множества натуральных чисел
N = {1, 2, 3, …}, которое используется при построении различных доказательств.
Принцип математической индукции
Пусть Р – некоторое утверждение, определенное на положительных целых N, т.е.
утверждение Р(n) либо истинно, либо ложно для каждого n из N. Если для Р вы-
полняются два следующих свойства:
1. P(1) истинно.
2. P(n + 1) истинно, если истинно P(n).
Тогда Р истинно для каждого положительного целого.
Обычно этот принцип используется как аксиома для доказательства других
результатов. Используем его для доказательства следующего результата:
Путь Р будет утверждением, что сумма первых n натуральных чисел, возведен-
ных в куб, равна т.е.
Р(n): 13 + 23 +33 + … + n3 =
Легко видеть, что P(n) истинно при n = 1, т.е. P(1) : 13 =
Допустим теперь, что P(n) истинно и докажем, что P(n + 1) также будет истинно.
Для этого прибавим к обеим частям выражения для P(n) следующее слагаемое (n + 1)3
13 + 23 +33 + …+n3 + (n + 1)3 = + (n + 1)3.
Преобразуем далее правую часть
P(n + 1): 13 + 23 +33 + …+ n3 + (n + 1)3 =
Таким образом, P(n + 1) истинно, когда истинно P(n). Теперь по принципу
математической индукции утверждение Р истинно для всех n. Иногда принцип
26 Глава 1. Теория множеств
математической индукции записывают в более удобном для использования
виде
1. P(1) истинно.
2. P(n + 1) истинно, если истинно P k) для всех 1 ≤ k < n.
Тогда Р истинно для каждого положительного целого.
1.11. Представление множеств формулами
При построении дискретной модели часто необходимо разбивать множества на
некоторые его части, чтобы исследовать те или иные свойства исходной модели.
Подобные задачи возникают как при разработке телекоммуникационных техно-
логий, так и в различных бизнес-приложениях. Рассмотрим такой пример. Пусть
элементами множества являются зоны торгового зала большого супермаркета и не-
обходимо разбить это множество на подмножества так, чтобы каждое подмножество
представляло собой совокупность зон, просматриваемых одной видеокамерой, при
условии, что видеокамер должно быть как можно меньше. Если зоны выбраны так,
что они покрывают все помещение зала, то при этом выбранные подмножества не
должны накладываться друг на друга, поскольку это приведет к неоптимальному
использованию видеокамер. Кроме того, возможно, что требуется просматривать не
всю площадь зала, а только некоторые ее части. Во всех таких случаях приходится
рассматривать некоторое множество, представляющее собой определенную сово-
купность подмножеств заданного множества.
Для универсального множества U всегда можно построить его разбиение, из
множеств которого легко получать требуемые совокупности. Наиболее конструк-
тивным разбиением для этих целей является система множеств, порождаемая
фундаментальными произведениями. Из 1.7 следует, что для любых n множеств
можно построить разбиение S универсального множества U на 2n подмножеств,
называемых фундаментальными произведениям.
Определение
Любое множество или совокупность множеств разбиения S можно представит
как объединение пересечений, каждое из которых является фундаментальным
произведением. Обратно, каждое непустое выражение из объединения фундамен-
тальных произведений задает некоторое множество или совокупность множеств
разбиения и такое задание однозначно определяет это множество.
Если рассматривать операцию объединения как сложение, а операцию пере-
сечения как умножение, то подобные выражения часто называют многочленами.
Эти многочлены можно преобразовывать, используя алгебраические методы.
Многочлен, образованный из фундаментальных произведений, единственным
образом задает любое подмножество разбиения. Будем называть такой много-
член каноническим. Осуществляя эквивалентные преобразования выражения для
многочлена в каноническом виде, при котором сохраняется множество, которое
он определяет, можно получать более простые выражения для аналитического за-
дания данного множества. Если многочлен для заданного множества не допускает
дальнейшего упрощения, то такой многочлен называется минимальным.
1.11. Представление множеств формулами 27
Рассмотрим пример использования многочленов.
Пример 1.6
Предположим, что в некотором университете проведена выборочная про-
верка посещаемости занятий девяти студентов по трем предметам: математике,
информатике и английскому языку. Обозначим через А множество тех студентов,
которые имеют, по крайней мере, один пропуск по математике. Тогда АС будет
представлять собой множество студентов, которые не имеют ни одного пропуска
по математике. Пусть В – множество студентов, которые имеют, по крайней
мере, один пропуск по информатике, и С – по крайней мере, один пропуск по
английскому языку.
В деканат поступили следующие сведения:
– список студентов, которые не имеют пропусков занятий ни по одному из
предметов, AС ∩ BС ∩ CС = ∅;
– список студентов, которые не имеют пропусков ни по математике, ни по
информатике, но имеют по английскому языку (В списке вместо фамилий
будем для простоты указывать номера студентов), AС ∩ BС ∩ C = {9};
– список студентов, которые не имеют пропусков по математике и английскому
языку, но имеют – по информатике, AС ∩ B ∩ CС = {8};
– список студентов, которые не имеют пропусков по математике, но имеют по
информатике и английскому языку, AС ∩ B ∩ C = ∅;
– список студентов, которые имеют пропуски по математике, но не имеют по
информатике и английскому языку, (A ∩ BС ∩ CС) = {1, 6};
– список студентов, которые имеют пропуски по математике и английскому
языку, но не имеют по информатике, A ∩ BС ∩ C = {2, 7};
– список студентов, которые не имеют пропусков ни по математике, ни по
информатике, но имеют по английскому языку, A ∩ B ∩ CС = {3};
– список студентов, которые имеют пропуски по всем трем предметам,
A ∩ B ∩ C = {4, 5}.
Получив эти данные, деканат хотел бы составить списки тех студентов, ко-
торые:
1. Имеют пропуски по математике, но не имеют по информатике.
2. Имеют пропуски по математике и информатике.
3. Имеют, по крайней мере, один пропуск по математике.
Для того чтобы ответить на вопрос первого пункта, т.е найти множество тех
студентов, которые имеют пропуски по математике, но не имеют по информатике,
надо составить многочлен из тех фундаментальных произведений, которые включают
в себя множество A ∩ BС. Таких фундаментальных произведений два. Их объединение
и дает искомый многочлен (A ∩ BС ∩ CС) ∪ (A ∩ BС ∩ C) = {1, 6} ∪ {2, 7} = {1, 2, 6, 7}.
Это легко доказать, если выполнить упрощение данной формулы:
(A ∩ BС ∩ CС) ∪ (A ∩ BС ∩ C) = (A ∩ BС) ∩ (C ∪ СС) = по закону дистрибутивности
= (A ∩ BС) ∩ U = поскольку (C ∪ СС) = U
= A ∩ BС по закону тождества
A ∩ U = А.
28 Глава 1. Теория множеств
Аналогичное рассуждение можно применить и для второго пункта
(A ∩ B ∩ C) ∪ (A ∩ B ∩ CС) = {4, 5} ∪ {3} = {3, 4, 5}, т.к.
(A ∩ B ∩ C) ∪ (A ∩ B ∩ CС) = (A ∩ B) ∩ (C ∪ СС) = по закону дистрибутивности
= (A ∩ B) ∩ U = поскольку (C ∪ СС) = U
= A ∩ B по закону тождества
A ∩ U = А.
Для ответа на третий пункт, т.е. для определения множества А, надо составить
многочлен из четырех фундаментальных произведений, содержащих множество А.
Этот многочлен имеет вид
(A ∩ BС ∩ CС) ∪ (A ∩ BС ∩ C) ∪ (A ∩ B ∩ C) ∪ (A ∩ B ∩ CC) =
= {1, 6} ∪ {2, 7} ∪ {3} ∪ {4, 5} = {1, 2, 3, 4, 5, 6, 7}.
Многочлен можно упростить
(A ∩ BС) ∩ (С ∪ СС) ∪ (A ∩ B) ∩ (С ∩ CС) = по закону дистрибутивности
(A ∩ BС) ∩ U ∪ (A ∩ B) ∩ U = поскольку (C ∪ СС) = U
(A ∩ BС) ∪ (A ∩ B) = по закону тождества
A ∩ (BС ∪ B) = по закону дистрибутивности
A ∩ U = A по закону тождества.
Решение задачи можно получить и при помощи диаграммы Венна, показанной
на рис. 1.11.
U
A ∩ B ∩ CС
{3}
AС ∩ BС ∩ C
{9}
A ∩ BС ∩ CC
{1, 6}
AС ∩ B ∩ CC
{8}
A ∩ BС ∩ C
{2, 7}
A ∩ B ∩ C
{4, 5}
AС ∩ B ∩ C
{∅}
AС ∩ BС ∩ C C
{∅}
А
В
С
Рис. 1.11
1.12. Многочлены алгебры множеств 29
Поскольку мы имеем все 8 комбинаций из трех исходных множеств и их до-
полнений, т.е. имеем все 8 фундаментальных произведений для трех множеств, то
к решению данной задачи можно подойти и иначе. Допустим, нам надо выполнить
первый пункт задачи, т.е. найти множество тех студентов, которые имеют пропу-
ски по математике, но не имеют их по информатике. Фактически нам надо найти
пересечение двух множеств: множества А (имеющих пропуски по математике) и
множества ВС (не имеющих пропусков по информатике), т.е. множество A ∩ BС.
Для того чтобы найти элементы этого множества, нам нужно выразить множества
A ∩ BС через фундаментальные произведения. Сделать это можно с помощью ис-
кусственного приема, который позволяет вводить в любое пересечение множеств
те множества, которые в нем отсутствуют, приводя его, тем самым, к объединению
фундаментальных произведений.
A ∩ BС = (A ∩ BС) ∩ (С ∪ СС) = поскольку С ∪ СС = U, а (A ∩ BС) ∩ U = (A ∩ BС)
= (A ∩ BС ∩ С) ∪ (A ∩ BС ∩ СC) по закону дистрибутивности.
Это решение по сути дела представляет собой действия, произведенные при
решении задачи в первом случае, но выполненные в обратном порядке. Этот же
способ позволяет выразить любое множество через фундаментальные произведения.
1.12. Многочлены алгебры множеств
Множества с операциями пересечения, объединения и дополнения, удовлетворя-
ющие абстрактным законам, введенным в 1.8, образуют алгебраическую систему,
называемую алгеброй множеств. Эта алгебра является булевой алгеброй и поэтому
часто использует идеи и терминологию булевой алгебры, однако следует отметить,
что эта терминология не вполне стандартизирована, что иногда приводит к раз-
личным названиям одних и тех же понятий. Рассмотрим некоторые понятия более
подробно.
Пусть имеется n переменных, каждая из которых определяет некоторое мно-
жество. Выражением алгебры множеств Е (или формулой) называется выражение,
составленное из этих переменных, соединенных при помощи операций объедине-
ния, пересечения и дополнения, например
Е1 = A ∩ (BС ∩ С)С ∪ (A ∩ BС ∩ СC)С,
Е2 = A ∩ (BС ∩ С) ∪ (A ∩ BС ∩ СC),
Е3 = (A ∩ BС ∩ С) ∪ (A ∩ BС ∩ СC),
Е4 = (AC ∪ BC) ∩ (AC ∪ BC ∪ С) ∩ (BC ∪ С),
Е5 = (AC ∪ B ∪ С) ∩ (A ∪ BC ∪ С) ∩ (AC ∪ BC ∪ С)
являются выражениями из трех переменных А, В и С.
Литералом называется переменная или дополнение переменной, например А,
АС, ВС и т.д. Произведением называется литерал или пересечение двух или более
литералов, таких, что ни одна пара из них не содержит одной и той же переменной.
Например, BС ∩ С, A ∩ BС ∩ СC, А, СC – являются произведениями, а выражения
30 Глава 1. Теория множеств
A ∩ BС ∩ АС и A ∩ BС ∩ BС – нет. Заметим, что любое пересечение литералов всегда
приводится либо к ∅, либо к произведению. Так, например, A ∩ BС ∩ АС = ∅, по-
тому что A ∩ АС = ∅ (по закону дополнения), а пересечение A ∩ BС ∩ BС = A ∩ BС,
потому что BС ∩ BС = BС (по закону идемпотентности).
Если при n переменных произведение состоит из n литералов, то его называют
фундаментальным произведением (некоторые авторы называют любое произведение
фундаментальным произведением).
Выражение, представляющее собой объединение различных произведений,
если в нем нет ни одного произведения, которое включается в другое произведение,
называют суммой произведений, или нормальной формой объединения пересечений,
или многочленом в нормальной форме. Из предыдущего примера Е1 является просто
выражением, Е2 и Е3 – являются выражениями в нормальной форме объединения
пересечений.
Если выражение состоит из объединения фундаментальных произведений, то
такое выражение называют полной нормальной формой объединения пересечений
или многочленом в канонической форме. Многочлен Е3, кроме того, что он имеет
нормальную форму объединения пересечений, является еще и многочленом, име-
ющим полную нормальную форму объединения пересечений.
Аналогично, если при n переменных объединение состоит из n литералов,
то его называют фундаментальным объединением и, если заменить операции
объединения на операции пересечения, а операции пересечения на операции
объединения, то можно получить нормальную форму пересечения объединений и
полную нормальную форму пересечения объединений. Выражение Е4 имеет нор-
мальную форму пересечения объединений, а Е5 – полную нормальную форму
пересечения объединений.
Любое выражение может быть преобразовано к эквивалентному выражению,
имеющему нормальную форму. Одно из отличий нормальной формы в том, что
в таком выражении операция дополнения применяется только к переменным.
Чтобы избавиться от дополнений, применяемых к выражениям, надо применять
закон Де Моргана.
Алгоритм 1.1 для преобразования выражения к нормальной форме объединения
пересечений.
Пусть имеется исходное выражение алгебры множеств Е.
Шаг 1. Используя законы Де Моргана и инволюции, приведем каждую скобку,
к которой применяется операция дополнения, к виду, в котором операция допол-
нения применяется только к переменным.
Шаг 2. Используя закон дистрибутивности объединения относительно пере-
сечения, раскроем скобки, содержащие объединения литералов, относительно
операций пересечения.
Шаг 3. Используя законы ассоциативности, дополнения и идемпотентности,
преобразуем каждое пересечение литералов либо в ∅, либо в произведение.
Шаг 4. Используя законы поглощения и тождества, упростим выражение Е, и
если оно состоит из объединения пересечений, то нормальная форма получена,
если же нет, то переходим к шагу 2.
1.13. Полные нормальные формы 31
Пример 1.7
Применим данный алгоритм для преобразования к нормальной форме следу-
ющего выражения
Е = ((А ∩ ВС) ∪ (В ∩ СС)С) ∩ (((В ∩ С) ∪ (АС ∩ С))С ∪ (А ∩ В)).
Шаг 1. Используя законы Де Моргана и инволюции, получим
Е = ((А ∩ ВС) ∪ ВС ∪ С) ∩ ((ВС ∪ СС) ∩ (А ∪ СС) ∪ (А ∩ В)).
Шаг 2. Используя закон дистрибутивности, раскроем скобки в правой части
выражения
Е = ((А ∩ ВС) ∪ ВС ∪ С) ∩ ((А ∩ ВС) ∪ (ВС ∩ СС) ∪ (А ∩ СС) ∪ (СС ∩ СС) ∪ (А ∩ В)).
Шаг 3. Преобразуем пересечение литералов в произведение
Е = ((А ∩ ВС) ∪ ВС ∪ С) ∩ ((А ∩ ВС) ∪ (ВС ∩ СС) ∪ (А ∩ СС) ∪ СС ∪ (А ∩ В)).
Шаг 4. Поскольку ВС включается в А ∩ ВС, то А ∩ ВС поглощается, также СС
включается в ВС ∩ СС и А ∩ СС, поэтому оба эти пересечения поглощаются и вы-
ражение Е принимает следующий вид
Е = (ВС ∪ С) ∩ ((А ∩ ВС) ∪ СС ∪ (А ∩ В)).
Здесь снова надо раскрывать скобки, поэтому переходим к Шагу 2.
Шаг 2. Раскроем скобки и получим
Е = (А ∩ ВС ∩ ВС) ∪ (ВС ∩ СС) ∪ (А ∩ В ∩ ВС) ∪ (А ∩ ВС ∩ С) ∪
∪ (С ∩ СС) ∪ (А ∩ В ∩ С).
Шаг 3. Преобразуем пересечение литералов в произведение
Е = (А ∩ ВС) ∪ (ВС ∩ СС) ∪ ∅ ∪ (А ∩ ВС ∩ С) ∪ ∅ ∪ (А ∩ В ∩ С).
Шаг 4. Пересечение А ∩ ВС включается в А ∩ ВС ∩ С, поэтому последнее по-
глощается и нормальная форма для Е имеет вид
Е = (А ∩ ВС) ∪ (ВС ∩ СС) ∪ (А ∩ В ∩ С).
1.13. Полные нормальные формы
Следует отметить, что терминология этого раздела не стандартизирована, так, по
аналогии с булевой алгеброй полные нормальные формы иногда называют со-
вершенными нормальными формами. Рассмотрим выражение Е = Е(x1, x2, …xn),
состоящее из объединения произведений, т.е. представленное в нормальной форме.
Если каждое произведение состоит точно из n литералов, то такое выражение на-
зывается полной нормальной формой объединения пересечений.
32 Глава 1. Теория множеств
Теорема 1.2. Любое выражение алгебры множеств может быть преобразовано
к эквивалентному ему выражению в полной нормальной форме, и такое представ-
ление является единственным.
В предыдущем разделе было показано, как преобразовать любое выражение
алгебры множеств к эквивалентному выражению в нормальной форме. Далее рас-
смотрим алгоритм, позволяющий трансформировать это выражение в эквивалент-
ное ему выражение в полной нормальной форме. Идея этого алгоритма состоит в
том, что если какое-то произведение Р в выражении Е не содержит i-й переменной,
то ее можно вести в Е, образуя произведение Р ∩ (xi ∪ xi
c) при i ≤ n.
Алгоритм 1.2 для преобразования выражения к полной нормальной форме объ-
единения пересечений.
Шаг 1. Пусть имеется выражение Е = Е(x1, x2, … xn), представленное в нормаль-
ной форме. Найдем произведение Р в выражении Е, которое не содержит i-й пере-
менной, и образуем произведение Р ∩ (xi ∪ xi
c). Это не нарушает эквивалентности
выражения, поскольку (xi ∪ xi
c) = U, а Р ∩ U = Р. Удалим повторяющиеся произ-
ведения (это возможно, поскольку Р ∪ Р = Р).
Шаг 2. Повторяем Шаг 1 до тех пор, пока каждое произведение в Е не станет
фундаментальным произведением, т.е. каждое произведение не будет включать
в себя все n переменных.
Пример 1.8
Применим данный алгоритм для выражения Е в нормальной форме, получен-
ного в Примере 1.7, чтобы преобразовать его к полной нормальной форме.
Е = (А ∩ ВС) ∪ (ВС ∩ СС) ∪ (А ∩ В ∩ С).
Шаг 1. Находим произведение А ∩ ВС, которое не содержит переменной С, и
образуем произведение (А ∩ ВС) ∩ (С ∪ СС), получим
Е = (А ∩ ВС) ∩ (С ∪ СС) ∪ (ВС ∩ СС) ∪ (А ∩ В ∩ С) =
= (А ∩ ВС ∩ С) ∪ (А ∩ ВС ∩ СС) ∪ (ВС ∩ СС) ∪ (А ∩ В ∩ С).
Шаг 2. Поскольку в Е имеется произведение ВС ∩ СС, которое не содер-
жит переменной А, то снова переходим к Шагу 1 и образуем произведение
(ВС ∩ СС) ∩ (А ∪ АС),
Е = (А ∩ ВС ∩ С) ∪ (А ∩ ВС ∩ СС) ∪ (ВС ∩ СС) ∩ (А ∪ АС) ∪ (А ∩ В ∩ С).
После раскрытия скобок в Е образуется два одинаковых фундаментальных про-
изведения А ∩ ВС ∩ СС. Одно из них необходимо удалить. Теперь Е представлено
в полной нормальной форме:
Е = (А ∩ ВС ∩ С) ∪ (А ∩ ВС ∩ СС) ∪ (АС ∩ ВС ∩ СС) ∪ (А ∩ В ∩ С).
Таким образом, если имеется выражение, представленное в нормальной форме,
то данный алгоритм позволяет алгебраическими преобразованиями привести его
к полной нормальной форме. Однако этот способ не единственный. Для этой же
цели можно также использовать и диаграммы Венна.
1.13. Полные нормальные формы 33
Рассмотрим пример. Пусть имеется разбиение множества U, показанное на
рис. 1.10. Выделим множество, которое задается формулой (нормальной формой
объединения пересечений) А ∪ (ВС ∩ С). Она задает объединение двух множеств:
А = {4, 5, 6, 7} и множества, представляющего собой пересечение множеств ВС и
С, т.е. множества ВС ∩ С = {1, 5}. Поэтому множество А ∪ (ВС ∩ С) = {1, 4, 5, 6, 7}.
На рис. 1.12 это множество заштриховано. Из диаграммы видно, что множество
А ∪ (ВС ∩ С) задается объединением пяти фундаментальных произведений:
множеству {4} соответствует фундаментальное произведение А ∩ ВС ∩ СС, множе-
ству {6} – А ∩ В ∩ СС, множеству {7} – А ∩ В ∩ С, множеству {5} – А ∩ ВC ∩ С, и
множеству {1} – АC ∩ ВС ∩ С. Объединение этих фундаментальных произведений
и дает полную нормальную форму
(А ∩ ВС ∩ СС) ∪ (А ∩ В ∩ СС) ∪ (А ∩ В ∩ С) ∪ (А ∩ ВС ∩ С) ∪ (АС ∩ ВС ∩ С).
U
A 6
4
5
7
2 B
3
C
1
Рис. 1.12
Заметим, что для любого множества существует не только единственная полная
нормальная форма объединения пересечений, но и единственная полная нормальная
форма пресечения объединений. Эту форму также можно найти двумя способами.
Так, для множества из предыдущего примера А ∪ (ВС ∩ С) раскроем скобки и полу-
чим выражение в нормальной форме пересечения объединений (А ∪ ВС) ∩ (А ∪ С).
В первой скобке нет переменной С, а во второй – переменной В. Поскольку выра-
жение (С ∩ СС) = ∅, то следующее выражение эквивалентно исходному
((А ∪ ВС) ∪ (С ∩ СС)) ∩ ((А ∪ С) ∪ (В ∩ ВС)) =
= (А ∪ ВС ∪ С) ∩ (А ∪ ВС ∪ СС) ∩ (А ∪ В ∪ С) ∩ (А ∪ ВС ∪ С)
= (А ∪ ВС ∪ С) ∩ (А ∪ ВС ∪ СС) ∩ (А ∪ В ∪ С) .
34 Глава 1. Теория множеств
Последнее выражение и будет полной нормальной формой пересечения объ-
единений для исходной формулы.
Найти данное выражение можно также и при помощи диаграммы Венна.
Поскольку в исходное множество {1, 4, 5, 6, 7} не вошли элементы {0, 2, 3}, то не-
обходимо образовать пересечение таких объединений, которые не содержат эти
три множества. Объединение А ∪ В ∪ С не содержит элемента {0}, объединение
А ∪ ВС ∪ С не содержит элемента {2}, и объединение А ∪ ВС ∪ СС не содержит
элемента {3}. Отсюда, образовав из них пересечение, можно получить полную
нормальную форму пересечения объединений
(А ∪ В ∪ С) ∩ (А ∪ ВС ∪ С) ∩ (А ∪ ВС ∪ СС).
Более подробно эти формы будут рассмотрены в упражнениях.
1.14. Определение минимальных форм
Множество можно задавать различными формулами. Хотя эти формулы выглядят
по-разному, но все они эквивалентны в том смысле, что они определяют одни и те
же элементы данного множества. Например, пусть имеется два выражения в нор-
мальной форме
Е1 = (В ∩ С) ∪ (АС ∩ СС),
Е2 = (В ∩ С) ∪ (АС ∩ В) ∪ (АС ∩ ВС ∩ СС).
Эти формулы эквивалентны, что нетрудно проверить, если преобразовать каж-
дую из них к полной нормальной форме, которая и для Е1, и для Е2 одна и та же:
(А ∩ В ∩ С) ∪ (АС ∩ В ∩ С) ∪ (АС ∩ В ∩ СС) ∪ (АС ∩ ВС ∩ СС).
Для того чтобы определить, какая из эквивалентных формул «проще», введем
следующие обозначения. Пусть Е – выражение в нормальной форме, и пусть
L(E) – количество литералов в этом выражении (считаются все вхождения), и
F(E) – количество произведений, из которых образовано Е. Так, для Е1 значение
L(E1) = 2 + 2 = 4 и F(E1) = 2, а L(Е2) = 2 + 2 + 3 = 7 и F(E2) = 3.
Пусть Е1 и Е2 эквивалентные выражения в нормальной форме. Тогда Е1 проще
Е2, если
L(E1) < L(Е2) и F(E1) ≤ L(Е2) или
L(E1) ≤ L(Е2) и F(E1) < L(Е2).
Выражение Е, представленное в нормальной форме, называется минимальным,
если не существует никакого другого эквивалентного ему выражения, которое про-
ще, чем Е. Следует заметить, что может существовать более одного эквивалентного
минимального выражения.
Произведение Р называется простым импликантом, для выражения Е, если
Р ∪ Е = Е
1.14. Определение минимальных форм 35
и нет никакого другого произведения, содержащегося в Р, которое обладает этим
свойством. Например, пусть
Е = (А ∩ С) ∪ (ВС ∩ С) ∪ (АС ∩ В ∩ С).
Можно показать, что выражение
(АС ∩ В) ∪ Е = Е, но АС ∪ Е ≠ Е и В ∪ Е ≠ Е.
Поэтому АС ∩ В является простым импликантом Е.
Теорема 1.3. Любое выражение Е, представленное в минимальной форме, яв-
ляется объединением простых импликантов Е.
Методы определения минимальных форм обычно базируются на алгоритмах,
которые позволяют находить простых импликантов и выбирать из них те, которые
и дают выражения в минимальной форме. Для определения простых импликантов
имеется метод соседства (его также называют методом консенсуса), который со-
стоит в следующем. Пусть Pi и Pj два произведения такие, что одно из них содержит
литерал Х, а другое ХС (т.е. какая-то переменная в одно произведение входит без
дополнения, а в другое – с дополнением, и других переменных с этим свойством в
данных произведениях нет). Тогда соседством Pi и Pj будет называться произведение
(без повторений), составленное из литералов Pi и Pj, из которых удалены Х и ХС, а
сами Pi и Pj называются соседними. Соседство не определено, если Pi = X и Pj = XC.
Из определения соседства следует следующее утверждение:
Если S является соседством Pi и Pj, то тогда
Pi ∪ Pj ∪ S = Pi ∪ Pj.
Пример 1.9. Найти соседство S для P1 и Р2.
1. P1 = (А ∩ В) и Р2 = (ВС ∩ СС), удалим В и ВС и образуем пересечение P1 и Р2
получим S = А ∩ СС.
2. P1 = АС ∩ ВС ∩ С и Р2 = ВС ∩ СС, удалим С и СС, получим без повторений
S = АС ∩ ВС.
3. P1 = В и Р2 = ВС ∩ СС, удаление В и ВС дает S = СС.
4. P1 = АС ∩ ВС ∩ С и Р2 = В ∩ С ∩ D, удаление ВС и В дает S = АС ∩ С ∩ D.
5. P1 = АС ∩ ВС ∩ С и Р2 = В ∩ СС, здесь две переменные В и С имеют дополне-
ния и поэтому P1 и Р2 не имеют соседства.
6. P1 = АС ∩ ВС ∩ С и Р2 = ВС ∩ С здесь нет переменой без дополнения и с до-
полнением и поэтому P1 и Р2 также не имеют соседства.
Метод соседства позволяет находить все простые импликанты для любой фор-
мулы в нормальной форме.
Алгоритм 1.3 для нахождения простых импликантов (метод соседства).
Пусть имеется исходное выражение алгебры множеств Е, представленное
в нормальной форме.
Шаг 1. Используя закон поглощения, удалим произведение Pi, которое включает
в себя произведение Pj.
Шаг 2. Если имеются два соседних произведения Pi и Pj, то добавим к Е сосед-
ство S, которое они определяют.
Шаг 3. Повторяем Шаг 1 и Шаг 2, пока они могут быть применены.
36 Глава 1. Теория множеств
Теорема 1.4. Когда метод соседства прекращает работу, тогда выражение Е пред-
ставляет собой объединение простых импликантов.
Пример 1.10
Найти все простые импликанты для выражения Е
Е = (А ∩ ВС ∩ СС) ∪ (АС ∩ ВС ∩ СС) ∪ (AC ∩ С) ∪ (АС ∩ ВС ∩ С) ∪ (А ∩ В ∩ С)
(удалено АС ∩ ВС ∩ С поглощаемое AC ∩ С)
= (А ∩ ВС ∩ СС) ∪ (АС ∩ ВС ∩ СС) ∪ (AC ∩ С) ∪ (А ∩ В ∩ С)
(для соседних произведений (А ∩ ВС ∩ СС) и (АС ∩ ВС ∩ СС) добавлено (ВС ∩ СС))
= (ВС ∩ СС) ∪ (А ∩ ВС ∩ СС) ∪ (АС ∩ ВС ∩ СС) ∪ (AC ∩ С) ∪ (А ∩ В ∩ С)
(удалены (А ∩ ВС ∩ СС) и (АС ∩ ВС ∩ СС) поглощаемые (ВС ∩ СС))
= (ВС ∩ СС) ∪ (AC ∩ С) ∪ (А ∩ В ∩ С)
(для соседних произведений (ВС ∩ СС) и (AC ∩ С) добавлено (AC ∩ ВС))
= (AC ∩ ВС) ∪ (ВС ∩ СС) ∪ (AC ∩ С)
(для соседних произведений (AC ∩ С) и (А ∩ В ∩ С) добавлено (В ∩ С))
= (AC ∩ ВС) ∪ (ВС ∩ СС) ∪ (AC ∩ С) ∪ (А ∩ В ∩ С) ∪ (В ∩ С)
(удалено (А ∩ В ∩ С) поглощаемое (В ∩ С))
= (AC ∩ ВС) ∪ (ВС ∩ СС) ∪ (AC ∩ С) ∪ (В ∩ С).
Поскольку ни одного нового импликанта образовать нельзя, алгоритм прекращает
свою работу и Е представлено в виде объединения четырех простых импликантов
= (AC ∩ ВС), (ВС ∩ СС), (AC ∩ С) и (В ∩ С).
Хотя метод соседства и дает все простые импликанты, он не отвечает на вопрос –
как для данного выражения выглядит эквивалентная ему минимальная форма, и
тем более, сколько для него имеется эквивалентных минимальных форм. Чтобы
найти минимальную форму, применим следующий алгоритм
Алгоритм 1.4 для нахождения минимальной формы в выражении, представля-
ющем собой объединение простых импликантов.
Пусть имеется исходное выражение алгебры множеств Е, представленное в нор-
мальной форме в виде объединения всех простых импликантов Е.
Шаг 1. Представим каждый простой импликант в виде объединения фундамен-
тальных произведений (используя алгоритм преобразования выражения к полной
нормальной форме объединения пересечений).
Шаг 2. Последовательно удалим из Е каждый такой имликант, все фундамен-
тальные произведения которого имеются среди фундаментальных произведений
остающегося выражения.
Пример 1.11. Применим этот алгоритм для выражения, полученного в При-
мере 1.10.
Е = (AC ∩ ВС) ∪ (ВС ∩ СС) ∪ (AC ∩ С) ∪ (В ∩ С).
Выразим каждый простой импликант в виде объединения фундаментальных
произведений
1.15. Представление формул алгебры множеств графами 37
AC ∩ ВС = (АС ∩ ВС ∩ С) ∪ (АС ∩ ВС ∩ СС)
ВС ∩ СС = (АС ∩ ВС ∩ СС) ∪ (А ∩ ВС ∩ СС)
AC ∩ С = (АС ∩ В ∩ С) ∪ (АС ∩ ВС ∩ С)
В ∩ С = (А ∩ В ∩ С) ∪ (АС ∩ В ∩ С).
Удалим импликант AC ∩ ВС, поскольку его фундаментальное произведение
(АС ∩ ВС ∩ С) входит в выражение для третьего импликанта, а (АС ∩ ВС ∩ СС)
входит в выражение для второго импликанта. Из оставшихся трех импликантов
ни один этим свойством не обладает, поэтому алгоритм прекращает свою работу и
минимальная форма для Е выглядит следующим образом
Е = (ВС ∩ СС) ∪ (AC ∩ С) ∪ (В ∩ С).
Заметим также, что метод соседних произведений можно использовать и при эк-
вивалентных преобразованиях выражений, чтобы уменьшить число произведений,
входящих в упрощаемый многочлен. Это можно сделать при помощи следующих
правил, называемых правилами соседства
(А ∩ В) ∪ (АС ∩ С) ∪ (В ∩ С) = (А ∩ В) ∪ (АС ∩ С)
(А ∪ В) ∩ (АС ∪ С) ∩ (В ∪ С) = (А ∪ В) ∩ (АС ∪ С).
Доказательство этих правил, использующее граф, рассмотрено далее.
1.15. Представление формул алгебры множеств
графами
Многочлену в полной нормальной форме можно взаимно однозначно поставить
в соответствие неориентированный двудольный граф. Как следует из парагра-
фа 1.13, каждое множество имеет единственную полную нормальную форму
объединения пересечений, а также единственную полную нормальную форму
пресечения объединений. Отсюда следует, что каждому множеству можно поста-
вить в соответствие единственный граф, задаваемый полной нормальной формой
объединения пересечений, и единственный граф, задаваемый полной нормальной
формой пересечения объединений. Заметим, что существуют множества, для
которых эти графы могут быть изоморфны. Из сказанного также следует, что име-
ются задачи, связанные с множествами, которые можно решить методами теории
графов.
Сначала необходимо определить понятие смежных произведений. Оно основано
на той же идее, которая используется при введении понятия соседства в парагра-
фе 1.14. Два фундаментальных произведения Pi и Pj называются смежными, если они
состоят из тех же самых переменных и различаются точно в одном литерале. Другими
словами, имеется какая-то переменная, которая в одно из этих фундаментальных
произведений входит без дополнения, а в другое – с дополнением. В частности,
объединение двух смежных фундаментальных произведений представляет собой
произведение, в котором на один литерал меньше.