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

Билет №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.

 

Билет №7. Отношение порядка. Упорядоченные множества.

Бинарное отношение называется отношение порядка на множестве, если оно транзитивно и антисимметрично.
Отношения порядка делятся на строгие (в случае антирефлексивности)и не строгие (в случае рефлексивности) отношение порядка. Кроме того, отношение порядка делятся на линейные и не линейные (частичного порядка).
Отношение порядка ρ называется линейным на множестве А, если для любых x, y ϵ А либо
(x, y) ϵ ρ, либо (y, x) ϵ ρ, либо x=y.
Отношение порядка, не являющиеся линейным, называется отношением частичного порядка.
Множества, на котором введено отношение порядка (частичного порядка), называется упорядоченным (частично упорядоченным) множеством.

 

Элемент а ϵ А называется наименьшим (наибольшим) элементом

Элемент а ϵ А называется минимальным (максимальным) элементом

 

Билет №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, определяемые таблицей: