ЛЕКЦИЯ 1

 

ТЕМА: ОСНОВЫ ТЕОРИИ МНОЖЕСТВ.

ПЛАН:

1. Понятие множества. Способы задания множеств.
2. Отношения между множествами.
3. Операции над множествами.
4. Алгебра множеств.
5. Теорема о количестве подмножеств конечного множества.
6. Формула включений и исключений.

 

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

 

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

Множества обозначаются заглавными буквами латинского алфавита , а элементы множества- строчными.

Приведем примеры множеств.

Классы (множества) чисел: N – натуральные числа, Z – целые числа, Q- рациональные числа, R- действительные (вещественные) числа, C – комплексные числа.

Студенты одной группы – множество, элементы которого- студенты, общее свойство – обучение одной специальности.

Множество В – корни уравнения ½ = cosx . Элементы – вещественные числа, общее свойство – обращают данное уравнение в верное равенство.

Если х – элемент множества Х, то говорят: х принадлежит Х и пишут : хХ. Если х не принадлежит Х, то пишут хХ.

С видами множеств вы знакомились при изучении элементов высшей математики, поэтому лишь напомним их : конечные множества, бесконечные, пустые, универсальные.

Конечные и бесконечные множества в свою очередь подразделяются на неупорядоченные и упорядоченные; неупорядоченные бесконечные – на счетные и несчетные.

Рассмотрим два основных способа задания неупорядоченных множеств:

1.      перечисление всех его элементов;

2.      описание характеристического (общего) свойства его элементов.

 

Первым способом задаются конечные множества.

Примеры:

А – множество чисел, являющихся делителями числа 20: А = {1, 2, 4, 5, 10, 20}.

В – список группы: В = {Архипов, Белов,…}.

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

{x | P(x)} и читается так: множество всех х таких, что х обладает свойством Р(х).

Примеры:

{x | x R, x² – 4 = 0}  - это конечное множество и его можно задать перечислением элементов : {2, -2}.

{x | x  R, 2< x < 5 } – бесконечное несчетное множество, а именно, числовой промежуток (2, 5).

{x | x  R, 1= sinx} – бесконечное счетное множество.

{x | x  R, x² + 9 = 0 } – это пустое множество, т.к.  ни одно вещественное число не удовлетворяет данному уравнению.

 

2.      Отношения между множествами.

 

Рассмотрим отношения между неупорядоченными множествами.

Если каждый элемент множества А принадлежит множеству В, то А называют подмножеством множества В.

Обозначения: А  В ( А принадлежит В, А включено в В, А содержится в В и т.д.),

В  А ( В включает А, В содержит А и т.д.)

 

Множества А и В называются равными, если А  В и В  А.

Обозначение: А = В.

 

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

Обозначение: А  В.

 

Примеры:

N – множество натуральных чисел, М – множество четных чисел, тогда М  N.

Пусть Х – множество студентов группы, У – множество студентов данной группы сдавших экзамен, тогда можно построить отношение У  Х, т.к. возможно , что все студенты успевающие.

А = {1, 3, 5, 10}, B = {10, 1, 1, 5, 3, 5}. Данные множества равны А = В, действительно:    А  В и В  А.

Если U – универсальное множество некоторой теории, то любое множество этой теории является его подмножеством. Например, множество комплексных чисел С – универсальное множество в теории чисел. Для всех классов чисел можно построить цепочку включений:    N  Z  Q  R  C.

 

Свойства включений.

1.      Для всякого множества В : В  В;

2.      Для любых множеств А, В, С, если А  В и В  С, то А  С;

3.      Для всякого множества В :   В.

 

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

 

Над множествами можно выполнять действия (операции), напоминающие сложение и умножение чисел. Но не тождественные им.

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

Краткая запись: АВ = {x | x A или х В}.

Соответствующая диаграмма Эйлера – Венна:

 

                                                                                                                     

 

	АВ- заштрихованная область

 

 

              

 

 

 

 

 

Пример: А = {2, 5, 7, 9}, В = {3, 5, 8, 9, 12}.

АВ = {2, 5, 7, 9}{3, 5, 8, 9, 12}= {2, 5, 7, 9, 3, 8, 12}.

 

 

Соответствующая диаграмма:

 

                                                                                          

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

 

Краткая запись: АВ = {x | xA и хВ}.

Соответствующая диаграмма Эйлера- Венна:

 

 

АВ – заштрихованная область

             

 

 

 

 

 

 

 

 

Пример:  АВ= {2, 5, 7, 9}{3, 5, 8, 9, 12}= {5,9}.

 

Диаграмма:

 

 

 

 

 

 

 

 

 

 

 

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

Краткая запись: А\В = {x| x A и xB}.

Соответствующая диаграмма Эйлера- Венна:

 

 

 

			А\В- заштрихованная область

 

 

 

 

 

 

 

 

Пример: А\В = {2, 5, 7, 9}\{3, 5, 8, 9, 12}= {2, 7}.

Диаграмма:

 

 

 

 

 

 

 

 

 

 

Если АВ = , то А\В= А и В\А = В.

                                                                                           

 

 

 

 

 

 

 

 

А

В

Если А  В, то А\В = .                                                   

 

 

 

 

 

 

 

 

 

Если U – универсальное множество и А U, то разность U\A называется дополнением множества А до множества U и обозначается .

Краткая запись: = {x| xU и xA}.

Соответствующая диаграмма Эйлера- Венна:

 

 

 

 

 

 

 

 

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

Краткая запись: AB= {x| xA\B или xB\A}.                               

Соответствующая диаграмма Эйлера- Венна:

     

В

А

Пример: АВ = {2, 5, 7, 9}{3, 5, 8, 9, 12}= {2, 7, 3, 8, 12}.

Диаграмма:

        

 

 

                                                             

 

 

 

 

 

1        3       2

Пример: Найти множество: (АВ)(С\Q), где:    

    Расставим порядок действий и выполним их по порядку:

1).

2).

3).

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

 

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

 

1. Коммутативность  А;  

2. Ассоциативность   ;  

3. Дистрибутивность   

4. Закон поглощения     

5. Закон де Моргана       

6.

7. =А;  

8.     

9.     

10. 

11. 

12. 

13.  А\В=А

 

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

Заметим, что если в равенстве заменить  на , U на  и наоборот, то получим справедливое равенство.

 Этот закон называется принципом двойственности.

Докажем, например, справедливость равенства  аналитически и с помощью диаграмм Эйлера – Венна.

Пусть , что означает хU и хАВ. Отсюда следует, что хА и хВ, но тогда

Построим диаграммы для обеих частей равенства и сравним их.

Диаграмма для левой части :

                                                

 

 

 

 

 

 

 

В

А

Диаграмма для правой части:

                                             

 

 

 

 

 

 

 

 

Сравнивая диаграммы, убеждаемся в справедливости равенства.

Пользуясь тождествами можно производить преобразования над множественными выражениями и доказывать тождества.

Пример1: доказать тождество

Рассмотрим два способа: с помощью диаграмм и тождеств.

1 способ

Левая часть тождества  

 

           - результат

 

 

 

 

 

 

 

Правая часть тождества

 

           - результат

                                             

 

 

 

 

2 способ

Преобразуем левую часть тождества :

Тем самым доказали верность тождества.

Пример2: Доказать тождество:  Составить двойственное и тоже доказать.

Доказательство справедливости равенства и двойственного равенства с помощью диаграмм предлагаем выполнить самостоятельно.

Приведем доказательство справедливости данного равенства путем преобразований (доказательство для двойственного проведите самостоятельно):

Пример3: Доказать тождество:

Преобразуем правую часть тождества:

=А(ВС) = А(ВС).

Тождество доказано.

 

5.      Теорема о количестве подмножеств конечного множества.

 

Рассмотрим множество А = {1, 2, 3 }, где |A| = 3, и множество В = {5, 6, 7, 8}, где |B| = 4.

Составим всевозможные подмножества множества А:

А, , {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}.

Всего получили 8 подмножеств.

Составим всевозможные подмножества множества В:

В, , {5}, {6}, {7}, {8}, {5,6}, {5,7}, {5,8}, {6,7}, {6,8}, {7,8}, {5,6,7}, {5,7,8}, {6,7,8}, {5,6,8}.

Получили 16 подмножеств.

Используя результаты рассмотренных примеров, можно предположить справедливость следующего равенства: n = 2^m, где n – количество подмножеств данного конечного множества, m – мощность множества.

