Дискретная математика : основные теоретико-множественные конструкции. Ч. I

№1751

ФЕДЕРАЛЬНОЕАГЕНТСТВОПООБРАЗОВАНИЮ

Кафедра автоматизированных систем управления

Ю.Ю. Прокопчук
А.И. Широков
Т.В. Дубравина

Дискретная математика

Основные теоретикомножественные
конструкции

Часть I

Учебное пособие
для студентов специальностей 220200 и 351400

Под редакцией В.А. Грузмана и А.Г. Дьячко

Рекомендовано редакционноиздательским
советом института

Москва  Издательство ´УЧЕБАª
2006

УДК 591.45 
 П78 

Р е ц е н з е н т  
доктор технических наук, профессор МГТУ В.А. Уткин 

Прокопчук Ю.Ю., Широков А.И., Дубравина Т.В. 
П78  
Дискретная математика: Основные теоретико-множественные конструкции. Ч. I: Учеб. пособие /Под ред. В.А. Грузмана 
и А.Г. Дьячко. – М.: МИСиС, 2006. – 119 с. 

Теория множеств (ТМ) – это учение о наиболее общих свойствах состоящих из объектов п р о и з в о л ь н о й  природы совокупностей и 
отношениях между ними. Опыт современной математики и анализ ее основ 
подтвердили тезис о том, что совокупность, или множество, служит той 
единственной категорией [26, с. 4], на основе которой может быть построено 
логически безупречно все «здание» математической науки. Изложенные в 
пособии сведения касаются описаний и характеристик основных понятий 
ТМ: множеств и кортежей, а также относящегося к ним математического 
аппарата. 
Содержание пособия соответствует программе курса «Дискретная математика». Предназначено для студентов специальностей 220200 и 351400, 
изучающих учебные дисциплины «Математическая логика и теория алгоритмов» и «Дискретная математика». 

© Московский государственный институт 
стали и сплавов (Технологический  
университет) (МИСиС), 2006 

ОГЛАВЛЕНИЕ 

От авторов ............................................................................................................. 5 
Введение ................................................................................................................ 6 
Примечание ........................................................................................................... 7 
Глава I. Элементы теории множеств .................................................................. 8 
§ 1. Исходные понятия..................................................................................... 8 
1. Собирательные понятия и их роль в процессе познания ............... 8 
2. Признаки понятия «совокупность» .................................................. 9 
3. О совокупностях, изучаемых в математике..................................... 9 
4. Описательное определение понятия «мощность множества» и 
порождаемые им свойства. Конечные и бесконечные множества.. 12 
5. Обозначения множеств и их элементов......................................... 13 
6. Определения и обозначения некоторых числовых множеств ..... 13 
Упражнения........................................................................................... 15 
Примечания........................................................................................... 17 
§ 2. Основные теоретико-множественные отношения ............................... 19 
1. Принадлежность............................................................................... 19 
2. Равенство........................................................................................... 21 
3. Задание множеств перечислением и описанием. Пустое 
множество ............................................................................................. 23 
4. Нестрогое и строгое включения...................................................... 25 
5. Комножества..................................................................................... 29 
Упражнения........................................................................................... 29 
Примечания........................................................................................... 39 
Приложение 1. Теоретико-множественная интерпретация понятия 
«свойство»............................................................................................. 42 
Упражнения........................................................................................... 43 
Примечания........................................................................................... 43 
§ 3. Основные теоретико-множественные операции.................................. 44 
1. О понятии «операция» ..................................................................... 44 
2. Булеан множества............................................................................. 44 
3. Объединение ..................................................................................... 44 
4. Пересечение ...................................................................................... 45 
5. Вычитание. Дополнение.................................................................. 47 
6. Симметрическое вычитание............................................................ 49 
7. О понятии «универсальное множество»........................................ 50 
Упражнения........................................................................................... 51 
Примечания........................................................................................... 54 
§ 4. Некоторые результаты теории множеств.............................................. 55 
1. Теорема о «пяти возможностях» (неальтернативный вариант) .. 55 
2. Теорема «о пяти возможностях»  (альтернативный вариант) ..... 56 
Упражнения........................................................................................ 59 
Примечание........................................................................................ 60 

