Матрицы бинарных
отношений
Рассмотрим два конечных
множества A
={a1,a2,…,am}
и B={b1,b2,…,bn}
и бинарное отношение

Определим матрицу
размера m×n
бинарного отношения Р по следующему
правилу:
Полученная матрица
содержит полную информацию о связях
между элементами.
Любая матрица, состоящая
из 0 и 1, является матрицей некоторого
бинарного отношения.
ПРИМЕР 1. Матрица бинарного
отношения

A={1,2,3},
заданного
на рисунке имеет вид
Основные свойства матриц
бинарных отношений:
-
Если
то
и
,
где сложение осуществляется по правилам
0+0=0, 1+1=0+1=1+0=1, а умножение – обычным
способом.
Итак,
-
Матрица
получается перемножением соответствующих
элементов из
и
:
.
-
Если
,
то
,
где умножение матриц производится по
обычному правилу умножения матриц, но
произведение и сумма элементов – по
определённым в свойстве 1 правилам. -
Матрица обратного
отношения Р-1
равна транспонированной матрице
отношения Р:
.
-
Если
,
то
.
-
Матрица тождественного
отношения idA
единична:
ПРИМЕР 2. Пусть

— матрицы отношений P и Q. Тогда
ПРИМЕР 3. Если

то
Рассмотрим свойства
отношений на языке матриц.
Пусть Р – бинарное
отношение на множестве

Отношение Р:
-
рефлексивно, если на
главной диагонали матрицы отношения
расположены только единицы; -
симметрично, если матрица
симметрична относительно главной
диагонали; -
антисимметрично, если в
матрице
все
элементы вне главной диагонали являются
нулевыми; -
транзитивно, если выполнено
соотношение
.
ПРИМЕР 4. Проверим, какими
свойствами обладает отношение

А={1,2,3}, изображённое на рисунке.
Составим матрицу отношения
Р:
Так как в матрице
на главной диагонали имеются нулевые
элементы, отношение Р не
рефлексивно.
Несимметричность матрицы
означает, что отношение Р не
симметрично.
Для проверки антисимметричности
вычислим матрицу

Поскольку в полученной
матрице все элементы, стоящие вне главной
диагонали, нулевые, отношение Р
антисимметрично.
Так как
(проверьте!), то

то есть Р является транзитивным
отношением.
Формальная теория моделирования использует алгебраические отношения, включая их в сигнатуры моделей алгебраических структур, которыми описывает реальные физические, технические и информационные объекты, процессы их функционирования. К числу последних я отношу, например, базы данных (реляционные базы данных (РеБД)). Не менее важной считаю область принятия решений, которая состоит из двух основных статистической и алгебраической, основанной целиком на теории отношений. Образовательный уровень специалистов в этой теории близок к нулю.
Откройте учебник по специализации и там увидите в лучшем случае об эквивалентностях, которые авторами трактуются весьма своеобразно. Одного защитившегося уже ДТН спрашиваю: Вы рассматриваете отношение эквивалентности на указывая ни носителя отношения, ни конкретного отношения, как оно у Вас выглядит в записи? Ответ: как выглядит — обыкновенно. Выясняется, что он обо всем этом имеет весьма смутное представление.
Публикаций по проектированию РеБД, кроме иностранных статей назвать затрудняюсь. В 90-х годах был оппонентом, писал отзыв на диссертацию, где рассматривались и иерархические, и сетевые, и реляционные БД. Но как-то год, полтора назад опять на отзыв пришла работа, автор пишет уже только о РеБД, о нормализации отношений БД, но теоретической новизны не показал. Во многих ВУЗах читается курс о базах данных, но не о том, как их создать, создать СУБД, а как правило, о том как эксплуатировать готовую (зарубежную) БД.
Преп. состав не готов научить специалистов IТ-шников создавать отечественные СУБД, ОS, языки программирования, я уж не говорю о БИС, СБИС, заказных БИС. Здесь, по-видимому, поезд ушел давно и надолго. Так что напрасно надуваются у некоторых щеки от гордости (читай снобизма) это видно по комментариям к чужим публикациям, покажите сами, что можете, а не балуйтесь никчемными переводами и перепевками чужого ради предмета гордости — «рейтинга» и «кармы». Сказывается не только отсутствие креатива, но простой образованности и воспитания.
Вторая предметная область неразрывно, связанная с отношениями, — принятие решений. Каждый из нас постоянно занят этим. Мы без решения осознанного или неосознанного пальцем не пошевелим. Мало кто понимает, а еще меньше пишет о решениях. В основе решения любого ЛПР (лица, принимающего решение) лежит предпочтение альтернатив. А моделью предпочтения как раз и является такой тип отношений, который назван «пространством отношений предпочтения». Но кто их изучает. Когда я пришел к «специалисту» по отношениям с вопросом о количестве отношений каждого типа, он не зная ответа, «убил» встречным вопросом, а зачем это Вам?
Понятие отношения
Думаю, что термин отношение знаком каждому читателю, но просьба дать определение поставит большинство в тупик. Причин для этого много. Они чаще всего в преподавателях, которые, если и использовали отношения в процессе преподавания, внимания на этом термине не заостряли, запоминающихся примеров, по-видимому, не приводили.
В моей памяти есть несколько на всю жизнь запомнившихся примеров. Об отображениях и об отношениях. Расскажу вначале об отображениях. Имеется два ведерка с краской. В одном белая в другом — черная. И есть коробка с кубиками (очень много). Грани имеют рельефные номера. Сколькими способами можно раскрасить грани кубиков в два цвета? Ответ неожиданный — столькими, сколько 6-разрядных двоичных чисел, или 26 = 64. Поясню подробнее ф: 2→6 отображаются 2 объекта в 6. Каждая строчка таблицы- дискретное отображение фi.
Построим таблицу с 6 колонками и краскам сопоставим число белая — нуль, черная — единица, а граням кубика колонки. Начинаем с того, что все 6 граней белые — это 6-мерный нулевой вектор. Вторая строчка одна грань черная, т. е. младший разряд заполнен 1. и так до исчерпания 6-разрядных двоичных чисел. Кубики ставим в общий длинный ряд. У каждого из них как бы появился номер от 0 до 63.
Теперь отображение наоборот. Пачка листов бумаги (много) и 6 красок (фломастеры).
Фломастерами разного цвета надо пометить обе стороны бумажных листов. Сколько листов потребуется. Ответ f: 6 → 2 или 62 =36. Речь идет о произвольных отображениях.
Перейдем к отношениям. Начнем с абстрактного множества — носителя отношения
А ={a1, a2, a3, …, an}.
О нем почитать можно здесь. Для лучшего понимания сократим множество до 3 элементов, т.е. А ={a1, a2, a3}. Теперь выполним декартово умножение А×А =А2,
А×А={(a1, a1),(a1, а2),(a1, a3),(a2, а1),(a2, a2),(a2, a3),(a3, a1),(a3, a2),(a3, a3)}.
Получили 9 упорядоченных пар элементов из А×А, в паре первый элемент из первого сомножителя, второй — из второго. Теперь попробуем получить все подмножества из декартова квадрата А×А. Вначале простенький пример.
Пример 1. Задано множество А ={a,b,c,d} из 4-х элементов. Выписать все его подмножества. В(А) ={Ø};{a};{b};{c};{d};{ab};{ac};{ad};{bc};{bd};{cd};{abc};{abd};{acd};{bcd};{abcd}; 24 = 16 подмножеств. Это булеан В(А) множества А и в него включено пустое подмножество.
Подмножества будут содержать из А×А разное количество элементов (пар): одну, две, три и так до всех 9 пар, включаем в этот список и пустое множество (Ø). Сколько же получилось подмножеств? Много, а именно 29= 512 элементов.
Определение. Любое подмножество декартова произведения (у нас квадрата) множества называется отношением. Заметим, в произведении используется одно и то же множество. Если множества разные, возникает не отношение, а соответствие.
Если декартово произведение из двух сомножителей, то отношение бинарное, если из 3-х -тернарное, из 4-х — тетрарное, из n — n-арное. Арность — число мест в отношении. Отношениям дают имена прописных букв R,H, P, S… Остановимся подробно на бинарных отношениях (БО), так как они играют очень важную роль в теории отношений. Собственно к бинарным отношениям могут быть сведены все остальные.
Символ отношения ставится слева от элементов R(x, y) или между ними x R y; х, у є А.
Определение Множество всех подмножеств множества А называется булеаном. Наш булеан состоит из 2|А×А| элементов, здесь|А×А| — мощность множества.
Отношения можно задавать в разном представлении над А={a1,a2,a3,a4}:
- перечислением элементов; R1={(a1,a2),(a1,a3),(a2,a3)(a2,a4)(a3,a2)(a3,a4}
- двоичным n = 16-разрядным вектором; <0110001101010000>;
- матрицей;
Рисунок 1.2. а)Матрица 4×4 бинарного отношения б) нумерация клеток Матрицы
Здесь используются номера клеток, заполненные единицами на рис. 1б)
— Векторное представление. Двоичный вектор для представления бинарного отношения формируется из элементов {0,1} следующим образом:
Рассмотренный пример задания отношения в векторной форме будет иметь следующий вид:
— Представление графом. Поставим в соответствие элементам множества
А ={x1,x2,z3,…,xn} точки на плоскости, т.е. вершины графа G = [Q, R].
Проведем в графе дугу от (xi) к (xj) тогда и только тогда, когда пара (xi,xj) є R (при i = j дуга (xi,xi) превращается в петлю при вершине (xi). Пример (рис. 1а) представления бинарного отношения A[4×4] графом изображен на рис.2.2.
Рисунок 2.2. Представление отношения ориентированным графом
Каталог бинарных отношений (n = 3)
Большое видится на расстоянии. Чтобы почувствовать отношения их разнообразие, мощность мне пришлось вручную создать каталог бинарных отношений над множеством из 3-х элементов, который включил все (боле 500 отношений) отношения. После этого «дошло» или «зашло»об отношениях.
Очевидно, что в каталог войдут 23×3 = 29 отношений, и каждое из них снабдим набором присущих им свойств. Ниже (табл. 3) приводится полный список всех 512 отношений над множеством А, |A| = 3, из трех элементов. Приводятся также результаты подсчета количества отношений (табл. 2), представленных сочетаниями номеров клеток декартова квадрата 3×3, различных подклассов для различных значений мощности множества-носителя (n = 3). Для каждого отношения указаны его основные свойства и принадлежность типу (табл. 3). Сокращения, используемые в каталоге раскрываются таблицей 2
Таблица 2. Количественные характеристики каталога при разных n
Сущность производимых операций с отношениями и их технику удобно пояснять на примерах, которые особенно просты и понятны для бинарных отношений. В операциях могут участвовать, два и/или более отношений. Операции, выполняемые над отдельными отношениями – унарные операции. Например, операции обращения (получение обратного) отношения, взятие дополнения, сужение (ограничение) отношения. Как пользоваться каталогом поясним примером примером.
Пример 2. Рассмотрим строку Nпр =14 таблицы каталога. Она имеет вид
Первые 9 символов строки (справа от равенства) — это двоичный вектор, соответствующий сочетанию из 9 по 2, а именно, номер первой клетки (отсчет слева направо) номер 5-й клетки матрицы бинарного отношения, т.е. элементы а1а1= а2а2 =1. Это сочетание имеет порядковый номер Ncч = 4 и сквозной номер Nпр = 14 в списке всех отношений. В остальных позициях этой строки стоят либо нули, либо единицы. Нули свидетельствуют об отсутствии свойства, соответствующего названию колонки нуля, а единицы – наличие такого свойства у рассматриваемого отношения.
Свойства и количественные характеристики отношений
Рассмотрим наиболее важные свойства отношений, которые позволят в дальнейшем выделить типы (классы) отношений, применяющиеся в реляционных базах данных в теории выбора и принятия решений и других приложениях. Далее будем обозначать отношение символом [R,Ω]. R- имя отношения, Ω — множество-носитель отношения.
1. Рефлексивность. Отношение [R,Ω] называется рефлексивным, если каждый элемент множества находится в отношении R сам с собой (рис. 2.3). Граф рефлексивного БО имеет во всех вершинах петли (дуги), а матрица отношения содержит (Е) единичную главную диагональ.
Рисунок 2.3. Рефлексивное отношение
2. Антирефлексивность. Отношение [R,Ω] называется антирефлексивным, если ни один элемент из множества не находится в отношении R сам с собой (рис. 2.4). Антирефлексивные отношения называют строгими.
Рисунок 2.4. Антирефлексивное отношение
3. Частичная рефлексивность. Отношение [R,Ω] называется частично
рефлексивным, если один или более элементов из множества не находится в отношении R сам с собой (рис. 2.5).
4. Симметричность. Отношение [R,Ω] называется симметричным, если вместе с упорядоченной парой (х, у) отношение содержит и упорядоченную пару (у, х) (рис. 2.6).
5. Антисимметричность. Отношение [R,Ω] называется антисимметричным, если, если для всякой упорядоченной пары (х, у) є R упорядоченная пара
(у, х)єR, только в случае х = у. Для таких отношений R∩R-1 ⊆ E (рис. 2.7).
6. Асимметричность. Отношение [R,Ω] называется асимметричным, если оно антирефлексивно и для всякой упорядоченной пары (х, у) є R упорядоченная пара (у, х) ∉ R, для отношений R ∩ R-1 = Ø (рис. 2.8).
7. Транзитивность. Отношение [R,Ω] называется транзитивным, если для всяких упорядоченных пар (х, у),(у, z) є R, в отношении R найдется упорядоченная пара (х, z) є R или если R×R⊆R (рис. 2.9).
8. Цикличность. Отношение [R,Ω] называется циклическим, если для его элементов {x1, x2, z3,…, xn} найдется подмножество элементов {xi,xi+1,…xr,…,xj,xi}, для которого можно выписать последовательность xiRxi+1R…RxjRxi. Такая последовательность называется циклом или контуром (рис. 2.10).
9. Ацикличность. Отношения, в которых отсутствуют контуры называются, ациклическими. Для ациклических отношений выполняется соотношение Rk∩R = Ø для любого k > 1 (рис. 2.11).
10. Полнота (связность). Отношение [R,Ω] называется полным (связным), если для любых двух элементов (у, z) є Ω один из них находится в отношении с другим (рис 2.12). Линейность. Линейные отношения – это минимально полные отношения.
Рисунок 2.12. Линейное отношение
Итак, нами установлено, что отношения, как математические объекты, обладают определенными свойствами, определение которых приведены ранее. В следующем пункте рассмотрим существо и проявление некоторых свойств:
- Рефлексивность х є А (хRx).
- Антирефлексивность х є А ¬(хRx).
- Симметричность х, у є А (хRy→yRx).
- Антисимметричность (xRy & yRx→x = y).
- Транзитивность; х, у, z є А(хRy & yRz →xRz).
- Цикличность; х, у є А; .
- Полнота x,y є А (xRy, yRx);
- Связность (x ≠ y→ xRy, yRx).
- Линейность x,y є А (xRy, yRx).
Анализ пространства отношений представляет сложную задачу теории и, надо отметить, далек от завершения. К основным результатам следует отнести выделение подмножеств отношений, образующих полные пространства отношений со всеми вытекающими из этого следствиями.
Количественные соотношения таких дискретных пространств представляют большой как
теоретический, так и практический интерес. Ниже рассматриваются некоторые аспекты количественных характеристик, связанных со свойствами отношений разных типов.
Операции над отношениями
Как и большинстве систем счисления с отношениями выполняются операции:
- унарные;
- бинарные;
- n-арные.
Ниже приведены таблицы булева ⊕ сложения и умножения & двух переменных x1 и x2, сложение по mod 2 и суммирование двоичных чисел:
Выше было введено понятие бинарного отношения, как подмножества упорядоченных пар декартова произведения множеств, а также были рассмотрены свойства отношений. Кроме того, были упомянуты бинарные отношения и матричное представление отношений. Рассмотрим теперь понятие отношения более подробно, кроме того, рассмотрим основные операции бинарных отношений, наиболее важные из всего их множества для отношений.
Для них должны выполняться следующие условия:
- арность операндов в операции должна совпадать;
- результатом операции должно быть отношение той же арности.
Для бинарных и n-арных отношений должно быть выполнено: область прибытия первого операнда должна совпадать с областью отправления второго операнда.
Унарные операции над отношениями
Обращение отношений. Обратным к отношению R называется отношение R-1, определяемое условием xR-1y<=>yRx. Более корректно эту операцию следовало бы назвать псевдообращением, так как р·р-1 ≠ Е = Δ.
Пусть отношение Р записано в форме перечисления входящих в него упорядоченных пар. Если в каждой паре поменять местами компоненты, то новые пары образуют отношение P-1, которое называют обратным к Р.
Обратное отношение к отношению P – такое отношение, которое образовано парами (ai aj), для которых (aj ai) є P-1. Для отношений в матричной форме обратные отношения получаются путем транспонирования матрицы Р.
9. Двойственное отношение (Pd) к отношению Р – отношение, образованное всеми теми парами, которые принадлежат универсальному отношению и не принадлежат обратному отношению (дополнение к обратному):
Pd = {(ai aj) | ((ai aj) єA×A) & (ai aj)∉
P
-1)} =(A×A) P-1.
Двойственное и обратное отношения в совокупности содержат все пары декартова произведения A×A и не имеют общих пар, они также как и отношения Р и
P
образуют разбиение A×A
Заметим, что ни для какого отношения Р не выполняется Р= Pd.
Сужение (РА1). Отношение [R1, A1] называется сужением отношения [R, A] на множество Ω1, если Ω1⊆ Ω и R1=R∩Ω1×Ω1. Отношение РА1 на множестве А1 ⊆ А – отношение РА1 на множестве А1, образованное всеми теми парами, которые принадлежат отношению Р и одновременно входят в состав декартова произведения А1 × А1. Другими словами, РА1 – пересечение отношений Р и А1×А1. Пусть А1 = {a1, a3, a4}, тогда для отношений Р и Q в матричной форме отношения сужения будут иметь вид:
Бинарные операции
Операции, требующие не менее двух отношений – n-арные (n-местные). В таких операциях могут участвовать отношения только одинаковой арности. Примеры таких операций: пересечение, объединение, разность, симметрическая разность отношений и некоторые другие. Если в операции используется более чем два отношения, то она выполняется последовательно для двух первых, а затем для итогового отношения и третьего и т.д.
Иначе говоря, эти операции определены для двух отношений. При операциях над отношениями предполагается, что области задания отношений (операндов и результата) совпадают, арности отношений совпадают, и результатом операции снова является отношение той же арности. В качестве примеров будем рассматривать операции над бинарными отношениями P и Q, заданными на дискретном множестве
А = {a1, a2, a3, a4} булевыми матрицами (нули в матрицу, как правило, не вписываются):
1. Пересечение (P ∩ Q) – отношение, образованное всеми теми парами элементов из А, которые входят в оба отношения, т.е. общие для P и Q,
P ∩ Q = {(ai aj) | ((ai aj) є P) & ((ai aj) є Q)}.
Матрица отношения P ∩ Q получается как булево пересечение матриц P и Q:
При отсутствии таких общих пар говорят, что пересечение отношений пусто, т.е. оно является нуль-отношением. Пересечением отношений R1 и R2 (R1∩R2 ) называется отношение, определяемое пересечением соответствующих подмножеств из А×А.
2. Объединение (PUQ). Объединением отношений R1 и R2 (R1UR2 ) называется отношение, определяемое объединением соответствующих подмножеств из А×А. Отношение, образованное всеми парами, составляющими или отношение P, или отношение Q, т.е. парами, принадлежащими хотя бы одному из отношений (связка ∨ — или объединительная)
P U Q = {(ai aj) | ((ai aj) є P) ∨ ( (ai aj) є Q)}.
Если в множестве А×А нет других пар, не вошедших в отношение PUQ, а пересечение их нулевое, то говорят, что отношения P и Q при объединении образуют полное отношение А×А, а их система – разбиение этого полного отношения. Объединение матриц отношений образуется как булева сумма матриц отношений:
3.Разность (PQ) – отношение, образованное теми парами из Р, которые не входят в отношение Q
PQ = {(ai aj) | ((ai aj) є P)&((ai aj)∉Q)}.
Разность для отношений в матричном представлении имеет вид
4. Умножение отношений. Упорядоченные пары, образующие отношения могут содержать одинаковые элементы, а могут и не содержать. Среди пар, имеющих в своем составе одинаковые элементы, выделим такие упорядоченные пары, которые назовем смежными (примыкающими) и которые имеют во второй паре 1-й элемент, а в первой паре 2-й элемент один и тот же. Определим произведение смежных пар как упорядоченную пару:
( ai ak)∙( ak aj) => (ai aj).
В терминах теории графов сказанное означает, что смежные пары образуют маршрут из точки (ai) в точку (aj) транзитом через точку (ak), состоящий из 2-х смежных дуг. Произведение этих дуг – третья дуга из точки (ai) в точку (aj), реализующая переход между крайними точками маршрута в том же направлении, минуя промежуточную точку (ak). Говорят, что дуга (ai aj) замыкает эти точки напрямую.
5. Симметрическая разность (P∆Q) – отношение, образованное теми парами, которые входят в объединение PUQ, но не входят в пересечение P∩Q. Другая форма определения объясняет название операции: P∆Q образовано теми упорядоченными парами, которые являются объединением разностей PQ и QP. Таким образом, выражение для симметрической разности записывается двумя разными способами:
P∆ Q = (PU Q)(P ∩ Q) = (PQ)U (QP).
Матрица симметрической разности имеет вид:
Из последней записи следует, что операция симметрической разности допускает перестановку операндов, т. е. коммутативна.
5. Композиция или произведение (P∙Q) – отношение, образованное всеми парами, для которых выполняется:
P∙Q = {(ai aj)|((ai ak) є P) & ((ak aj) є Q)}.
Другими словами, каждая упорядоченная пара в результирующем отношении есть результат умножения смежных пар, из которых 1-я пара принадлежит первому сомножителю-отношению, 2-я – второму сомножителю-отношению. Операция композиции не коммутативна.
Композиция (Р◦Q) на множестве М – отношение R, заданное на том же множестве М, которое содержит пару (x, y), когда существует Z є M такое, что (x, z) є P и (z, y) є Q.
При матричном представлении отношений матрица композиции отношений равна булеву произведению матриц исходных отношений:
Частный случай композиции отношений – квадрат отношения.
Можно показать, используя индукцию, что n-я степень отношения определяется рекуррентно по формуле:Pn=Pn-1◦Р, это означает, что пара (x,y) є Pn в том случае, когда в матрице Р существует цепочка элементов: такая, что (xi, xi+1)є P, 1<i<n–1.
Операция композиции обладает свойством ассоциативности (как произведение матриц).
Композиция отношений на множестве М – результат попарной композиции отношений при любой расстановке скобок. Область задания результата композиции при этом не меняется.
Композиция для булевых матриц отношений образуется в результате булева произведения матриц этих отношений.
Таблица 3. Каталог бинарных отношений (n = 3). Кликабельно
Литература
1. Авдошин С.М., Набебин А.А. Дискретная математика. Модулярная алгебра, криптография, кодирование. — М.: ДМК Пресс, 2017. -352 с.
2. Акимов О.Е. Дискретная математика.Логика, группы, графы- М.: Лаб.Баз. Зн., 2001. -352 с.
3. Андерсон Д.А. Дискретная математика и комбинаторика.- М.: Вильямс, 2003. -960 с.
4. Берлекэмп Э. Алгебраическая теория кодирования. -М.: Мир,1971.- 478 с.
5. Ваулин А.Е. Дискретная математика в задачах компьютерной безопасности. Ч 1- СПб.: ВКА им. А.Ф. Можайского, 2015. -219 с.
6. Ваулин А.Е. Дискретная математика в задачах компьютерной безопасности. Ч 2- СПб.: ВКА им. А.Ф. Можайского, 2017. -151 с.
7. Горенстейн Д. Конечные простые группы.Введение в их классификацию.-М.: Мир,1985.- 352 с.
8. Грэхем Р., Кнут Д., Пташник О. Конкретная математика.Основание информатики.-М.: Мир,1998.-703 с.
9. Дейт К. Введение в системы баз данных. -М.: Наука,1980. -463 с.
10. Елизаров В.П. Конечные кольца.- М.: Гелиос АРВ,2006. — 304 с.
Иванов Б.Н. Дискретная математика: алгоритмы и программы-М.: Лаб.Баз. Знаний., 2001. -280 с.
11. Ерусалимский Я.М. Дискретная математика: теория, задачи, приложения-М.: Вузовская книга, 2000.-280 с.
12. Корн Г., Корн Т. Справочник по математике для научных работников и инженеров.-М.: Наука, 1973.-832 с.
13. Лидл Р., Нидеррайтер Г. Конечные поля: В 2-х т. Т.1 -М.: Мир,1988. — 430 с.
14. Лидл Р., Нидеррайтер Г. Конечные поля: В 2-х т. Т.2 -М.: Мир,1988. — 392 с.
15. Ляпин Е.С., АйзенштатА.Я., Лесохин М.М., Упражнения по теории групп.-М.: Наука,1967.-264 с.
16. Мейер Д. Теория реляционных баз данных. -М.: Мир, 1987.- 608 с.
17. Муттер В.М. Основы помехоустойчивой телепередачи информации. -Л. Энергоатомиздат,1990.- 288 с.
18. Нагао М., Катаяма Т., Уэмура С. Структуры и базы данных. — М.: Мир, 1986. — 197 с.
19. Наумов А.Н. и др. Системы управления базами данных и знаний.-М.: Финансы и статистика,1991.-352 с.
20. Набебин А.А.Дискретная математика.- М.: Лаб.Баз. Знаний., 2001. -280 с.
21. Новиков Ф.А. Дискретная математика для программистов.- СПб.: Питер, 2000. -304 с.
22. Розенфельд Б.А. Многомерные пространства.-М.: Наука,1966.-648 с.
23. Ульман Дж. Основы систем баз данных. — М.: Финансы и статистика,1983.-334 с.
24. Холл М. Теория групп.-М.: Изд. ИЛ, 1962.- 468 с.
25. Шиханович Ю.А. Группы, кольца, решётки. — СПб.: Кирцидели,2006. — 368 с.
26. Шнеперман Л.Б. Курс алгебры и теории чисел в задачах и упражнениях: В 2-х ч Ч.2.-Мн.: Выш. шк., 1987. -256 с.
27. Шнеперман Л.Б. Сборник задач по алгебре и теории чисел.- Минск: Дизайн ПРО,2000. -240 с.
Здравствуйте на странице расположен курс лекций по дискретной математике с примерами решения заданий и выполнением задач. В лекциях рассматриваются все темы по предмету «Дискретная математика«: теория множеств (множества, отношения, функции), комбинаторика и общая алгебра (алгебраические системы). Для краткой записи утверждений используются следующие обозначения символов:
Для любых предложений 


