UML_4822 дм практикум

Задача 11. Приведите примеры таких множеств А, В, C, D, что А В,

В D, D C, A D, B D.

Задача 12. Задайте с помощью высказывательной формы следующие множества:

1);

2){1, 2};

3){1, 2,…, n};

4)множество всех целых четных чисел;

5)множество, состоящее из всех чисел вида 2n, n N0 (множество степеней числа 2);

6)множество степеней числа 3;

7)множество всех простых чисел.

Поскольку понятие множества является неопределяемым и потому недостаточно четким, то при задании необходимо, чтобы описание свойства его элементов было точным и недвусмысленным (непротиворечивым). Рекомендуется рассматривать только такие множества, возможные элементы которых были бы достаточно четко очерченными и неизменяемыми объектами. Например, вряд ли разумно рассматривать множество идей, множества капель воды в стакане и т.п. Также нельзя рассматривать и множества всех множеств, так как его рассмотрение может привести к противоречию, которое известно под названием парадокса Рассела. Парадокс Рассела состоит в следующем. Чаще всего приводятся примеры множеств, которые не содержат себя в качестве элементов. Например, такими множествами являются N0, Q, R, Z и др. Но если рассматривать множество всех множеств, то оно содержит себя в качестве своего элемента. Теперь определим множество М таким образом: его элементами являются все такие множества Y, что Y Y. Может быть одно из двух: либо М М, либо М М. Оказывается, что в каждом случае получаем противоречие. действительно, если М М, то, по определению М, также М М; если же М М, то снова, по определению М, имеем М М.

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

Определение. Ординарное множество – множество, которое не является своим собственным элементом.

Определение. Экстраординарное множество – множество, которое содержит самого себя в качестве элемента.

11

Задача 13. Является ли парадоксальным требование профессора решить студенту те и только те задачи, которые не мог решить ни один студент?

Ответ. Да, поскольку если студент найдет задачу, которую не мог решить ни один студент, и все же решит ее, то она перестанет быть задачей, которую не мог решить ни один студент.

1.2. Понятие подмножества

Введем важное отношение между множествами – отношение включения.

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

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

и <). Например, N Z, Z Q, Q R, {x | (x N0) (–x N0)} Z.

Включение В А называется обратным включению А В. Очевидно,

Эти два свойства отношения включения относятся к основным свойствам, в число которых входят и следующие: для любых двух множеств А,

В и С

Пример 14. Доказать утверждение (1.3). Пусть А В и В С. Требуется доказать, что если а А, то а С. Если а А, то из А В следует, что а В, а отсюда и из В С следует, что а С. Следовательно, утверждение (1.3) доказано.

По аналогии докажите утверждения (1.4)-(1.6).

12

Из свойства (1.5) следует: для того, чтобы доказать, что А=В, достаточно доказать, что А В, и затем, что В А. Согласно свойствам (1.1) и (1.2), у любого множества А есть по крайней мере два подмножества: и А, при этом если А= , то эти подмножества совпадают.

Определение. Подмножества и А множества А называются его несобственными подмножествами.

Следовательно, пустое множество и каждое одноэлементное множество обладают только несобственными подмножествами. Если данное множество содержит, по крайней мере, два элемента, то оно имеет и собственные подмножества. Например, всевозможные подмножества множества {a, b} суть , {a}, {b} и {a, b}, из которых {a} и {b} – собственные подмножества множества {a, b}.

Определение. Множество всех подмножеств множества А называется множеством-степенью множества А и обозначается через Р(А).

Итак, согласно этому определению, множество Р(А) – это {X | X A}. Пример 15. Дано множество A = {1, 2, 3}. Найти его Р(А).

