- •Раздел 1. Множества.
- •1.1. Множества и подмножества.
- •1.2. Способы задания множеств.
- •1.3. Операции над множествами.
- •1.4. Свойства операций над множествами
- •1.5. Разбиение и покрытия
- •1.6. Булеан
- •1.7. Генерация всех подмножеств заданного универсума
- •1.8. Алгоритм построения бинарного кода Грея
- •1.9. Алгоритмы пересечения, объединения двух множеств и проверки включения слиянием
Раздел 1. Множества.
Элементы и множества. Способы задания множеств. Сравнение множеств. Мощность множества. Операции над множествами и их свойства. Разбиение и покрытия. Булеан. Генерация всех подмножеств заданного универсума. Алгоритм построения бинарного кода Грея. Алгоритмы пересечения, объединения двух множеств и проверки включения слиянием.
1.1. Множества и подмножества.
Одними из основных, исходных понятий математики являются понятия множества и его элементов. Понятие множества принадлежит к числу фундаментальных неопределяемых понятий математики. Можно сказать, что множество – это любая совокупность объектов. Объекты, из которых составлено множество называются его элементами. Элементы множества различны и отличимы друг от друга. Принадлежность элемента а множеству М обозначается а М (a принадлежит М); непринадлежность а множеству М обозначается а М или а М.
Множество А называется подмножеством множества В (обозначение А В; знак называется знаком включения), если всякий элемент А являётся элементом В. При этом говорят, что В содержит или покрывает А. Множества А и В равны, если их элементы совпадают, иначе говоря, если А В и В А. Второй вариант определения равенства множеств указывает и на наиболее типичный метод доказательства того, что данные множества равны, заключающийся в доказательстве сначала утверждения А В («в одну сторону»), а затем В А («в другую сторону»). Форму утверждения о равенстве двух множеств имеют многие математические теоремы. Пример — тригонометрическая теорема, состоящая из двух утверждений: а) всякое решение уравнения sin х = 1 имеет вид /2 ± k; б) всякое число вида /2 ± k является решением уравнения sin х = 1.
Если А В и А В, то А часто называется собственным, строгим или истинным подмножеством В (обозначение А В; знак называется знаком строгого включения).
Множества могут быть конечными (т. е. состоящими из конечного числа элементов) и бесконечными. Если элементы бесконечного множества можно перенумеровать, то оно называется счетным, иначе – несчетным (вещественные числа, комплексные числа). Число элементов в конечном множестве М называется мощностью М и часто обозначается М. Мощность бесконечного множества — более сложное понятие.
Множество мощности 0, т. е. не содержащее элементов, называется пустым и обозначается . Принято считать, что пустое множество является подмножеством любого множества. Пустое множество введено в математике для удобства и единообразия языка. Например, если исследуется множество объектов, обладающих каким-либо свойством и впоследствии выясняется, что таких объектов не существует, то гораздо удобнее сказать, что исследуемое множество пусто, чем объявлять его несуществующим. Утверждение «множество М непусто» является более компактной формулировкой равносильного ему утверждения «существуют элементы, принадлежащие М».
1.2. Способы задания множеств.
Для задания множества нужно указать, какие элементы ему принадлежат.
Основные способы задания множеств:
Перечисление элементов – задание множества через указание списка элементов (обозначается в фигурных скобках через запятую). Например, А = {а, b, d, h}.
Характеристический предикат – некоторое условие, выраженное в форме логического утверждения или процедуры, возвращающей логическое значение. Если для данного элемента условие выполнено, то он принадлежит множеству, иначе – не принадлежит. Например, М = {х | Р(х)}.
Порождающая процедура – процедура, которая, будучи запущенной, порождает некоторые объекты, являющиеся элементами определяемого множества. Например: М = {х | х = }