Справедливость предположения подтверждает теорема, которую мы примем без доказательства.

Теорема: Если для конечного множества А его мощность равна т, то количество всех подмножеств данного множества, обозначаемое Р(А), равно 2^т.

Пример: Вычислить количество подмножеств множества М – делителей числа 20.

Составим множество М и найдем его мощность :

М = {1,2,4,5,10,20}. Мощность |M| = 6, тогда количество подмножеств равно Р(М) = 2⁶ = 64.

 

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

 

Проиллюстрируем теперь применение операций над множест­вами для решения задач о нахождении числа элементов мно­жеств, заданных несколькими условиями. Ниже мы будем рас­сматривать только конечные множества.

Пример:  В классе 30 учащихся, 16 из них занимаются му­зыкой, 17 увлекаются теннисом, а 10 занимаются и музыкой, и теннисом. Есть ли в классе ученики, равнодушные и к музыке, и к теннису, и если есть, то сколько их?

Решение: Если сложить число учащихся, интересующихся музыкой, с числом учащихся, занимающихся теннисом, т. е. 16+17=33, то учащиеся, интересующиеся и музыкой, и тенни­сом, окажутся учтенными дважды. Поэтому, чтобы определить число учащихся, интересующихся музыкой или теннисом, нужно из суммы 16+17 вычесть число учащихся, учтенных дважды, т. е. тех, кто интересуется и музыкой, и теннисом. По условию их 10. Таким образом, число интересующихся теннисом или музы­кой равно: 16+17—10=23 ученика. А так как в классе всего 30 учащихся, то 30—23 ==7 учащихся равнодушны и к музыке, и к теннису.

Задача решена по следующему алгоритму: пусть имеется два конечных множества А и В. Тогда:

п(АВ) = п(А) + п(В )- п(АВ) (1)

В нашем случае А — множество учащихся, интересующихся му­зыкой, и n(A) = 16, В—множество учащихся, интересующихся теннисом, и n(B) = 17, n(AB) =10, и тогда по полученной формуле  n(AUВ)=16+17-10=23.

Усложним задачу: пусть к тем, кто интересуется в классе му­зыкой — множеству А, и к тем, кто увлекается теннисом — мно­жеству В, добавляются еще и те, кто интересуется театром— множество С. Сколько учеников увлекается или музыкой, или теннисом, или театром, т. е. чему равно число n{ABC)?

Если множества А, В и С пересекаются лишь попарно, т. е. АВС=, то подсчет можно вести, как и прежде: снача­ла сложить п(А)+п(В)+п(С), а затем вычесть число тех эле­ментов, которые подсчитаны дважды, т. е. вычесть число n{AB}+n(AC)+n(BC). Если же множество АВС,, то его элементы оказались неучтенными: сначала их трижды учли, когда складывали п(А}+п (В)+п(С), а затем трижды отнимали их, вычитая n{AB}+n(AC)+n(BC). Таким об­разом, число                                                           п(А)+п(В)+п(С )- (n{AB}+n(AC)+n(BC))

меньше истинного результата ровно на число элементов в пере­сечении множеств АВС, которое и следует добавить для по­лучения верного результата:

п(А)+п(В)+п(С )- (n{AB}+n(AC)+n(BC))+п(АВС) (2)

 

Аналогичная формула может быть получена для любого числа множеств.

В формулах (1) и (2) подсчитывается, сколько раз каждый элемент включается и исключается, поэтому их называют фор­мулами включений и исключений.

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

Пример1: На вступительном экзамене по математике были предложены три задачи: по алгебре, планиметрии и стереометрии. Из 1000 абитуриентов задачу по алгебре решили 800, по планиметрии — 700, а по стереометрии — 600 абитуриентов. При этом задачи по алгебре и планиметрии решили 600 абитуриен­тов, по алгебре и стереометрии — 500, по планиметрии и стерео­метрии — 400. Все три задачи решили 300 абитуриентов. Суще­ствуют ли абитуриенты, не решившие ни одной задачи, и если да, то сколько их?