Решение. Р(А) = { , {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}.

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

Ясно, что бесконечное множество имеет неограниченное число различных подмножеств, то есть если А – бесконечное множество, то и Р(А) – бесконечное.

Если множество А состоит из n элементов, то можно определить общее число всевозможных подмножеств n-элементного множества А.

Теорема о мощности множества-степени. Если |A| = n, то

множества множества А (пустое множество и само множество А). Задача 16. Определите отношение между множествами:

1)N и N0;

2)Z и Q;

3)Q и R;

4)прямоугольников и параллелограммов с равными диагоналями;

5)прямоугольников и четырехугольников с равными диагоналями;

6)]3, 5[ и ]3, 5];

7)]2, 7[ и [3, 5];

8)А = {x R | x2 + 1 = 0} и B = {x C | x2 + 1 = 0}.

Ответ. 1) N0 N;

13

2)Z Q;

3)Q R;

4)множество прямоугольников включается в множество параллелограммов с равными диагоналями;

5)множество прямоугольников включается в четырехугольников с равными диагоналями;

6)]3, 5[ ]3, 5];

7)]2, 7[ [3, 5];

8)А B.

Задача 17. Докажите следующие утверждения. Для любых множеств

А и В:

а) если А В, то А=В или А В; б) если А=В, то А В;

в) если А В, то А В;

г) Р(А);

д) если а А, то {a} Р(А).

Решение. Докажем, например, а). Пусть А В, тогда по определению подмножества все элементы множества А принадлежат и множеству В. Здесь возможны два случая: первый – если мощности множеств А и В совпадают, то все элементы множества В также принадлежат и А, то есть В А, а это значит, по утверждению (1.5), что А=В; второй случай – если мощность множества В больше мощности множества А, то множество В содержит по крайней мере один элемент, для которого справедливо, что b B и b A, а это значит, что А В и по определению строгого включения имеем А В.

Аналогичными рассуждениями можно доказать б) и в).

в) Множество-степень Р(А) по определению само является множеством, следовательно, согласно утверждению (1.2) Р(А), то есть оно содержит в качестве несобственного подмножества и пустое множество.

д) Поскольку множество-степень Р(А) является множеством всех подмножеств множества, то для любого а А справедливо, что {a} Р(А).

Задача 18. Покажите, что для n 2 множеств A1, A2,…, An условие A1 A2 … An A1 выполняется тогда и только тогда, когда A1= A2 =…= An.

Решение. Это утверждение можно доказать, если использовать определение подмножества, а также утверждение (1.5).

1.3. Алгебра множеств

Способы получения новых множеств из уже имеющихся называются операциями над множествами. Рассмотрим основные свойства этих опе-

14

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

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

Выражение A B читается: «объединение А и В» или «А, объединенное с В».

Если некоторое множество А изобразить левым, а некоторое множество В – правым кругом (рис. 2,а), то заштрихованная фигура на рис. 2,б изобразит A B . Такие изображения называют кругами Эйлера (иногда используют термин «диаграмма Венна», однако последний обозначает более сложные выражения).

Аналогично определяется объединение (соединение, сумма) n 2 множеств A1, A2,…, An.

Определение. Объединением (соединением, суммой) множеств A1, A2,…, An называется множество (обозначаемое через A1 A2 ... An или

n

Ai ), состоящее из всех и только тех элементов, которые принадлежат

i 1

хотя бы одному из множеств A1, A2,…, An.

Пример 20. Пусть A1 – множество четных натуральных чисел; A2 – множество, состоящее из числа 10 и всех нечетных натуральных чисел, не делящихся на 5; A3 – множество натуральных чисел, делящихся на 5. Тогда

15

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

элементов, то множества А и В называют непересекающимися или говорят, что множества А и В не пересекаются (см. рис. 3, б).

Определение. Если же A B , то множества А и В называют пересекающимися.

Множества находятся в общем положении, если выполнены следующие три условия: существуют элементы a, b и c такие, что: 1) а А, но

а В; 2) b A, но b B; 3) c A B .

