Лекция 2.

п.2. Декартово произведение. Мощность множества.

2.1. Декартово произведение множеств.

Упорядоченная пара интуитивно определяется как совокупность, состоящая из двух элементов x и y, расположенных в определенном порядке. Две пары и считаются равными тогда и только тогда, когда x=u и y=v.

Определение 2.1. Пусть A и B – два множества. Прямым (декартовым) произведением двух множеств A и B называется множество всех упорядоченных пар, в котором первый элемент каждой пары принадлежит A, а второй принадлежит B:

.

Пример. Пусть и . Тогда

.

.

Пример. На координатной плоскости построить следующее множество:

(-1; 3]×[1; 3)

Решение. Первое множество помещаем на оси OX, второе на оси OY. Множество всех пар, т. е. декартово произведение, изображается точками заштрихованного прямоугольника, но без левой и нижней стороны.

,

3
 

y
 

Как вы знаете, точка на плоскости может быть задана упорядоченной парой координат, то есть двумя точками на координатных осях. Поэтому координатную плоскость можно задать в виде . Метод координат ввел в употребление Рене Декарт (), отсюда и название «декартово произведение».

В частности, если A пусто или B пусто, то, по определению, A´B пусто.

Понятие прямого произведения допускает обобщение.

Прямое произведение множеств

A1, A2, …, An – это множество наборов (кортежей):

.

Множества Ai не обязательно различны.

Степенью множества A называется его прямое произведение самого на себя. Обозначение:

НЕ нашли? Не то? Что вы ищете?

.

Соответственно, и вообще .

Пример. Пусть B={0, 1}. Описать множество Bn.

Решение. Множество Bn состоит из последовательностей нулей и единиц длины n. Они называются строкой бит или битовой строкой длины n.

2.2. Мощность множества.

Альберт Эйнштейн как-то говорил: «Не все, что можно сосчитать, сосчитано, и не все, что сосчитано, можно сосчитать». Хотя это высказывание не очень воодушевляет, попытаемся заняться подсчетами.

Говорят, что между множествами A и B установлено взаимно однозначное соответствие, если каждому элементу множества A соответствует один и только один элемент множества B и каждому элементу множества B соответствует некоторый элемент множества A. В этом случае говорят также, что множества A и B изоморфны и используют обозначение A~B.

Определение 2.2. Два множества A и B называются эквивалентными, или равномощными, если между этими множествами может быть установлено взаимно однозначное соответствие. В этом случае пишут: A~B, или |A|=|B|, и говорят, что множества A и B имеют равные мощности.

Пример. 1) Множество десятичных цифр равномощно множеству пальцев на руках человека.

2) Множество четных натуральных чисел (2N) равномощно множеству всех натуральных чисел (N).

Определение 2.3. Множество A называется конечным, если оно эквивалентно Jn при некотором n, где Jn={1, 2, …, n} – множество n первых натуральных чисел.

Определение 2.4. Мощностью конечного множества A, которое содержит k элементов, называется число его элементов. Она обозначается |A|=k.

Пустое множество считается конечным с числом элементов равным нулю, т. е. |Æ|=0.

Таким образом, если множество A конечно, т. е. |A|=k, то элементы A всегда можно перенумеровать, то есть поставить в соответствие элементам номера из отрезка натурального ряда 1..k с помощью некоторой процедуры. Наличие такое процедуры подразумевается, когда употребляется запись A={a1, a2, …, ak}.

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

Множества, которые не являются конечными, называются бесконечными. Если некоторое множество A равномощно множеству N, т. е. A~N, то множество A называется счетным (в зарубежной литературе: множество называются счетным, если оно конечно или счетно бесконечно). Счетное множество A – это такое множество, все элементы которого могут быть занумерованы в бесконечную последовательность a1, a2, …, an, …, так, чтобы при этом каждый элемент получил лишь один номер n и каждое натуральное число n было бы номером лишь одного элемента множества A. Мощность счетного множества принято обозначать через ( – первая буква древнееврейского алфавита, называемая «алеф», символ читается: «алеф-нуль»). В частности |N|=.

Пример. Множество Z – множество целых чисел счетно.

Решение. Рассмотрим множество целых чисел Z:

…, -n, …, -3, -2, -1, 0, 1, 2, 3, …, n, … .

На первый взгляд, кажется, что это множество невозможно перенумеровать. Однако эту нумерацию можно осуществить, применив следующую хитрость: двигаясь не в одном направлении, а все время менять его. Иными словами, будем нумеровать так: числу 0 дадим номер 1, числу 1 – номер 2, числу -1 – номер 3, числу 2 – номер 4, числу -2 – номер 5, и т. д. Таким образом, получаем взаимно однозначное соответствие между множеством Z и N. А значит, множество Z счетно.

Множество A называется несчетным, если его мощность больше мощности множества N. В таком случае множество A называется континуальным или континуумом. Мощность континуума обозначается . Следующую теорему примем без доказательства.

