Задание множеств

Дискретная (или прерывная) математика – область математики, в которой изучаются структуры, основанные на конечных множествах, или же на бесконечных множествах, но предполагающих отделимость составляющих их элементов.

Наиболее значимой областью применения методов дискретной математики является область компьютерных технологий. Дискретная математика и примыкающие к ней дисциплины изучаются во всех университетах и институтах, где осуществляется подготовка специалистов в области программирования, математики, а также по экономическим и техническим направлениям.

 

Понятие "множество" является первичным и неопределяемым понятием математики. Георг Кантор (1845 – 1918) – немецкий математик, чьи работы лежат в основе современной теории множеств, говорил, что "множество – это многое, мыслимое как единое".

Множество можно представить себе как совокупность объектов (предметов), обладающих некоторым общим свойством. Объекты (предметы), составляющие данное множество, называются его элементами. Для того чтобы некоторую совокупность элементов можно было назвать множеством, необходимо, чтобы выполнялись следующие условия:

1) должно существовать правило, позволяющее определить, принадлежит ли указанный элемент данной совокупности;

2) должно существовать правило, позволяющее отличать элементы друг от друга.

Для обозначения множества используют заглавные буквы латинского алфавита, а в фигурных скобках через запятую выписывают его элементы (например ). Если элемента принадлежит множествуA, то это обозначается: .

Элементами множества могут быть любые объекты – числа, векторы, точки, матрицы и т.п. В частности элементами множества могут являться множества.

Для числовых множеств общепринятыми являются следующие обозначения:

N – множество натуральных чисел (целых положительных чисел);

N₀ – расширенное множество натуральных чисел (к натуральным числам добавлено число нуль);

Z– множество всех целых чисел, куда входят положительные и отрицательные целые числа, а также нуль.

Q – множество рациональных чисел. Рациональное число – это число, которое может быть записано в виде обыкновенной дроби.

R – множество действительных чисел.

Каждый раздел математики использует свои множества. Начиная решать какую-либо задачу, прежде всего, определяют множество тех объектов, которые будут в ней рассмотрены.

Множество, включающее в себя все объекты, рассматриваемые в задаче, называют универсальным множеством или универсумом (для данной задачи).Универсальное множество принято обозначать буквой U(или Ω). Универсальное множество является максимальным множеством в том смысле, что все объекты являются его элементами.

Отметим, что "универсальное множество" понятие относительное: оно выбирается для какого-нибудь определенного раздела науки и притом часто даже явно не определяется, а просто подразумевается.

Множество, имеющее конечное число элементов, называется конечным.

Множество называется бесконечным, если оно состоит из бесконечного числа элементов.

Множество называетсясчетным, если можно занумеровать его элементы, например, a₁,a₂,…и т. д. Если существует элемент с самым большим номером, то множество является конечным, если же в качестве номеров задействованы все натуральные числа, то множество является бесконечным счетным множеством.

Множество, в котором нет ни одного элемента, называется пустым множеством и обозначается Ø (например, А=Ø).

Мощностью конечного множества (размером конечного множества) называют количество его элементов. Мощность пустого множества равна нулю.

Множество, состоящее из некоторых элементов другого множества, называется его подмножеством. Утверждение, что множество В является подмножеством множества А, записывают так: . Считается, что пустое множество является подмножеством любого множества.

У любого множества есть обязательно хотя бы два подмножества: пустое множество и само множество. Эти два подмножества называются несобственными подмножествами. Любое подмножество, отличное от несобственного, называется собственным подмножеством данного множества.

Множества, состоящие из одних и тех же элементов, называются равными. При этом порядок перечисления элементов множества значения не имеет.

 

Задать множество А – это значит, указать способ, позволяющий относительно любого элемента xуниверсального множества однозначно установить, принадлежитxмножеству А или нет. Множества можно задавать различными способами. Рассмотрим некоторые из них:

1. Списком (перечислением). Дается список элементов, входящих в данное множество. Этим способом можно задавать только конечные или счётные множества.

Примеры:

1) A={0, 0.2, 0.4, 0.6, 0.8, 1} – множество, содержащее 6 элементов (конечное множество).

2)B={0, 0.1, 0.11, 0.111, 0.1111, …} – бесконечное счетное множество.

3)P={1, 2, {1, 2}, 3, {1, 2, 3}} - множество, содержащее 5 элементов, два из которых – {1, 2} и {1, 2, 3}, сами являются множествами.

2. Описанием характеристических свойств. В этом случае указывают свойство, которым обладает каждый элемент множества, но не обладает никакой объект, не принадлежащий множеству.

Примеры:

1) Т - множество студентов, обучающихся по направлению «Прикладная информатика».

2) – множество действительных чисел, больших или равных нулю, и меньших единицы.

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

Пример: .

4. Разрешающей процедурой. Формулируется правило решения вопроса, верно ли xєAдля любого x, например, с помощью характеристической функции. Характеристической функцией множества А называется функция , заданная на универсальном множествеU и принимающая значение единица на тех элементах множества U, которые принадлежат А, и значение нуль на элементах, которые не принадлежат А:

, (xє U).

Пример:

Рассмотрим в качестве примера универсальное множество U={1, 2, 3, …, 10} и два его подмножества: А – множество чисел, меньших 7, и В – множество чётных чисел. Характеристические функции множеств А и В имеют вид

Запишем характеристические функции и в таблицу:

 

x (xє U)

 

5. Графически. Удобной иллюстрацией множеств являются диаграммы Эйлера-Венна, на которых универсальное множество изображается прямоугольником, а его подмножества – кругами или эллипсами.

 

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

Следует подчеркнуть, что, как правило, один и тот же объект может быть представлен многими разными способами, причем нельзя указать способ, который является наилучшим для всех возможных случаев. В одних случаях выгодно использовать одно представление, а в других — другое. Выбор представления зависит от целого ряда факторов: особенностей представляемого объекта, состава и относительной частоты использования операций в конкретной задаче и т. д. Умение выбрать наиболее подходящее для данного случая представление является основой искусства практического программирования. Хороший программист отличается тем, что он знает много разных способов представления и умело выбирает наиболее подходящий.