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