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

Лекция 1.

 

п.1.  Множества. Операции над множествами.

 

1.1.  Множество. Способы задания множеств.

 

Множество – это любая совокупность объектов, которые называются элементами множества.

В этом интуитивном определении, принадлежащим немецкому математику Георгу Кантору, существенным является то обстоятельство, что собрание предметов само рассматривается как один предмет, мыслится как единое целое. Расплывчатость, недостаточность этого определения стала понятней, когда в 1879 году итальянский логик Бурали-Форти, а немного позже выдающийся философ и логик Бертран Рассел открыли парадоксы, указывающие на внутреннюю противоречивость канторовой теории множеств. Чтобы устранить такие противоречия и парадоксы, для теории множеств были предложены аксиоматические системы. Наиболее известны системы Цермело-Френкеля фон Неймана (ZF), Гильберта-Бернайса-Геделя и Рассела-Уайтхеда. По сути, мы оставим понятие множества неопределенным, и будем считать множество заданным, если его элементы однозначно определены и это не приводит к каким-либо противоречиям.

Множества обозначаются прописными буквами латинского алфавита: A, B, X, Y, A1, A2, …, элементы множеств – строчными буквами: a, b, x, y, a1, a2, … .

Символ Î обозначает принадлежность. Запись означает, что элемент x принадлежит множеству A. Если элемент x не принадлежит множеству A, то пишут .

Множества бывают: 1) конечные; частный случай – единичное (одноэлементное);

                                                2) бесконечные;

                                                3) пустое (Ø).

Пустым множеством называют множество, не содержащее ни одного элемента.

 

Способы задания (описания) множеств:

1) Множество A определяется непосредственным перечислением всех своих элементов a1, a2, …, an, т.е. записывается в виде:  A={a1, a2, …, an}. При задании множества перечислением обозначения элементов обычно заключают в фигурных скобках и разделяют запятыми. Перечислением можно задавать только конечные множества.

2) Множество A определяется как совокупность тех и только тех элементов из некоторого основного множества T, которые обладают общим свойством P(x). В этом случае используется обозначение , т.е. задается характеристи-ческим предикатом. Характеристическим предикатом можно задать как конечные, так и бесконечные множества.

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

Пример 1.1.  - множество натуральных чисел от 1 до 4. Множество задано перечислением всех своих элементов. Причем, элемент 3ÎA, а 5ÏA.

,

Пример 1.2.  M={токарные, сверлильные, строгальные, резьбофрезерные, …} - множество станков.

,

Пример 1.3.  Множество A из примера 1.1. можно задать характеристическим предикатом .

,

Пример 1.4.  Зададим рекурсивно множество X алгоритмом:

   1)  3ÎX;

   2)  если xÎX, то элемент и (1-x) принадлежат X;

   3)  других элементов  в X нет.

Заметим, что это множество – конечное, и его можно было задать выписыванием его элементов

.

,

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

Пример 1.5.  Множество N задается следующими правилами:

   1)  задается базис  индукции (исходный элемент):

1ÎN;

   2)  указывается  индуктивный переход:

если nÎN, то (n+1)ÎN;

   3)  устанавливается  правило замыкания:

других элементов, кроме построенных правилами 1 и 2, в N нет.

,

 

 

1.2.  Подмножество. Равенство множеств.

Универсум. Булеан.

 

Определение 1.1.  Множество A называется подмножеством множества B (обозначается AÍB), если каждый элемент A есть элемент B, т.е. если xÎA, то xÎB.

Символ Í обозначает отношение включение между множествами.

Пример 1.6.  Пусть и . Тогда BÍA. Но .

,

В частности, каждое множество есть подмножество самого себя, т.е. AÍA.

 

Определение 1.2.  Пусть A и B – некоторые множества. Говорят, что A равно B, и пишут A=B, если для любого x имеем: xÎA тогда и только тогда, когда xÎB.

Иначе говоря, A=B тогда и только тогда, когда AÍB и BÍA.

Если AÍB и A¹B, то это записывается AÌB, и говорят, что A есть собственное подмножество B. Пустое множество есть подмножество любого данного множества A, т.е. ÆÌA.

Таким образом, доказательство равенства двух множеств A и B состоит из двух этапов:

1)  Доказать, что A есть подмножество B.

2)  Доказать, что B есть подмножество A.

 

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

В теории чисел универсальное множество обычно совпадает с множеством всех целых или натуральных чисел. В математическом анализе универсальное множество может быть множество всех действительных чисел или множество всех точек n-мерного пространства. Следует отметить, что универсальное множество U, хотя, и названо универсальным, однозначно не определено, если точно не указана область рассмотрения (предметная область). Конечно, любое множество, содержащее U, может быть использовано как универсальное множество.

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

Пример 1.7.  Так для множества за универсум можно взять множество натуральных чисел, т.е. U=N.

,

Определение 1.4.  Булеаном множества A (обозначается P(A)) называется множество, состоящее из всех подмножеств множества A.

