9957

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

Пример 1.4. Проверить с помощью диаграмм Венна дистрибутивный закон.

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

11

Пример 1.5. Записать формулу, соответствующую заштрихованной части диаграммы Венна

В результате получили формулу ( А В) \ С.

Пример 1.6. Выполнить операции над множествами, заданными формулой: M ÷ U , где М – произвольное множество, U – универсум.

Решение. Вначале выражаем симметрическую разность через объединение двух разностей: А ÷ U = (М \ U) (U \ М ) .

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

Если из универсума U вычесть произвольное множество М, то будет

получено дополнение М . Выполняя дополнение дополнения, получим М = М .

А ÷ U = (М \ U ) (U \ М ) = М = М = М .

Пример 1.7. Упростить выражение

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

Пример 1.8. Доказать, что A \ (B È C ) = (A \ B)Ç (A \ C ).

12

AÈB = A + B - AÇB .

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

13

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

AÈBÈС = A + B + С - AÇB - AÇС - ВÇС + AÇBÇС .

Установим теперь общую формулу для нахождения числа элементов суммы A1 È A2 È...È An подмножеств множества А, где А – множество всех m

предметов, а Ai - подмножество всех тех предметов, каждый из которых обладает i- м свойством.

Теорема. A1 È A2 È...È An = A1 + A2 +...+ An - A1 Ç A2 - A1 Ç A3 - … - An−1 Ç An + A1 Ç A2 Ç A3 +...+ An−2 È An−1 Ç An -...+ (-1) n−1 A1 Ç...Ç An (1).

Замечание. Правая часть этого равенства является суммой n слагаемых, k -е слагаемое имеет вид (-1)k −1 Sk ( A1 Ç A2 Ç...Ç An ), где Sk ( A1 Ç A2 Ç...Ç An ) –

есть сумма чисел N ( Ai1 Ç Ai2 Ç...Ç Aik ) по всем возможным пересечениям ровно

к разных множеств из множеств A1 , A2 ,... An . Если мы пересекаем нечетное количество множеств, то мощность этого пересечения берется со знаком «плюс», а если четное, то со знаком «минус», причем учитываются всевозможные пересечения заданных n множеств.

При выводе формулы (1) подсчитывают для каждого элемента, сколько раз он включается и сколько раз он исключается, поэтому ее называют

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

Пример 1.11. Каждый ученик класса – либо девочка, либо блондин, либо любит математику. В классе 20 девочек, из них 12 блондинок, и одна блондинка любит математику. Всего в классе 24 ученика-блондина, математику из них 12, а всего учеников (мальчиков и девочек), которые любят математику 17, из них 6 девочек. Сколько учеников в данном классе?

Решение. Если А – множество девочек, В – множество блондинов, С – учеников, которые любят математику, то AÈBÈС - искомое число. АÇВ – множество блондинок, АÇС – множество девочек, которые любят математику,

14

ВÇС – множество всех блондинов (мальчиков и девочек), которые любят математику, АÇВÇС – множество блондинок, которые любят математику.

Тогда AÈBÈС = A + B + С - AÇB - AÇС - ВÇС + AÇBÇС =

=20+24+17- (12+6+12)+1=32.

Пример 1.12. В НИИ работают 67 человек. Из них 47 знают английский язык, 35 – немецкий язык, 20 – французский язык, 23 знают английский и немецкий, 12 – английский и французский, 11 – немецкий и французский, 5 – все три языка. Сколько человек в институте не знают ни одного языка?

Решение. Применим формулу (1): 67-47-20-35+23+12+11-5=46-40=6.

Итак, сначала из общего числа сотрудников вычитают число тех, кто знает один из языков (и может быть другие). При этом некоторые оказываются «вычтенными» дважды, поскольку знают два языка, поэтому прибавляют числа 23, 12, 11, показывающие, сколько человек владеют двумя языками (и может быть еще и третьим). Но лица, владеющие тремя языками, оказываются сначала трижды «вычтенными», а потом трижды «прибавленными». Так как их надо все-таки вычесть, то приходится еще отнять число 5.■

Пример 1.13. Система классификации получает на вход устройство, данные о котором заносит в таблицу «Оборудование» для дальнейшей обработки информации. Таблица содержит поля «Устройство», «Назначение» и «Год выпуска» с символьными именами А, В и С соответственно. Система формирует запросы, представленные в таблице:

16

Решение:

Двумя полями и возможными их значениями множество записей в базе данных разбивается на шесть непересекающихся подмножеств: A, B, C, D, E, F. Запросы, удовлетворяющие этим множествам, представлены в таблице:

