Оглавление
Введение. 3
1. Множества. Операции над множествами. Декартово произведение множеств. 4
2. Бинарные отношения. 7
2.1 Отношение эквивалентности. 8
2.2 Отношение частичного порядка. 9
Заключение. 11
Список литературы. 12
Введение
Линейная алгебра изучает математические модели объектов, процессов и зависимостей, с которыми имеют дело в технике, биологии, социологии и других областях деятельности человека. Их особенность – дискретный, как правило, конечный характер. Это ограничивает возможность использования моделей и методов классической непрерывной математики. Поэтому линейная алгебра – самостоятельное направление современной математики.
Дискретная и непрерывная математика взаимно дополняют друг друга. Понятия и методы одной часто используются в другой. Например, системы линейных уравнений как модели непрерывной математики характеризуются конечным множеством линейно независимых уравнений и при определенных условиях конечным множеством решений.
Особенность большинства задач линейной алгебры – возможность их решения полным перебором допустимых решений в силу конечного множества их вариантов. Однако с ростом размерности задачи простой перебор достаточно быстро становится бессильным. Для многих важных задач до настоящего времени не найдено эффективных алгоритмов решения. Поэтому ищут «хитрые» алгоритмы для упрощения перебора и определения пусть не точного, а хотя бы приближенного, но хорошего решения.
1. Множества. Операции над множествами. Декартово произведение множеств
Множества обычно обозначаются заглавными латинскими буквами A, B или с подстрочным индексом A1, A2, элементы множества обозначаются строчными буквами латинского алфавита a, b или с подстрочным индексом a1, a2. Принадлежность элемента x множеству A обозначается x∈ A; если элемент не принадлежит множеству, тогда пишем x∉A . Пустое множество будем обозначать ∅.
Введём следующие понятия:
-
B является подмножеством множества A , то есть B⊆A ⇔x∈B ⇒ x∈A , то есть каждый элемент x∈B обладает свойством x∈A.
-
∀A ∅ ⊆ A, то есть ∅ является подмножеством любого множества.
-
Множества A и B равны, то есть A=B , ⇔ A⊆B и B⊆A.
-
B является строгим подмножеством множества A , будем обозначать это B⊂A , ⇔ B⊆A и B≠A.
-
B является собственным подмножеством множества A ⇔ B⊂A и B≠∅.
2. Бинарные отношения
2.1 Отношение эквивалентности
Отношение эквивалентности представляет собой строгое математическое определение таких обыденных понятий как «одинаковость» или «неразличимость».
Отношение эквивалентности обозначается X~Y. Отношение эквивалентности обладает свойствами:
-
Рефлексивности: X~Y;
-
Симметричности: если X~Y, то Y~X;
-
Транзитивности: если X~Y и Y~Z, то X~Z.
Важнейшее значение эквивалентности состоит в том, что это отношение определяет признак, который допускает разбиение множества М на непересекающиеся подмножества, называемые классами эквивалентности. И наоборот: всякое разбиение множества М на непересекающиеся подмножества определяет между элементами этого множества некоторое отношение эквивалентности.
Например, отношение «проживать в одном доме», заданное в множестве жителей города, является эквивалентностью и разбивает это множество на непересекающиеся подмножества людей, являющихся соседями по дому.
Все элементы, принадлежащие некоторому классу Мi разбиения {М1, М2,..., Мn} множества М на классы эквивалентности, связаны отношением эквивалентности. Любой из этих элементов определяет данный класс и может служить его представителем или эталоном.
2.2 Отношение частичного порядка
Отношение порядка принято обозначать символом £. Запись x£y означает, что пара (x, y) принадлежит множеству А ⊂ М × М, являющемуся отношением порядка в М, причем x предшествует y (или y следует за x).
Отношение порядка обладает следующими свойствами:
-
Рефлексивности х£Х;
-
Транзитивности: если x£y, а y£z , то x£z;
-
Антисимметричности: если x£y, а y£x, то x=y.
Множество, на котором определено отношение порядка, называется упорядоченным, и говорят, что порядок введен этим отношением.
Если для любых двух элементов x и y множества М имеет место отношение x£y (или y£x), то М – совершенно (линейно) упорядоченно.
Например, множество натуральных или действительных чисел с естественным отношением порядка £ являются совершенно упорядоченными.
В общем случае может оказаться, что для некоторых пар (x, у) ни одно из соотношений x£y и y£x не имеет места. Такие элементы называются несравнимыми, а множество М называется частично упорядоченным.
Примерами частичного порядка является отношение «быть делителем», отношение включения ⊂ и т.п. Так, отношение включения на множестве подмножеств Мi некоторого универсума М рефлексивно (Мi⊂Мi), транзитивно (если Мi⊂Мj, a Мj⊂Мk, то Мi⊂Мk) и антисимметрично (из Мi⊂Мj, и Мj⊂Мi следует Мi=Мj), но среди всевозможных подмножеств имеются такие, что ни одно из соотношений из Мi⊂Мn, и Мn⊂Мi не имеет места. Аналогично не все пары элементов из множества натуральных чисел находятся в отношении «быть делителем».
Заключение
Множество - это неопределяемое понятие, представляющее некоторую совокупность данных. Элементы множества можно отличать друг от друга, а также определять, принадлежит ли данный элемент данному множеству. Над множествами можно выполнять операции объединения, пересечения, разности и дополнения.
Новые множества можно строить при помощи понятия декартового произведения. Декартово произведение нескольких множеств - это множество кортежей, построенное из элементов этих множеств.
Отношение - это подмножество декартового произведения множеств. Отношения состоят из однотипных кортежей. Каждое отношение имеет предикат отношения и каждый n-местный предикат задает n-арное отношение.
Отношение является математическим аналогом понятия "таблица".
Отношения обладают степенью и мощностью. Степень отношения - это количество элементов в каждом кортеже отношения (аналог количества столбцов в таблице). Мощность отношения - это мощность множества кортежей отношения (аналог количества строк в таблице).
В математике чаще всего используют бинарные отношения (отношения степени 2). В теории баз данных основными являются отношения степени . В математике, как правило, отношения заданы на бесконечных множествах и имеют бесконечную мощность. В базах данных напротив, мощности отношений конечны (число хранимых строк в таблицах всегда конечно).
