Лекция: Множества

5

Тема 1.1. Основы теории множеств. (4 часа).

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

З1: основные принципы математической логики, теории множеств и теории алгоритмов

ОК2, ПК 1.1

СОДЕРЖАНИЕ ЗАНЯТИЯ

Изучение нового материала

Вопросы (план)

1. Основные понятия теории множеств. 1

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

3. Алгебра множеств – операции. 4

4. Геометрическая интерпретация множеств 4

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

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

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

Множество относится к категории наиболее общих, основополагающих понятий математики. Поэтому вместо строгого определения обычно принимается некоторое основное положение о множестве и его элементах. Так, группа выдающихся математиков, выступающая под псевдонимом Н. Бурбаки, исходит из следующего положения: “Множество образуется из элементов, обладающих некоторыми свойствами и находящихся в некоторых отношениях между собой или с элементами других множеств. ” В нашей же книге приведено следующее определение этого понятия:

Множество - начальное, неопределяемое понятие в математике. Под множеством понимается объединение отдельных объектов (элементов множества) в единое целое.

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

1. Основные понятия теории множеств.

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

Элементами множества мы будем называть объекты, которые образуют данное множество, и обладают некоторыми свойствами и находятся в некоторых отношениях между собой или с элементами других множеств.

Элементы множества сами могут являться некоторыми множествами. Например, одна книга из множества книг в шкафу может рассматриваться как множество страниц. Множества обозначают заглавными, а элементы множеств - строчными латинскими буквами.

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

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

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

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

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

Подмножества, равенство множеств

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

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

Например, множество конденсаторов электронной сети является подмножеством всех ее компонентов, множество положительных чисел является подмножеством множества действительных чисел.

Отличия А В и А  В заключается в том, что отношение А В допускает и тождественность (А = В), т. е. любое множество можно рассматривать как подмножество самого себя (А  А), в то время как символ строго включения А В ставится тогда, когда в множестве В содержатся не только элементы множества А. Выполнение соотношений А В и В А возможно только при А = В. И обратно, А = В, если А В и BА. Эти соотношения являются признаком равенства множеств через отношение включения.

Конечные и бесконечные множества

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

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

Совершенно очевидно, что множество цифр в десятичной системе счисления конечно: A={1,2,3,4,5,6,7,8,9,0}, а множество точек окружности бесконечно.

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

1) Множество можно задать простым перечислением его элементов А = {a₁, a₂,... , a_n} . Но этот способ не пригоден для задания бесконечных множеств и даже в случае конечных множеств часто практически нереализуем. Ведь не пересчитаешь количество рыб в Тихом океане, хотя совершенно очевидно, что их множество конечно.

2) Один из способов задания множества состоит в описании элементов определяющим (характеристическим) свойством:

Множество Х = {х| Р(x) },

где Р(х) - предикат, описывающий элементы х множества Х. Р(х) - например, есть множество животных с хоботом - множество слонов.

Или, например, пусть A-множество всех натуральных чисел. Тогда ясно, что 0.75 А, а также крокодил или планета Сатурн не принадлежат данному множеству.

В геометрии часто приходится иметь дело с множествами, заданными своими характеристическими свойствами. Так, определение “окружностью называется геометрическое место точек плоскости, равноудаленных от данной точки этой плоскости” означает, что множество точек плоскости, равноудаленных от данной точки этой плоскости, совпадет с множеством точек некоторой окружности.

Примеры:

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

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

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

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

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