Решение. Пусть U — множество всех абитуриентов, А —. множество абитуриентов, решивших задачу по алгебре, В — множество абитуриентов, решивших задачу по планиметрии, С — множество абитуриентов, решивших задачу по стереометрии. По условию n(U) =1000, n(A) = 800, n(В)=700, n(С)=600, n(AB)= 600, n(AC) = 500, n(BC) = 400, n(ABC) =300. В множество ABC  включены все абитуриенты, решившие хо­тя бы одну задачу. По формуле (2) имеем:

n(А U В U С) == 800 + 700 + 600 - 600 - 500 - 400 + 300 =900.

Отсюда следует, что не все поступающие решили хотя бы одну задачу. Ни одной задачи не решили

n(U) - n(AUBUC)=1000 - 900==100 (абитуриентов).

Пример2: Социологи опросили 45 учащихся девятых клас­сов, среди которых 25 юношей. При этом выяснилось: 30 человек имеют за полугодие оценки 4 и 5, из них 16 юношей, спортом занимаются 28 учеников, среди них 18 юношей, и 17 учеников, успевающих только на хорошо и отлично, 15 юношей учатся на хорошо и отлично и занимаются спортом.    Первый математик класса взглянул на результаты и заявил, что там есть ошибки. Как это ему удалось выяснить?

Решение: Обозначим через А множество юношей, В — множество успевающих на 4 и 5, С — множество спортсменов. По условию задачи n(A)=25, n(В)=30, n(С)=28, n(AB)=16, n(AC)=18, n(BC)=17, n(ABC)=15. Найдем общее чис­ло учащихся, которые или являются юношами, или занимаются спортом, или успевают на 4 и 5. По формуле (2) получаем:

n (A UBUC)=25+30+28- 16- 18- 17+15=47. Этого быть не может, так как обследовалось всего 45 учеников! Следовательно, в данных сведениях есть ошибки.

На рисунке  это решение проиллюстрировано с помощью диаграммы Эйлера — Венна. В пересечении множеств А, В и С за­пишем число 15, так как по условию n(ABC)=15. В мно­жестве AB\С запишем число 16—15=1, в множестве BC\А - число 18-15=3, в множестве BC\А—число 17-15=2, в множестве A\(BC)— число 25-(1+15+3)=6, в множестве В\(А C) — число 30-(1 + 15+2)= 12, в множест­ве С\(АВ)— число 28-(3+15+2)=8. Чтобы найти n(АВС), достаточно сложить записанные числа, поскольку они соответствуют множествам, не пересекающимся между со­бой. Получим число 47 > 45, что невозможно по условию задачи.

 

 

 

                                                                       

 

Задачи для самостоятельного решения

 

1.              Опишите множество М точек на плоскости: a) {M| OM = R}; б) {M| OM R};               в) {M| AM = MB}.

2.              Даны множества :  Построить множество ((АВ)(В\С)) . Найти количество подмножеств построенного множества. Показать соответствующую диаграмму Эйлера – Венна.

3.              Доказать с помощью диаграмм Эйлера – Венна справедливость закона поглощения.

4.              Доказать тождества с помощью диаграмм и путем преобразований:

5.              В отделе института работают несколько человек. Каждый из них знает хотя бы один иностранный язык, причем: 6 знают немецкий, 6 – английский, 7 – французский, 4 – английский и немецкий, 3 – немецкий и французский, 2 – французский и английский, 1 – все три языка. Сколько всего человек работает в отделе? Сколько из них знают только английский?

6.              Из 35 учащихся класса 20 посещают математический кружок, 11 – физический, 10 – не посещают кружки. Сколько учеников посещают математический и физический кружки одновременно, сколько – только математический?

 

Контрольные вопросы

 

1.      Объясните понятие множества. Приведите примеры множеств. Как обозначаются множества и их элементы?

2.      Какие существуют способы задания множеств?

3.      С помощью характеристического свойства задайте конечное, бесконечное несчетное, бесконечное счетное и пустое множества.

4.      Как обозначается принадлежность элемента множеству и не принадлежность?

5.      Какие существуют отношения между двумя множествами?

6.      Перечислите операции над множествами с приведением соответствующих диаграмм Эйлера – Венна.

7.      Перечислите тождества алгебры множеств.

8.      Сформулируйте теорему о количестве подмножеств конечного множества.

9.      Запишите формулы количества элементов в объединении двух и трех множеств.