Дискретная математика для социологов

Учебное пособие

Е. А. Евсеев

ДИСКРЕТНАЯ  
МАТЕМАТИКА 
ДЛЯ СОЦИОЛОГОВ

ИЗДАТЕЛЬСТВО САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

УДК 512+519.1(075.8)
ББК 22.176
Е25

Р е ц е н з е н т ы: д-р техн. наук, проф. В. М. Буре (С.-Петерб. гос. ун-т); канд. социол.
наук, доц. Е. В. Тыканова (НИУ ВШЭ — Санкт-Петербург)

Рекомендовано к публикации
Учебно-методической комиссией факультета социологии
Санкт-Петербургского государственного университета

Е25
Евсеев Е. А.
Дискретная математика для социологов: учеб. пособие. — СПб.:
Изд-во С.-Петерб. ун-та, 2020. — 304 с.
ISBN 978-5-288-06020-5

В пособии рассматриваются основные области дискретной математики, необходимые для социологов: элементы теории множеств, математической логики
и бинарных отношений, теория графов, комбинаторика. Кроме классических разделов в пособие включены основы нечетких множеств и краткое описание математических основ анализа социальных сетей. Особое внимание уделено качественным характеристикам соотношений между объектами, свойствам, связанным с конечными множествами, наглядным формам использования математических понятий, методам абстрагирования, интерпретациям используемых понятий
и результатов. После каждого параграфа предлагаются упражнения и задачи для
самостоятельной работы. В тексте приводится решение типовых задач. Некоторые задания снабжены указаниями для решения.
Пособие адресовано в первую очередь студентам гуманитарных направлений — в рамках курсов дискретной и высшей математики, математических методов и моделей в гуманитарных науках, информатике — может быть также полезно для студентов магистратуры факультета социологии и других гуманитарных
факультетов при изучении аналогичных математических курсов.

УДК 512+519.1(075.8)
ББК 22.176

ISBN 978-5-288-06020-5

c⃝
Санкт-Петербургский
государственный
университет, 2020

c⃝
Е. А. Евсеев, 2020

Оглавление

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

Список используемых символов и сокращений . . . . . . . . . . . . . . . . . .
7

Глава 1. Множества и элементы математической логики . . . . . . . .
8

1.1. Основные понятия. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . .
8
Упражнения. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . .
13
1.2. Операции над множествами. Декартово произведение
множеств. Векторы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . .
14
Упражнения. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . .
21
1.3. Нечеткие множества . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . .
23
Упражнения. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . .
38
1.4. Элементы формальной логики высказываний . . . . . . . . . . . . . . . . .
40
Упражнения. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . .
50
1.5. Логика предикатов .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . .
51
Упражнения. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . .
57
1.6. Логический вывод .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
58
Упражнения. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . .
62
1.7. Элементы нечеткого логического вывода . . . . . . . . . . . . . . . . . . . . . .
63
Упражнения. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . .
72

Глава 2. Комбинаторика. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
74

2.1. Основные комбинаторные принципы. . . . . . . . . . . . . . . . . . . . . . . . . . .
74
Упражнения. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . .
78
2.2. Перестановки, размещения и сочетания.. . . . . . . . . . . . . . . . . . . . . . .
81
Упражнения. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . .
87
2.3. Размещения и сочетания с повторениями .. . . . . . . . . . . . . . . . . . . . .
90
Упражнения. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . .
95

Глава 3. Бинарные отношения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
97

3.1. Определение бинарного отношения . . . . . . . . . . . . . . . . . . . . . . . . . . . .
97
Упражнения. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . .
104
3.2. Нечеткие бинарные отношения.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
106
Упражнения. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . .
110

3

Оглавление

3.3. Свойства бинарных отношений . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
111
Упражнения. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . .
119
3.4. Свойства нечетких бинарных отношений . . . . . . . . . . . . . . . . . . . . . .
122
Упражнения. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . .
123
3.5. Операции над отношениями.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
124
Упражнения. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . .
142
3.6. Действия с нечеткими бинарными отношениями . . . . . . . . . . . . . .
145
Упражнения. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . .
148
3.7. Отношения эквивалентности .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
149
Упражнения. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . .
158
3.8. Отношения толерантности .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
159
Упражнения. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . .
165
3.9. Отношения порядка .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . .
168
Упражнения. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . .
180
3.10. Отношения порядка и предпочтения. . . . . . . . . . . . . . . . . . . . . . . . . .
184
Упражнения. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . .
205
3.11. Соответствия, отображения, изоморфизмы . . . . . . . . . . . . . . . . . . .
206
Упражнения. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . .
220

Глава 4. Графы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
224

4.1. Основные понятия. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . .
224
Упражнения. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . .
234
4.2. Пути, маршруты, циклы, связность .. . . . . . . . . . . . . . . . . . . . . . . . . . .
237
Упражнения. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . .
244
4.3. Числовые характеристики и матрицы графов . . . . . . . . . . . . . . . . .
247
Упражнения. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . .
258
4.4. Деревья.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
261
Упражнения. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . .
271
4.5. Сети . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . .
273
Упражнения. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . .
293