{x | x  R, 2x

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

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

Пустое и универсальное множества

Пустым называется такое множество, которое не содержит никаких элементов.

Обычно пустое множество обозначают символом: 

Роль пустого множества аналогична роли числа нуль. Это понятие можно использовать для определения заведомо несуществующей совокупности элементов (например, множества зеленых слонов). Более существенным мотивом введения пустого множества является то, что заранее не всегда известно (или неизвестно вовсе) существуют ли элементы, определяющие какое-то множество. Например, множество выигрышей в следующем тираже спортлото на купленные билеты может оказаться пустым. Пустое множество является подмножеством любого множества, т.е.   А, где А - любое множество.

Универсальным называется множество, которое содержит все возможные элементы, встречающиеся в данной задаче (U).

Например: имеется группа студентов. A - множество юношей группы, B - множество отличников. В данной задаче универсальным является множество cтудентов группы, а множества A и B являются его подмножествами: A U, B U .

Мощность множества. Упорядоченные множества

Число элементов в конечном множестве М называется мощностью М и обозначается |M|.

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

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

A= , в более общем случае: A=, n=1,n

В=(а,в,с)

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

Применение аппарата теории множеств

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

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

1. Алгебра множеств – операции.

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

Объединение (сумма) A B есть множество, которое содержит все элементы, входящие либо в A, либо в B, либо в A и B одновременно.

А={a, b, m}; В={n, c, p}; А В={a, b, c, m, n, p}

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

А - множества успевающих учеников,

В - множества девочек,

С - множества неуспевающих мальчиков.

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

А = {1, 2, ..., 59}; В = {2, 4, ..., 80}; А∩В = {2, 4, ..., 58}

Пересечением множеств А и В предыдущего примера будет множество успевающих девочек.

Разность A\B есть множество, содержащее все элементы A, не входящие в B.

А = {a, b, ..., p}; В = {a, b, ..., k}; А \ В = {l, m, n, o}

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

Дополнение (отрицание) A есть множество U\A. Обозначается

или -A.

Читается “не А”

Дополнением множества В (множества девочек) будет множество мальчиков.

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

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

1. Геометрическая интерпретация множеств

Диаграммы Эйлера-Венна – геометрические представления множеств. Построение диаграммы заключается в изображении большого прямоугольника, представляющего универсальное множество U, а внутри его – кругов (или каких-нибудь других замкнутых фигур), представляющих множества. Фигуры должны пересекаться в наиболее общем случае, требуемом в задаче, и должны быть соответствующим образом обозначены. Точки, лежащие внутри различных областей диаграммы, могут рассматриваться как элементы соответствующих множеств. Имея построенную диаграмму, можно заштриховать определенные области для обозначения вновь образованных множеств.

Операции над множествами рассматриваются для получения новых множеств из уже существующих.

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

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

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

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

О пределение. Абсолютным дополнением множества А называется множество всех тех элементов, которые не принадлежат множеству А (рис. 5):

Приоритет операций в алгебре множеств.

1. отрицание A

2. A∩ B

3. AB

4. A\B

Пусть нужно расставить скобки в формуле:

E=A\B ∩ D\B, то, с учетом приоритетов, следует сделать так:

E=(A\(B (()∩ D)))\B.

Законы и тождества алгебры множеств.

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

Таблица 1

Примеры решения типовых задач

Пример 5. С помощью диаграмм Эйлера – Венна проиллюстрируем справедливость соотношения  (рис. 6).

Убедились, что в обоих случаях получаем равные множества. Следовательно, исходное соотношение справедливо.

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

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

Рис.8

Запишем сначала А В,

Рис.9

затем (А В)\С, получим:

Рис.10

 Доказать следующее тождество .

Решение.

Докажем это тождество двумя способами: аналитически (используя равносильности алгебры множеств) и конструктивно (используя диаграммы Эйлера-Венна).

1.

2. Построим соответствующие диаграммы Эйлера-Венна (рис. 7).

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

Рассмотрим множество А = {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.

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

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

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

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

Вопросы для закрепления изученного материала:

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

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

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

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

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

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

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

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

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

Информационное обеспечение обучения:

1. Математическая логика и теория алгоритмов : учебное пособие / сост. А. Н. Макоха, А. В. Шапошников, В. В. Бережной ; Министерство образования Российской Федерации и др. – Ставрополь : Северо-Кавказский Федеральный университет (СКФУ), 2017. – 418 с. – Режим доступа: по подписке. – URL: https://biblioclub.ru/index.php?page=book&id=467015 – Библиогр. в кн. – Текст : электронный.

2. Математика и информатика : учебник и практикум для среднего профессионального образования / Т. М. Беляева [и др.] ; под редакцией В. Д. Элькина. — 2-е изд., перераб. и доп. — Москва : Издательство Юрайт, 2021. — 402 с. — (Профессиональное образование). — ISBN 978-5-534-10683-1. — Текст : электронный // Образовательная платформа Юрайт [сайт]. — URL: https://urait.ru/bcode/469943

3. Перемитина, Т.О. Математическая логика и теория алгоритмов / Т.О. Перемитина ; Министерство образования и науки Российской Федерации, Томский Государственный Университет Систем Управления и Радиоэлектроники (ТУСУР). – Томск: ТУСУР, 2016. – 132 с.: ил. – Режим доступа: по подписке. – URL: http://biblioclub.ru/index.php?page=book&id=480886.