Теорема о пяти возможностях. Для любых двух множеств А и В имеет место хотя бы один из следующих пяти случаев: 1) А=В; 2) А В; 3) В А; 4) A B ; 5) А и В находятся в общем положении (если оба множества А и В не пусты, то имеет место только один случай теоремы).

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

16

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

Строгое доказательство теоремы состоит в следующем. Пусть А и В

– любые множества. Допустим, что не выполнен каждый из случаев 2-5 этой теоремы (если для двух множеств А и В хотя бы один из случаев 2-5 имеет место, то терема доказан). Тогда покажем, что А=В. Предположи м противное, то есть А≠В. Это значит: а) существует такой элемент х, что х А и х В; б) существует такой элемент у, что у В и у А. В случае а) существует такой элемент z1, что z1 В и z1 А, так как не выполняется случай 3 этой теоремы. В случае б) существует такой элемент z2, что z2 А и z2 В, так как не выполняется случай 2 этой теоремы. Далее, так как случай 4 не имеет места, то существует элемент d, такой, что d A B . теперь получаем, что элементы в случае а) – х, d и z1, а в случае б) – у, d и z2 удовлетворяют условию, что множества А и В находятся в общем положении. Получили противоречие, так как, по допущению, случай 5 места не имеет. Следовательно, А=В. Теорема доказана.

Определение. Пересечением множеств A1, A2,…, An называется

всех и только тех элементов, которые принадлежат одновременно всем множествам A1, A2,…, An.

Пример 22. Пусть A1 – множество четных натуральных чисел; A2 – множество, состоящее из числа 10 и всех нечетных натуральных чисел, не делящихся на 5; A3 – множество натуральных чисел, делящихся на 5. Тогда

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

A \ B x | x A & x B .

Выражение А\В читается: «разность А и В» или «А без В».

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

Если А и В – множества, показанные на рис. 2, а, то множества А\В и В\А представляются заштрихованными фигурами на рис. 4, а и б соответственно.

17

а б

Рис. 4. Разность двух множеств А и В

Пример 23. Если А = {1, 2, 3, 4}, B = {1, 3, 5}, C = {5, 6}, то А\В ={2, 4}, А\C = C, B\C ={1, 3}, C\B ={6}, B\A ={5}.

Определение. Если в некотором рассмотрении все множества являются подмножествами некоторого фиксированного множества U, то это множество называется универсальным (для этого рассуждения) или универсумом рассуждения, или просто универсумом.

Так при рассмотрении множеств студентов в группе (отличники; студенты, получающие стипендию; студенты, проживающие в общежитии и т.д.) роль универсального множества играет множество студентов в группе.

Универсальное множество обладает интересным свойством, кото-

ство (см. рис. 5), в которое входят как все элементы множества А, так и все элементы множества А, так что A U будет состоять из тех же элементов, что и U, то есть представляет собой универсальное множество.

U

А

Рис. 5. Соотношение универсума U и произвольного множества А

Определение. Множество A , определяемое из соотношения A U \ A, называется дополнением множества А до универсального мно-

жества U (обозначается также CUA, СА или А’), то есть

A x | x U & x A .

18

На рис. 5 множество A представляет собой незаштрихованную область.

Пример 24. Если положить, что универсумом является множество

Определение. Симметрической разностью множеств А и В называется множество, обозначаемое через А В и определяемое следующим образом:

Выражение А В (иногда вместо А В пишут А-В, или А В, или А+В) читается: «симметрическая разность А и В» или «А симметрично В».

Если А и В – множества, показанные на рис. 2, а, то множество А В показано на рис. 6 в виде заштрихованной фигуры.

АВ

Рис. 6. Разность множеств А и В

Дизъюнктивная сумма получается объединением элементов множеств А и В за исключением тех, которые встречаются дважды.

Задача 26. Отобразите кругами Эйлера множества А, В, С, если известно, что А В и В С.

Ответ. См. рис. 7.

C

В

A

Рис. 7. Решение задачи 26

19