Содержание:
Множества
Определение и способы задания множеств
Множество — это любое собрание вполне определенных и различимых объектов нашей интуиции или интеллекта, мыслимое как единое целое. Это описание множества принадлежит основателю теории множеств Георгу Кантору (1845 — 1918).
Объекты, из которых состоит множество, называются его эле- ментами. Множества будем обозначать прописными буквами латинского алфавита (A, B, C, X, Y, Z, . . .) , а элементы множеств — строчными (x, y, z, a, b, c, . . .) . Зафиксируем следующие обозначения для наиболее важных числовых множеств: N — множество натуральных чисел, Z — множество целых чисел, R — множество действительных чисел.
Множество A называется подмножеством множества B (обозначается — A ⊆ B , знак ⊆ называется знаком включения),если каждый элемент множества A является элементом множества B .
Множества A и B равны ( A = B ), если одновременно имеют место включения A ⊆ B и B ⊆ A . Принадлежность элемента x множеству A обозначается x ∈ A , непринадлежность элемента x множеству A обозначается x ∈/ A .
Множество, не содержащее элементов, называется пустым и обозначается ∅ .
Множество, включающее элементы всех рассматриваемых в конкретной ситуации множеств, называется универсальным для данной ситуации и обозначается U . Для любого множества имеют место включения: ∅ ⊆ A ⊆ U .
Рассмотрим способы задания множеств. Множество может быть задано:
- а) описанием характеристического свойства его элементов,
- б) при помощи списка или перечисления элементов множества,
- в) при помощи порождающей процедуры и т. д.
При задании множества A при помощи его характеристического свойства P (x) пишут A = {x| P (x)}.
При помощи списка могут задаваться только конечные множества, т. е. множества, состоящие из конечного числа элементов.
Порождающая процедура описывает способ получения элементов множества из уже полученных элементов или других объектов. Весьма распространенной порождающей процедурой является образование множеств из других множеств при помощи операций, которые рассмотрим ниже.
Операции над множествами и их свойства
Объединением множеств A и B называется множество A ∪ B , состоящее из тех и только тех элементов, которые принадлежат хотя бы одному из множеств A или B :
A ∪ B = {x | x ∈ A или x ∈ B}.
Пересечением множеств A и B называется множество A ∩ B , состоящее из тех и только тех элементов, которые принадлежат одновременно множествам A и B :
A ∩ B = {x | x ∈ A и x ∈ B}.
Разностью множеств A и B называется множество A B тех и только тех элементов из A , которые не принадлежат множеству B :
A B = {x | x ∈ A и x ∈/ B}.
Дополнение 

Симметричной разностью множеств A и B называется множество:
Эти операции можно наглядно проиллюстрировать следующим образом:
Приведенные здесь рисунки называются диаграммами Эйлера-Венна.
Операции над множествами обладают следующими свойствами:
= A (закон двойного отрицания);
- A ∪ B = B ∪ A (коммутативность объединения);
- A ∩ B = B ∩ A (коммутативность пересечения);
- A ∪ (B ∪ C) = (A ∪ B) ∪ C (ассоциативность объединения);
- A ∩ (B ∩ C) = (A ∩ B) ∩ C (ассоциативность пересечения);
- A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) (1-й дистрибутивный закон);
- A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) (2-й дистрибутивный закон);
-
- A ∪ (A ∩ B) = A (закон поглощения);
- A ∩ (A ∪ B) = A (закон поглощения);
- A ∪ ø = A ;
- A ∩ ø = ø;
- A ∪ U = U ;
- A ∩ U = A .
Мощность конечного множества
Число элементов конечного множества A называется его мощностью и обозначается |A| .
Говорят, что между множествами A и B установлено взаимооднозначное соответствие, если задан закон, по которому каждому элементу множества A соответствует один и тот же элемент множества B .
Между конечным непустым множеством A мощности n и отрезком натурального ряда {1, 2, . . . , n} существует взаимооднозначное соответствие.
Приведем очевидные свойства мощности конечных множеств:
1) | ø | = 0 ; 2) из A ⊆ B следует |A| ≤ |B| , если при этом 
Прямое произведение двух и более множеств.
Прямым произведением двух множеств A = {a1, . . . , am} и B = {b1, . . . , bn} называется множество A × B упорядоченных пар вида (ai, bj) , где
Прямым произведением k множеств A1 , A2 , . . . , Ak называется множество A1 × A2 × . . . × Ak упорядоченных наборов 
Эти определения кратко можно записать так: A × B = {(a, b) | a ∈ A, b ∈ B}.
Теорема о мощности прямого произведения. Мощность прямого произведения конечного числа конечных множеств равна произведению мощностей этих множеств
|A1 × A2 × . . . × Ak| = |A1| · |A2| · . . . · |Ak|, k ∈ N.
Доказательство. Рассмотрим вначале случай двух множеств и докажем формулу |A × B| = |A| · |B| .
Пусть A = {a1, . . . , am} и B = {b1, . . . , bn}, тогда элементы A × B множества можно раcположить в виде следующей таблице:
которая содержит m строк и n столбцов. Поэтому число записанных в таблице упорядоченных пар равно mn = |A | * | B |.
Для доказательства теоремы в случае произвольного k воспользуемся методом математической индукции. При k = 1 теорема, очевидно, имеет место. Предположим, что она выполняется для случая (k − 1) -го множества и докажем ее для случая k множеств. С этой целью установим взаимооднозначное соответствие между множествами:
A1 × A2 × . . . × Ak и (A1 × A2 × . . . × Ak−1) × Ak
по правилу: элементу 

их мощности совпадают; используя утверждение теоремы для случая двух множеств, получаем:
|A1×A2×. . .×Ak| = |(A1×A2×. . .×Ak−1)×Ak| = |A1×A2×. . .×Ak−1||Ak|.
В силу предположения индукции |A1 × . . . × Ak−1| = |A1| . . . |Ak−1| , что завершает доказательство теоремы.
Множество 
Из теоремы о мощности прямого произведения следует:
Пусть E = {0, 1}, тогда 


Булеан множества
Булеаном Б(A) множества A называется множество всех подмножеств этого множества: Б(A) = {X|X ⊆ A}, если A = {a1, . . . , an}, то
Теорема о мощности булеана. Пусть A — конечное множество мощности n , тогда мощность его булеана равна 2n : |Б(A)| = 2n .
Доказательство. Установим соответствие между множествами Б(A) и En по правилу: подмножеству 
В качестве примера приведенного в доказательстве теоремы соответствия рассмотрим случай n = 3 . Пусть A = {α, β, γ}, тогда
Б(A) = {ø, {α}, {β}, {γ}, {α, β}, {α, γ}, {β, γ}, {α, β, γ}};
E3 = (0, 0, 0), (1, 0, 0), (0, 1, 0), (0, 0, 1), (1, 1, 0), (1, 0, 1), (0, 1, 1), (1, 1, 1) .
Соответствие между E3 и Б(A) может быть установлено 8! различными способами (оно равно числу перестановок из элементов множества E3 ). В данном случае элементы множества E3 записаны так, что эле- менту, стоящему на k -ом месте, 

Отметим следующее свойство булеана:
Б(A ∪ B) = {A1 ∪ B1|A1 ∈ Б(A), B1 ∈ Б(B)}.
Действительно, пусть произвольное множество C ∈ Б(A ∪ B) , т. е. C ⊆ A ∪ B . Обозначим через A1 = C ∩ A , B1 = C ∩ B . Тогда A1 ⊆ A , B1 ⊆ B и C = A1 ∪ B1 , где A1 ∈ Б(A) , B1 ∈ Б(B) . Докажем обратное включение. Если A1 ∈ Б(A) , B1 ∈ Б(B) , то A1 ⊆ A , B1 ⊆ B . Тогда A1 ∪ B1 ⊆ A ∪ B ⇒ A1 ∪ B1 ∈ Б(A ∪ B) .
Рекомендации к решению задач:
Предположим, что все встречающиеся в задачах этого и следующего параграфов множества являются подмножествами некоторого универсального множества U . При решении предложенных для самостоятельной работы задач ( § 7 ) полезно использовать следующие факты.
1) Изображение множеств при помощи диаграмм Эйлера-Венна, при этом множества A , B , C располагаются в в общем положении , когда
Пример №1
Проверим равенство множеств (A∪B)∩C и A∪(B∩C) .
Для этого изобразим их с помощью диаграмм Эйлера-Венна:
На рис.6 штриховкой обозначено множество (A ∪ B) ∩ C , а на рис.7 — A ∪ (B ∩ C) . Очевидно, что это разные множества.
2) Определения и основные свойства операций над множествами, а также доказанные свойства этих операций.
Пример №2
Докажем второй дистрибутивный закон,
A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C),
используя определение операций объединения и пересечения для множеств и второй дистрибутивный закон для высказываний. При этом и в дальнейшем используется символ . . . ⇐⇒ . . . , который означает эквивалентность утверждений, стоящих слева и справа от него.
Решение. Пусть 
x ∈ A ∪ (B ∩ C) ⇐⇒ x ∈ A или x ∈ (B ∪ C) ⇐⇒
⇐⇒ x ∈ A или (x ∈ B и x ∈ C) ⇐⇒ (x ∈ A или x ∈ B) и (x ∈ A или x ∈ C) ⇐⇒ (x ∈ A∪B) и (x ∈ A∪C) ⇐⇒ x ∈ (A∪B)∩(A∪C).
3) При рассмотрении равенств, содержащих символы операций 

Первое из этих равенств непосредственно следует из определения операции :
Второе из равенств (1.1) является следствием первого.
Пример №3
Докажем равенство (A B) C = (A C) (B C).
Используем при этом первое из равенств (1.1), закон де Моргана, первый дистрибутивный закон и др.
Пример №4
Докажем равенство множеств
На первом шаге использовалось второе из равенств (1.1), на следующем шаге использовался закон де Моргана, далее первый дистрибутивный закон для множеств. Выражения в первой и третьей скобках последнего равенства есть пустые множества, поэтому
Пример №5
Докажем равенство (A ∩ B) × (C ∩ D) = (A × C) ∩ (B × D).
Произвольным элементом множества, стоящего справа, является упорядоченная пара (x, y) . Пусть
(x, y) ∈ (A∩B)×(C∩D) ⇐⇒ (x ∈ A∩B) и (y ∈ C∩D) ⇐⇒ (x ∈ A и x ∈ B)
и (y ∈ C и y ∈ D) ⇐⇒ (x, y) ∈ (A × C) и (x, y) ∈ (B × D) ⇐⇒
⇐⇒ (x, y) ∈ (A × C) ∩ (B × D).
Бинарные отношения
Определение и способы задания отношений
Подмножество 

Говорят, что элементы 

Одноместное отношение это просто подмножество 

Наиболее часто встречающимися являются двуместные или бинарные отношения. Ниже будем рассматривать только бинарные отношения, поэтому для краткости слово «бинарные» будем опускать. Если а и b находятся в отношении 

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


Так, для бинарных отношений 


Отношение также можно задать с помощью рисунка, который называют графом. Каждому элементу 






Операции над отношениями
Поскольку отношения на множестве А являются подмножествами множества 






Отношение 


Произведением отношений 


Транзитивным замыканием отношения 



Транзитивным замыканием отношения «быть сыном» является отношение «быть прямым потомком». Оно представляет собой объединение отношений «быть сыном», «быть внуком» , «быть правнуком» и т.д. Транзитивным замыканием «жить в одном городе» является то же отношение.
Свойства отношений
Отношение 



Примерами рефлексивных отношений являются отношения 


Отношения 
Отношение 




Отношения «жить в одном городе», «иметь общий делитель, отличный от 1» на множестве целых чисел, «быть симметричным относительно оси» на множестве точек плоскости являются примерами симметричных отношений. Отношения 

Таблица (матрица) симметричного отношения симметрична относительно главной диагонали
Теорема. Отношение 
Доказательство. Действительно, пусть 




Отношение 

Отношения 
Теорема. Если 
Доказательство. Из определения транзитивности замыкания следует, что 








Отношение эквивалентности
Отношение называется отношением эквивалентности и (или просто эквивалентностью), если оно рефлексивно, симметрично и транзитивио.
Будем говорить, что имеет место разбиение множества А на классы, если существует система 
Теорема. Между совокупностью различных разбиений множества А на классы, и семейством всех отношений эквивалент пост а на этом множестве существует взаимнооднозначное соответствие.
Доказательство. Пусть имеет место разбиение (2.1) множества А на классы. Построим отношение 




















Пусть 
















Предположим, что последнее не верно: существует элемент 









Если 





Мощность множества 
Фактор-множество множества N по отношению «иметь общий остаток от деления на 5» состоит из пяти счетных классов: 
Отношение порядка
Отношение 
Отношение 
Говорят, что два элемента 




Множество А, на котором задано отношение порядка (строгого или нестрогого), называется полностью упорядоченным, если любые его два элемента сравнимы, и частично упорядоченным, если это не так.
Пусть множество А упорядочено отношением порядка 
Элемент 


Элемент 


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



Отношение включения 

В качестве А рассмотрим множество 





Построенное отношение является отношением нестрогого порядка на частично упорядоченном множестве 
Рекомендации к решению задач:
При доказательстве равенств и включений для отношений можно пользоваться методикой, разработанной в главе 1, §7 для множеств. При этом следует учитывать, что элементами отношения на множестве А являются упорядоченные пары
Пример №6
Докажем справедливость равенства
Решение. Пусть
Пример №7
Пусть 

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

Пример №8
Пусть на множестве 







Пример №9
Покажем, что отношение 

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






Правило произведения. Правило произведения для двух объектов: Пусть объект а можно выбрать m способами и после каждого такого выбора объект b можно выбрать n способами, тогда выбор пары объектов а и b в указанном порядке можно осуществить m • n способами.
Данное правило произведения равносильно утверждению
Правило произведения является следствием теоремы о мощности прямого произведения конечного числа конечных множеств.
Правило произведения для случая произвольного числа объектов формулируется следующим образом: Пусть объект 





Последнее правило применяется, если требуется выполнить одно за другим одновременно 
Понятие k-выборки
Понятие 
Пусть 

При реализации описанных в таблице процедур мы получаем комбинацию элементов из множества А вида 

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

Элементы упорядоченной выборки заключаются в круглые скобки (например (1,2)).
Элементы неупорядоченной выборки без повторений заключаются в фигурные скобки (например {1,2}), а элементы неупорядоченной выборки с повторениями в квадратные скобки (например [1,2]).
Упорядоченные выборки (3,2) и (2,3) считаются различными, хотя и составлены из одних и тех же элементов. Для тех же самых элементов «2» и «3» неупорядоченные выборки {3,2} и {2,3} (или [3,2] и [2,3]) считаются одной и той же.
Рассмотрим множество, которое содержит три элемента А — {1, 2, 3} . Составим из элементов этого множества всевозможные 2 — выборки.
Упорядоченные 2-выборки без повторений: (1,2), (2,1), (1,3), (3, 1), (2,3), (3,2).
Упорядоченные 2-выборки с повторениями: (1,2), (2, 1), (1,3), (3,1), (2,3), (3,2), (1,1), (2,2), (3,3).
Неупорядоченные 2-выборки без повторений: {1,2}, {1,3}, {2,3}.
Неупорядоченные 2-выборки с повторениями: [1,2], [1,3], [2,3 , [1,1], [2,2], [3,3].
В следующих параграфах будут даны формулы для подсчета количества 
Размещения с повторениями и без повторений. Перестановки без повторений
Размещениями из n элементов по к называются упорядоченные 
Размещениями без повторений из n элементов по 


Размещениями с повторениями из n элементов по 

Перестановками из n элементов называются размещения без повторений из n элементов по n . Их число обозначается, 
Теорема. Имеют место следующие равенства:
где
Доказательство. Пусть 




Число таких наборов равно мощности прямого произведения множеств
В силу теоремы о мощности прямого произведения имеем:
Умножим и разделим последнее выражение на 
Размещения с повторениями из элементов множества А по к представляют собой упорядоченный набор 


Третье получается из первого при 
Сочетания с повторениями и без повторений
Сочетаниями из а элементов по 
Сочетаниями без повторений из n элементов по k называются неупорядоченные k -выборки из n элементов без повторений. Их число обозначается 
Сочетаниями с повторениями из n элементов по k называются неупорядоченные k -выборки из n элементов с повторениями. Их число обозначается 
Теорема. Имеют место следующие равенства:

Доказательство. Прежде чем доказать равенство для 




На основании вышеизложенного имеем равенство:
Аналогичная ситуация имеет место в общем случае: чтобы получить все 


Перейдем к доказательству второго равенства (3.2). Введем обозначения: 
по 

Неупорядоченная k-выборка 





Пусть 





Мы установили взаимооднозначное соответствие между множествами 
Теорема доказана.
Перестановки с повторениями. Подсчет числа беспорядков
Классическая задача комбинаторики о числе разбиений с повторениями формулируется следующим образом: сколькими способами можно разбить n различных предметов на k групп, по 


Такие комбинации называются перестановками с повторениями.
Число различных перестановок из 



Действительно, для первой группы можно выбрать 









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

Рассмотрим еще один вид перестановок n предметов — циклические перестановки.
Задача заключается в следующем: рассматриваются n предметов, расположенных не в ряд, а по кругу. В этом случае перестановки считаются одинаковыми, если они получаются при переходе друг в друга при вращении, т.е. при циклическом сдвиге. Число таких перестановок из различных предметов
Немаловажной является и задача о «подсчете числа беспорядков» , когда требуется найти число 
Свойства сочетаний. Бином Ньютона
При помощи формулы (3.2) посредством алгебраических преобразований легко получить следующие свойства сочетаний:
Биномом Ньютона называется равенство
Докажем его, пользуясь методом математической индукции. При n = 1 имеем очевидное равенство:
Предположим, что равенство (3.3) имеет место при n = k и, исходя из этого предположения, докажем его для случая n = к + 1:
Из равенства (3.3), положив сначала х = а = 1, затем х = {—а) — 1, получим новые свойства сочетаний:
Так как сочетание без повторений из n элементов по k представляет собой k-элементное подмножество множества мощности n, то величина 
Общий случай формулы включений и исключений
Пусть имеется N элементов, каждый из которых может обладать или не обладать свойствами 





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

Обозначим через А, В, С множества элементов, обладающих свойствами 



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

Это равенство верно для любого конечного множества элементов, в частности для множества элементов, обладающих свойством 




В каждом слагаемом здесь присутствует 
а в правой части, сгруппировав слагаемые с одинаковым количеством свойств, получим правую часть равенства (3.5). Теорема доказана.
Частный случай формулы включений и исключений
Предположим, что число 

Используя введенные обозначения, получим следующие выражения для сумм в (3.5):
Положив далее 
Применение формулы включений и исключений
Рассмотрим множество чисел {1,2,… ,n} и найдем число D(n) перестановок 
Обозначим через 


Нетрудно заметить, что 


Здесь мы имеем тот случай, когда величины 
Число элементов N в рассматриваемом случае равно числу перестановок из n элементов: 


В случае n = 3 из (3.8) находим, что число D(3) перестановок, в которых числа 1, 2, 3 не стоят на своих местах, равно 2.
Рекомендации к решению задач:
При решении комбинаторных задач, в которых требуется определить количество некоторых выборок (комбинаций) из данного множества элементов, основным моментом является правильное определение типа (характера) выборок — упорядоченные это выборки или нет, с повторениями или без повторений. Эти различные комбинации называются размещениями, сочетаниями и перестановками, определения которых были даны выше.
Добавим, что при решении задач комбинаторики можно пользоваться терминологией: элементы (объекты), из которых состоит k-выборка, помещаются в «ячейки». Порядок заполнения «ячеек» может быть произвольным, но нужно выбирать наиболее простой.
Пример №10
Сколько есть трехзначных чисел, делящихся на 4, в записи которых не используются цифры 0, 4, 5, 6, 8, 9?
Решение. Число делится на 4 тогда и только тогда, когда две последние его цифры образуют число, делящееся на 4. В нашем случае это числа 12, 32, 72. Для построения комбинации понадобятся две «ячейки»: в первую можно поместить одну из цифр 1, 2, 3, 7; во вторую одну из ранее перечисленных двухзначных чисел. Первый объект можно выбрать 4 способами, второй объект 3 способами. По правилу произведения ответом на поставленный вопрос является число 4 • 3 = 12.
Применяя правило произведения, следует обратить внимание на условие. Выбор каждого последующего элемента не должен зависеть от выбора предыдущего. Следующий пример является иллюстрацией к этому замечанию.
Пример №11
Сколько есть шестизначных чисел, в каждом из которых нет одинаковых цифр, а вторая и четвертая цифры нечетны?
Решение. Очевидно, что надо взять шесть «ячеек». Заполним эти «ячейки» . В первую «ячейку» поместим одну любую из 9 цифр (кроме «0»). Во вторую «ячейку» нужно поместить нечетную цифру. Так например, если на первое место мы поставили цифру 2, то на второе место можно поставить одну из цифр «1», «3», «5», «7» или «9». Если же на первом месте уже стоит цифра «9», то на второе место можно поставить только «1», «3», «5» или «7». Указанный способ выбора является неудобным, поэтому рассмотрим другой порядок заполнения «ячеек» вторая, четвертая, первая, третья, пятая, шестая. Во вторую поместить одну из 5 нечетных цифр, в четвертую любую из 4 оставшихся нечетных цифр, в первую одну из 7 (кроме «О» и тех двух, что уже стоят, в третью любую из 7 оставшихся, в пятую любую из 6 оставшихся, в шестую — любую из 5 оставшихся. В результате получим .5 • 4 • 7 • 7 • 6 • 5 = 29 400 чисел, обладающих заданным свойством.
В некоторых случаях для того, чтобы найти число элементов конечного множества, обладающих требуемым свойством, удобно найти сначала число элементов, не обладающих этим свойством, и затем вычесть это число из общего числа элементов множества.
Пример №12
Сколько есть пятизначных чисел, в записи которых есть хотя бы одна четная цифра?
Решение. Всего пятизначных чисел 9 • 10 • 10 • 10 • 10 = 90 000, из них
5 • 5 • 5 • 5 • 5 = 3125 чисел, которые состоят только из нечетных цифр. Поэтому количество требуемых чисел равно 86 875.
Разберем типичные задачи на применение правила суммы и формулы включений и исключений.
Пример №13
Сколькими способами из 28 костей домино можно выбрать кость, на которой есть «1» или «6»?
Решение. Выбрать кость, содержащую « 1 » , можно семью способами, содержащую «6» тоже семью способами, но среди этих способов есть один общий — это выбор кости «1 : 6 ». В соответствии с правилом суммы общее число способов нужной кости можно осуществить 7 + 7— 1 = 13 способами.
Пример №14
Сколькими способами можно составить трехцветный полосатый флаг, если имеется материал шести различных цветов?
Решение. Нужно найти число 3-выборок из 6 элементов без повторений (так как все цвета различны). Порядок, в котором располагаются выбранные цвета, существенен. Следовательно, нужно найти число упорядоченных выборок, т.е. число размещений из 6 по 3 без повторений:

Данную задачу можно решить и другим способом. Для выбора цвета первой полосы имеется 6 вариантов. После произведенного выбора цвет для второй полосы можно выбрать 5 из оставшихся 5 способов. Далее выбираем цвет для третьей полосы из 4 оставшихся 4 способами. По правилу произведения имеем: 6 • 5 • 4 = 120 способов.
Пример №15
Сколько существует различных наборов длины 10 из нулей и единиц?
Решение. Так как набор состоит из десяти элементов, которые принимают только два возможных значения « 0 » или « 1 » , то в этом наборе будут присутствовать одинаковые значения элементов (т.е. элементы повторяются). Следовательно, нужно найти число упорядоченных выборок с повторениями:

Пример №16
В магазине имеются в продаже мобильные телефоны 7 торговых марок. Сколькими способами можно купить: а) 5 аппаратов разных торговых марок; б) 4 аппарата; в) 15 аппаратов?
Решение. В случае а) нужно подсчитать число неупорядоченных 5-выборок из 7 возможных без повторений (все телефонные аппараты разных торговых марок). Их число определяется по формуле:

В случаях б) и в) нас интересуют неупорядоченные выборки из 7 элементов с повторениями длины 4 и 15 соответственно. Их значения определяются по формулам:
б) 
в) 
Пример №17
Семь девушек водят хоровод. Сколькими различными способами они могут встать в ряд?
Решение. Если девушки стояли бы на месте, то получилось бы 7! способов перестановок в ряду. Но так как они кружатся, то их положение относительно окружающих предметов несущественно, а важно только их взаимное расположение. Поэтому перестановки, переходящие друг в друга при кружении (циклическом сдвиге), нужно считать одинаковыми. Так как из каждой перестановки сдвигом можно получить еще 6 новых, то количество интересующих нас перестановок будет равно: 7!/7 = б!.
Пример №18
В ходе экзаменационной сессии 1 студентов получили оценки «отлично», 12 — «хорошо», 13 — «удовлетворительно», 5 — «хорошо» и «отлично», 7 «хорошо» и «удовлетворительно», 8 — «отлично» и «удовлетворительно». У трех студентов все виды оценок. Сколько студентов в группе, если известно, что все они сдали сессию? Сколько отличников в группе? Сколько в группе чистых «троечников»?
Решение. В условии задачи 

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

число чистых «троечников» равно:

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



Решение. Из данных 


Пример №20
Сколькими способами можно переставить буквы слова «перелет» так, чтобы три буквы «е» не шли подряд?
Решение. Объединим все буквы «е» в один блок «еее». Число перестановок, в которых все три буквы «е» идут подряд, равно числу перестановок из 5 объектов: «еее», «и», «р», «л», «т», т.е. Р(5) = 5! = 120. Всего же перестановок с повторениями из букв данного слова можно составить 
Пример №21
Сколькими способами можно расставить m нулей и k единиц, где 
Решение. Выпишем сначала m нулей. Для единиц получается m + 1 место (одно место слева, m — 1 в промежутках между нулями и одно справа). На любые из этих m + 1 мест можно поставить одну из k единиц. Это можно осуществить 

Пример №22
Найти число способов разбиения n одинаковых предметов по k урнам (n и k произвольные натуральные числа).
Решение. Переименуем урны, расположив их в ряд. Между ними будет (k — 1) промежуток. Поставим в соответствии каждому разбиению предметов но урнам последовательность из нулей и единиц следующим образом: сначала последовательность имеет группу из «0», число которых равно числу предметов в первой урне, затем ставим одну перегородку, обозначив ее за «1»; далее столько «0», сколько предметов во второй урне, и опять ставим «1»; затем столько «0», сколько в третьей урне, и т.д., заканчивается последовательность группой «0»; их столько, сколько предметов в последней урне. Следовательно, в такой последовательности будет n нулей и (k — 1) единиц, всего (n + k — 1) цифр. Тогда число способов разбиения будет равно 
Пример №23
Комиссия состоит из n человек. Документы хранятся в сейфе. Сколько замков должен иметь сейф, сколько ключей для них нужно изготовить и как распределить между членами комиссий, чтобы доступ к сейфу был возможен тогда и только тогда, когда соберутся вместе не менее m человек комиссии 
Решение. Какие бы m — 1 членов комиссии не собрались, должен найтись замок, который они не смогут открыть, но ключ от этого замка имеется у каждого из n — (m — 1) = n — m + 1 > 0 остальных членов комиссии (появление кого-нибудь из которых дает возможность открыть сейф). Следовательно, число замков равно 

Пример №24
Сколькими способами можно расставить в шеренгу n различных львов и m различных тигров так, чтобы никакие два тигра не шли друг за другом (
Решение. Расставим сначала всех львов, оставив между каждыми двумя промежуток. Это можно сделать Р(n) способами, так как все львы разные, если бы все львы были одинаковы, то расставить их в ряд можно было одним способом. Теперь для расстановки тигров имеется (n + 1) место (либо одно впереди всех львов, либо одно после всех, либо между ними — (n — 1)). Так как порядок тигров существенен (они все разные), то число их способов расстановки равно 

Линейные рекуррентные соотношения второго порядка
Линейным рекуррентным соотношением второго порядка (ЛРС) называется функциональное уравнение вида
где 

Из вида ЛРС (4.1) следует, что для вычисления значения функции 



называются начальными условиями для ЛРС (4.1).
Рассмотрим в качестве примера ЛРС

Если 
Нетрудно убедиться, что и в случае произвольных начальных условий (4.3) значение функции 
Решением ЛРС называется функция f(n) (f : N —► R), при подстановке которой в (4-1) получается, равенство, истинное при всех n € N.
Функция 


Частным решением ЛРС (4.1) называется, решение, удовлетворяющее начальным условиям (4.2).
В дальнейших рассуждениях используется очевидный факт: при любых 
Общим решением ЛРС (4-0 называется вещественная функция 








Свойства решений
Лемма. Пусть 



Доказательство. Так как 

Умножим первое тождество на 

откуда следует, что функция 
Алгебраическое уравнение второго порядка

называется характеристическим уравнением, соответствующим ЛРС (4.1).
Случай простых корней характеристического уравнения
Теорема (об общем решении JIPC в случае простых корней характеристического уравнения). Пусть 


Доказательство. Покажем, что функция 


что равносильно равенству: 


Пусть 


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

Здесь мы воспользовались тем, что 

Частные решения 

Теорема доказана.
Случай кратных корней характеристического уравнения
Рассмотрим случай, когда 

Теорема (об общем решении ЛРС в случае кратного корня).
Пусть 

Доказательство. Покажем, что функция 

что равносильно равенству 


Повторяя рассуждения предыдущей теоремы, находим постоянные 





Теорема доказана.
Соотношение Фибоначчи
Рекуррентное соотношение

известно как соотношение Фибоначчи. Характеристическое уравнение для соотношения (4.10) имеет вид: 


Числами Фибоначчи называется решение соотношения (4.10), удовлетворяющее начальным условиям F( 1) = 0, F(2) = 1. Полагая в формуле (4.11) n = 1 и n = 2, получим для 

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

1) выписывается характеристическое уравнение

и находятся его корни
2) если 
3) если 
4) для нахождения частного решения 




Затем найденное решение системы 

Если 



Пример №25
Найти общее решение ЛРС 

Решение. Характеристическое уравнение в этом случае имеет вид: 





Пример №26
Найти общее и частное решение ЛРС

Решение. Характеристическое уравнение 

Далее находим частное решение. Система уравнений для 
Решая эту систему, находим 


Пример №27
Пусть 



Для доказательства воспользуемся методом математической индукции. При 