Приложение 2. Об аксиоматическом подходе к построению теории 
множеств ................................................................................................61 
1. Определение множества Г. Кантором. Обсуждение  
определения ...........................................................................................61 
2. Принцип экстенсиональности (равнообъемности)........................61 
3. Способы задания множеств .............................................................62 
4. Парадокс Б. Рассела. Подходы к устранению парадоксов из 
теории множеств ...................................................................................63 
5. Смысл и значение аксиоматической теории множеств ................64 
6. Аксиоматическое построение теории множеств  
(фрагментарно)......................................................................................65 
7. Замечания о способах задания множества .....................................66 
Упражнения ...........................................................................................68 
Примечания............................................................................................68 
Глава II. Кортежи.................................................................................................69 
§ 1. Исходные понятия....................................................................................69 
1. Признаки понятия «кортеж» и его определение............................69 
2. Параметры кортежа, его изображение в логико-математическом 
языке и графовая интерпретация.........................................................71 
3. Пустой кортеж. Классификации кортежей по длине и природе 
компонент. Диагональные кортежи ....................................................74 
4. Равенство кортежей ..........................................................................76 
Упражнения ...........................................................................................77 
Примечания............................................................................................82 
§ 2. Операции над кортежами ........................................................................83 
1. Проектирование.................................................................................84 
2. Инвертирование. Симметричные кортежи.....................................85 
3. Присоединение. Критерии симметричности кортежа и 
коммутативности операции присоединения ......................................88 
4. Компонирование. Критерий коммутативности операции 
компонирования ....................................................................................90 
5. Компонирование одноэлементных множеств, состоящих из 
кортежей.................................................................................................94 
Упражнения ...........................................................................................94 
Примечания..........................................................................................107 
§ 3. Действия над парами и диаграммы результатов операций над ними....108 
1. Операции над парами .....................................................................108 
2. Изображение результатов действий над парами диаграммами .109 
Упражнения .........................................................................................111 
Примечание..........................................................................................111 
Приложение 3. Указатель знаков и обозначений.......................................112 
Приложение 4. Указатель терминов............................................................113 
Библиографический список..............................................................................116 

Памяти 
Эммануила Марковича 
Бравермана 

От авторов 

Данное пособие авторы посвящают памяти Эммануила Марковича Бравермана, профессора Московского государственного 
института стали и сплавов (МИСиС), скончавшегося после тяжелой 
и продолжительной болезни в апреле 1976 г. 
Э.М. Браверман работал на кафедре инженерной кибернетики 
МИСиС, руководимой академиком С.В. Емельяновым, в должности 
профессора в период с 1966 по 1976 г. Его учебные курсы были направлены главным образом на изложение методов решения 
дискретных и непрерывных экстремальных задач и отличались оригинальностью и глубиной, а также математической строгостью и 
педагогическим мастерством. Кроме того, в его курсах впервые в 
МИСиС освещались вопросы теории систем и системного анализа. 
Позже основы этой теории были включены в учебные планы всех 
специальностей, и в студенческих группах стали регулярно проводиться лекционные и практические занятия, отражающие те или 
иные ее аспекты. В период своей работы в МИСиС Э.М. Браверман 
руководил общеинститутским научно-методическим семинаром 
«Основы теории больших систем». Э.М. Браверман создал лично и в 
соавторстве несколько общесоюзных учебников и учебных пособий, 
которые вышли в издательстве «Наука». 
Авторы данного пособия работали с Э.М. Браверманом более 
десяти лет на учебной и научной ниве в качестве студентов или сотрудников. У них до настоящего времени сохранились самые теплые 
воспоминания о нем как об эрудированном специалисте, прекрасном 
педагоге и, что особенно важно, в высшей степени доброжелательном старшем товарище. 

ВВЕДЕНИЕ 