Запросу (A≠«printer») или (С≠2012) удовлетворяет множество записей, равное объединению множеств Р = А В С и Q = А В D E ,

отвечающих запросам (A≠«printer») и (С≠2012) соответственно. Мощность объединения этих множеств равна:

P È Q = P + Q - P Ç Q = A + B + C + A + В + D + Е - ( A + В) = = A + B + C + D + Е = 37

Запросу (С≠2010) и (С≠2003) удовлетворяет множество записей С F ,

мощность которого равна C + F =11.

Запросу «неверно, что ((A=«monitor») и (С=2012))» удовлетворяет

A + B + С + D + Е + F . Суммируя правые и левые части уравнений системы,

17

получим A + B + С + D + Е + С + F + A + B + D + Е + F = 37 +11 + 34 2 × ( A + B + С + D + Е + F ) = 82

Ответ: A + B + С + D + Е + F = 41

Задачи.

1. Сколько элементов в каждом из множеств:

5){1, {}1 , 2, {1,{2,3}}, }

2.Какие из следующих утверждений верны:

1){1,2} {{1,2,3}{, 1,3},1,2}

3.Известно, что А Í В и аÎ А. Какие из следующих утверждений верны:

1)аÏ В

2)аÎ В

3)А В

4)аÎ А È В

5)аÎ А Ç В

6)аÎ А \ В

7)аÎ А ¸ В

8)а Í А

9){а} А

18

4.Известно, что {а} В. Является ли число 2 элементом множеств:

A = {1,3,5,6}, B = {- 3,0,1,2,4}, C = {x x2 = 4x - 4}

5.Перечислите все элементы следующих множеств:

3) множество всех двузначных натуральных чисел, делящихся на 5, но не делящихся на 10.

6.Перечислить все элементы множества: а) {x x Í {}1 }; б) {x x Í {1,2,3}}.

7.Перечислите все подмножества множества {{1,2}, {3},1}, {{}1 , {2},1,2}.

8.Докажите, что {{1,2}, {2,3}} ¹ {1,2,3}.

9.Проверьте, что А и 2 А имеют общий элемент, если А = {1,2, {1,2}}.

10.Пусть А = {1,4,5}, В = {2,4,6}. Найдите А È B, А Ç B, А \ B, B \ А, А ÷ B, 2 А .

11.Соедините знаком включения следующие пары множеств:

1)A = {x Î R lg x = 2 - lg5}, B = {20,30};

2)A = {x Î R x2 - 7x +12 = 0}, B = {x Î R x3 - 7x2 + 12x = 0}.

12. Пусть U – множество сотрудников некоторой фирмы. А – множество всех сотрудников старше 35 лет. В – множество сотрудников, имеющих стаж работы более 10 лет, С – множество менеджеров фирмы каков содержательный смысл (характеристическое свойство) каждого из следующих множеств:

а) B ; б) А Ç В Ç С ; в) А È В Ç С ; г) В \ С ; д) С \ В.

13. В результате поиска в Интернете выданы адреса Web-страниц www.cont1,

www.cont3, www.st1, www.st2, www.inf.au содержат информацию о книгах

по техническим наукам, страницы www.st1, www.st2, www.st3, www.inf.ru,

www.inf.au – сведения о периодических изданиях, адрес www.inf.au

19

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

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

а) Если АÍВ и ВÍС, то АÍС

б) Если АÍВ и ВÌС, то АÌС

г) Если АÌВ и ВÍС, то АÌС

д) Если АÌВ и ВÌС, то АÌС

15.Приведите пример множеств А, В, С, Д, Е, удовлетворяющих одновременно следующим условиям: АÌВ, ВÎС, СÌД, ДÌЕ.

16.Приведите пример множеств А, В, С таких, что

1)A B, B C, A C

2)A B, A C, C B

3)A B, B C, A C

17.Какие из следующих утверждений верны для всех множеств А, В, С: 1) Если АÏВ и ВÏС, то АÏС.

2) Если А¹В и В¹С, то А¹С.

3) Если АÎВ и не верно, что ВÍС, то АÏС.

18.Доказать, что А Ì В тогда и только тогда, когда А \ В = Æ.

19.Доказать, что А = В тогда и только тогда, когда А ÷ В = Æ.

20. Доказать, что 2 AÇB = 2 A Ç 2 B , где 2А – множество всех подмножеств множества А.

21. Обследование 100 студентов дало следующие результаты о количестве студентов, изучающих различные иностранные языки: испанский 28; немецкий 30; французский 42; испанский и немецкий 8; испанский и французский 10; немецкий и французский 5; все три языка 3.