Докажем его для случая n = k + 1. Действительно, по предположению индукции и из уравнения Фибоначчи получаем:

Пример №28
Построить ЛРС, частные решения которого имеют вид:
Решение. Из вида частных решений искомого рекуррентного соотношения корни его характеристического уравнения 
Перепишем его в стандартном виде 


Множества, функции, отношения
Множества и операции над ними
Основные понятия теории множеств:
Определение: Множеством М называется объединение в единое целое определенных различимых однотипных объектов 
Множество можно описать, указав какое-то свойство, присущее всем элементам этого множества.
Замечание. Вообще говоря, понятие множества считается первичным (исходным) понятием, и, как таковое, не определяется. Приведённое выше определение следует, скорее, считать уточнением понятия множества.
Множество, все элементы которого являются числами, называется числовым. В дальнейшем мы будем, прежде всего, рассматривать именно такие множества. Множество, элементами которого являются другие множества, называется классом или семейством.
Множество, содержащее конечное число элементов, называется конечным. При подсчёте количества элементов учитываются только различные (неповторяющиеся) элементы.
Множество, не содержащее элементов, называется пустым и обозначается символом
Множество может быть задано перечислением (списком) своих элементов, порождающей процедурой или описанием характеристических свойств (предикатом), которым должны обладать его элементы. Причём в последнем случае необходимо формулировать описание характеристических свойств элементов множества достаточно корректно, для того, чтобы множество было определено вполне однозначно. Добавим, что многие числовые множества могут быть заданы всеми тремя указанными способами (например, множество четных однозначных чисел).
Пример №29
Некоторые примеры множеств, заданных различными способами.
а) 

Мощностью конечного множества 


Определение: Если все элементы множества 

Определение: Если A с В, то множество A называется подмножеством множества В (также говорят, что В покрывает A). Если при этом 

Замечание. Не следует считать равносильными отношения принадлежности 



Парадокс Рассела. Задание множеств характеристическим предикатом может привести к противоречиям. Рассмотрим множество всех множеств, не содержащих себя в качестве элемента: 




Для трех множеств А, В, С справедливы следующие соотношения:
Связь между включением и равенством множеств устанавливается следующим соотношением:
Здесь знак 
В заключение добавим, что Г. Кантор предложил использовать понятие «универсального множества» (универсум), как бы противоположного понятию пустого множества

Операции над множествами и их свойства
Определение: Объединением множеств А и В называется множество С, элементы которого принадлежат хотя бы одному из множеств А и В. Обозначается 
Геометрическое изображение множеств в виде области на плоскости называется диаграммой Эйлера-Вэйна.
Определение: Пересечением множеств А и В называется множество С, элементы которого принадлежат каждому из множеств А и В. Обозначение 

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

Пример №30
Исходя из определения равенства множеств и операций над множествами, доказать тождество и проверить его с помощью диаграммы Эйлера-Вэйна.
Из записанных выше соотношений видно, что
Что и требовалось доказать. Для иллюстрации полученного результата построим диаграммы Эйлера — Вэйна:
Пример №31
Исходя из определения равенства множеств и операций над множествами, доказать тождество.
Если некоторый элемент 
Множество 
Множество 
Множество 
Таким образом, тождество можно считать доказанным.
Векторы и прямые произведения
Вектором (кортежем) в линейной алгебре и дискретной математике называют упорядоченный набор элементов. Это не есть определение вектора, поскольку целесообразнее это понятие считать основным.
Элементы, определяющие вектор, называются координатами или компонентами. Координаты нумеруются слева направо, а их число называется длиной или размерностью вектора. В отличие от элементов множества, координаты вектора могут совпадать. Координаты вектора заключаются в круглые скобки, например 
Определение: Два вектора равны, если они имеют равную длину и их соответствующие координаты равны. Иначе говоря, векторы 


Определение: Прямым произведением множеств А и В (обозначение 


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



Пример №32
Множество 
Координатное представление точек плоскости было впервые предложено Р.Декартом и исторически является первым примером прямого произведения. Поэтому часто прямое произведение множеств называют декартовым произведением.
Пример №33
Даны множества 


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

Определение: Проекцией вектора 

Теорема 1.1. Мощность произведения конечных множеств 
Следствие.
Эта простая теорема и сё следствие впоследствии широко используются в комбинаторике.
Соответствия и функции
Соответствия
Определение: Соответствием между множествами А и В называется некоторое подмножество G их декартова произведения: 
Если 
В принятых обозначениях, каждый элемент 



Соответствие называется полностью определённым, если D(G) = А, то есть каждый элемент множества А имеет хотя бы один образ во множестве В; в противном случае соответствие называется частичным.
Соответствие G называется сюрьективным, если E(G) = В, то есть если каждому элементу множества В соответствует хотя бы один прообраз во множестве А .
Соответствие G называется функциональным (однозначным), если любому элементу множества А соответствует единственный элемент множества В.
Соответствие называется иньективным, если оно является функциональным, и при этом каждый элемент множества В имеет не более одного прообраза.
Соответствие G называется взаимнооднозначным (биективным), если любому элементу множества А соответствует единственный элемент множества В, и наоборот. Можно сказать также, что соответствие является взаимнооднозначным, если оно является полностью определённым, сюръектпвным, функциональным, и при этом каждый элемент множества В имеет единственный прообраз.
Пример №34
а) Англо-русский словарь устанавливает соответствие между множествами слов русского и английского языка. Оно не является функциональным, так как почти каждому русскому слову соответствует несколько английских переводов; оно, также, не является, как правило, полностью определённым соответствием, так как всегда существуют английские слова, не включённые в данный словарь. Таким образом, это частичное соответствие.
б) Соответствие между аргументами функции 

в) Соответствие между расположенными на шахматной доске фигурами и занимаемыми ими полями является взаимно однозначным.
г) Соответствие между телефонами города Вязьмы и их пятизначными номерами обладает, на первый взгляд, всеми свойствами взаимнооднозначного соответствия. Однако оно, например, не сюръективно, поскольку существуют пятизначные числа, не соответствующие никаким телефонам.
Взаимнооднозначные соответствия и мощности множеств
Если между двумя конечными множествами А и В существует взаимнооднозначное соответствие, то эти множества равномощны. Этот очевидный факт позволяет, во-первых, установить равенство мощности этих множеств, не вычисляя их. Во-вторых, часто можно вычислить мощность множества, установив его однозначное соответствие с множеством, мощность которого известна, либо легко вычисляется.
Теорема 2.1. Если мощность конечного множества А равна n, то число всех подмножеств А равно 

Множество всех подмножеств множества М называется булеаном и обозначается 
Для конечных множеств выполняется: 
Определение: Множества А и В называются равномощными, если между их элементами можно установить взаимнооднозначное соответствие.
Заметим, что для конечных множеств это утверждение легко доказать. Для бесконечных множеств оно определят само понятие равномощности.
Определение: Множество А называется счётным, если оно равномощно множеству натуральных чисел
Очень упрощённо можно сказать, что данное бесконечное множество является счётным, если для его элементов можно установить нумерацию с помощью натуральных чисел.
Без доказательства примем ряд важных фактов:
- Любое бесконечное подмножество множества натуральных чисел является счётным.
- Множество
является счётным.
- Множество рациональных чисел R является счётным (является следствием из предыдущего утверждения).
- Объединение конечного числа счётных множеств является счётным.
- Объединение счётного числа конечных множеств является счётным.
- Объединение счётного числа счётных множеств является счётным.
Все эти утверждения, как можно видеть, позволяют достаточно успешно устанавливать факт, что данное множество является счётным. Однако сейчас будет показано, что не всякое бесконечное множества является счётным; существует множества большей мощности.
Теорема 2.2 (теорема Кантора). Множество всех действительных чисел из отрезка [0; 1] не является счётным.
Доказательство. Допустим, что множество 
Теперь рассмотрим любую бесконечную десятичную дробь вида 

Следствие 1. Множество действительных чисел R континуально.
Следствие 2. Множество всех подмножеств счётного множества континуально. Как показывается в теории множеств (с помощью метода, аналогичного приведённому выше), для множества любой мощности множество всех его подмножеств (булеан) имеет более высокую мощность. Поэтому не существует множества максимальной мощности. Например, множество-универсум 

Отображения и функции
Функцией называется любое функциональное соответствие между двумя множествами. Если функция 




Полностью определённая функция 


Если 

Отображение типа
Пример №35
а) Функция 

б) Функция
в) Функция 
г) Функция 



Определение: Функция типа 



Например, сложение, умножение, вычитание и деление являются двухместными функциями на 

Определение: Пусть дано соответствие 






Определение: Если соответствие, обратное к функции 

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




Пример №36
Функция 



Определение: Пусть даны функции 




Композиция функций 






Для многоместных функций 




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





Одноместное (одномерное) отношение — это просто некоторое подмножество А. Такие отношения называют признаками. Говорят, что 


Наиболее часто встречающимися и хорошо изученными являются двухместные или бинарные отношения. Если а и b находятся в отношении R , это обычно записывается в виде 
Пример:
Бинарные отношения на множестве N .
а) Отношение 
Пример:
Бинарные отношения на множестве точек координатной плоскости.
а) Отношение «быть равноудалёнными от начала координат» выполнятся для пар точек (1;-4) и (-4;1), но не выполнятся для пары точек (3;0) и (-2; 6). б) Отношение «принадлежать окружности, центр которой находится в начале координат», выполняется для первой пары точек из предыдущего примера и не выполняется для второй пары. в) Отношение «быть удалёнными на разное расстояние от начала координат» выполняется для всех точек, для которых не выполняется отношение, описанное в пункте «б».
Пусть дано отношение 









Строго говоря, само отношение 


Для задания бинарных отношений можно использовать любые способы задания множеств (например, список пар, для которых данное отношение выполняется). Отношения на конечных множествах обычно задаются списком или матрицей. Матрица бинарного отношения на конечном множестве 



Пример:
Для конечного множества 
а)
б) 
в)
Поскольку отношения на множестве 



Определение: Отношение 


Непосредственно из определения следует, что 

Свойства отношений
Определение: Отношение 


Главная диагональ матрицы рефлексивного отношения содержит только единицы.
Определение: Отношение 


Главная диагональ матрицы рефлексивного отношения содержит только нули.
Например, отношения 

Определение: Отношение 




Матрица симметричного отношения симметрична относительно главной диагонали: 
Определение: Отношение 



Отношение «быть симметричным относительно оси абсцисс» является симметричным: если первая точка симметрична второй относительно этой оси, то и вторая точка симметрична первой. Отношение 


Нетрудно убедиться в том, что отношение 

Определение: Отношение 



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






Замечание. Замыкание является весьма общим математическим понятием. Упрощенно говоря, замкнутость означает, что многократное повторение допустимых шагов не выводит за определённые границы. Например, множество натуральных чисел замкнуто относительно операции сложения, однако открыто (то есть незамкнуто) относительно операции деления.
Если отношение 

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

б) Утверждения вида 


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










Эта система обладает следующими свойствами:
1) она образует разбиение множества 
Все эти свойства прямо следуют из определения отношения эквивалентности. Действительно, если бы, например, классы 





Построенное разбиение, то есть система классов — подмножеств множества 


Пример 2.
а) Все классы эквивалентности по отношению равенства 
Отношения порядка
Определение 1. Отношение 
Определение 2. Отношение 
Оба типа отношений вместе называются отношениями порядка. Элементы 




Пример 3.
а) Отношения 





б) Определим отношения 


1)
2) 

Тогда, например, (1, 2, 3) < (1, 2,4), но (1,2,3) и (1,-2,4) несравнимы. Таким образом, эти отношения частично упорядочивают 
в) На системе подмножеств множества 



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


Пример 4.
а) Наиболее известным примером лексикографического упорядочения слов является упорядочение слов в словарях. Например, лес 

б) Если рассматривать числа в позиционных системах счисления (например, в десятичной системе) как слова в алфавите цифр, то их лексикографическое упорядочение совпадает с обычным, если все сравниваемые числа имеют одинаковое количество разрядов. В общем же случае эти два вида могут не совпадать. Например, 10 < 1073 и 20 < 1073, но 10 


в) Лексикографическое упорядочивание цифровых представлений дат вида 19.07.2004 (девятнадцатое июля две тысячи четвёртого года) не совпадает с естественным упорядочением дат от более ранних к более поздним. Например, дата 19.07.2004 «лексикографически» старше восемнадцатого числа любого года. Чтобы возрастание дат совпадало с лексикографическим упорядочением, обычное представление надо «перевернуть», то есть записать в виде 2004.07.19. так обычно делают при представлении дат в памяти ЭВМ.
Введение в общую алгебру
Свойства бинарных алгебраических операций:
Определение: На множестве А определена алгебраическая операция, если каждым двум элементам этого множества, взятым в определенном порядке, однозначным образом поставлен в соответствие некоторый третий элемент из этого же множества.
Примерами алгебраических операций могут служить такие операции как сложение и вычитание целых чисел, сложение и вычитание векторов, матриц, умножение квадратных матриц, векторное умножение векторов и др.
Отметим, что скалярное произведение векторов не может считаться алгебраической операцией, т.к. результатом скалярного произведения будет число, и числа не относятся к множеству векторов, к которому относятся сомножители.
Замечание. Вообще говоря, операция, определённая таким образом, называется бинарной, поскольку в ней участвуют два элемента. Но также можно говорить об унарных операциях, в которых участвует только один элемент данного множества, и в соответствие ему однозначным образом поставлен второй элемент этого множества. Таковы, например, операции извлечения корня квадратного или нахождения модуля числа.
Аналогично можно определить тринарную и прочие операции на данном множестве, в зависимости от количества участвующих в них элементов. В общем случае, 


Определение: Операция 

Тождественной операцией на множестве 
Для того чтобы описанные ниже соотношения выглядели бы более привычно, положим результат применения бинарной операции 



Определение: Операция 


Операции сложения и умножения чисел коммутативны, а вычитание и деление некоммутативны. Также некоммутативна операция умножения матриц (как известно из курса линейной алгебры).
Определение: Операция 


Выполнение условия ассоциативности означает, что скобки в выражении 



Правда, запись 



Определение: Операция 



и дистрибутивной справа относительно операции 

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


Алгебраические структуры
Определение: Пусть дано некоторое множество 





Определение: Множество 











Пример 1.
а) Алгебра 


б) Пусть задано множество 





в) Множество 


Определение: Замыканием множества 




Например, в алгебре целых чисел 
Теорема 5.1. Непустое пересечение подалгебр образует подалгебру.
Гомоморфизм и изоморфизм
Алгебры с различными типами (в смысле, определённом в пункте 1), очевидно, имеют существенно различное строение. Если же алгебры имеют одинаковый тип, то наличие у них сходства характеризуется вводимых ниже понятий.
Определение: Пусть даны две алгебры 



Смысл данного определения состоит в следующем. Независимо от того, выполнена ли сначала операция 





Сейчас мы определим некоторые виды гомоморфизма, обладающие дополнительными свойствами.
Определение: Гомоморфизм, который является инъекцией, называется мономорфизмом.
Определение: Гомоморфизм, который является сюръекцией, называется эпиморфизмом.
Определение: Гомоморфизм, который является биекцией, называется изоморфизмом.
Таким образом, можно сказать, что изоморфизм — это взаимно однозначный гомоморфизм.
Замечание. Если множества-носители двух данных алгебр равны, то их гомоморфизм называется эндоморфизмом, а изоморфизм — автоморфизмом.
Теорема 5.2. Если 



Пример 2.
а) Пусть 







б) Изоморфизмом между алгебрами 



в) Булевы алгебры, образованные двумя различными множествами одинаковой мощности, изоморфны: операции у них просто одинаковы (см. выше), а отображением 
Теорема 5.3. Отношение изоморфизма является отношением эквивалентности на множестве алгебр.
Понятие изоморфизма является одним из важнейших понятий в математике. Его сущность можно выразить следующим образом. Если две алгебры изоморфны, то элементы и операции любой из них можно переименовать таким образом, что эти алгебры совпадут. Это позволяет, получив некоторое эквивалентное соотношение в данной алгебре, распространять его на любую изоморфную ей алгебру. Распространённое в математике выражение «с точностью до изоморфизма» означает, что рассматриваются только те свойства объектов, которые сохраняются при изоморфизме, то есть являются общими для всех изоморфных объектов. В частности, изоморфизм сохраняет коммутативность, ассоциативность и дистрибутивность.
Различные виды алгебраических структур
Полугруппы
Определение: Полугруппой называется алгебра вида 

Как правило, в качестве такой операции 




Замечание. Не следует понимать сказанное выше в том смысле, что полугруппа всегда включает в себя именно арифметическую операцию умножения. Термин «умножение» здесь является достаточно условным. Символ 

В общем случае, 
Если множество-носитель полугруппы содержит такой элемент 







Пример 1.
а) Алгебра 

б) Алгебра 


в) Алгебра 
Определение: Если любой элемент полугруппы 


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




Определение: Полугруппа, в которой нет определяющих соотношений, и любые два различных слова обозначают различные элементы группы, называется свободной.
Доказано, что каждую полугруппу можно получить из некоторой свободной полугруппы введением некоторых определяющих соотношений. Элементы заданной так полугруппы — это слова в алфавите образующих, причём некоторые слова равны (то есть задают один элемент) в силу определяющих соотношений. Они позволяют из любого слова получить любые эквивалентные ему слова. Отношение равенства слов есть отношение эквивалентности. Кстати, намного сложнее выяснить для двух данных слов, можно ли получить одно из другого с помощью определяющих соотношений. Исследование этой проблемы оказало значительное влияние на теорию алгоритмов.
Группы
Определение 1. Группой называется полугруппа с единицей, в которой для каждого элемента 


Если не использовать в определении понятие полугруппы, то определить понятие группы можно следующим образом.
Определение 2. Множество 
1) для любых трех элементов 
2) в множестве 


3) для любого элемента 

Замечание. Различные множества могут образовывать группу относительно какой-либо операции и не являться группой относительно другой операции.
Число элементов в множестве-носителе называется порядком группы. Группа, в которой операция коммутативна, называется коммутативной или абелевой. Группа, в которой все элементы являются степенями одного элемента, называется циклической. Для абелевых групп часто применяется аддитивная форма записи: операция обозначается, как сложение, а единица обозначается, как 0.
Пример 2.
а) 


б) Алгебра 



в) Множество невырожденных квадратных матриц порядка 
г) Множество матриц одинакового порядка 
Замечание. Нахождение элемента, обратного данному, в общем случае, есть унарная операция. Поэтому тип любой группы (2,1). Иногда, при записи конкретной группы указывают в скобках кроме бинарной операции ещё и эту унарную операцию, либо (чаще) нейтральный элемент группы. Например, для группы из примера 2.а соответствующая запись имеет вид 

Поля и кольца
Определение: Множество 


Если операция умножения, определенная в кольце коммутативна, то такое кольцо называется коммутативным кольцом.
Из определения следует, что любое кольцо имеет две бинарные и одну унарную (см. пункт 2) операцию, поэтому его тип — (2,2,1).
Определение: Полем называется коммутативное кольцо, в котором для любого ненулевого элемента 


Другими словами, для любой пары элементов 


Пример 3.
а) Алгебра 