1. Теория множеств (ТМ) – это учение о наиболее общих 
свойствах и отношениях между совокупностями объектов различной 
природы. Она была создана усилиями логиков и математиков 
XIX века, которые стремились построить логический базис для математического анализа. Первые труды в этой сфере (Б. Больцано, 
Р. Дедекинд, Г. Фреге) в основном были посвящены изучению числовых множеств и множеств числовых функций. Решительный шаг 
в создании ТМ сделал Г. Кантор (1845 – 1918), заслуги которого заключаются в том, что он, во-первых, начал рассматривать множества 
элементов п р о и з в о л ь н о й  п р и р о д ы ,  и, во-вторых, получил 
фундаментальные результаты, связанные с понятием мощность 
множества (гл. I, § 1, п. 4). 
После начального периода недоверия к ТМ, вызванного появлением антиномий [1, т. 1, с. 292 – 296, ст. «Антиномия»; 10, с. 48 
ст. «Антиномия»], которое было преодолено главным образом при 
помощи так называемого аксиоматического метода (см. прил. 2 к 
гл. I), началось ее триумфальное шествие по всем областям математики и других наук, которое продолжается и сейчас.  
2. Рассмотрим вкратце теоретико-познавательные аспекты 
понятия множество. 
Во-первых, его становление отражает синтетическую функцию мышления, направленную на построение новых объектов из 
исходных. Процедура такого построения связана с движением мысли 
от единичного к общему посредством абстрагирования от частностей. 
Например, 
изучение 
таких 
отдельных 
математических 
предметов как числа, приводит нас к рассмотрению сначала отдельных числовых множеств, а затем – множеств абстрактных объектов 
[2, с. 4, ст. «Абстрактные объекты»]1). 
Во-вторых, понятие множество служит хорошим подспорьем для решения одной из важнейших общенаучных задач: 
с в е д è н и я  (р е д у к ц и и ) сложного к простому. Например, такие 
столь внешне непохожие друг на друга вещи, как геометрические 
линии, фигуры и тела удобно рассматривать как совокупности, состоящие из объектов одного и того же вида – точек. Здесь идея 

множества используется для унификации описания и анализа уже 
имеющихся в наличии различных довольно сложных математических предметов. 
И наконец, в-третьих, общенаучная практика свидетельствует 
о необычайной широте и плодотворности понятия множество. В 
частности, опыт современной математики и анализ ее основ подтвердили тезис о том, что такой вид совокупностей, как множества 
служит тем е д и н с т в е н н ы м  исходным «материалом», на основе 
которого может быть «построено» все «здание» математической науки [5, с. 12 – 13]. Отсюда вытекает универсальность языка ТМ, 
являющегося фрагментом логико-математического языка (ЛМЯ) 
[27, 28], служащего для описания современной математики. 
3. Из сказанного выше следует, что для изложения математики 
достаточно 
лишь 
одного-единственного 
языка 
– 
языка, 
описывающего ТМ. Если прежде считали, что каждый раздел математики зависит от с п е ц и ф и ч е с к о й  интуиции исследователя, 
дающей ему первичные понятия и утверждения, и поэтому для каждого 
из 
них 
необходим 
с в о й  
с а м о с т о я т е л ь н ы й  
формализованный язык [26, с. 14], то сегодня мы знаем, что, логически говоря, возможно «вывести» практически всю современную 
математику из единственного источника – ТМ. Таким образом, нам 
будет достаточно, выбрав подходящий формализованный язык, пояснить, как «передать» на нем теорию множеств, а затем, по мере 
того как мы будем обращаться к различным разделам математики, 
показать, как они включаются в ТМ [5, с. 23]. В нашей серии учебной 
литературы по дискретной математике, в которую включаются, в частности, работы [21 – 28], начало этому положено в данном пособии. 
4. Авторы благодарят И.В. Одина за подготовку графических 
материалов. 

Примечание 

1)*Наглядный пример построения множества вещественных 
чисел на основе единственного понятия пустое множество приведен в [4, с. 6].* 

