Билет №1.Способы задания множеств. Подмножества. Отношения между множествами.

Множество – это вполне определенная совокупность различимых между собой предметов, понимаемая как единое целое. Предметы, составляющие множества, называется его элементами. Множества обозначаются обычно большими латинскими буквами: A B C M N и тд. Если предмет а является элементом множества А, то пишут а ϵ А. Если множества А конечно и состоит из элементов а1 а2, … ,аn ,то пишут: А={ а1 а2, … ,аn}. В случаях, когда число элементов какого либо множества А достаточно велико (или бесконечно), или эти элементы не известны, применяется запись вида: А={x|P(x)}, где символом P(x) обозначается характеристическое свойство элементов x множества А. Ø- множество в котором нет элементов (пустое множество). Множество А называется подмножеством множества В (А вложено В), если каждый элемент множества А является элементом множества В. А В Пустое множество и само множество являются подмножествами для любого множества А(Ø А, А ). Они называются тривиальными подмножествами множествами. Подмножества, не совпадающие с тривиальными, называются собственными. Множество всех подмножеств множества А называется булеаном множества А и обозначается 2^А. Если множество А состоит из n элементов, то множества 2^А состоит из 2 ⁿ элементов. Множества А и В называются равными (А=В), если они состоят из одних и тех же элементов. А=В тогда и только тогда, когда А В и В А. Операции над множествами.

Объединением (А В) множества А и В называется множества всех предметов которые являются элементами множества А, или элементами множества В или их общими элементами. А В = {с |c ϵ A или с ϵ В или с ϵ А, В}. Пересечением (А В) множества А и В называется множество предметов, являющихся элементами обоих множеств А и В. А В={x |x ϵ A и x ϵ B}. Дополнением Ᾱ множества А называется множества всех элементов универсального множества (U), не являющихся элементами множества А. Разностью А\В множеств А и В называется множество, элементами которого являются элементы множества А но не являющиеся элементами множества В. Декартовым произведением множеств А и В называется множества упорядоченных пар, первый элемент которых есть элемент множества А, второй элемент есть элемент множества В. (А×В={(а, b)| a ϵ A, b ϵ B}. Универсальным множеством (U) называется множества, для которого все рассматриваемые задачи или теории множества являются подмножествами.

Билет №2.Мощность множества. Представление множеств в эвм.

1) Множества А и В называются равномощными (эквивалентными), если между их элементами можно установить взаимно – однозначное соответствие. Для конечных множеств их равномощность означает равное количество элементов в этих множествах. Количество элементов в конечном множестве множестве А называется его мощностью и обозначается |a|. Множество А называется счетным, если можно установить взаимно – однозначное соответствие (нумерацию) между элементами этого множества и множества N натуральных чисел. Любое конечное множество не является счетным. Теорема Кантора: Множества действительных чисел отрезка [0, 1] не является счетным. Говорят, что множества равномощное отрезку [0, 1], имеет мощность континуума.

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

Номер N_A кода множества А в этой последовательности однозначно определяется самим кодом и является записью А₂ в десятичной системе счисления. Количество кодов в этой последовательности равно 2ⁿ и, следовательно, мощность множества 2^U всех подмножеств множества U также равно 2ⁿ . (|2^U|=2ⁿ) Логической суммой (дизъюнкцией) и логическим произведением (конъюнкцией) булевых переменных x и y называется функции x ˄ y и x ˅ y, определяемые таблицей:

Билет №3.Отношения на множествах. График и граф бинарного отношения.

1. n-арным отношением на множестве А называется любое подмножества упорядоченных n-ок элементов этого множества. При n = 3 отношение называется тернарным, при n=2 бинарным, при n = 1 унарным. Обозначение: ρ, σ, τ… Таких образом, если ρ – n- арное отношение на множестве А, то ρ Аⁿ. Областью определения D_ρ отношение ρ называется множеством всех первых элементов пар, входящих в ρ; областью значений R_ρ отношение ρ называется множество всех вторых элементов пар, входящих в ρ. Бинарным отношение от X к Y называется любое подмножество множества X×Y.

2. Графиком бинарного отношения ρ, заданного на множестве А называется множество точек на плоскости с координатами (x, y): (x, y) ϵ ρ. Графом отношения ρ называется геометрическая фигура на плоскости, состоящая из точек – вершин графа, и линии их соединяющих – ребер графа. Вершины графа обозначают элементы множества, на котором определено отношение, а ребро графа соединяющих вершины a и b графа, проводится в том случае, когда a, b ϵ ρ. В этом случае ребро изображается со стрелкой от вершины a к вершине b.

Билет №4.Свойства бинарных отношений.

Отношение ρ, заданное на множестве А, называется рефлексивным, если Отношение ρ, заданное на множестве А, называется антирефлексивным, если Отношение ρ, заданное на множестве А, называется симметричным, если

Отношение ρ, заданное на множестве А, называется антисимметричным, если

Отношение ρ, заданное на множестве А, называется транзитивным, если

График рефлексивного на А отношения включает все точки в (x, x) биссектрисы 1–го и 3–го координатных углов для x ϵ A. Граф рефлексивного отношения имеет в каждой его вершине петлю. График антирефлексивного отношения не имеет ни одной точки (x, x) на биссектрисе 1-го и 3-го координатных углов для x ϵ A, а на его графе нет петель. График симметричного отношения – эта фигура, симметричная относительно биссектрисы

График рефлексивного на А отношения включает все точки в (x, x) биссектрисы 1–го и 3–го координатных углов (прямой x=y). Граф симметричного отношения не имеет ориентированных ребер. График антисимметричного отношения не имеет точек симметричных относительно биссектрисы 1-го и 3-го координатных углов, на самой же биссектрисе точки графика могут быть. Граф антисимметричного отношения не имеет неориентированных ребер, но может иметь петли. На графике транзитивного отношения вместе с каждой парой точек (a, b) и (b, c) должна быть точка (a, c), это означает, что четвертая вершина прямоугольника так же должна быть на графике.