Решётки
До сих пор нами рассматривались алгебры, то есть множества, на которых заданы операции. Множества, на которых кроме операций, заданы отношения, называются алгебраическими системами. Таким образом, алгебры можно считать частным случаем алгебраических систем, у которых множество алгебраических отношений пусто. Другим частным случаем алгебраических систем являются модели — множества, на которых заданы только отношения.
Рассмотрим здесь лишь один пример алгебраической системы, который наиболее часто встречается в теоретической алгебре и её приложениях — решётки.
Определение: Решёткой называется множество 



(идемподентность);
(коммутативность);
(ассоциативность);
(поглощение).
Решётка называется дистрибутивной, если выполняются два следующих условия 
Определение: Если в решётке существует элемент 0, такой что для любого 

Определение: Если в решётке существует элемент 1, такой что для любого а выполняется 
Определение: Решётка, имеющая верхнюю и нижнюю грани, называется ограниченной.
Теорема 6.1. Если нижняя (верхняя) грань решётки существует, то она единственная.
Определение: В ограниченной решётке элемент 


Пример 4.
а) Любое полностью упорядоченное множество, например, множество целых чисел, можно превратить в решётку, определив для любых 


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




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

Обозначается 

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



3) Дизъюнкция. Дизъюнкцией (логическим «или») двух высказываний 


4) Импликация. Импликацией (логическим следованием) двух высказываний 



Обозначается 



5) Эквиваленция. Эквиваленцией (логической равносильностью) двух высказываний 

Обозначается 
С помощью этих основных таблиц истинности можно составлять таблицы истинности сложных формул.
Замечание. В дальнейшем мы познакомимся с принципиально иной, более широкой трактовкой тех понятий, которые мы определили в данной лекции. Мы будем их рассматривать уже не как операции над высказываниями, но как некоторые функции. Поясним на следующем примере. Запись 



Пример №37
С помощью таблиц истинности проверить, являются ли эквивалентными формулы 
Составим таблицы истинности для каждой формулы:
Данные формулы не являются эквивалентными.
Пример №38
С помощью таблиц истинности проверить, являются ли эквивалентными формулы 
Составим таблицы истинности для заданных формул.
Из составленных таблиц видно, что данные формулы не равносильны
Основные равносильности
Для любых формул А, В и С справедливы следующие равносильности:

Булевы функции
Определение: Булевой функцией 
Вообще говоря, между логическими высказываниями, логическими связками и булевыми функциями просматривается явная аналогия (подробнее она рассматривается в следующей лекции). Если логические функции могут принимать значения истинно или ложно, то для булевой функции аналогами этих значений будут значения 0 или 1.
Для булевых функций также можно составить таблицы значений, соответствующим основным логическим операциям.
Логические функции
Ниже будет подробно рассматриваться двухэлементное множество В и двоичные переменные, принимающие значения из этого множества. Его элементы часто обозначают 0 и 1, однако они, вообще говоря, не являются числами в обычном смысле (хотя и похожи на них по некоторым свойствам). Наиболее распространённая интерпретация двоичных переменных — логическая: «да» — «нет», «истинно» — «ложно». В контексте, содержащем одновременно двоичные и арифметические величины, а также функции, эта интерпретация обычно фиксируется явно. Например, в языках программирования (Pascal и др.) вводится специальный тип переменной — логическая переменная, значения которой обозначаются true и false. В данной лекции логическая интерпретация двоичных переменных не везде является обязательной, поэтому будем считать, что В — {0;l}, рассматривая 0 и 1 как формальные символы, не имеющие арифметического смысла.
Функции алгебры логики
Определение: Алгебра, образованная множеством В вместе со всеми возможными операциями на нём, называется алгеброй логики.
Определение: Функцией алгебры логики (логической функцией) называется 

Первый термин является более точным, однако второй более распространён, особенно в приложениях. Он и будет использоваться в дальнейшем. Итак, логическая функция 



Определение: Алгебра, образованная 




Множество всех 


Всякая логическая функция 

Наборы, на которых значение функции равно 1, часто называют единичными наборами функции 


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



Определение: Переменная 


Иначе говоря, переменная считается несущественной, если изменение её значения в любом наборе не изменяет значения функции. В этом случае функция 











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






Логических функций двух переменных — шестнадцать; они приведены в таблице 3.
Функции 




Среди представленных в таблице 3 функций отмстим те, которые уже знакомы нам в качестве логических операций, изученных в ходе предыдущей лекции.
Функция 




Операцию 
Функция 




Функция 


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


Обозначается: 


Функция 
Функция 
Есть ещё две функции двух переменных, имеющие специальные названия. Функция 



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






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

Определение: Говорят, что формула 







Соответственно, формулы 



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



Все формулы, построенные подобным образом, то есть содержащие только символы переменных, скобки и знаки функций из множества 

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




Всякая формула, выражающая данную функцию, как суперпозицию других функций, задаст способ её вычисления (при условии, что известно, как вычислять исходные функции). Этот способ определяется следующим очевидным правилом: формулу можно вычислить, только если уже вычислены значения всех её подформул. Применим, например формулу (*) к набору 


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

штрих Шеффера — можно представить формулами 

Определение: Формулы, представляющие одну и ту же функцию называются эквивалентными или равносильными.
Эквивалентность формул принято обозначать знаком равенства, поэтому можно записать:
Существует стандартный метод для выяснения эквивалентности двух формул. По каждой формуле восстанавливается таблица функции, а затем две полученные таблицы сравниваются. Таким способом в предыдущеё лекции мы устанавливали равносильность высказываний. Он весьма громоздок, так как требует 

Булевы алгебры
В данной лекции будут рассмотрены способы представления логических функций в виде суперпозиций функций И, ИЛИ, НЕ.
Разложение функций по переменным. Совершенная дизъюнктивная нормальная форма
Введём обозначения: 





Теорема 8.1. Всякая логическая функция

где 


Равенство (1) называется разложением по переменным 



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








Пример №39
Составить СДНФ для функции, заданной таблицей:
Поскольку данная таблица (уже встречавшаяся ранее) содержит три единичных набора, СДНФ будет конъюнкцией трёх дизъюнкций. В свою очередь, каждая дизъюнкция включает три переменных — по числу их в функции 
Получим:
Напомним, что, подобно знаку умножения, знак дизъюнкции 
Единственная функция, которая не имеет СДНФ — это константа 
Формулы, содержащие кроме переменных и скобок, только знаки дизъюнкции, конъюнкции и отрицания, будем называть булевыми формулами.
Теорема 8.2. Всякая логическая функция может быть представлена булевой функцией, то есть как суперпозиция дизъюнкции, конъюнкции и отрицания.
Булева алгебра функций
Выше мы обозначили множество всех логических операций на двухэлементном множестве 

Определение: Булевой алгеброй логических функций называется алгебра вида 
Замечание. На практике мы имеем дело не самими функциями, а с представляющими их формулами, то есть с алгеброй формул, которая значительно шире, поскольку каждую функцию представляет бесконечное множество формул. Чтобы «синхронизировать» их алгебре формул придаётся следующий вид. Элементами алгебры формул объявляются не сами формулы, а классы эквивалентности формул, то есть классы формул, представляющих одну и ту же функцию. Определённая таким образом, алгебра формул называется алгеброй Линденбаума — Тарского. Она изоморфна булевой алгебре функций.
Теперь рассмотрим основные свойства булевых операций (частично уже знакомые по теме «Элементы математической логики»).
- Ассоциативность: a)
.
- Коммутативность: а)
.
- Дистрибутивность конъюнкции относительно дизъюнкции:
.
- Дистрибутивность дизъюнкции относительно конъюнкции:
.
- Идемпотентность: а)
.
- Двойное отрицание:
- Свойства констант:
- Правила де Моргана: а)
Очень важные соотношения, которые часто будут использоваться в дальнейшем. С их помощью (а также с помощью соотношения 6) дизъюнкция заменяется конъюнкцией и наоборот.
- Закон противоречия:
.
- Закон «исключённого третьего»:
.
Все соотношения 1-10 можно проверить указанным ранее стандартным методом -вычислением обеих частей равенств на всех наборах значений переменных. Эти равенства остаются справедливыми и в случае подстановки вместо переменной любой логической функции и, следовательно, любой формулы, представляющей эту функцию. Важно лишь соблюдать следующее правило подстановки формулы вместо переменной.
При подстановке формулы 


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






Замечание. Есть существенная разница между подстановкой и заменой. При подстановке переменная заменяется формулой; при этом формула может быть любой, лишь бы производилась одновременная замена ею всех вхождений переменной. При замене подформул может быть заменена любая подформула, однако, не на любую другую, а только на подформулу, эквивалентную ей. При этом замена всех вхождений исходной подформулы не обязательна.
Эквивалентные преобразования
Пример:
Возьмём соотношение 8а и подставим вместо переменной 







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


Далее будем опускать доказательства приводимых равенств, которые при желании можно получить из соотношений 1 — 10 и уже доказанных равенств.
б) Склеивание: 


Одним из главных видов упрощения формул является приведение их к дизъюнктивной нормальной форме (ДНФ).
Определение: Элементарными конъюнкциями называются конъюнкции переменных или их отрицаний, в которых каждая переменная встречается не более одного раза. Дизъюнктивной нормальной формой называется формула, имеющая вид дизъюнкции элементарных конъюнкций.
Заметим, что СДНФ является частным случаем ДНФ.
Приведение формулы к ДНФ выполняется так. Сначала с помощью соотношений 6 и 8 все отрицания «спускаются» до переменных. Затем раскрываются скобки. После этого с помощью соотношений 5, 9 и 10 удаляются лишние конъюнкции и повторения переменных в конъюнкциях. Наконец, с помощью соотношений 7а — 7е удаляются лишние константы. При этом необходимо помнить, что ДНФ данной формулы может быть не единственной.
Пример №40
Привести к ДНФ формулу
Решение:

Доказано, что если из формулы 



Теорема 8.3. Для любых двух эквивалентных формул 



Аналогично понятию ДНФ определяется понятие конъюнктивной нормальной формы (КНФ), то есть КНФ есть конъюнкция элементарных дизъюнкций. Переход от КНФ к ДНФ и обратно всегда осуществим (обычно, с помощью формул Де Моргана).
Пример №41
Привести формулу 
Булевы алгебры и теория множеств
1. Двойственность
Определение: Функция 

Если взять отрицание обеих частей равенства и подставить 




Пример:
Если рассматривать логические функции, то, очевидно, дизъюнкция двойственна конъюнкции и наоборот (непосредственно следует из правил Де Моргана). Отрицание является самодвойственной функцией. Функция-константа 


Пользуясь определением двойственности нетрудно доказать следующее утверждение, называемое принципом двойственности.
Теорема 10.1. Если в формуле 




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




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



Булева алгебра и теория множеств:
Ранее были описаны булевы алгебры множеств, то есть алгебры вида 


Определение: Всякая алгебра типа (2,2,1) называется булевой алгеброй, если её операции удовлетворяют соотношениям 1-10 (см. предыдущую лекцию).
В алгебре множеств элементами являются подмножества фиксированного универсального множества 

В одной из предыдущих лекций отмечалось взаимно однозначное соответствие между множеством 










Пусть даны два вектора 

Поскольку компоненты (координаты) векторов принимают значения 0 или 1, то указанные операции — это просто логические операции над двоичными переменными, поэтому операции над векторами естественно назвать покомпонентными логическими операциями над двоичными векторами.
Пример №42
Даны векторы 

Решение:
Заметим, что подобные операции (наряду с логическими операциями над переменными) входят в систему команд любой современной ЭВМ.
Теорема 10.2. Если мощность множества 


Эта простая по содержанию теорема имеет огромное значение в математике. Она позволяет заменить теоретико-множественные операции над системой подмножеств данного множества поразрядными логическими операциями над двоичными векторами.
Похожая по формулировке, но значительно отличающаяся по смыслу теорема существует для множества всех логических функций 




Теорема 10.3. Если мощность множества 



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

ДНФ, интервалы и покрытия
Теоретико-множественная интерпретация булевой алгебры предлагает очень удобный язык для изучения дизъюнктивных нормальных форм (ДНФ) и построения методов их упрощения. Рассмотрим кратко основные понятия, связанные с ДНФ.
Введём следующее обозначение: обозначим через 









Если функция 













Пример №43
Рассмотрим функцию 



Далее, очевидно, что 



В рассматриваемом случае говорят, что конъюнкция 


Представление некоторой функции в виде ДНФ соответствует представлению её единичного множества в виде объединения интервалов; в совокупности все конъюнкции ДНФ покрывают всё единичное множество функции 
элементы некоторого интервала 


Полнота и замкнутость
Ранее нами рассматривались два способа задания логических функций — табличный и с помощью формул. Таблица задаёт функцию непосредственно как соответствие между двоичными наборами и значениями функции на этих наборах. Этот способ универсален, то есть, пригоден для любых функций, однако слишком громоздок. Формула — гораздо более компактный способ задания функции, но она задаёт функцию через другие функции. Поэтому для любой системы функций 
получен положительный ответ для системы 

Функционально полные системы
Определение: Система функций 

Из теоремы 8.2 следует, что система 



Теорема 11.1. Если все функции функционально полной системы 


Пример 1.
а) Системы 

С точки зрения функциональной полноты систему 


избыточными, зато формулы в них получаются гораздо длиннее: замена одной операции на другую вносит в формулу сразу три лишних отрицания.
б) Системы 

Таким образом, система 



в) Система 




На свойствах этой системы остановимся подробнее.
Алгебра Жегалкина и линейные функции
Определение: Алгебра над множеством логических функций с двумя бинарными операциями 
Замечание. Операция 

В алгебре Жегалкина выполняются следующие соотношения (знак умножения 
2.1. 


Кроме того, выполняются соотношения, ранее сформулированные булевой алгебры, относящиеся к конъюнкции и константам. Отрицание и дизъюнкция выражаются так:
2.5 

Если в произвольной формуле алгебры Жегалкина раскрыть скобки и произвести все упрощения по вышеуказанным соотношениям, то получится формула, имеющая вид Суммы произведений, то есть полином (многочлен) по модулю 2. Такая формула называется полиномом Жегалкина для данной функции.
От булевой формулы всегда можно перейти к формуле алгебры Жегалкина, используя равенства 2.5 и 2.6, а также прямое следствие из равенства 2.6: если 


Пример 2. Составить полиномы Жегалкина для данных функций:
а) 
Заметим, что если в полученных полиномах Жегалкина произвести обратную замену функций, то получим упрощенные формулы булевой алгебры.
Теорема 11.2. Для всякой логической функции существует полином Жегалкина и притом единственный.
Существование такого полинома, по сути, уже доказано, а для доказательства его единственности достаточно показать существование взаимно однозначного соответствия между множеством всех функций 
Определение: Функция, у которой полином Жсгалкина имеет вид 

Bee функции от одной переменной линейны. Также линейными являются функции эквивалентность и сумма по модулю 2.
Замкнутые классы. Монотонные функции
Определение: Множество 


Всякая система 




Пример 3.
а) Множество всех дизъюнкций, то есть функций вида 
б) Множество всех линейных функций является замкнутым классом, так как подстановка формул вида 
Важнейшим примером замкнутого класса является класс монотонных функций, который будет рассмотрен далее.
Ранее рассматривалось отношение частичного порядка 




Определение: Функция 



Пример 4.
а) Функция 
б) Дизъюнкция и конъюнкция любого числа переменных являются монотонными функциями.
в) Рассмотрим две функции от трёх переменных, заданных следующей таблицей.
Функция 



Проверка монотонности функции непосредственно по определению требует анализа таблицы функции и может оказаться достаточно трудоёмкой. Поэтому весьма полезной для установления монотонности является следующая теорема. Всякая булева формула, не содержащая отрицаний, представляет собой монотонную функцию отличную от константы; наоборот, для любой монотонной функции, отличной от 0 и 1, найдётся представляющая её булева формула без отрицаний.
Теорема 11.3. Всякая булева формула, не содержащая отрицаний, представляет собой монотонную функцию отличную от константы; наоборот, для любой монотонной функции, отличной от 0 и 1, найдётся представляющая её булева формула без отрицаний.
Из данной теоремы и того очевидного факта, что подстановка нескольких формул без отрицаний в формулу без отрицаний снова даёт формулу без отрицаний, вытекает следующая теорема.
Теорема 11.4. Множество всех монотонных функций является замкнутым классом.
Но поскольку всякая булева формула без отрицаний является суперпозицией дизъюнкций и конъюнкций, из данной теоремы непосредственно получаем следствие.
Следствие. Класс монотонных функций является замыканием системы функций
Теоремы о функциональной полноте
Теперь перейдём к рассмотрению основного вопроса, поставленного в рамках данной лекции: каковы необходимые и достаточные условия функциональной полноты для произвольной системы функций 


Лемма 1 (о немонотонных функциях). Если функция 
Практически данная лемма является утверждением, противоположным теореме, обратной к теореме 11.3. Смысл её заключается в том, что для функции

Лемма 2 (о нелинейных функциях). Если функция 
Иначе говоря, существует представление дизъюнкции и конъюнкции в виде суперпозиции констант, отрицаний и нелинейной функции 
Замечание. При традиционных обозначениях переменных в выражениях вида 
Две указанные леммы позволяют получить все булевы операции с помощью немонотонных функций, нелинейных функций и констант. Это ещё не полнота в точном смысле слова, так как константы с самого начала предполагались данными. Однако такое предположение часто бывает оправданным в различных приложениях (прежде всего в синтезе логических схем). Поэтому есть смысл ввести ослабленное определение полноты.
Определение: Система функций 


Очевидно, что из обычной полноты системы следует её слабая полнота.
Теорема 11.5 (первая теорема о функциональной полноте). Для того, чтобы система функций 
1) Необходимость. Классы монотонных и линейных функций замкнуты и содержат 0 и 1. Поэтому если 

2) Достаточность. Пусть 
Пример 5.
а) Система 



Для формулировки необходимых и достаточных условий «сильной» полноты (в отличие от слабой) нужно ввести ряд определений, описывающих ещё три замкнутых класса функций.
Определение: Функция 


Оба данных класса функций являются замкнутыми, что проверяется подстановкой констант в суперпозиции. Равным образом замкнутый класс образуют самодвойственные функции 
Теорема 11.6 (вторая — основная — теорема о функциональной полноте). Для того чтобы система функций 
Язык логики предикатов
1. Предикаты.
Определение: Предикатом 




Иначе говоря, 






Для любых 













Всякой функции 






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

Пример 1.
а) Предикат 

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



в) В описаниях вычислительных процедур и, в частности, в языках программирования, часто встречаются указания типа «повторять цикл до тех пор, пока переменные 



Кванторы
Пусть 






Высказывание «существует такое значение 










Смысл связанных и свободных переменных в предикатах принципиально различен. Свободная переменная — это обычная переменная, которая может принимать различные значения из множества 










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

Пример 2.
а) Пусть 




б) Рассмотрим двухместный предикат 















Истинные формулы и эквивалентные соотношения
При логической (истинностной) интерпретации формул логики возможны три основные ситуации.
1. Если в области 






2. Если формула 




3. Если формула 



Определение: Формулы называются эквивалентными, если при любых подстановках одинаковых констант они принимают одинаковые значения. В частности, все тождественно истинные (и все тождественно ложные) формулы являются эквивалентными.
Отмстим, что если формулы 


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