Список использованной литературы . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
294

Список рекомендуемой литературы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
295

Приложения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
296

I. Контрольные вопросы.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
296
II. Примеры тестовых заданий и вопросов . . . . . . . . . . . . . . . . . . . . . . . . .
298

Предисловие

В подготовке современных специалистов в области социологии важную
роль играет изучение разделов математики, связанных с систематизацией
и обработкой информации, с описанием социальных отношений, структур и процессов, носящих в основном качественный характер. Особое значение имеют методы, позволяющие выделять и описывать существенные
стороны рассматриваемых объектов и связей между ними, выявлять общность подходов, математических конструкций, использовать качественные
характеристики в формализованных конструкциях.
Опыт и практика современной науки показывают, что в гуманитарных областях мы должны ориентироваться и опираться в первую очередь
на язык и понятия дискретной математики, которая предлагает не только
средства формализованного представления знаний о социальных явлениях, но и способы обработки, преобразования информации, возможности
использования различных средств для описания одних и тех же явлений.
Подобные допустимые преобразования позволяют получать новые знания
об объектах исследования, проводить дальнейшую формализацию и анализ моделей.
Целью пособия является формирование представлений о методах и
возможностях дискретной математики. Пособие призвано раскрыть содержание основных разделов теории множеств, бинарных отношений и графов, комбинаторики и математической логики, продемонстрировать основные методы и приемы построения дискретных математических моделей. Наряду с классическими темами рассматриваются вопросы, актуальные для современных приложений математики в социологии, например
нечеткие множества, социальные сети.
Содержание пособия соответствует программе курса «Дискретная математика», читаемого на факультете социологии СПбГУ, и содержит дополнительные материалы, призванные расширить представление о возможностях современной математики. Автор стремился упростить изложение материала, полагая, что при необходимости более детального рассмот
5

Предисловие

рения отдельных разделов читатель обратится к академическим изданиям,
некоторые из которых можно найти в списке рекомендуемой литературы.
Список литературы, использованной при подготовке текста, ни в коей мере не претендует на библиографическую полноту и содержит только непосредственно необходимые источники.
Пособие рассчитано в первую очередь на студентов факультета социологии СПбГУ, обучающихся по направлениям «Социология» и «Социальная работа» в рамках курсов дискретной и высшей математики, математических методов и моделей в социологии, информатике, сетевого анализа.
Пособие может быть также полезно магистрантам факультета социологии,
а также других гуманитарных направлений при изучении аналогичных математических курсов. Отдельные главы пособия могут составлять основу
специальных курсов и семинаров, а также использоваться для самостоятельной работы.
Способ изложения материала определяется целями и спецификой подготовки специалистов в области социологии. Особое внимание уделено качественным характеристикам соотношений между объектами, свойствам,
связанным с конечными множествами, наглядным формам представления математических понятий, методам абстрагирования, интерпретациям
используемых понятий и полученных результатов. Теоретические сведения приводятся без доказательств. Особое внимание уделено обоснованиям и возможности использования рассматриваемых понятий в практических исследованиях, разбору иллюстративных примеров. Номер примера
включает в себя номер главы, номер параграфа в этой главе и порядковый номер примера в параграфе. Нумерация рисунков, таблиц и формул
сквозная в каждой главе. Номер теоремы состоит из номера главы, номера
параграфа и порядкового номера теоремы в параграфе.
После каждого параграфа приводятся упражнения и задания для самостоятельной работы. Некоторые задания носят теоретический характер, требуют творческого подхода, другие — условные типовые упражнения — направлены на формирование практических навыков решения задач. В Приложении приведены контрольные вопросы и тестовые задания
по всем темам. Перед основным текстом приведен список используемых
сокращений и обозначений, а также греческий алфавит.
От читателей предполагается наличие определенной математической
подготовки в рамках школьного курса математики.
Автор благодарен всем коллегам и студентам, которые помогли исправить досадные опечатки. Особую благодарность хотелось бы выразить
В. В. Скитовичу и А. Е. Евсееву за ценные замечания и мудрые советы, без
которых эта книга не состоялась бы.

Список используемых символов и сокращений

Греческий алфавит
A α
альфа
B β
бета
Γ γ
гамма
∆ δ
дельта
E ǫ ε
эпсилон
Z ζ
дзета
H η
эта
Θ θ ϑ
тета
I ι
йота
K κ κ
каппа
Λ λ
лямбда
M µ
мю (ми)
N ν
ню (ни)
Ξ ξ
кси
O o
омикрон
Π π ϕ
пи
P ρ ̺
ро
Σ σ ς
сигма
T τ
тау
Υ υ
ипсилон
Φ φ ϕ
фи
X χ
хи
Ψ ψ
пси
Ω ω
омега

Логические символы (кванторы)
∀
Квантор всеобщности, читается: «для любого. . . », «для всех. . . »,
«для каждого. . . » или «каждый. . . », «любой. . . », «все. . . »
∃
Квантор существования, читается: «существует. . . » или
«найдется. . . »

