Лекция 1. Начала теории множеств.

Элементы дискретной математики

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

СОДЕРЖАНИЕ:

Лекция 1.Начала теории множеств

Лекция 2.Комбинаторика

Лекция 3.Алгебра высказываний и булева алгебра.

Лекция 4.Событие и вероятность

Лекция 5.Дискретные и непрерывные случайные величины

Лекция 6.Элементы математической статистики

Лекция 7.Элементы теории графов. основные понятия.

Лекция 1. Начала теории множеств.

Цель: Изучить основные понятия теории множеств.

План:

1. Понятие множества

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

3. Отображения множеств.

3. Вопросы для контроля знаний и подведения итога прочитанной лекции

1. Понятие множества. Множество — это совокупность, собрание каких-либо объектов, объединяемых общим признаком или свойством. Эту фразу нельзя рассматривать как определение понятия «множество», так как в ней слово «множество» заменено столь же неопределенным термином «совокупность». Так, можно говорить о множестве всех студентов данного курса, о множестве телевизоров с цветным изображением в данной аудитории, о множестве всех натуральных чисел и т.д. Объекты, входящие в данное множество, будем называть элементами множества.

Множества будем обозначать прописными (большими) латинскими буквами А, В, С, ... , X, Y, ... , а их элементы — малыми буквами а, b, с, ..., х, у, ... .

Если элемент а является элементом множества А, то пишут а Î А (читается «а принадлежит А», или «а из А»). В этом случае говорят также, что «а содержится в А», «а входит в А» и т. п.

Если а не является элементом множества А, то будем писать аÏ А («а не принадлежит А» или «а не содержится в А» и т.д.).

Если элементами множества являются числа, то оно называется числовыми.

Многие из числовых множеств имеют специальные названия и обозначения. Таковы, например, сегмент, или отрезок [а, Ь], по­луинтервалы [а, b) и (а, b] (см. подразд. 2.1, п. 1).

Множество всех целых положительных чисел 1, 2, 3, ... n, ... называют натуральным рядом и обозначают N.

Множество всех действительных чисел обозначают R, или (-∞, +∞) (см. подразд. 2.1, п. 1).

Если множество содержит лишь конечное число элементов, то оно называется конечным. В противном случае множество называется бесконечным. Например, множество листьев на дереве или множество слушателей в данной аудитории — конечные множества; множество точек на плоскости — бесконечное множество. Числовые множества N, R,, [а, b] (при а ≠ b] также бесконечны.

Существуют разные формы задания множества. Наиболее простая состоит в указании всех элементов множества. Так, запись A = {1, 2, 3} означает, что множество A состоит из трех элементов 1, 2 и 3. Если число элементов бесконечно, то используется многоточие. Например, множество всех натуральных чисел записывается так: N= {1, 2, 3,...}. Иной способ задания множества состоит в описании элементов определяющим свойством Р(х) (формой от х), общим для всех элементов А = {х: Р(х)}. Например, А = {х: х = 2k, k = 1, 2, ...} означает, что множество А состоит из четных положительных целых чисел 2, 4, 6, ... .

Если множества А и В состоят из одних и тех же элементов, т. е. если каждый элемент множества А является элементом множества В и, наоборот, каждый элемент множества В является элементом множества A, то множества А и В равны (тождественны, совпадают). Таким образом, множество однозначно определяется своими элемен­тами и не может содержать одинаковых элементов. Если множества А и В равны, то пишут А = В. Например, {1, 2} = {2, 1}.

Пусть теперь имеются два множества А и В, относительно которых известно только, что каждый элемент множества В является элементом множества А. В этом случае говорят, что В есть подмножество А, и пишут В ÌА (“Ì “ - знак включения). Говорят еще, что «А содержит В» или «В включено в А». В частности, В может совпадать с А.

Пример 11.1.Множество четных чисел есть подмножество множества целых чисел.

Теорема 11.1. Если В Ì А и А Ì В, то А = В.

Доказательство. Из В Ì А следует, что любой элемент из В является элементом множества А, а из А Ì В — что любой элемент из А является элементом множества В, т.е. множества А и В состоят из одних и тех же элементов и, значит, А = В.

Обычно приходится рассматривать множества А, В, С и т.д., которые являются подмножествами некоторого достаточно обширного множества, рамки которого определяются целями нашего исследования. Такое исходное множество называется универсальным и обозначается через U. Если изучаются всевозможные числовые множества, то универсальным будет множество всех действительных чисел.

Множество, не содержащее ни одного элемента, называется пустым. Его обозначают Æ. Примерами пустого множества могут служить: множество людей на Солнце, множество действительных корней уравнения х² + 1 = 0.

Теорема 11.2. Пустое множество является подмножеством любого множества А.

Доказательство. Из определения подмножества следует, что В является подмножеством А, если В не содержит элементов, не являющихся элементами А. Но пустое множество не содержит ни одного элемента, поэтому оно не содержит и элементов, не принадлежащих А. Отсюда следует, что пустое множество есть подмножество любого множества А.

2. Операции над множествами.Пусть даны два множества А и В.

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

Обозначается: С = А È В (или С = А + В). Знак «È» называется знаком объединения.

На рис. 11.1 изображены два множества точек плоскости: круг А и круг В. Их объединение — это область, покрытая или горизонтальной, или вертикальной штриховкой.

Заметим, что А È А = А. В общем случае А с А и В так же, как и В с А и В.

Пример 11.2. {1, 2, 3}È{2, 3, 4} = {1, 2, 3, 4}.

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

Обозначается: С = А Ç В (или С = А В). Знак Ç называется знаком пересечения. На рис. 11.1 пересечение множеств А и В — это область покрытая и горизонтальной, и вертикальной штриховкой.

Заметим, что А Ç А = А. В общем случае (А Ç В) Ì А и (А Ç В) Ì В.

Пример 11.3. {1, 2, 3} п {2, 3, 4} = {2,3}.

Для некоторой пары множеств может оказаться, что их пересечение — пустое множество. Так, например, {1, 2, 3} Ç {5, 6, 7} = Æ. Пустым будет и пересечение множеств А и B, изображенных на рис. 11.2.

Множества, пересечение которых пусто, называются непересекающимися.

Введенные операции объединения и пересечения множеств легко обобщаются на большее чем два число множеств. Так, множество С называется объединением множеств А₁ ÈА₂ È ... А_п, если С состоит из всех тех элементов, которые принадлежат хотя бы одному из множеств А_k, k=1,2,..., п. Обозначается С = А₁ ÈА₂ È ... А_п , или кратко С = . На рис. 11.3 изображено объединение множеств А₁, А_2,, A₃ (вся заштрихованная область).

Аналогично множество С называется пересечением или общей частью множеств А_ь А₂,..., А„, если оно состоит из всех тех элементов, которые принадлежат всем множествам А_k,, к =1, 2,..., п. Обозначается С = А₁ ÇА₂Ç ... А_п или кратко С = .

На рис. 11.4 пересечение множеств А_ь А_2> А₃ — область, покрытая тройной штриховкой.

Введем еще одну операцию — вычитание множеств. Пусть имеются два множества А и В.

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

Разность множеств А и В обозначается А\В. При этом В может содержаться в множестве А полностью, частично или совсем не включаться. На рис. 11.5, а — в изображены эти три случая. Разность А\В каждый раз заштрихована. Заметим, что в последнем случае, т. е. когда А Ç В = Æ, разность А\В = А. В общем случае А\В Ì А.

б

Рис. 11.6

Если A Ì В, то разность А\В называется дополнением множества А до множества В. Дополнение некоторого множества А до универсального множества U обозначается или ùА. Таким образом, если А Ì В, то U можно представить в виде объединения двух непересекающихся множеств:

U = А È В

Говорят при этом, что множество U разбито на два множества на А и . Аналогичному разбиению можно подвергнуть множество А, или множество , или то и другое. При этом мы получим более мелкое разбиение исходного множества U. Этот процесс можно продолжить и далее. В итоге получим представление множества U в виде объединения попарно непересекающихся подмножеств: кратко U = , где А_i ÇА_j=Æ, если i≠j .

Для наглядного изображения соотношений между подмножествами какого-либо универсального множества используют диаграммы Эйлера-Венна (Джон Венн (1834—1923) — английский математик.). Само универсальное множество U, изображают в виде прямоугольника, а его подмножества — в виде кругов, расположенных внутри прямоугольника. Множества, полученные в результате операций над множествами А и В, изображены на рис. 11.6, а — в заштрихованными областями. Непересекающиеся множества, изображаются неперекрывающимися областями (рис. 11.7, а), а включение множества соответствует области, целиком располагающейся внутри другой (рис. 11.7, б). Дополнение множества А (до U), т.е. множество А изображается той частью прямоугольника, которая лежит за пределами круга, изображающего А (рис. 11.7, в).

Рис. 11.7

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

1. = А;

2. А È А = А, А ÇA = А;

3. А È = U, А Ç = А,

4. А È U = U, А Ç U = А,

5. А È Æ= А, А ÇÆ = Æ,

6. (закон де Моргана), (закон де Моргана);

7. АÈВ= В ÈА (коммутативность и),

А ÇВ = ВÇА (коммутативность п

8. А È (В È С) = (А È В) È С (ассоциативность È),

А Ç (В Ç С) = (А Ç В) Ç С (ассоциативность Ç)

9.А È (В ÇС) = (А È В) Ç (А È С) (дистрибутивность È относительно Ç);

А Ç (В È С) = (А Ç В) È (А Ç С) (дистрибутивность Ç относительно È).

Проверим для примера закон де Моргана . Пусть х Î . Тогда хÎ U и хÏ АÈВ. Следовательно, х Ï А и х Ï В. Отсюда хÎ и хÎ , ипотому х Î Ç . Таким образом,

(11.1)

Если теперь хÎ Ç , то х Î и х Î . Отсюда х Î U и х Ï А, х Ï В. Значит, хÏ А È В, т. е. х Î . Итак,

(11.2)

Включения (11.1) и (11.2) в силу теоремы 11.1 и доказывают закон де Моргана.

Пользуясь операциями объединения, пересечения и вычитания множеств, можно из некоторых исходных множеств А, В, С и т.д. по­лучать новые множества: (АÈВ) Ç , (A\ ) È( \С) и т.д. К этим множествам можно применять указанные операции и получать еще более сложные выражения и т.д. Законы 1 — 9 позволяют преобразовывать эти выражения, упрощать их, из одних получать другие. Таким образом, получаем исчисление множеств, или алгебру множеств. Это исчисление является примером так называемой булевой алгебры, или алгебры Буля.

4. Отображения множеств.Пусть имеются два множества D и Е. Это могут быть множества совершенно различной природы. Например, может быть, что D— это множество людей, населяющих земной шар, а Е — шкала цветов.

Предположим, что существует правило, по которому каждому элементу из D ставится в соответствие определенный элемент из Е. Тогда это правило называют отображением множества D в Е (рис. 11.8).

Например, каждому человеку земного шара можно поставить в соответствие цвет его волос. Так будет определено отображение множества людей в шкалу цветов. Подобно этому можно определить отображение множества людей в множество имен, множества книг в множество языков и т.д. Вместо слова «отображение» говорят также «функция» и, если задано отображение множества D в Е, то говорят, что на множестве D задана (определена) функция со значениями в Е. Для обозначения функции мы будем, как правило, использовать букву f. Эта договоренность не помешает нам при нужде использовать и другие буквы g, h, f, С и т. п.

Если на множестве D определена некоторая функция f со значениями в Е, то общий элемент множества D обозначается обычно х и называется независимой переменной или аргументом этой функции, а отдельные конкретные элементы множества D называются значениями аргумента. Значения аргумента часто обозначают той же буквой, что и сам аргумент, с прибавлением каких-либо индексов, например, х₀, х₁, х_n и т.п. Элемент из Е, соответствующий элементу х Î D, в силу правила f называется значением функции f элементе х и обозначается f (x) (читается: «эф от икс»).

Множество D называется областью определения функции f Множество всех элементов f(х), соответствующих элементам хÎА, где А — произвольное подмножество множества D называется образом множества A и обозначается f(A). В частности, f(D) называется областью значений функции f. Область значений f(D) есть подмножество множества Е, которое в общем случае может и не совпадать со всем Е. Если же f(D) = Е, то говорят, что f есть отображение D на Е.

Две функции f и g равны (тождественны, совпадают), если совпадают их области определения, и если для любого х из области определения имеет место равенство

f (x) = g(x).

Если разным элементам х Î D, соответствуют разные элементы f (x) ÎЕ, то отображение f, называют взаимно однозначным (рис. 11.9).

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

Если f взаимно однозначное отображение, то каждому элементу YÎ f (D) можно поставить в соответствие определенный элемент хÎD, именно тот, значение функции на котором равно у. Так будет установлено отображение образа f (D) на множество D. Это отображение называется обратным по отношению к/и обозначается f ^-1.

Если образ f (D) есть подмножество множества D, то говорят, что функция f отображает D в себя. Например, функция f= sin x отображает все множество действительных чисел на подмножество этого множества — промежуток [-1, 1].

Вопросы для контроля знаний и подведения итога прочитанной лекции

1. Что понимают под термином «множество» и под элементами множества?

2. Как обозначаются и изображаются множества?

3. Укажите основные виды операций над множествами.

4. Что называют отображением множества D в Е?