Аналогично доказывается истинность соотношения 
1) Дистрибутивность квантора 
2) Дистрибутивность квантора 3 относительно дизъюнкции:
Если же кванторы 

3) 

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




Пусть 

5)
6)
7)

Эти соотношения означают, что формулу, не содержащую переменной 
Доказательства в логике предикатов
Метод доказательства формул, содержащих переменные, путём непосредственной подстановки в них констант называется методом интерпретаций или методом моделей. Подстановка констант позволяет интерпретировать формулу как осмысленное утверждение об элементах конкретного множества. Поэтому такой метод, выясняющий истинность формулы путём обращения к её возможному смыслу называется семантическим (смысловым). Метод интерпретаций удобен для доказательства выполнимости формул или их неэквивалентности, поскольку и в том, и в другом случае достаточно найти одну подходящую подстановку. Он удобен также для исследования истинности формул на конечных областях. Дело в том, что если область 
Заменяя все кванторы по этим соотношениям, любую формулу логики предикатов можно перевести в формулу, состоящую из предикатов, соединённых логическими операциями. Истинность такой формулы на конечной области проверятся конечным числом подстановок и вычислений. Методы рассуждений, использующие только конечные множества конечных объектов, называются финитными.
Для бесконечных же областей, в общем случае, при доказательстве тождественной истинности формул метод интерпретации связан с большими трудностями. Поэтому для построения множества истинных формул в логике предикатов выбирается иной путь. Это множество порождается из неких исходных формул (аксиом) с помощью формальных процедур — правил вывода. Используются лишь формальные (а не содержательные), внешние свойства последовательности символов, образующих формулы, причём эти свойства полностью описываются правилами вывода. Множества, порождённые таким формальным методом, называются формальными.
Комбинаторика
В этой лекции даются основные начальные сведения из комбинаторики. Это служебный раздел математики, занимающийся исследованием различных комбинаций элементов всевозможных множеств. Формулы комбинаторики широко используются теории вероятностей, в теории вычислительных машин, в некоторых разделах экономике, в статистике и других прикладных дисциплинах.
Правила суммы и произведения
Будем в дальнейшем оперировать только с множествами, содержащими конечное число элементов. На бесконечные множества все нижеприведённые правила и формулы не распространяются.
Теорема 13.1. Пусть даны непересекающиеся конечные множества 

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







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




Теорема 13.2. Число элементов в декартовом произведении множеств 
Как и в предыдущем случае, сформулируем данную теорему упрощенным образом для двух множеств. Если элемент 








Оба сформулированных правила верны для любого конечного числа конечных множеств, и, в соответствующей форме, называются обобщёнными.
Пример 1.
а) В некоторой средней школе имеется три пятых класса, в которых обучаются соответственно 28, 31 и 26 учащихся. Требуется одного из них выбрать для участия в совете школы. Сколькими способами можно сделать выбор?
По правилу суммы получаем 28 + 31 + 26 = 85.
б) В секции фигурного катания занимаются 14 мальчиков и 18 девочек. Сколькими различными способами из детей, занимающихся в секции, можно образовать спортивные па-
По правилу произведения получаем 14 -18 = 252.
Размещения
Определение: Любой вектор длины 







Пример 2. Куплено различных 12 книг. На полке можно поставить в ряд ровно 6 книг. Сколькими различными способами можно это сделать?
Будем считать различными не только те случаи, когда берутся разные книги, но и когда они по-разному расставлены на полке (в различном порядке). Тогда речь идёт о перестановках по 6 из 12. Получаем: 
Рассмотрим существенно другой случай, а именно когда элементы множества 
Определение: Любой вектор длины 









Пример 3. Сколько различных комбинаций может получиться при одновременном бросании трёх игральных костей?
Каждая игральная кость представляет собой кубик, на гранях которого нанесено от одного до 6 очков. При каждом бросании мы будем получать наборы вида 

Замечание. Очевидно, что размещения без повторений являются частным случаем размещений с повторениями.
Перестановки
Определение: Любой вектор длины 






Из определения и формулы видно, что перестановки без повторений есть частный случай размещений без повторений, при условии 
Пример №44
Сколькими различными способами можно расставить на полке 10 различных книг?
Здесь, в отличие от примера 2, значение имеет только порядок расставляемых книг. Поэтому речь идёт о перестановках из 10 элементов. Получаем: 






Положив в последней формуле 
Пример №45
Сколько различных шестизначных чисел могут быть записано с помощью цифр 1, 2, 2, 2, 3, 3?
Имеется набор из шести цифр, в котором цифра 2 повторяется трижды и цифра 3 -дважды. Полученные числа будут представлять собой перестановки с повторениями из 6 элементов. Получаем:
Сочетания. Бином Ньютона
Прежде всего, отметим одно существенное отличие перестановок от размещений. Если в размещениях векторы различаются и по составу элементов, и по их расположению (порядку) в наборе, то в перестановках векторы различаются только по расположению элементов. Естественно рассмотреть случай, когда векторы, наоборот, будут различаться только по составу элементов.
Определение: Любые различные векторы длины 




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

Замечание 1. Сочетания являются частным случаем размещений. Разница между сочетаниями и размещениями из определения неочевидна, но на конкретных примерах её легко видеть. Так, например, векторы (1,2,3) и (3,2,1) являются различными размещениями, но обозначают одно и то же сочетание.
Замечание 2. Для сочетаний без повторений обязательно требование 

Пример 6.
а) В отделе работают 10 сотрудников. Требуется отобрать трёх из них для того, чтобы направить в командировку. Сколькими способами можно это сделать?
Поскольку имеет значение только то, какие именно сотрудники отобраны, то речь идёт о сочетаниях без повторений по 3 элемента из 10. Получаем:
б) В цветочном магазине имеются в продаже 5 различных видов цветов. Покупателю требуется составить букет из 7 цветов. Сколькими способами можно это сделать?
Будем считать различными те букеты, которые отличаются друг от друга по подбору цветов. Поскольку цветы в букете могут повторяться, то речь идёт о сочетаниях с повторениями по 7 элементов из 5. Тогда получим
Одним из наиболее известных примеров использования комбинаторных формул является так называемый бином Ньютона. В общем виде формула бинома (двучлена) Ньютона выглядит так:
С частными случаями применения этой формулы ( для случаев 

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


При этом элементы множества 

Определение: Если вершина 



В множестве 



Множество 

Псевдограф без петель называется мультиграфом.
Если в наборе 
Ниже, на рисунке 1.1 изображен граф, на рисунке 1.2 мультиграф, на рисунке 1.4 -псевдограф.
Графу соответствует геометрическая конфигурация. Вершины обозначаются точками (кружочками), а ребра — линиями, соединяющими соответствующие вершины. На рисунке 1 изображены некоторые неориентированные графы.
Рисунок 1.
Замечание 1. Слово «линия», которое мы используем, подразумевает несущественность того, какая конкретно линия используется для соединения двух вершин графа, то есть её геометрические характеристики не имеют значения.
Замечание 2. Граф можно определить, также как совокупность двух множеств 



Определение: Если 


Определение: Если пары в наборе 
Если пишут 



Определение: Вершины 


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


Отношение инцидентности можно определить матрицей 

Столбцы этой матрицы будут соответствовать вершинам графа, а строки — его рёбрам. Если ребро 



Пример №46
Составить матрицу инцидентности неориентированного графа, изображённого на рисунке 3.
Рисунок 3.
Строим матрицу инцидентности в виде таблицы:
Для ориентированного графа матрица инцидентности составляется иначе. Это матрица 

Если вершина 










Пример №47
Построить матрицу инцидентности для графа, изображённого на рисунке 4.
Строим матрицу инцидентности в виде таблицы:
Ещё проще задавать граф с помощью таблицы рёбер. Она состоит из двух столбцов; в левых содержатся названия рёбер, а в правых — инцидентные им вершины (для ориентированных графов обязательно сначала указывается начало ребра, потом конец). Ниже приведены таблицы рёбер для графов из примеров 1 и 2.
Для примера 1:
Для примера 2:

Очевидно, по списку ребер можно построить его таблицу инцидентности. Действительно, каждая строка этого списка соответствует строке матрицы с тем же номером; аналогично можно выполнить обратную процедуру.
Ещё одним способом представления графа является построение для него матрицы смежности. Это квадратная матрица 





Матрица смежности неориентированного графа обязательно симметрична. Размерность матрицы указывает на количество вершин, а число рёбер равно половине единиц, имеющихся в матрице.
Матрица смежности ориентированного графа отличается только тем, что 
и только в том случае, когда в паре смежных вершин 



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

Перенумерация вершин графа задаётся строкой 




Маршруты, цепи и циклы
Основные определения
Пусть 



Определение: Маршрутом (путем) для графа 

Любой отрезок конечного или бесконечного маршрута 



Заметим, что одно и то же ребро может встречаться не один раз. Вершина 


Рисунок 1.
Рассмотрим случай, когда 
Определение: Незамкнутый маршрут (путь) называется цепью. Цепь, в которой все вершины попарно различны, называется простой цепью.
В простой цепи любая вершина маршрута инцидентна не более чем двум его рёбрам.
Определение: Замкнутый маршрут (путь) называется циклическим маршрутом или циклом (контуром). Цикл, в котором все вершины попарно различны, называется простым циклом.
Иначе говоря, простой цикл — это циклический маршрут, в котором любые два соседние ребра имеют одну инцидентную вершину. Последовательности 


Рисунок 2.
Участок цепи или цикла является цепью; соответственно, участок простой цепи или простого цикла является простой цепью.
Связные компоненты графов
Определение: Вершины 







Очевидно, что при существовании маршрута 






Если вершина







Определение: Граф называется связным, если все его вершины связаны между собой.
Поэтому все подграфы связного графа 

Расстояния. Диаметр, радиус и центр графа. Протяжённости
Пусть 





Штрихи в обозначении используются, потому что не обязательно рёбра под одинаковыми индексами будут совпадать.
Если же и 






Определение: Минимальная длина простой цепи с началом в вершине 

Расстояние 




1) 


2)
Также для расстояния 

Это позволяет, для простоты рассуждений, измерять расстояние между вершинами по числу рёбер простой цепи, соединяющей их (тем более, что геометрические характеристики рёбер мы не учитываем).
Определение: Диаметром конечного графа 

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



Определение: Вершина 

Максимальное удаление от центра графа называется его радиусом и обозначается 
Замечание. Граф может иметь более одного центра. Например, в полном неориентированном графе, в котором две любые различные вершины соединены ребром, радиус равен единице, а любая вершина является центром.
Пусть 


Определение: Протяжённостью 
Эйлеровы графы
Определение: Цепь (цикл) в графе 

Теорема 15.1. Для того, чтобы связный граф 
Рисунок 3
Задача, которая привела к появлению понятия Эйлерова цикла, широко известна в истории математики. Это так называемая задача о кенигсбергских мостах. Расположение семи мостов в городе Кенигсбергс в начале XVIII века приведено на рисунке За. Требуется обойти город, пройдя через каждый мост ровно один раз, и вернуться в исходную точку.
Можно представить описанную задачу следующим образом. Имеется связный неориентированный граф с четырьмя вершинами и семью рёбрами. Требуется выяснить, существует ли простой цикл, позволяющий обойти данный граф по маршруту, включающему в себя по одному разу каждое ребро графа.
Именно решение данной задачи привело Л. Эйлера к доказательству приведённой выше теоремы. Кстати, согласно ей, данная задача неразрешима, поскольку степени всех вершин графа нечётны.
Теорема 15.2. Для того, чтобы связный граф 
По сути дела, теоремы 15.1 и 15.2 описывают условия, при которых можно построить геометрическую фигуру «не отрывая карандаша от бумаги», одной сплошной линией. Только в первом случае начало и конец этой линии будут совпадать, а во втором случае они будут различны.
Определение: Цикл (цепь) в графе 

Пример №48
а) 
б) 



Также необходимым условием существования гамильтонова цикла является связность графа.
Некоторые классы графов и их частей
Деревья
Определение: Связный неориентированный граф без циклов называется неориентированным деревом или просто деревом.
Из определения следует, что дерево не может содержать ни петель, ни кратных ребер.
Определение: Несвязный неориентированный граф без циклов называется лесом; связные компоненты леса являются деревьями.
Очевидно, что люба часть дерева или леса также не имеет циклов. В таком графе любая цепь является простой — в противном случае, она содержала бы цикл.
Теорема 16.1. Любые две вершины дерева связаны одной и только одной цепью. Обратно, если две любые вершины графа можно связать только одной цепью, то он является деревом.
Определение: Вершина 

Если конечное дерево состоит более чем из одной вершины, оно имеет хотя бы две концевые вершины и хотя бы одно концевое ребро.
Пусть в дереве 









В нём все рёбра имеют направление от корня (см. рисунок 1).
Рисунок 1.
Если же изменить направления всех рёбер ориентированного дерева на противоположные (к корню), то получится ориентированный граф, который называется сетью сборки. В общем случае, такой граф тоже является ориентированным деревом. В каждую вершину ориентированного дерева, за исключением корня, входит только одно ребро. Иначе говоря, эта вершина является концом только одного ребра. Отсюда прямо следует, что в конечном дереве число вершин на один превышает число рёбер.
Замечание. Любое дерево можно ориентировать, выбрав в качестве корня любую его вершину.
Пусть дано конечное дерево 
Далее удалим из дерева все вершины типа 1 и инцидентные им рёбра. Останется связный граф 


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


Определение: Цикломатическим числом конечного неориентированного графа 




Цикломатическое число дерева равно нулю. Цикломатические числа остальных конечных графов положительны.
Ориентированные графы
Понятие ориентированного графа (орграфа) было определено ранее. Сейчас рассмотрим подробнее, как выглядят в таком графе пути и циклы.
Пусть дан ориентированный граф 




Дадим определение пути в ориентированном графе. Сразу оговоримся, что это понятие можно определять различными способами; мы приводим только один.
Определение: Путь из вершин и рёбер — это такая последовательность рёбер и вершин графа 







Путь, состоящий из одной вершины, имеет нулевую длину. Каждому пути 


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


Пусть вершины конечного ориентированного графа пронумерованы от 1 до 



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






Символ 
Множества могут содержать как конечное число элементов, так и бесконечное. Например, множество всех корней уравнения 
Определение 1.1. Множество, не содержащее ни одного элемента, называется пустым и обозначается символом
Число элементов конечного множества называется его мощностью. Если множество 




Замечание 1.1. Элементами множества могут быть множества. Например, можно говорить о множестве групп некоторого факультета университета.
Элементы этого множества — группы, являющиеся в свою очередь множествами студентов. Но конкретный студент одной из групп уже не является элементом множества групп факультета.
Определение 1.2. Множество, элементами которого являются другие множества, называется семейством (классом).
Определение 1.3. Если все элементы данной совокупности множеств принадлежат некоторому одному множеству, то такое множество называется универсальным множеством, или универсумом, и обозначается
Множество считают заданным, если о любом объекте можно сказать, принадлежит он этому множеству или не принадлежит. Множество можно задать следующими способами.
- перечислением всех его элементов (списком);
- характеристическим свойством элементов множества;
- порождающей процедурой.
Первый способ задания множеств применим только для конечных множеств, да и то при условии, что число элементов множества невелико. Если 



Замечание 1.2. Порядок перечисления элементов множества не имеет значения. Так, множества 
Вторым способом можно задавать как конечные, так и бесконечные множества. Характеристическое свойство — это такое свойство, которым обладает каждый элемент, принадлежащий множеству, и не обладает ни один элемент, который ему не принадлежит. Обозначив символом 

Порождающая процедура описывает способ получения элементов нового множества из уже полученных элементов или из других объектов. Тогда элементами множества считаются все объекты, которые могут быть получены с помощью этой процедуры. С помощью порождающей процедуры можно задавать множества, содержащие любое число элементов.
Пример 1.1.
Определим различными способами множество 
- порождающая процедура определяется правилами:
Подмножества
Определение 1.4. Множество 


Пример 1.2.
Пусть 



Если множество 






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




Определение 1.5. Множества 

Справедливо следующее утверждение, которое также можно рассматривать в качестве определения равных множеств.
Утверждение 1.1.
Замечание 1.3. Из утверждения 1.1 вытекает способ доказательства равенства двух множеств: если доказать, что каждый элемент из множества 



Говорят, что множество 






Пример 1.3.
Имеют место следующие строгие включения числовых множеств:
Определение 1.6. Множество всех подмножеств множества 
Пример 1.4.
Если 
Операции над множествами
Определим операции над множествами, с помощью которых можно получать из любых имеющихся двух множеств новые множества.
Определение 1.7. Объединением (суммой) 


Таким образом, по определению,
Заметим, что в объединение двух множеств 





Определение 1.8. Пересечением (произведением) 


Таким образом, по определению,
Замечание 1.4. Если 



Из определения пересечения следует, что
Определение 1.9. Разностью 

Таким образом, по определению,
Замечание 1.5. Если 

Определим, опираясь на определения 1.7-1.9, операции симметрической разности и дополнения множества.
Определение 1.10. Симметрической разностью (кольцевой суммой) 



Таким образом, по определению,
Определение 1.11. Дополнением 



Таким образом, по определению,
Пример 1.5.
Пусть 
Решение:
Введем некоторые обобщения вышеприведенных определений. Пусть 



Если 

Определение 1.12. Пусть 





Таким образом, 
Пример 1.6.
Пусть 
Решение:
Семейства 


Определение 1.13. Покрытие 


Таким образом, 
Пример 1.7.
Пусть 
Решение:
Среди перечисленных семейств только 





Рассмотрим основные, наиболее важные свойства операций объединения, пересечения и дополнения над множествами.
Свойства операций над множествами
Пусть задан универсум 

1. идемпотентность:


2. коммунативность:


3. ассоциативность:


4.дистрибутивность:




5. поглощение:
6.свойства нуля:
7. свойства единицы: 



Доказательство. Справедливость каждого из этих свойств можно доказать, используя утверждение 1.1 и замечание 1.3.
В качестве примера приведем доказательство дистрибутивности объединения относительно пересечения:
Пусть
Надо доказать, что множества 




В случае 





Предложим теперь, что 

При этом если 




Из 
Диаграммы Эйлера — Венна
Для графического (наглядного) изображения множеств и их свойств используются диаграммы Эйлера — Венна (Леонард Эйлер (1707-1783) — швейцарский математик, механик и физик; Джон Венн (1834 — 1923) — английский логик). На них множество отождествляется с множеством точек на плоскости, лежащих внутри некоторых замкнутых кривых, например окружностей (так называемые круги Эйлера). В частности, универсальное множество 
Проиллюстрируем с помощью диаграмм Эйлера — Венна введенные определения. На рисунках 1.1 — 1.5 результат выполнения операции выделен штриховкой.
Прямое произведение множеств
При задании некоторого конечного множества списком его элементов порядок указания элементов этого множества не имеет значения. Например, множества 


Введем новое исходное понятие — понятие упорядоченной пары 


Определение 1.14. Упорядоченные пары 
В частности, 

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





Определение 1.15. Два кортежа 

Введем еще одну операцию над множествами.
Определение 1.16. Прямым {декартовым) произведением



