- •1. Множества и операции над ними
- •1.1. Множества. Определения, примеры. Способы задания множеств
- •Способы задания множеств
- •I. Задание множества списком
- •II. Порождающая процедура
- •III. Задание множества описанием его элементов (разрешающая процедура)
- •1.2.Операции над множествами
- •2.Векторы и прямые произведения
- •2.1. Векторы
- •2.1.Проекции векторов и векторных множеств на оси
- •3. Элементы комбинаторики
- •3.1. Правило произведения
- •3.2. Размещения без повторений
- •3.3. Размещения с повторениями
- •3.4. Перестановки без повторений
- •3.5. Перестановки с повторениями
- •3.6. Сочетания без повторений
- •3.6. Правило суммы
- •4. Соответствия
- •4.1 Определения и примеры
- •4.2. Взаимно однозначные соответствия и мощность множеств
- •4.3. Счетные множества
- •О парадоксе Кантора
- •5. Отношения
- •5.1. Определения и примеры
- •5.2. Способы задания бинарных отношений
- •5.3. Свойства отношений
- •5.4. Отношение эквивалентности
- •Классы эквивалентности
- •5.5. Отношение порядка
- •6. Элементы общей алгебры
- •6.1. Алгебры
- •6.2. Свойства бинарных алгебраических операций
- •6.3.Гомоморфизм и изоморфизм алгебр
- •7. Булева алгебра и теория множеств
- •7.1. Основные определения
2.Векторы и прямые произведения
2.1. Векторы
Определение: Вектор - это упорядоченный набор элементов (“кортеж” - размещение).
Определение: Координаты или компоненты вектора - это элементы, образующие вектор. Координаты нумеруются слева направо.
Определение: Длина (размерность) вектора - число координат вектора.
В отличие от элементов множества, его координаты могут совпадать. Обозначение вектора: в круглых скобках, координаты - через запятую (0, 5, 4, 5, 0, 1). Иногда скобки и даже запятые опускаются.
Определение: Векторы длины 2 называют упорядоченными парами;
длины 3 - тройками;
длины 4 - четверками;
длины n - n-ками.
Определение: Два вектора равны, если они имеют одинаковую длину, и соответствующие их координаты равны, т. е.
,
если m = n и
.
Определение: Прямым произведением множеств А и В (обозначается АВ) называется множество всех пар (a, b) таких, что. В частности, если А = В, то обе координаты принадлежат А (обозначим).
Аналогично:
Определение: Прямое произведение n множеств () называется множеством всех векторов , длины n таких, что .
обозначается .
Примеры:
1) Множество - множество точек плоскости, т. е. множество всех пар вида (a, b), где и является координатами точек плоскости. Координатное представление точек плоскости предложил Декарт. Это исторически первый пример прямого произведения. Поэтому иногда прямое произведение называется декартовым.
2)
.
Тогда - множество, содержащее обозначение всех 64-х клеток шахматной доски.
3) Рассмотрим множество всех числовых матриц 3 4, матриц вида:
,
где Принадлежит множеству R. Строки матрицы - элементы множества (векторы длины 4). Сама матрица рассматривается как упорядоченный набор элементов множества . Компоненты матрицы, заданной таким образом - строки, а не числа; . Содержательный смысл этого неравенства в следующем: в векторе нет никакой информации о строении матрицы; тот же вектор мог бы перечислять элементы матрицы 4 3 или 2 6, которые, как математические объекты, вовсе не совпадают с матрицей 4 3.
Итак, компонентами вектора могут быть также и векторы:
.
4) Пусть А - конечное множество, элементами которого являются символы (буквы, цифры, знаки препинания, знаки операций и т. д.). Такие множества обычно называют алфавитом.
Определение: Слова длины n в алфавите А - это элементы множества .
Определение: Множество всех слов в алфавите А - это множество
Здесь слово определено как вектор. При написании слова не принято пользоваться разделителями: скобками, запятыми; они могут оказаться символами самого алфавита. Поэтому слово в алфавите обозначается как конечная последовательность символов из алфавита А.
Примеры:
1) Десятичное число – слово в алфавите {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}.
2) Текст, отпечатанный на машинке, – слово в алфавите, определяемом клавиатурой этой машинки.
Теорема (о мощности прямого произведения множеств).
Пусть - конечные множества и
.
Тогда мощность множества равна произведению мощностей множеств :
.
Доказательство:
Докажем методом математической индукции. Для n = 1. Теорема тривиально верна. Предположим, что она верна для n = k. Докажем, что она справедлива для n = k + 1.
По предположению
.
Возьмем любой вектор из и припишем справа элемент , так как , то это можно сделать способом. При этом мы получим различных векторов из лишь из одного вектора из . Так как таких векторов в штук, то приписыванием к каждому из них справа всех по очереди элементов из получим новых векторов из , причем все они различны и других векторов в не содержится. Поэтому для n = k + 1 теорема верна и верна для любых n.
Следствие: .
Эта теорема и ее следствие лежат в основе очень многих комбинаторных фактов.