ГЛАВА I. ЭЛЕМЕНТЫ ТЕОРИИ 
МНОЖЕСТВ 

§ 1. Исходные понятия 

1. Собирательные понятия и их роль в процессе 
познания 

Напомним, что в логике собирательным называют такое понятие, в содержании которого необходимо присутствуют признаки, 
отражающие интуитивно ясную идею о б ъ е д и н и т е л ь н о с т и, или 
к о л л е к т и в и з и р у е м о с т и  (от лат. сollectivus – собирательный), 
в том или ином смысле, и тем самым позволяющие рассматривать 
его объем как единое целое [10, с. 554, ст. «Собирательное понятие»]. Так, понятия церковь, государство, полк, оркестр, команда 
(экипаж), стая и т.д. являются собирательными1). 
То, что разумно сказать о собирательном понятии, может 
оказаться истинным, ложным, либо неосмысленным для каких-то 
предметов из его объема2). Так, используя в рассуждении собирательное понятие корабельная роща, мы имеем в виду, что лишь 
какие-то ее деревья подходят для строительства кораблей, а вовсе не 
то, что для этой цели годится каждое из них. *Другой пример. Совокупность {N, 1, {1, 2}} – конечная. Однако среди трех ее членов 
конечной является только совокупность {1, 2}. Совокупность N – 
бесконечная. Число же один вообще не является совокупностью в 
нашем понимании [24, с. 5 – 6]. Поэтому утверждение о его конечности не истинно либо ложно, а абсурдно*. 
Среди различных видов понятий собирательные занимают особое место в научном и учебном процессе, поскольку именно они часто 
выступают в качестве и с х о д н ы х  о б ъ е к т о в  той или иной теории, 
на основе которых строятся п р о и з в о д н ы е  о б ъ е к т ы  и вокруг 
которых развивается дальнейшее учение. *Например, собирательные 
понятия множество (п. 3) и кортеж (см. далее гл. II, § 1, п. 1) являются 
б а з и с н ы м и  в  современной математике.* 

2. Признаки понятия «совокупность» 

Собирательное понятие совокупность (предметов), являясь одним из начальных в современной науке, представляет собой 
общенаучную категорию [26, c. 8]. Поэтому мы в состоянии только както пояснить его при помощи других категорий или проиллюстрировать. 
Так, мы можем говорить о совокупности студентов, находящихся в этой 
аудитории в настоящее время; о совокупности корней какого-то уравнения; о совокупности фруктов в данной корзине; о совокупности 
снежинок, упавших на площадку, и т.д. Умственный акт возникновения 
этого понятия мы способны представить себе, например, следующим 
образом. Располагая отдельными предметами, или элементами, мы 
мысленно собираем, объединяем их в одно целое, то есть образуем н о в ы й  предмет, который и отражаем в понятии совокупность (этих 
предметов, или элементов)3). Такое его описание, данное скорее в психологических, чем логических терминах, довольно расплывчато и 
поэтому неосторожное обращение с ним иногда приводит к парадоксам 
[10, с. 431, ст. «Парадокс»]. Чтобы по возможности избежать их, попытаемся сформулировать и раскрыть некоторые признаки, которые мы 
хотели бы «вложить» в содержание этого понятия [26, c. 7]. 
СВ1 На природу элементов совокупности, их свойства и отношения между ними, в частности, их взаиморасположение 
априóри4) не накладывается никаких ограничений. 
СВ2 Совокупность, построенная из исходных элементов, – это 
н о в ы й  о б ъ е к т , отличный от каждого из них5). 
Из сказанного следует, что в качестве первоначального, «рабочего» определения совокупности может быть принято такое: 
Совокупность – это объект, фактически имеющий или потенциально способный иметь элементы, из которых он состоит.  

3. О совокупностях, изучаемых в математике 