Таким образом, по определению,
В частности, если
Пример 1.8.
Пусть 
Если 






Рассмотрим геометрическую интерпретацию прямого произведения двух числовых множеств 



Пример 1.9.
Изобразить на координатной плоскости 
Решение:
Пример 1.10.
Определить, прямое произведение каких множеств 
Решение:
Метод математической индукции
Метод математической индукции используется для доказательства утверждений, в формулировке которых участвует натуральный параметр 






Запись принципа математической индукции в символической форме выглядит так:
Для доказательства утверждений методом математической индукции используется схема рассуждений, состоящая из следующих этапов:
- База индукции. Доказывается истинность утверждения
для
(обычно это удается сделать непосредственной проверкой).
- Индуктивное предположение. Допускается, что утверждение
верно для всех
- Индукционный переход. Исходя из индуктивного предположения, доказывается истинность
- Вывод. На основании первых трех этапов и принципа математической индукции делается вывод о справедливости утверждения для любого
Замечание 1.6. Если требуется доказать утверждение 
Замечание 1.7. Иногда бывает нужно доказать справедливость некоторого утверждения 



Замечание 1.8. С помощью принципа математической индукции можно давать индукционные определения. При этом для определения понятия 




Пример 1.11.
Доказать, что для любого натурального числа 
Доказательство. Обозначим через 

Докажем истинность данного равенства методом математической индукции.
1. База индукции. Проверим истинность равенства при

2. Индуктивное предположение. Предположим истинность равенства при
3. Индукционный переход. Докажем истинность равенства при

Так как в силу индуктивного предположения 

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

Получили, что из истинности равенства при 
4. На основании пунктов 1 — 3, приведенных выше, и принципа математической индукции следует, что данное равенство истинно для любого
Соответствия
Определение 1.17. Соответствием между множествами 

Если 


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


Пример 1.12.
Пусть 


На рис. 1.7 представлен граф соответствия
Определение 1.18. Множество всех первых элементов упорядоченных пар, входящих в соответствие 
Здесь и далее знак 
Определение 1.19. Множество всех вторых элементов упорядоченных пар, входящих в соответствие 
Пример 1.13.
Найдем область определения и область значений соответствия 
Определение 1.20. Если 


Определение 1.21. Если 

Пример 1.14.
На рис. 1.7 изображен граф частичного соответствия 



Определение 1.22. Множество всех 



Определение 1.23. Множество всех 



Определение 1.24. Если 



Определение 1.25. Если 



Пример 1.15.
Рассмотрим соответствие 

Определение 1.26. Соответствие 

Определение 1.27. Соответствие 

Определение 1.28. Соответствие 

Другими словами, соответствие между 



Пример 1.16.
На рис. 1.7 — 1.10 изображены графы соответствий 









Утверждение 1.2. Если между конечными множествами 
Доказательство. Предположим противное. Пусть 
Если 


Если 


Замечание 1.9. На основании утверждения 1.2 можно выполнить следующие действия:
- установить равенство мощностей двух множеств, не вычисляя этих мощностей;
- вычислить мощность множества, установив его взаимно однозначное соответствие с множеством, мощность которого известна или легко вычисляется.
Задачи, связанные с определением мощности конечного множества
Теорема 1.1. Если 

Доказательство. Пусть 
- База индукции. Если
Следовательно,
- Индуктивное предположение. Пусть для любого множества
мощности
теорема справедлива, то есть
- Индукционный переход. Докажем справедливость теоремы для
Рассмотрим
Положим
и
Имеем:
Между элементами множеств
можно установить следующее взаимно однозначное соответствие: каждому элементу
множества
сопоставить элемент
множества
Тогда, по утверждению 1.2,
Так как
то, по индукционному предположению,
и
Следовательно, теорема верна для любых
Теорема 1.2. Пусть 



- База индукции. Очевидно, что для
теорема верна.
- Индуктивное предположение. Пусть теорема справедлива для
- Индукционный переход. Докажем справедливость теоремы для
Возьмем произвольный кортеж 













Следствие.
Поставим задачу подсчитать мощность объединения 
Пусть 




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

где
По индуктивному предположению, имеем:
Из (3), учитывая (4) и (5), получаем формулу (2).
Формула (2) называется формулой включений и исключений. Ее частный случай при 
Следствие. Пусть 


Доказательство. Рассмотрим множества 
Тогда согласно формуле (1)
и, следовательно,
Подставляя (2) в (8), получаем формулу (7).
Пример 1.17.
Студенты третьего курса, изучающие информационные технологии в университете, могут изучать и дополнительные дисциплины по выбору. В этом году 30 из них выбрали дисциплину «Информационные технологии моделирования интерьера», 35 предпочли дисциплину «Информационные технологии в рекламе», а 20 решили изучать дисциплину «Информационные технологии моделирования ландшафта». Кроме того, 15 студентов изъявили желание посещать «Информационные технологии моделирования интерьера» и «Информационные технологии в рекламе», 7 — «Информационные технологии в рекламе» и «Информационные технологии моделирования ландшафта», 10 — «Информационные технологии моделирования интерьера» и «Информационные технологии моделирования ландшафта», 3 — все три дисциплины. Сколько студентов выбрали по крайней мере одну дополнительную дисциплину? Сколько из них предпочли только дисциплину «Информационные технологии в рекламе»?
Решение:
Пусть 



На основании формулы (6), имеем:
Используя последовательно формулы (8) и (1), получаем:
Таким образом, 56 студентов выбрали по крайней мере одну дополнительную дисциплину и 16 — только дисциплину «Информационные технологии в рекламе».
Комбинаторика
Комбинаторика – раздел дискретной математики, который посвящен решению задач пересчета и перечисления элементов множества (обычно конечного), обладающих заданным набором свойств.
Если требуется найти число элементов, принадлежащих данному множеству и обладающих заданными свойствами, то это задача пересчета. Если необходимо выделить все элементы множества, удовлетворяющие заданным свойствам, то это задача перечисления.
Решение многих комбинаторных задач основано на следующих двух правилах.
Правила суммы и произведения
Пусть 






В комбинаторике этот факт называется правилом суммы. Для 







Другим часто применяемым в комбинаторике правилом является правило произведения. Сформулируем и докажем частный случай этого правила для кортежа длины 2: «Если объект 




Доказательство. Пусть 




















Правило произведения в общем случае доказывается методом математической индукции.
Пример 2.1.
В одной группе учится 25 человек, в другой — 20. Сколькими способами можно выбрать на конференцию:
а) одного делегата от двух групп;
б) по одному делегату от каждой группы?
Решение:
Начальный этап решения обеих задач состоит в выборе делегата от первой группы, следующий этап — определение представителя второй группы. В задании под буквой а) существенным является то, что оба действия не могут быть выполнены одновременно, поскольку они взаимно исключают друг друга. Должен быть выполнен либо первый этап, либо второй. Рассуждения соответствуют правилу сложения, по которому получают 20 + 25 = 45 способов. Аналогично, для решения задания под буквой б) необходимо применить правило произведения, согласно которому выбрать по одному делегату от каждой группы можно 
Размещения и сочетания
Определение 2.1. Набор элементов 



Определение 2.2. Выборка называется упорядоченной, если в ней задан порядок следования элементов.
Таким образом, упорядоченная 



Определение 2.3. Выборка называется неупорядоченной, если порядок следования элементов в ней не является существенным.
Две различные неупорядоченные 
В выборках могут допускаться или не допускаться повторения элементов.
Определение 2.4. Упорядоченная 

Определение 2.5. Упорядоченная 

Определение 2.6. Перестановкой без повторений из 



Определение 2.7. Неупорядоченная 

Определение 2.8. Неупорядоченная 

Заметим, что любое 


Пример 2.2.
Пусть 
Число 





Утверждение 2.1.
Доказательство. Каждое 


Соглашение. В дальнейшем для общности формул условимся считать, что
Утверждение 2.2.
Доказательство. Случай 









Следствие.
Утверждение 2.3.
Доказательство. Случай 












Доказательство. Каждому 



























Пример 2.3.
Пусть 


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


Определение 2.9. Пусть имеется 



Если число элементов в каждой группе равно соответственно
то есть 

Утверждение 2.5
Доказательство. Согласно правилу произведения число перемещений элементов, не меняющих данную перестановку равно 


Рассмотренный в параграфах 2.1 и 2.2 теоретический материал можно представить в виде схемы, использование которой может быть полезно при решении задач (рис. 2.1).
Примеры решения задач:
Пример 2.4.
Бросают две игральные кости (с шестью гранями каждая). Сколькими способами они могут упасть так, что либо на каждой грани выпадет четное число очков, либо на каждой грани выпадет нечетное число очков?
Решение:
Пусть 







Пример 2.5.
Сколькими способами три награды (за первое, второе и третье места) могут быть распределены между 10 участниками соревнований?
Решение:
Требуется найти число способов, сколькими из 10 человек можно выбрать троих, без повторений, так как один человек не может занимать сразу два призовых места. Разные варианты искомых выборок могут быть одинаковыми по составу, но отличаться лишь порядком следования элементов или, иначе говоря, способом распределения призовых мест между выбранными тремя участниками. Задача сводится к нахождению числа всех (10, 3)-размещений без повторений. Следовательно, три награды могут быть распределены между 10 участниками соревнований 
Пример 2.6.
Имеется 10 различных книг. Сколькими способами их можно расставить на полке?
Решение:
Расстановке подлежат все имеющиеся 10 книг, и вариант от варианта отличается только порядком следования книг на полке. Искомое число способов равно числу всех (10, 10)-размещений без повторений или числу всех
перестановок без повторений из 10 элементов. Получаем: 
Пример 2.7.
Сколько двузначных чисел можно составить, используя цифры 7, 4 и 5?
Решение:
Порядок следования цифр в числе важен. Например, 47 и 74 -две различные выборки, удовлетворяющие условию задачи. Кроме этого, комбинация, например, 77 также является одним из решений. Значит, речь идет о размещениях с повторениями из трех по два. Следовательно, количество чисел равно
Пример 2.8.
Сколькими способами можно вытянуть 5 карт трефовой масти из стандартной колоды, содержащей 52 карты?
Решение:
Всего в колоде 13 карт трефовой масти. Из этих 13 карт надо выбрать 5, причем без повторений и учета порядка следования карт в выборке. Разные варианты должны отличаться по составу. Следовательно, требуется найти число всех (13,5)-сочетаний:
Пример 2.9.
В магазине продается 4 сорта пирожных: бизе, эклеры, песочные, наполеоны. Сколькими способами можно выбрать 7 пирожных?
Решение:
Каждая покупка — это выборка из 4 элементов по 7, причем с повторениями, так как 
Пример 2.10.
У врача 3 таблетки одного лекарства, 2 таблетки — другого и 4 таблетки — третьего. Сколькими способами он может распределить прием имеющихся таблеток по одной в день?
Решение:
Общее число таблеток 3 + 2 + 4 = 9 равно числу дней приема лекарств, то есть все таблетки входят в выборку, но присутствуют повторяющиеся неразличимые элементы — таблетки одного лекарства. Решение задачи сводится к нахождению числа всех перестановок с повторениями из 9 элементов:
Бином Ньютона
Исторически название бином Ньютона несправедливо, поскольку формулу 

Для натурального показателя 
Доказательство. Для доказательства формулы (9) применим метод математической индукции.
- База индукции. Пусть
- Индуктивное предположение. Предположим, что формула (9) верна для
- Индукционный переход. Докажем справедливость формулы (9) для
В данном случае получаем
Заменим индекс суммирования 


Выровняем пределы изменения индексов суммирования в обеих суммах. Для этого введем дополнительно 
Отсюда

Замечание 2.2. Для нецелого 
Свойства биномиальных коэффициентов. Треугольник Паскаля
Биномиальное разложение служит основой для многих комбинаторных формул. Например:
1. Пусть 



подмножеств 


2. Пусть 

Действительно,
4. В ходе доказательства формулы (9) мы получили
Тождество (10) позволяет вычислить значения 



В 




строке слева и справа от него, то для получения 
Эту таблицу называют треугольником Паскаля, по имени французского математика Блеза Паскаля, в трудах которого она встречается. Это название так же, как и бином Ньютона, исторически неточно, поскольку такую таблицу уже знал упомянутый ранее Омар Хайям.
Отношения. Отображения
Понятие отношения
Определение 3.1. 


В случае 

При 








Пусть 







В дальнейшем речь будет идти о бинарных отношениях, так как они наиболее часто встречаются и хорошо изучены. Если не будет специально оговорено, то под «отношением» будем понимать бинарное отношение. Частично бинарные отношения (соответствия) уже были рассмотрены в параграфе 1.7. Введем еще несколько определений.
Определение 3.2. Пусть 







Определение 3.3. Для любого множества 


Определение 3.4. Графиком бинарного отношения 


Определение 3.5. Пусть 




Пример 3.1.
Если 



Замечание 3.1. Матрица бинарного отношения 

Способы задания бинарных отношений
Бинарные отношения можно задать одним из перечисленных способов.
1. Списком входящих в отношение элементов (см. пример 1.12).
2. Характеристическим свойством.
Пример 3.2.
3.Графиком {только для подмножеств
Пример 3.3.
График, изображенный на рис. 3.1, задает отношение 
4. Графом. Понятие графа отношения (или графа соответствия) между двумя различными множествами было введено в параграфе 1.7. Граф, изображенный на рис. 1.7, задает отношение 








Любое бинарное отношение на конечном множестве можно представить ориентированным графом. Обратно, любой ориентированный граф представляет бинарное отношение на множестве его вершин.
Пример 3.4.
Граф, изображенный на рис. 3.2, задает отношение

5. Матрицей.
Пример 3.5.
Если 

задает отношение
Операции над бинарными отношениями
Бинарные отношения — это множества упорядоченных пар. Следовательно, над ними можно выполнять любые теоретико-множественные операции, в частности, операции объединения и пересечения. Определим еще две операции над отношениями.
Определение 3.6. Отношением 


Пример 3.6.
Пусть 
Определение 3.7. Композицией (суперпозицией) отношений 



Пример 3.7.
Если 
Утверждение 3.1. Для любых бинарных отношений 

Доказательство. Каждое из свойств 1 — 3 представляет собой равенство
двух множеств. Следовательно, доказательство можно провести на основании определений 1.5, 3.6 и 3.7.
Свойства матриц бинарных отношений
1.Пусть 

2.Пусть 

4. Пусть 
Пример 3.8.
Пусть 


Свойства бинарных отношений
Пусть
Определение 3.8. Отношение 

Примерами рефлексивных отношений являются отношение делимости на множестве целых чисел, отношение включения на булеане непустого множества.
Отношение 
Определение 3.9. Отношение 

Например, отношение неравенства на некотором числовом множестве, отношение перпендикулярности на множестве всех прямых евклидовой плоскости являются антирефлексивными.
Отношение антирефлексивно тогда и только тогда, когда ни одна вершина графа не имеет петли.
Определение 3.10. Отношение 

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

Например, отношение меньше 
Отношение антисимметрично тогда и только тогда, когда вместе с каждым ребром

Замечание 3.2. Свойство антисимметричности не совпадает со свойством несимметричности. Например, отношение 





Определение 3.12. Отношение 

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




Решение:
Изобразим графы отношений

Выясним с помощью матрицы 
1. Отношение 

2. Отношение 

3. Отношение 

Следовательно, отношение 

Отношение 
Отношение эквивалентности
Определение 3.13. Бинарное отношение на множестве 
Отношение эквивалентности обычно обозначают символами
Примерами отношения эквивалентности являются отношение равенства на множестве действительных чисел, отношение параллельности на множестве прямых евклидовой плоскости.
Определение 3.14. Пусть 


Класс эквивалентности, порожденный элементом 



Определение 3.15. Представителем класса эквивалентности называется любой элемент этого класса.
Определение 3.16. Пусть 



Теорема 3.1 (прямая). Пусть 


Доказательство. Так как отношение 























Из теоремы 3.1 непосредственно вытекает следующее следствие.
Следствие. Пусть 

Пусть 




Теорема 3.2 (обратная). Отношение 




Доказательство. 1. Так как 
Следовательно, по определению отношения 

2. Пусть 





3. Пусть 


Отсюда 




Из п. 1-3 следует, что 


Пример 3.10.
На множестве 




Решение:
Построим граф отношения 





Замечание 3.3. Частным случаем отношения эквивалентности 




В другом частном случае все элементы множества 

В любом другом случае среди классов эквивалентности имеется хотя бы один класс, который содержит больше одного элемента и в то же время не совпадает с самим множеством
Замечание 3.4. Понятие отношения эквивалентности имеет большое значение в математике. Дело в том, что элементы, входящие в один класс эквивалентности неразличимы с точки зрения рассматриваемого отношения эквивалентности. Поэтому считают, что класс эквивалентности определяется любым своим представителем (произвольным элементом этого класса). Это позволяет вместо всех элементов множества изучать совокупность представителей каждого класса эквивалентности. Свойства, которыми обладают все элементы некоторого класса эквивалентности, изучаются на одном его представителе.
Отношения эквивалентности играют важную роль в определении математических понятий.
Счетные и несчетные множества
Определение 3.17. Множества 

Утверждение 3.3. Бинарное отношение «быть изоморфными» на совокупности множеств является отношением эквивалентности.
По теореме 3.1 все множества относительно отношения «быть изоморфными» разбиваются на классы эквивалентности, каждый из которых состоит из попарно изоморфных между собой множеств.
Определение 3.18. То общее, что есть у всех множеств одного и того же класса эквивалентности по отношению «быть изоморфными» (количество элементов), называется кардинальным числом (т.е. количественным) или мощностью множеств данного класса.
Таким образом, мощность множества представляет собой обобщение понятия «число элементов» на случай произвольного (конечного или бесконечного) множества. Как и для конечного множества, мощность бесконечного множества 
Определение 3.19. Множества 
Пример 3.11.
Пусть 



Пример 3.12.
Пусть 





В теории конечных множеств имеет место утверждение: «часть меньше целого».
Пример 3.13.
Между конечным множеством и его собственным подмножеством нельзя установить взаимно-однозначное соответствие.
Определение 3.20. Множество 

В противном случае множество называется бесконечным.
Определение 3.21. Множество 

Пример 3.14.
Рассмотрим 





Таким образом, в теории бесконечных множеств теряет силу утверждение, что «часть меньше целого».
Определение 3.22. Кардинальное число называется конечным, если оно является мощностью конечного множества.
Определение 3.23. Кардинальное число называется бесконечным, если оно является мощностью бесконечного множества.
Определение 3.24. Конечные ненулевые кардинальные числа называются натуральными числами.
Другими словами, натуральное число — это общее свойство класса конечных непустых равномощных множеств.
Наименьшей бесконечной мощностью является 
Определение 3.25. Множества, равномощные множеству натуральных чисел, называют счетными.
Другими словами, множество является счетным, если его элементы можно перенумеровать. Мощность любого счетного множества равна
Пример 3.15.
Множество 
Запишем множество 
Таким образом, все положительные числа и нуль нумеруются нечетными числами, а все отрицательные целые числа — четными.
Пример 3.16.
Множество 
Перенумеруем сначала все положительные рациональные числа. Для этого выпишем в виде таблицы сначала все положительные дроби со 5 знаменателем 1, потом все положительные дроби со знаменателем 2, далее со знаменателем 3 и т.д. Нумерацию будем проводить по квадратам. При этом если некоторая дробь занумерована, то последующие дроби, выражающие то же число, будем пропускать. Получим следующую нумерацию:
После того как занумерованы все положительные рациональные числа, все рациональные числа нумеруются аналогично целым числам. Для этого надо перенумерованные положительные и отрицательные рациональные числа записать отдельно в виде двух строк, и числа одной строки нумеровать четными номерами, а второй — нечетными, оставив еще один номер для нуля.
Теорема 3.3 (Кантора). Множество всех действительных чисел несчетно.
Доказательство. Предположим противное. Пусть все действительные числа занумерованы: 

В равенствах 

Выберем цифру 






Мощность множества всех действительных чисел 


На множестве кардинальных чисел введем отношение 




Известно, что мощность 
Есть ли между 

Рассмотрим без доказательства несколько теорем, относящиеся к теории бесконечных множеств.
Теорема 3.4. Всякое подмножество счетного множества конечно или счетно.
Теорема 3.5. Объединение счетного числа счетных множеств счетно.
Теорема 3.6. Всякое бесконечное множество 


Теорема 3.7. Всякое бесконечное множество 


Теорема 3.8. (Кантора — Бернштейна). Если каждое из двух множеств 


Замечание 3.5. Сергей Натанович Бернштейн (1880 — 1966) — советский математик.
Теорема 3.9. Для произвольного множества 

Теорема 3.10. Булеан 


Отношение порядка. Диаграммы Хассе
Пусть 
Определение 3.26. Отношение 
Пример 3.17.
Пусть 


Заметим, что симметричный предпорядок является отношением эквивалентности.
Определение 3.27. Отношение 


Определение 3.28. Отношение 
Отношение строгого порядка не является частичным порядком, так как оно не рефлексивно.
Пример 3.18.
Отношение из примера 3.17 не является частичным порядком, а отношение делимости на множестве целых чисел — является.
Определение 3.29. Пусть 

Пример 3.19.
Пусть 



Определение 3.30. Частичный порядок 
Определение 3.31. Пусть 


Другими словами, частично (линейно) упорядоченным множеством является непустое множество 
Пример 3.20.
Пара 



Определение 3.32. Элемент 

Определение 3.33. Элемент 

Наибольший (наименьший) элемент частично упорядоченного множества


Теорема 3.11. Пусть 



Пример 3.21.
Частично упорядоченное множество 




Пример 3.22.
Частично упорядоченное множество 



Определение 3.34. Пусть 



Пример 3.23.
Рассмотрим частично упорядоченное множество 




Определение 3.35. Пусть 


Точная верхняя грань подмножества 


Пример 3.24.
В условиях примера 3.21 имеем, что
Определение 3.36. Линейный порядок 


Определение 3.37. Пусть 


Пример 3.25.
Упорядоченная пара 



Пусть 












Пример 3.26.
Диаграммы Хассе частично упорядоченных множеств 

Пример 3.27.
а) Рассмотрим частично упорядоченное множество



