- •Раздел I. Основы теории множеств. Системы счисления. Комбинаторика
- •Глава 1. Множества, операции с ними. Алгебра множеств
- •1.1. Элементы и множества
- •1.2. Отображения, функции, предикаты
- •1.3. Метод математической индукции
- •1.4. Способы задания множеств
- •Перечисление
- •Задание с помощью логических функций (предикатов)
- •1.5. Предметные операции на множествах. Формула множества
- •1.6. Операции сравнения — логические операции с множествами
- •1.7. Алгебра множеств. Ее формулы, теоремы и законы
- •Глава 2. Мощность множеств
- •2.1. Мощность. Счетные множества
- •2.2. Множества мощности континуум
- •Глава 3. Бинарные отношения на множествах
- •3.1. Определение и способы задания отношений
- •3.1.1. Перечисление (список пар)
- •3.1.2. Матрица
- •3.1.3. Задание отношений при помощи предикатов
- •3.2. Аксиомы на отношениях
- •3.3. Основные типы отношений
- •3.3.1. Отношение эквивалентности
- •3.3.2. Отношение нестрогого (частичного) порядка
- •3.3.3. Отношение строгого порядка
- •3.4. Проверка типов отношений. Решение задач
- •Контрольные задания по теме
- •I. Общая теория множеств
- •Глава 4. Системы счисления
- •4.1. Позиционные системы счисления с постоянными основаниями. Представления целых чисел Рассмотрим общие правила представления количественных величин в позиционных системах счисления.
- •4.2. Переводы целых чисел в позиционных системах счисления
- •4.2.1. Перевод целых чисел из произвольной системы с постоянным основанием р 10 в десятичную систему
- •4.2.2. Перевод целых чисел из десятичной системы счисления в системы с произвольными постоянными основаниями p 10
- •4.2.5. Представление двоичной байтовой информации в шестнадцатеричной и десятичной системах
- •4.3. Дробные и смешанные числа в позиционных системах счисления с постоянными основаниями
- •4.3.1 Перевод правильных десятичных дробей в систему счисления с иным основанием p 10
- •4.3.2 Перевод правильных дробей из системы с основанием p 10 в десятичную систему счисления
- •4.4. Арифметические действия с целыми числами в системах с произвольными основаниями. Их компьютерное представление
- •4.4.1 Сложение
- •4.4.2 Вычитание
- •4.4.3. Прямой и дополнительный коды целых чисел. Их представление в памяти компьютера, сложение и вычитание
- •4.5. Двоичные (булевы) векторы
- •4.6. Смешанные позиционные системы счисления. Факториальная система
- •4.6.1. Перевод целых чисел из десятичной системы в смешанную с основаниями р0, р1, ... , рk
- •Глава 5. Комбинаторика
- •5.1. Основная задача комбинаторики. Характеристики комбинаторных задач
- •5.2. Основные правила подсчета чисел комбинаторных множеств
- •5.2.1. Правило сложения
- •5.2.2. Формула включений-исключений
- •5.2.3. Правило умножения
- •5.2.4. Правило учета сходства и различия
- •5.3. Размещения (размещения с повторениями)
- •5.4. Перестановки и размещения без повторений различных объектов. Упорядоченность перестановок
- •5.5. Перестановки и размещения без повторений групп одинаковых объектов
- •5.6. Сочетания
- •5.7. Понятие вероятности
- •Контрольные задания по теме
- •II. Системы счисления. Комбинаторика
3.3. Основные типы отношений
Рассмотрим наиболее употребительные типы отношений.
3.3.1. Отношение эквивалентности
Данное отношение удовлетворяет следующим трем аксиомам: 1) рефлексивности, 2) симметричности и 3) транзитивности.
Практический смысл отношения эквивалентности заключается в том, что оно разбивает множество, на котором определено, на классы.
Определение. Пусть множество Х разбито на подмножества Х1,Х2,..., Хn таким образом, что все они попарно не пересекаются и объединение их равно Х:
1) Хi = Х, (i = 1,...,n);
2) Х i Х, Х j Х , (ij) Х i Х j =.
В этом случае говорят, что произведено разбиение Х на классы Х1, ... , Хn. Элементы хi и хj множества Х эквивалентны по отношению к его разбиению, если они принадлежат одному и тому же классу Хk.
Замечание.
1. Мощность множества классов эквивалентности может быть как конечной, так и бесконечной (счетной, континуум и т.д.).
2. Смысл понятия эквивалентности в том, что с точки зрения разбиения множества Х элементы хi и хj неразличимы, если попадают в один класс. Обычно отношение эквивалентности обозначают символом « ».
Определение. Поэлементным будем называть такое разбиение множества на классы эквивалентности, где каждый класс Хi содержит ровно один элемент из Х.
Фиктивным будем называть разбиение в котором выделен один класс Х1, совпадающий со всем Х, (Х1 = Х).
Пример 1. Рассмотрим в качестве Х множество натуральных чисел N. Его можно разбить отношением эквивалентности на два непересекающихся класса, дающих в сумме все N: множество четных (делящихся на 2 без остатка) чисел N2 и множество нечетных (делящихся на 2 с остатком 1) чисел N2. При этом само множество пар отношения будет образовано: а) всеми парами четных чисел; б) всеми парами нечетных чисел. Смешанные пары (четное число с нечетным и наоборот) в него не войдут.
Данное отношение эквивалентности можно задать при помощи предиката Р(х, у) = «х - у кратно 2».
Пример 2. Х = N. Х1 = {1}, Х2 = {2, 3}, Х3 = {4, 5, 6, 7},…, Хi = {множество целых чисел от 2i-1 до 2i–1}. Выделенные множества Х1,Х2, ... не пересекаются, объединение их равно N. Следовательно, они разбивают N на классы. Их число бесконечно. Несложно показать, что { Хi }=0. Множество пар, составляющих отношение, будет следующим: {(1, 1); (2, 2); (2, 3); (3, 2); (3, 3); (4, 4); (4, 5); (4, 6); (4, 7); (5, 4); (5, 5); (5, 6)…}.
Отношение можно задать при помощи предиката, непосредственно задающего структуру классов эквивалентности: Р(х,у)= «2i-1 ≤ х, у ≤ 2i-1, i N».
Пример 3. Х = {1, 2, 3, 4, 5, 6}. Ниже приведены при помощи матриц примеры отношений, реализующих следующие разбиения Х на классы: 1) разбиение: Х1= {1,2}, Х2= {3}, Х3= {4, 5, 6}; 2) фиктивное: Х1= Х ; 3) поэлементное: Х1 = {1}, Х2 = {2}, Х3 = {3}, Х4 = {4}, Х5 = {5}, Х6 = {6}.
|
1 |
2 |
3 |
4 |
5 |
6 |
1 |
+ |
+ |
- |
- |
- |
- |
2 |
+ |
+ |
- |
- |
- |
- |
3 |
- |
- |
+ |
- |
- |
- |
4 |
- |
- |
- |
+ |
+ |
+ |
5 |
- |
- |
- |
+ |
+ |
+ |
6 |
- |
- |
- |
+ |
+ |
+ |
|
1 |
2 |
3 |
4 |
5 |
6 |
1 |
+ |
+ |
+ |
+ |
+ |
+ |
2 |
+ |
+ |
+ |
+ |
+ |
+ |
3 |
+ |
+ |
+ |
+ |
+ |
+ |
4 |
+ |
+ |
+ |
+ |
+ |
+ |
5 |
+ |
+ |
+ |
+ |
+ |
+ |
6 |
+ |
+ |
+ |
+ |
+ |
+ |
|
1 |
2 |
3 |
4 |
5 |
6 |
1 |
+ |
- |
- |
- |
- |
- |
2 |
- |
+ |
- |
- |
- |
- |
3 |
- |
- |
+ |
- |
- |
- |
4 |
- |
- |
- |
+ |
- |
- |
5 |
- |
- |
- |
- |
+ |
- |
6 |
- |
- |
- |
- |
- |
+ |