Лекции по "Развитию операционных систем"

Лекция 2.

 

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

 

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

 

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

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

.

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

.

.

,

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

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

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

 

 

 

 

 

 

 

 

 

,

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

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

 

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

Прямое произведение множеств A1, A2, …, An – это множество наборов (кортежей):

.

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

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

.

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

 

Пример 2.3.  Пусть 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 имеют равные мощности.

Пример 2.4.  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|= .

Пример 2.6.  Множество 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.)

Доказательство.  Докажем теорему методом математической индукции.

Базис индукции.  Пусть n=2. Пусть множества X1=A и X2=B, мощности которых соответственно равны k1 и k2, т.е. |A|=k1, |B|=k2. Так как AÇB=Æ, то

.

Индуктивный переход.  Пусть теорема верна для n. Покажем, что для n+1 будет тоже справедливо. Тогда

■

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

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

                                     (2.3.2.)

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

Доказательство.  Докажем теорему методом математической индукции.

Базис индукции.  Пусть n=2. Пусть множества X1=A и X2=B, мощности которых соответственно равны k1 и k2, т.е. |A|=k1, |B|=k2. Первый компонент упорядоченной пары можно выбрать k1 способами, второй – k2 способами. Таким образом, всего имеется k1×k2 различных упорядоченных пар. Значит,

.

Индуктивный переход.  Предположим справедливость утверждения теоремы для n. Покажем, что для n+1 оно будет тоже справедливо. В самом деле, добавляя еще одно множество в декартово произведение, видим, что

■

Пример 2.7.  Сколько существует целых чисел между 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.

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