Пример 1.8.  Пусть . Следовательно, булеан множества A есть множество P(A)= .

,

Множество A из примера 1.8. содержит три элемента, а булеан P(A) состоит из 23=8 элементов. В общем случае, если множество A содержит n элементов, множество P(A) включает 2n элементов, т.к. A имеет 2n подмножеств. По этой причине P(A) часто обозначают через 2A.

 

 

1.3.  Операции над множествами.

 

Множество часто задают графически с помощью диаграмм Эйлера [Л. Эйлер (1707-1783) – швейцарский математик, механик и физик].

 

 

Изображение множеств с помощью фигур на плоскости восходит к XIII в. Известный создатель первого «философского компьютера» Р. Луллий (ок. 1235 – ок. 1315) «вычислял» с помощью сочетания кругов на плоскости, цвета, букв и цифр такую «величину», как «судьба человека».

В дальнейшем графическое изображение множеств было плодотворно исследовано Дж. Венном (1834-1923), создавшим диаграммную теорию изучения множеств различной природы.

Диаграммы, задающие множества, будем называть диаграммы Эйлера-Венна.

 

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

 

Определение 1.5.  Объединением множеств A и B называется множество, (которое обозначается AÈВ) состоящее из всех элементов, которые принадлежат хотя бы одному из множеств А или В.

 

Определение 1.6.  Пересечением множеств А и В называется множество, (которое обозначается АÇВ) которое состоит из общих элементов этих множеств.

Определение 1.7.  Разностью множеств А и В называется множество, (которое обозначается А\В) всех тех и только тех элементов множества А, которые не принадлежат В.

Определение 1.8. Симметрическая разность множеств А и В (обозначается А∆В) есть множество (А\В)È(В\А).

 

Определение 1.9.  Дополнением множества А (обозначается ) – это множество элементов универсума, которые не принадлежат А, т.е.  \А.

 

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

а)  ;           в)  ;

б)  ;                     г)  если , то .

,

 

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

 

- множество, характеризующее размерные связи и содержащее погрешности обработки ;

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

- множество, характеризующее элементы  и виды управляющей информации, где УП – управляющая программа, L – траектория режущего инструмента, G – подготовительные команды, М – вспомогательные команды, Э – команды электроавтоматики;

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

- множество, характеризующее экономические  связи; - себестоимость операции, - себестоимость штучная, Q – производительность.

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

,

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

;

 

Операции над множествами обладают рядом важных свойств.

Теорема 1.1.  Пусть задан универсум U. Тогда " A, B, C Ì U выполняются следующие свойства:

1.  Свойства коммутативности:     АÈВ=ВÈА

                                                          АÇВ=ВÇА

2.  Свойства ассоциативности:      АÈ(ВÈС)=(АÈВ)ÈС

                                                         АÇ(ВÇС)=(АÇВ)ÇС

3.  Свойства  дистрибутивности:    АÇ(ВÈС)=(АÇВ)È(АÇС)

                                                          АÈ(ВÇС)=(АÈВ)Ç(АÈС)

4.  Свойства тождества:                 АÈÆ=А                АÇÆ=Æ

                                                         АÈU=U                АÇU=А

5.  Законы идемпотентности:        АÈA=A

                                                         АÇA=A

6.  Свойства поглощения:             АÈ(АÇВ)=А

                                                        АÇ(АÈВ)=А

7.  Двойное дополнение:             

8.  Свойства дополнения:             АÈ =U

                                                        АÇ =Æ

9.  Законы де Моргана:               

     Заметим, что  .

Доказательство.  Докажем свойство дистрибутивности È относительно Ç:

АÈ(ВÇС)=(АÈВ)Ç(АÈС).

Пусть M= АÈ(ВÇС)  и K=(АÈВ)Ç(АÈС).

1)  Докажем, что MÍK.                                         2)  Докажем, что KÍM.

 Пусть элемент xÎM, тогда                                       Пусть элемент xÎK, тогда

Значит, MÍK.                                                                           Значит, KÍM.

3)  Так как MÍK и KÍM, то M=K, то есть АÈ(ВÇС)=(АÈВ)Ç(АÈС).

Остальные тождества доказываются аналогично.                                                                    ■

 

Определение 1.10.  Покрытием множества A называется набор подмножеств , где I – некоторое множество индексов, если каждый элемент A принадлежит хотя бы одному из Ai.

Пример 1.11.  Пусть A={W, V, d, à}. Тогда {{W}, {V, W}, {d, V, à}} является покрытием множества A.

,

 

Определение 1.11.  Разбиением множества A называется набор его попарно непересекающихся подмножеств , где I – некоторое множество индексов.

- разбиение множества A, если выполняются два условия:

1)  ;

2)  , т.е. aÎA тогда и только тогда, когда aÎAi для некоторого iÎI.

Пример 1.12.  Пусть A={W, V, d, à}. Тогда множество <A>={{W}, {d, V, à}} является разбиением множества A.

,