Теорема 2.1. Множество всех действительных чисел имеет мощность континуума, т. е. |R|=C.

2.3. Теоремы сложения и умножения.

Формула включений и исключений.

Чтобы подсчитать число элементов конечного множества, образованного в результате объединения или пересечения некоторых конечных множеств, используется комбинаторный анализ. Мы рассмотрим теоремы сложения и умножения, а так же формулу включений и исключений.

Теорема 2.2. (Теорема сложения)

Пусть – конечные попарно непересекающиеся множества, т. е. . Тогда

(2.3.1.)

Теорема 2.3. (Теорема умножения)

Пусть заданы конечные множества . Тогда

(2.3.2.)

т. е. число элементов декартова произведения множеств равно произведению количеств элементов сомножителей.

Пример. Сколько существует целых чисел между 0 и 1000, содержащих ровно одну цифру 6?

Решение. Пусть S – множество целых чисел между 0 и 1000, содержащих ровно одну цифру 6. Рассмотрим три подмножества S1, S2 и S3 множества S.

S1 – множество, которое содержит число, состоящее из одной цифры, и эта цифра 6;

S2 – множество, содержащее двузначные числа ровно с одной цифрой, равной 6;

S3 – множество, содержащее трехзначные числа ровно с одной цифрой, равной 6.

Множество S1 содержит только один элемент – число 6. Значит, | S1|=1.

В множестве S2 каждый элемент, содержащей 6, имеет ее либо первой, либо второй цифрой. Если 6 – вторая цифра, то существует 8 различных чисел, которые будут стаять на первом месте, поскольку первое число не может быть 0 или 6. Если 6 – первая цифра, то таких чисел 9, поскольку вторая цифра не может быть 6. Таким образом, S2 содержит 8+9=17 элементов, т. е. | S2|=17.

Элемент из S3 содержит 6 как первою, вторую или третью цифру. Если 6 – первая цифра, то существует 9 вариантов выбора второй цифры и 9 вариантов выбора третьей цифры. Согласно комбинаторному принципу умножения, S3 содержит 9 ´9=81 чисел с первой цифрой. Если 6 – вторая цифра, то имеются 9 вариантов выбора третьей цифры и 8 вариантов выбора первой цифры, поскольку первая цифра не может быть нулем. Следовательно, S3 содержит 9´8=72 числа, у которых 6 – вторая цифра. Аналогично, S3 содержит 72 числа, у которых 6 – третья цифра. Следовательно, всего S3 содержит 81+72+72=225 элементов, т. е. |S3|=225.

Поскольку и множества S1, S2 и S3 попарно непересекающиеся, то

.

Поставим задачу подсчитать число элементов в объединении

X=X1ÈX2È…ÈXm

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

Теорема 2.4. (Формула включений и исключений).

Для конечных множеств , справедлива формула включений и исключений.

(2.3.3.)

В частности для двух множеств эта формула примет вид:

.

Для трех множеств формула включений и исключений примет вид:

.

Название этой теоремы подчеркивает использование последовательных включений и исключений элементов подмножеств.

Пример 2.8. Сколько положительных целых чисел, меньших 1001, делятся на 2, 3 или 5?

Решение. Пусть X – множество положительных целых чисел, которые делятся на 2, 3 или 5. Рассмотри три подмножества X1, X2 и X3 множества X.

X1 – множество положительных целых чисел, которые делятся на 2. Число элементов или мощность этого множества равно .

X2 – множество положительных целых чисел, которые делятся на 3. Число элементов или мощность этого множества равно .

X3 – множество положительных целых чисел, которые делятся на 5. Число элементов или мощность этого множества равно .

Тогда множество X1ÇX2 – множество положительных целых чисел, которые делятся на 2 или 3. Число элементов или мощность этого множества равно . Множество X1ÇX3 – множество положительных целых чисел, которые делятся на 2 или 5. Число элементов или мощность этого множества равно . Множество X2ÇX3 – множество положительных целых чисел, которые делятся на 3 или 5. Число элементов или мощность этого множества равно .

Множество X1ÇX2ÇX3 – множество положительных целых чисел, которые делятся на 2, 3 или 5. Число элементов или мощность этого множества равно .

Воспользуемся формулой включения и исключения, чтобы найти число элементов множества X. Получаем

2.4. Представление множеств в компьютере.

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

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

Тем, кто желает больше узнать о различных способах представления множества в компьютерах, можно порекомендовать следующую книгу:

Новиков математика для программистов. Учебник для вузов. 2-е изд. – СПб.: Питер, 2006.

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

Пусть задан конечный универсум U, и число элементов в нем не превосходит разрядности компьютера, . Элементы универсума нумеруются:

.

Подмножество A универсума U представляется кодом (машинным словом или битовой шкалой) C, в котором:

где – это i-й разряд кода C.

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

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