Функции
Определение 3.38. Соответствие 




Таким образом, соответствие 














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


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






Функции называются также отображениями. Пусть 








Определение 3.39. Функция 
Определение 3.40. Функция 


Заметим, что сюръективная функция 

Определение 3.41. Функция 

Пример 3.29.
Какие из соответствий, графы которых изображены на рис. 3.13, являются инъективными, сюръективными, биективными функциями?
Решение:
Функции 


Определение 3.42. Если соответствие, обратное к функции 

Так как в обратном соответствии образы и прообразы меняются местами, то для существования функции, обратной к функции 


Утверждение 3.4. Для функции 


Определение 3.43. Пусть даны функции 


Композиция функций 


Алгебраические структуры
Алгебраические операции и их свойства
Бинарные и 
Пусть 
Определение 4.1. Отображение множества 
Примерами бинарных алгебраических операций являются обычное сложение и умножение на множестве целых чисел, объединение и пересечение на булеане непустого множества.
Определение 4.2. Отображение множества 






Определение 4.3. Частичная функция из множества 

Пример 4.1.
1. Пусть 


2. Операция деления рациональных чисел является частичной бинарной алгебраической операцией на множестве рациональных чисел.
3. Операция, ставящая в соответствие каждому кортежу натуральных чисел длины 

Для обозначения 






Свойства бинарных алгебраических операций
Пусть 
Определение 4.4. Бинарная алгебраическая операция 
Определение 4.5. Бинарная алгебраическая операция 
Если операция 

Определение 4.6. Бинарная алгебраическая операция 

Пример 4.2.
1. Сложение и умножение действительных чисел являются коммутативными и ассоциативными бинарными алгебраическими операциями. Умножение действительных чисел дистрибутивно относительно сложения, но сложение не дистрибутивно относительно умножения, так как условие 
2. Операции объединения и пересечения подмножеств непустого множества 
3. Композиция функций есть ассоциативная бинарная алгебраическая операция. Композиция функций не коммутативна, так как условие

Нейтральные элементы
Пусть 
Определение 4.7. Элемент 

Теорема 4.1. Если нейтральный элемент относительно операции 
Доказательство. Пусть 

Пример 4.3.
1. Число 0 есть нейтральный элемент относительно сложения действительных чисел. Число 1 есть нейтральный элемент относительно умножения действительных чисел.
2. На булеане 

Симметричные элементы
Пусть 


Определение 4.8. Элемент 





Пример 4.4.
1. Любое целое число имеет симметричный к нему элемент относительно сложения — то же число, взятое со знаком минус.
2. Любое ненулевое действительное число 

Теорема 4.2. Если операция 

Доказательство. Пусть 




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


Пустое множество замкнуто относительно любой операции
Пример 4.5.
Сложение и вычитание являются бинарными алгебраическими операциями на множестве всех действительных чисел. Множество всех положительных действительных чисел замкнуто относительно сложения, но не замкнуто относительно вычитания.
Аддитивная и мультипликативная форма записи бинарной алгебраической операции
Для обозначения бинарной алгебраической операции 





Элемент, симметричный к элементу 

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






Понятие алгебраической структуры
Определение 4.10. Алгебраической структурой (универсальной алгеброй или просто алгеброй) называется упорядоченная пара 

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






Если 

Наиболее частым является случай, когда сигнатура конечна. Если
то вместо записи 
Замечание 4.1. Для обозначения алгебры везде, где это необходимо, используется рукописная прописная буква латинского алфавита, а для обозначения ее носителя — соответствующая печатная прописная буква.
Определение 4.11. Алгебры 

Пример 4.6.
1. Пусть 

2. Пусть 



Определение 4.12. Пусть алгебры 











Определение 4.13. Пусть 









Если 

Из определений 4.12 и 4.13 непосредственно вытекает следующая теорема.
Теорема 4.3. Пусть 




Пример 4.7.
Рассмотрим алгебру 







Алгебры с одной бинарной алгебраической операцией
Рассмотрим алгебры, наиболее часто используемые в теории и на практике.
Пусть 
Определение 4.14. Алгебра 
Таким образом, группоид определяется непустым множеством 

Если множество 
Определение 4.15. Пусть на конечном множестве 






Замечание 4.2. Артур Кэли (1821 — 1895) — английский математик.
Замечание 4.3. 1. Если операция 
2. Если для некоторого 




3. Пусть элемент 





Определение 4.16. Алгебра 
Пример 4.8.
Алгебра 
Определение 4.17. Алгебра 



Другими словами, моноидом является полугруппа с нейтральным элементом.
Пример 4.9.
Алгебра 
Определение 4.18. Алгебра 
— ассоциативная бинарная операция;
- существует нейтральный элемент относительно
- для каждого элемента
существует симметричный к нему элемент
относительно операции
Таким образом, группа — это моноид, в котором каждый элемент симметризуем.
Определение 4.19. Полугруппа, моноид или группа называется коммутативной (коммутативным) или абелевой (абелевым), если бинарная алгебраическая операция коммутативна.
Замечание 4.4. Нильс Абель (1802 — 1829) — норвежский математик.
Определение 4.20. Если носитель группы имеет конечную мощность, то группа называется конечной, а мощность ее носителя — порядком группы. В противном случае группа называется бесконечной.
Пример 4.10.
Полугруппы 
Пример 4.11.
Алгебра 

Пример 4.12.
Алгебра 

Пример 4.13.
Доказать, что множество 
Решение:
Покажем, что 

Действительно,


1. Докажем, что операция 
Рассмотрим левую и правую части этого равенства:
Итак, первая аксиома группы выполняется. Легко видеть, что операция 
2. Покажем, что существует нейтральный элемент относительно 
Рассмотрим равенство






3. Докажем, что для каждого элемента из 

Покажем, что 
Итак, для любого 


Алгебры с двумя бинарными алгебраическими операциями
Среди алгебр с двумя бинарными алгебраическими операциями особо выделяются кольца и поля.
Определение 4.21. Алгебра 
- алгебра
есть коммутативная аддитивная группа;
- алгебра
есть мультипликативный моноид;
- умножение дистрибутивно относительно сложения, то есть
Замечание 4.5. В дальнейшем под словом «кольцо» будем подразумевать ассоциативное кольцо с единицей.
Элементы множества 
Определение 4.22. Группа 

Определение 4.23. Моноид 


Определение 4.24. Кольцо называется коммутативным, если операция умножения коммутативна, т.е.
Пример 4.14.
Алгебра 
Определение 4.25. Полем называется коммутативное кольцо, в котором нуль кольца отличен от единицы кольца и для каждого ненулевого элемента существует обратный к нему относительно операции умножения.
Пример 4.15.
Кольцо целых чисел 
Пример 4.16.
Множества 
Пример 4.17.
Выяснить, образует ли алгебра 
Решение:
Докажем сначала, что операции сложения и умножения матриц являются бинарными алгебраическими операциями на множестве




Сложение произвольных матриц (если оно определено) коммутативно и ассоциативно. Значит, 

матрица 






Умножение произвольных матриц (если оно определено), а значит и матриц из множества 



Выполним преобразования:
Если 





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


Нуль кольца отличен от единицы кольца: 


Значит, множество 

Итак, алгебра 
Конечные поля
Наряду с бесконечными полями, существуют конечные поля, называемые полями Галуа в честь французского математика Эвариста Галуа (181 1 — 1832), который в возрасте около 20 лет создал основы современной алгебры и, в частности, открыл конечные поля. Конечные поля играют центральную роль в криптографии, в математических моделях микромира и др. Рассмотрим основные построения теории конечных полей Галуа.
Определим сначала бинарное отношение делимости на множестве
Определение 4.26. Целое число 









Предложение 

Далее рассмотрим еще одно бинарное отношение 
Определение 4.27. Целые числа 


Если целое число 


Покажем, что отношение сравнимости по модулю 


Следовательно, отношение 



По теореме 3.1 отношение эквивалентности 


1) любые два класса вычетов по модулю п либо совпадают, либо не пересекаются. Объединение всех классов вычетов по модулю п совпадает с множеством
2) пусть 


3) если 

Пример 4.18.
Пусть 
Выясним, какова мощность фактор-множества 
Утверждение 4.1. Целые числа 


Существуют 


Итак, множество целых чисел по отношению сравнимости по модулю 



Определение 4.28. Введем на множестве 
Определение операций сложения и умножения на множестве 

Алгебра 
Пример 4.19.
Рассмотрим кольцо 


Кольцо 







Следующая теорема говорит о том, что существует много конечных полей.
Теорема 4.4. Кольцо 

Булевы алгебры
Рассмотрим понятие булевой алгебры, имеющее большое число приложений в программировании и вычислительной технике. Оно возникло в трудах ирландского математика и логика Джорджа Буля (1815 — 1864) как аппарат символической логики.
Определение 4.29. Алгебра 









Замечание 4.6. Аксиома 







Бинарную операцию 




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



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





Свойства булевой алгебры
Утверждение 4.2 (принцип двойственности). Для любой теоремы булевой алгебры двойственная теорема также верна.
Теорема 4.5. Нейтральные элементы 

Теорема 4.6.
Замечание 4.7. Знак 
Теорема 4.7 (закон идемпотентности).
Теорема 4.8 (закон идентичности).
Теорема 4.9 (закон абсорбции или поглощения).
Теорема 4.10 (закон инволюции).
Теорема 4.11 (законы де Моргана).
Теорема 4.12.
Докажем, например, теорему 4.11, в частности, 


Второй закон де Моргана верен по принципу двойственности.
Гомоморфизмы алгебр
Пусть 










где 
Определение 4.31. Гомоморфизмом алгебры 







Определение 4.32. Гомоморфизм 




Определение 4.33. Гомоморфизм алгебры 

Определение 4.34. Гомоморфизм 




Определение 4.35. Алгебры 


Другими словами, отображение 




Определение 4.36. Гомоморфизм алгебры 
Определение 4.37. Изоморфизм алгебры 
На рис. 4.1 представлена схема определения частного случая гомоморфизма.
Пример 4.22.
Дано отображение
Выяснить, является ли 
Решение:
Пусть 


Преобразуя левую и правую части равенства, получим:
Из (15) и (16) следует, что 

Далее выясним, является ли отображение 
Это условие не выполняется, так как для любых
Следовательно, отображение 
Имеем, 

Таким образом, 


Пример 4.23.
Дано отображение 
Решение:
Проверим, сохраняет ли 

Преобразуя левую и правую части равенства, получим:
Из (17) и (18) следует, что 

Далее, 

Имеем: 

Значит, 

Алгебраические системы. Решетки
На непустом множестве 
Определение 4.38. Алгебраической системой называется упорядоченная пара 



Множество 

Если множество отношений 



Рассмотрим пример алгебраической системы, который широко используется в математической информатике.
Определение 4.39. Решеткой называется алгебраическая система 



Другими словами, решеткой является частично упорядоченное множество 

Замечание 4.8. Операции 
Замечание 4.9. Операции 
Замечание 4.10. Если в алгебраической системе 



Наименьший элемент решетки (если он существует) называют нулем и обозначают через 0. Наибольший элемент решетки (если он существует) называют единицей и обозначают через 1. В конечных решетках всегда имеются 0 и 1.
Пример 4.24.
Пусть 



Диаграмма Хассе частично упорядоченного множества 


Пример 4.25.
Любое линейно упорядоченное множество 


Определение 4.40. Решетка 
Пример 4.26.
Рассмотрим решетку, диаграмма Хассе которой изображена на рис. 4.3. Она не является дистрибутивной, так как 
Пример 4.27.
Решетка 
Понятие булевой алгебры является частным случаем понятия решетки.
Определение 4.41. Булевой алгеброй называется дистрибутивная решетка 


Пример 4.28.
Решетка 


Лекции по предметам:
- Математика
- Алгебра
- Линейная алгебра
- Векторная алгебра
- Геометрия
- Аналитическая геометрия
- Высшая математика
- Математический анализ
- Теория вероятностей
- Математическая статистика
- Математическая логика
Тема занятия: Графическое и матричное
представление бинарных отношений
Цель занятия:
—
закрепление
теоретических знаний, полученных по теме: «Понятие бинарных отношений. Примеры
бинарных отношений»;
—
приобретение
навыков построения бинарных отношений в виде матрицы и графа.
Основные теоретические
положения
Двуместным или
бинарным отношением на множестве А называется подмножество его квадрата RÍА2. Бинарным
отношением между множествами А и В называется подмножество RÍА´В. Будем обозначать бинарное
отношение символом R. Если упорядоченная пара (а1, а2)
принадлежит отношению R, то это обозначается следующим образом: (а1,
а2)ÎR или а1Rа2.
Областью
определения
бинарного отношения называется множество
dR={а | $b: aRb}.
Областью
значений
называется множество ρR={b | $a: aRb}.
Пример 1. Пусть дано множество А={1,
2, 3}. Определим на нем одно из возможных бинарных отношений.
Решение.
А2={(1,
1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)}.
RÍА2={(1, 2), (1,
3), (2, 3)}.
Отношение равенства на множестве натуральных чисел – это бинарное
отношение: R={(a, b) | aÎN, bÎN, a=b}.
dR=ρR=N.
Обратным
отношением для
отношения R называется отношение
R-1={(b,
a) | (a, b)ÎR}.
Таким образом, в
обратном отношении элементы всех упорядоченных пар меняются местами.
Отношения можно
задавать:
1. С использованием любого
способа задания множеств.
2. С использованием матрицы
бинарного отношения.
3. С использованием графа.
Матрицей
бинарного отношения R называется квадратная матрица R порядка n, элементы которой
задаются следующим образом:
rij =
Пример 2. Построить матрицу для
отношения R={(1,
2), (2, 3), (3, 1), (3, 2)}.
Решение.
Матрица будет
иметь вид: R=
Каждому бинарному
отношению можно поставить в соответствие граф G=(X,U), представляющий собой
совокупность множеств X и U, где Х – множество вершин графа, а U – множество
дуг, соединяющих все или некоторые из этих вершин. При этом вершины аi,
аj соединяются дугой, если (аi, аj)ÎR.
Пример 3. Построить граф для отношения R={(1, 2), (2, 3), (3, 1),
(3, 2)}.
Задания для
самостоятельной работы:
1.
Построить
матрицу и граф бинарного отношения:
а) R={(1,2), (1,3), (2,2), (2,4), (2,6),
(3,2), (3,4), (3,6), (4,1), (4,6), (5,2), (6,1), (6,4),(6,5)}
б) R={(1,3), (1,4), (2,1), (2,3), (2,5),
(3,1), (3,3), (3,5), (4,2), (4,5), (5,1), (6,2), (6,5),(6,6)}
2.
Записать
бинарное отношение, отображенное графом:
Контрольные вопросы:
1. Что называется бинарным
отношением?
2. Как определить области
значений и определения бинарного отношения?
3. Как можно задать бинарное
отношение?







,


:
.
,
,
.
,
.




все
.





































= A (закон двойного отрицания);










































































































































является счётным.






















(идемподентность);
(коммутативность);
(ассоциативность);
(поглощение).



































.
.
.
.
.


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












































































































































для
(обычно это удается сделать непосредственной проверкой).
верно для всех 











































Следовательно, 
мощности 
теорема справедлива, то есть 
Рассмотрим
Положим
и
Имеем:
Между элементами множеств
можно установить следующее взаимно однозначное соответствие: каждому элементу
множества
сопоставить элемент
множества
Тогда, по утверждению 1.2,
Так как
то, по индукционному предположению,
и
Следовательно, теорема верна для любых 

теорема верна.






формула (2) совпадает с (1).
множеств, где 
множеств. Для этого разобьем множества
на две группы:







































В данном случае получаем














































— рефлексивно 
— антирефлексивно 
— симметрично 
— антисимметрично 
— транзитивно 
— рефлексивно
главная диагональ матрицы
состоит из одних единиц.
— антирефлексивно
главная диагональ матрицы
состоит из одних нулей.
— симметрично
матрица
симметрична относительно главной диагонали.
— антисимметрично
матрица
вне главной диагонали содержит только нули.














































































































— ассоциативная бинарная операция;
существует симметричный к нему элемент
относительно операции 














есть коммутативная аддитивная группа;
есть мультипликативный моноид;

















































