Если проанализировать процесс эволюции понятия совокупность, то можно выделить два его основных направления [5, с. 325 – 328]. 
Во-первых, ф и л о с о ф с к о - л о г и ч е с к о е  направление, в 
процессе развития которого были выявлены и сформулированы такие связи между объектами, как принадлежность элемента 
совокупности (см. § 2, п. 1), равенства и включения совокупностей 
(см. § 2, пп. 2 и 3, соответственно), и другие. Эти интуитивно понятные отношения широко применяются во всех научных дисциплинах. 
Можно предположить, что ученые любой специальности более или 
менее сознательно пользовались ими всегда6). 

И, во-вторых, направление, посвященное исследованию к о л и ч е с т в е н н ы х  характеристик совокупностей, то есть тех их 
сторон, которые и служат одним из предметов исследования математической науки [26, с. 11 – 12]. Сюда относится, в частности, и вопрос о 
числе элементов совокупности, или ее мощности7). Отсутствие в течение долгого времени полной ясности по этому вопросу, то есть по 
«количественной стороне» понятия совокупность, послужило причиной 
появления разного рода неопределенностей и недоразумений на пути 
развития этого направления. Проиллюстрируем сказанное. 
Очевидно, что подсчет числа элементов одних совокупностей, например, пальцев конечности или глаз человека, может быть 
осуществлен довольно легко, других, в частности, статей Большой 
Советской Энциклопедии (БСЭ), хотя и вызывает технические трудности, но все же может быть реализован. А, например, подсчет числа 
элементов совокупности, состоящей только из в с е х  натуральных 
чисел, вызывает затруднения у читателя, который прочитал пособие 
только до этого места, а с соответствующей литературой не знаком. 
Кроме того, по тем или иным причинам процедура пересчета элементов совокупности отнюдь не всегда оказывается выполнимой, а если 
и выполнима, то ведет к точному в определенном смысле результату. 
Приведем несколько примеров, иллюстрирующих это утверждение. 
Пример 1. Рассмотрим совокупность А, представляющую 
собой собрание отдельных капель жидкости, помещенных в сосуд. 
Когда А построена, ее элементы оказываются попарно неотделимыми друг от друга, и поэтому они не могут быть пересчитаны. Таким 
образом, причина отсутствия точной количественной оценки совокупности А состоит в том, что предметы, из которых она построена, 
став элементами А, оказываются н е р а з л и ч и м ы м и .  
Пример 2. Здесь речь пойдет о совокупности В всех предметов зеленого цвета, находящихся в моей комнате. Сегодня к В 
принадлежит и стоящий на столе свежий цветок. Но, завянув и пожелтев, он не будет входить в нее уже через неделю. Однако В может 
пополниться, например, двумя книгами в зеленых переплетах, взятыми мною в библиотеке. «Граница» В является «открытой» для 
миграции элементов, и поэтому число ее элементов то уменьшается, 
то увеличивается, что позволяет говорить нам только о числе ее элементов в данный конкретный момент времени. Мощность В – это не 
натуральная константа, а натуральная переменная8). Таким образом, 
причина отсутствия мощности у совокупности В только одна: изменяющееся во времени количество ее элементов. 

Пример 3. Рассмотрим совокупность С идей о чем-либо, например, о математике. С нею происходят изменения двух указанных 
выше видов: соединение и отделение одних идей от других, а также 
изменяющийся состав.  
Приведенные примеры свидетельствуют о том, что вовсе не 
любая совокупность может быть охарактеризована количественно 
совершенно точно. Не анализируя здесь причины сказанного, а ограничившись только приведенными выше примерами, подчеркнем, что 
в математике, в известном смысле самой точной из наук, такие совокупности н е  р а с с м а т р и в а ю т с я  и  н е  и с с л е д у ю т с я . 
Чтобы уточнить класс совокупностей, изучаемых в математике, к признакам СВ1 – СВ2, принадлежащим любой из них, 
следует добавить еще какие-то, присущие только так называемым 
м а т е м а т и ч е с к и м  с о в о к у п н о с т я м , то есть таким, относительно каждой из которых вопрос о ее мощности осмыслен и 
корректен. Рассмотренные выше примеры наводят на мысль, что эти 
признаки должны быть по меньшей мере следующими. 
М1 Элементы совокупности представляют собой попарно 
различимые объекты.  
М2 Элементы и состав совокупностей не меняются с течением времени. 
Совокупности, отвечающие признакам СВ1 – СВ2 и М1 – М2, 
будем называть математическими совокупностями, или множествами9). Очевидно, что к ним относятся совокупности всех пальцев 
руки человека; статей БСЭ; числовые совокупности, например, N, R 
и т.д. и их части; а также совокупности, состоящие из точек прямой, 
плоскости, пространства и т.п. И не относятся совокупности, составленные из капель жидкости, собранных в сосуд; зеленых предметов в 
моей комнате; идей о математике; фруктов в корзине; снежинок, 
упавших на площадку (см. п. 2) и т.п. 
Резюмируя изложенное относительно второго направления 
эволюции понятия «совокупность», мы можем сказать сегодня, что 
к о л и ч е с т в е н н о  м о г у т  о ц е н и в а т ь с я  н е  п р о и з в о л ь н ы е  
с о в о к у п н о с т и ,  
а  
и х  
о т д е л ь н ы й  
в и д  
–  
м н о ж е с т в а .  Они, а также созданные на их основе объекты, являются именно теми предметами, которые изучает современная 
математика. Речь о них пойдет дальше. Отметим, что многие результаты, полученные в гл. I – VI, верны и для совокупностей. 
Кроме терминов м н о ж е с т в о  и  с о в о к у п н о с т ь  используют синонимичные им: собрание (предметов), коллекция (лат. 

collectio – собрание), ансамбль (фр. ensemble – вместе, слаженность) 
и другие10), а также словá семейство и область, которые являются 
м а т е м а т и ч е с к и м и  п о л и с е м а м и , то есть имеют в математике и другие значения11). Далее термин множество мы будем 
использовать в качестве основного. Читатель без особого труда может 
обобщить 
полученные 
о 
множествах 
результаты 
на 
соответствующие результаты о совокупностях. Изучению совокупностей, в частности, множеств, посвящен отдел математической 
науки [26, с. 11], носящий название «Теория множеств», основные 
фрагменты которого изложены в разделе «Основные теоретикомножественные конструкции» нашего курса. 

4. Описательное определение понятия «мощность 
множества» и порождаемые им свойства. Конечные и 
бесконечные множества 

В [26, c. 13] говорится, что, хотя математические объекты интересны и сами по себе, но не менее важны и свойства, которыми 
одни из них могут обладать, а другие – нет. В данном пункте мы рассмотрим более подробно свойство, присущее л ю б о м у  множеству – 
его м о щ н о с т ь  (в частности, ч и с л о  е г о  э л е м е н т о в ). 
Наличие признаков М1 и М2, постулирующих попарную различимость и неизменность во времени элементов множества, а также 
постоянство его состава позволяют охарактеризовать его количественно. И опять, для одних множеств это сделать довольно просто, для 
других – сложнее, а для третьих – хотя и можно, но пока неизвестно, 
как. Так, множество всех пальцев конечности человека состоит из пяти 
предметов, а глаз – из двух. Подсчет числа элементов множества всех 
статей БСЭ хотя и громоздок, но все же может быть осуществлен. Однако, если располагать только знаниями, изложенными в данном 
пособии до этого места, вряд ли можно точно ответить на вопрос о количественной оценке натурального ряда. В свое время, достигнув 
определенного уровня развития теории, на этот и подобные вопросы мы 
получим вполне определенные и исчерпывающие ответы. Пока же, 
предполагая и н т у и т и в н о  ясным понятие число элементов, или 
мощность множества, будем пользоваться им в тех случаях, когда 
это не вызывает каких-либо затруднений, главным образом в примерах. Мощность множества Х обозначают через |X|. Очевидно, что 
уже сейчас мы могли бы охарактеризовать некоторые множества 
к о л и ч е с т в е н н о , а именно – натуральными числами, то есть одно