Запись i = 1, n означает, что индекс i принимает все значения натуральных чисел
от 1 до n: i = 1, 2, 3, . . ., n.

Глава 1

Множества и элементы
математической логики

1.1.
Основные понятия

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

8

1.1. Основные понятия
9

Создатель теории множеств Георг Кантор (1845–1918), формулируя
понятие множества, писал, что множество, или совокупность — это собрание определенных и различных объектов нашей интуиции или интеллекта,
мыслимое в качестве единого. Такая формулировка предполагает подход
к понятию множества как к первоначальному, исходному понятию, не сводящемуся к каким-либо другим, более ранним понятиям. Можно считать
эту формулировку «определением» понятия множества.
Если объект x является элементом множества A, то говорят, что x
принадлежит множеству (или содержится в множестве) A, и
пишут x ∈ A или A ∋ x. В противном случае пишут x /∈ A или A ̸∋ x,
а также x ¯∈ A или A ¯∋ x.
Если множество не содержит ни одного элемента (например, свойство,
задающие множество, таково, что ни один из рассматриваемых объектов
им не обладает), то говорят, что это множество пусто. Пустое множество
обозначается символом ∅.
Пример 1.1.1. Примеры множеств:
1. Множество M1 действительных решений уравнения x2 − 1 = 0.
2. Множество M2 студентов факультета социологии СПбГУ. Здесь
требуется уточнить, кого считать студентом факультета СПбГУ: только
ли числящихся в списках студентов факультета и имеющих действующий
студенческий билет факультета социологии СПбГУ, или когда-либо учившихся на факультете, или окончивших факультет и получивших диплом
и т. п. Еще сложнее определить множество хороших студентов.
3. Множество M3 букв латинского алфавита.
4. Множество вопросов анкеты.
5. Множество анкет, полученных в результате опроса.
6. Множество M4 людей, возраст которых превышает 100 лет.
7. Множество M5 действительных корней уравнения x2 + 1 = 0. ■
Пример 1.1.2. Во всех разделах математики и ее приложениях большую роль играют числа. Напомним обозначения основных числовых множеств:
• множество натуральных чисел N = {1, 2, 3, 4, . . .};
• множество целых чисел Z = {. . . , −3, −2, −1, 0, 1, 2, 3, . . .};
• множество рациональных чисел Q = {a

b | a, b ∈ Z, b ̸= 0};
• множество действительных (вещественных) чисел R, состоящее из
всех рациональных и иррациональных чисел.
Есть еще множество комплексных чисел, обозначаемое обычно C, но в
рамках данного пособия мы не будем использовать комплексные числа. ■
Множества, состоящие из конечного числа элементов, называются конечными, в противном случае — бесконечными. Число элементов в

Глава 1. Множества и элементы математической логики

конечном множестве A называется его мощностью и обозначается |A|
(более подробное и формальное определение понятие мощности множества
дано в параграфе 3.11).
Для записи множества используются фигурные скобки, порядок следования элементов множества при записи не имеет значения, обычно каждый элемент записывается один раз, без повторений. Например, если множество A состоит из элементов a, b, c, то этот факт записывают следующим
образом: A = {a, b, c}.
Способы задания множеств следующие.
1. Задание множества перечислением (списком) элементов. Этим
способом задаются конечные множества, число элементов которых невелико. Например, в п. 1 примера 1.1.1 множество M1 состоит из двух элементов: M1 = {−1, 1}.
При задании конечного множества перечислением может использоваться многоточие, если число элементов достаточно велико, но их список понятен. Например, множество букв латинского алфавита из п. 3
примера 1.1.1 можно записать так: M3 = {a, b, c, d, . . . , x, y, z}, при этом
предполагается, что все знакомы с латинским алфавитом, в противном
случае эта запись бессмысленна. Множество натуральных чисел N бесконечно, оно не может быть задано перечислением своих элементов, но
по аналогии с конечными множествами в этом случае используют запись
N = {1, 2, 3, 4, . . .}, многоточие в конце означает неограниченное (но понятное по структуре) продолжение перечня.
2. Задание множества характеристическим свойством. В рамках как практических, так и теоретических исследований часто используют фиксированное множество, содержащее в качестве своих элементов все
рассматриваемые объекты. Такое множество называется универсальным
множеством, или просто — универсумом, и обозначается через U.
Множество A считается заданным, если задано свойство, такое, что
для каждого объекта x универсального множества можно однозначно установить, обладает ли этот объект рассматриваемым свойством, т. е. является ли объект x элементом множества A, или нет. Еще раз подчеркнем, что
единственным требованием, предъявляемым к такому свойству, является
возможность однозначно установить, обладает ли объект этим свойством
или нет. В этом случае говорят, что множество задано своим (характеристическим) свойством: все элементы этого множества и только они обладают эти свойством.
Если множество A задано свойством P(x), выделяющим элементы
этого множества из всех остальных объектов нашего рассмотрения, то
этот факт записывают как A = {x | P(x)}. Если необходимо явно ука