- •Билет №1.Способы задания множеств. Подмножества. Отношения между множествами.
- •Билет №2.Мощность множества. Представление множеств в эвм.
- •Билет №5.Отношение эквивалентности. Классы эквивалентности.
- •Билет №6. Разбиения множеств и отношения эквивалентности.
- •Билет №7. Отношение порядка. Упорядоченные множества.
- •Билет №12.Разбиение множества. Числа Стирлинга 2-го рода и числа Белла.
- •Билет №13.Лексикографическое упорядочение постановок.
Билет №5.Отношение эквивалентности. Классы эквивалентности.
Рефлексивное, симметричное и транзитивное отношение называется отношением эквивалентности. Классном эквивалентности [a]ρ с представителем а называется множество всех тех элементов множества А, которые говорят эквивалентны элементу а: [a]ρ = {x| x ϵ A, (x, a) ϵ ρ}. Свойства классов эквивалентности:
Класс эквивалентности не зависит от его представителя. Если b ϵ [a]ρ , то [a]ρ = [b]ρ .
Различные классы эквивалентности не пересекаются. Если [a]ρ [b]ρ ≠ Ø, то [a]ρ = [b]ρ .
Множество всех классов эквивалентности отношения ρ на множестве А называется фактор – множеством множества А по отношению ρ и обозначается А/ρ .
Билет №6. Разбиения множеств и отношения эквивалентности.
Разбиения множества А называется семейство его непустых подмножеств, объединение которых совпадает с множеством А, а пересечение любых двух из них пусто. Теорема: 1. Пусть ρ отношение эквивалентности на множестве А. Тогда фактор – множества А/ρ является разбиением множества А. 2. Любое разбиение множества порождает на нем некоторые отношения эквивалентности.
Отношение эквивалентности: Рефлексивное, симметричное и транзитивное отношение называется отношением эквивалентности. Классном эквивалентности [a]ρ с представителем а называется множество всех тех элементов множества А, которые говорят эквивалентны элементу а: [a]ρ = {x| x ϵ A, (x, a) ϵ ρ}. Свойства классов эквивалентности:
Класс эквивалентности не зависит от его представителя. Если b ϵ [a]ρ , то [a]ρ = [b]ρ .
Различные классы эквивалентности не пересекаются. Если [a]ρ [b]ρ ≠ Ø, то [a]ρ = [b]ρ .
Множество всех классов эквивалентности отношения ρ на множестве А называется фактор – множеством множества А по отношению ρ и обозначается А/ρ .
Билет №7. Отношение порядка. Упорядоченные множества.
Бинарное отношение называется отношение порядка на множестве, если оно транзитивно и антисимметрично. Отношения порядка делятся на строгие (в случае антирефлексивности)и не строгие (в случае рефлексивности) отношение порядка. Кроме того, отношение порядка делятся на линейные и не линейные (частичного порядка). Отношение порядка ρ называется линейным на множестве А, если для любых x, y ϵ А либо (x, y) ϵ ρ, либо (y, x) ϵ ρ, либо x=y. Отношение порядка, не являющиеся линейным, называется отношением частичного порядка. Множества, на котором введено отношение порядка (частичного порядка), называется упорядоченным (частично упорядоченным) множеством.
Элемент а ϵ А называется наименьшим (наибольшим) элементом
Элемент а ϵ А называется минимальным (максимальным) элементом
Билет №8. Композиция отношений. Инверсия отношения.
Композицией ρ ◦ τ отношений ρ и τ называется множество всех таких пар (x, z), что для некоторых y (x, y) ϵ τ и (y, z) ϵ ρ таким образом, ρ ◦ τ ={x, z|существует y, такое что y (x, y) ϵ τ и (y, z) ϵ ρ}. Инверсия и отношение ρ называется отношение ρ ͝ = {(x, y)|(y, x) ϵ ρ}. Операции и композиция и инверсия обладают свойствами:
1.ρ ◦ τ ≠ τ ◦ ρ 2. (ρ ◦ τ) ◦ σ = ρ ◦ (τ ◦ σ) 3.(ρ ◦ τ) ͝ = τ ͝ ◦ ρ ͝
Билет №9.Размешение, перестановки, сочетания и их количество.
Размещениями называются комбинации, составленные из n различных элементов по m элементов, которые отличаются либо составом, либо их порядком. Определенное выше понятие размещений называют еще размещениями без повторений. Если при выборе размещений каждый выбранный элемент возвращать в множества А, то полученные комбинации называют размещениями с повторениями.
Перестановками из n элементов называются комбинации, состоящие из одних и тех же n элементов, отличающиеся друг от друга только порядком.
Перестановками с повторениями называются комбинации, в которых могут повторятся некоторые элементы и которые отличаются только порядком.
Сочетанием из n элементов по m элементов называется неупорядоченное подмножество n – элементного множества, состоящее из m элементов.