Лекции по дискректке. Лекции по ДМ. Лекции по дискретной математике лекция Элементы теории множеств. Основные понятия
 Скачать 152.76 Kb.
|
|
А.А. Феоктистова ЛЕКЦИИ ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ Лекция 1.Элементы теории множеств. Основные понятия. Основные понятия. Подмножества. Способы задания множеств. Опера- ции над множествами. Графическая иллюстрация множеств, отношений и операций над ними. Основные свойства операций над множествами. Литература: 1. Аляев Ю.А., Тюрин С.Ф. Дискретная математика и математическая логика. — М.: Финансы и статистика, 2006. — 368 с. 2. Андерсон Дж. А. Дискретная математика и комбинаторика: пер. с англ. — М.: Издательский дом «Вильямс», 2004. — 960 с. 3. Новиков Ф.А. Дискретная математика для программистов. — СПб.: Питер, 2000. — 304 с. 4. Ерусалимский Я.М. Дискретная математика: теория, задачи, прило- жения. 3-е издание. — М.: Вузовская книга, 2000. — 280 с. Понятие множества принадлежит к числу основных, неопределяемых понятий математики. Оно не сводится к другим, более простым понятиям. Поэтому его нельзя определить, а можно лишь пояснить, указывая синони- мы слова «множество» и приводя примеры множеств: множество – набор, совокупность, собрание каких-либо объектов (элементов), обладающих об- щим для всех их характеристическим свойством. Под множеством в математике понимается любая совокупность каких- либо объектов. При этом сами объекты, составляющие множество, называ- ются элементами множества. Например, можно говорить о множестве яблок в мешке, множестве натуральных чисел, множестве геометрических фигур на плоскости и т. д. Как правило, множество объединяет однотипные эле- менты (яблоки, числа и т.д.). Но это – не обязательно. Можно рассматри- вать множества, состоящие из разнородных элементов. Обычно множества обозначают заглавными латинскими буквами (A, B, C, . . .), а их элементы – прописными (a, d, c, . . .). Задание множеств. Чтобы задать множество, нужно указать, какие элементы ему принадле- жат. Это можно сделать различными способами: перечислением элементов; характеристическим предикатом; порождающей процедурой. Характеристический предикат — это некоторое условие, выраженное в форме логического утверждения или процедуры, возвращающей логическое значение. Если для данного элемента условие выполнено, то он принадле- жит определяемому множеству, в противном случае — не принадлежит. 1 Порождающая процедура — это процедура, которая, будучи запущен- ной, порождает некоторые объекты, являющиеся элементами определяемо- го множества. Примеры. Операции над множествами. Самого по себе понятия множества еще недостаточно. Нужно определить способы конструирования новых множеств из уже имеющихся, то есть опе- рации над множествами. 1. Сравнение множеств. Множество A содержится в множестве B (мно- жество B включает множество A), если каждый элемент A есть элемент B: A ⊂ B : x ∈ A → x ∈ B. В этом случае A называется подмножеством B, B — надмножеством A. Если A ⊂ B, A 6= B, то A называется собственным подмножеством B. Заметим, что M ⊂ M . А также пустое множество есть подмножество лю- бого множества. Для обозначения собственных множеств используют знак A ⊂ B, а для несобственных — A ⊆ B. Два множества равны, если они являются подмножествами друг друга: A = B : A ⊂ B ∨ B ⊂ A. Мощность множества M обозначается как |M |. Для конечных множеств мощность — это число элементов. Например, мощность пустого множества Ø равна нулю. Если |A| = |B|, то множества A и B называют равномощ- ными. 2. Oбъединение множеств. Объединением множеств A и B назы- вается множество, состоящее из всех элементов, принадлежащих хотя бы одному из множеств A или B. Объединением множеств A и B называется новое множество, состоящее из элементов множеств A и B. Символическая запись этого определения: A ∪ B = {x|x ∈ A или x ∈ B}. Примеры объединений двух множеств: 1) Пусть A = {2; 5; 7}, B = {3; 5; 6}. Тогда A ∪ B = {2; 3; 5; 6; 7}. 2) Пусть A = [−1/4; 2], B = [−2/3; 7/4]. Тогда A ∪ B = [−2/3; 2]. 3) Пусть A = {x|x = 8k, k ∈ Z}, B = {x|x = 8n − 4, n ∈ Z}. Тогда A ∪ B = {x|x = 4m, m ∈ Z}. Операция объединения множеств может проводиться не только над дву- мя множествами. Определение объединения множеств можно распростра- нить на случай любого количества множеств и даже – на систему множеств. Система множеств определяется так: если каждому элементу α множества M отвечает множество A α , то совокупность всех таких множеств мы будем 2 называть системой множеств. Обозначается ∪ n i=1 A i 3. Пересечение множеств. Пересечением множеств A и B называет- ся множество, состоящее из всех элементов, принадлежащих одновременно каждому из множеств A и B. Пересечением двух множеств A и B называется множество, элементы ко- торого содержатся и в A, и в B. Символическая запись этого определения: A ∩ B = {x|x ∈ A и x ∈ B}. Если множество A задается характеристиче- ским свойством P (x), a множество — свойством Q(x), то в A ∩ B входят элементы, одновременно обладающие и свойством P (x), и свойством Q(x). Примеры пересечений двух множеств: 1) Пусть = {2; 5; 7; 8}, = {3; 5; 6; 7}. Тогда A ∩ B = {5; 7}. 2) Пусть = [−1/4; 7/4], = [−2/3; 3/2]. Тогда ∩ = [−1/4; 3/2]. 3) Пусть = {x|x = 2k, k ∈ Z}, B = {x|x = 3n, n ∈ Z}. Тогда A ∩ B = {x|x = 6m, m ∈ Z}. 4) Пусть — множество всех прямоугольников, — множество всех ромбов. Тогда A ∩ B — множество фигур, одновременно являющихся и прямоуголь- никами, и ромбами, т.е. множество всех квадратов. 4. Разность множеств. Разностью A\B множеств A и B называется множество, состоящее из всех элементов множества A, которые не принад- лежат множеству B, т.е. A\B = {x|x ∈ A и x / ∈ B}. Примеры разностей множеств: 1. Пусть A = {1; 2; 5; 7}, = {1; 3; 5; 6}. Тогда \ = {2; 7}, а B\A = {3; 6}. 2. Пусть = [−1/4; 2], = [−2/3; 7/4]. Тогда\ = (7/4; 2], а B\A = [−2/3; −1/4). 3. Пусть A — множество всех четных целых чисел, B — множество всех целых чисел, делящихся на 3. Tогда A\B — множество всех четных целых чисел, которые не делятся на 3, а B\A — множество всех нечетных целых чисел, кратных трем. 5. Дополнение множества. Пусть множество A и B таковы, что A ⊆ B. Тогда дополнением множества A до множества называется раз- ность B\A. В этом случае применяется обозначение C B A = B\A. Если в качестве множества B берётся универсальное множество U , то применяется обозначение C = C U A = U \A (или ¯ A = U \A ) и такое множество просто на- зывают дополнением множества A. Таким образом, символическая запись определения дополнения множества будет следующей: ¯ A = {x|x / ∈ A}. 6. Симметрическая разность. Симметрическую разность можно вве- сти двумя способами: симметрическая разность двух множеств A и B — это 3 такое множество, куда входят все те элементы первого множества, которые не входят во второе множество, а также те элементы второго множества, которые не входят в первое множество. A 4 B = (A\B) ∪ (B\A). симметрическая разность двух множеств A и B — это такое множество, куда входят те элементы обоих множеств, которые не являются общими для двух заданных множеств. A 4 B = (A ∪ B)\(A ∩ B). Универсальное множество. Свойства. Универсальное множество — в математике множество, содержащее все мыслимые объекты. Универсаль- ное множество единственно. Любой объект, какова бы ни была его природа, является элементом универсального множества. В частности, само универ- сальное множество содержит себя в качестве одного из многих элементов. Любое множество является подмножеством универсального множества. В частности, само универсальное множество является своим подмножеством. Объединение универсального множества с любым множеством равно уни- версальному множеству. В частности, объединение универсального множе- ства с самим собой равно универсальному множеству. Пересечение универ- сального множества с любым множеством равно последнему множеству. В частности, пересечение универсального множества с самим собой равно уни- версальному множеству. Исключение универсального множества из любого множества равно пустому множеству. В частности, исключение универсаль- ного множества из себя равно пустому множеству. Исключение любого мно- жества из универсального множества равно дополнению этого множества. Дополнение универсального множества есть пустое множество. Симметри- ческая разность универсального множества с любым множеством равна до- полнению последнего множества. В частности, симметрическая разность универсального множества с самим собой равна пустому множеству. Свойства операций над множествами: 1) если A ⊂ B и B ⊂ C, то A ⊂ C (транзитивность), 2) если A ⊂ B и B ⊂ A, то A = B, 3) A ∪ A = A, 4) A ∪ = A, 5) A ∩ A = A, 6) A ∩ = , 7) A\A = , 4 8) A ∪ B = B ∪ A (коммутативность сложения), 9) A ∩ B = B ∩ A (коммутативность умножения), 10) (A ∪ B) ∪ C = A ∪ (B ∪ C) (ассоциативность сложения), 11) (A ∩ B) ∩ C = A ∩ (B ∩ C) (ассоциативность умножения), 12) A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) (дистрибутивность умножения относительно сложения), 13) A ∩ (B\C) = (A ∩ B)\(A ∩ C) (дистрибутивность умножения отно- сительно вычитания), 14) A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) (дистрибутивность сложения отно- сительно умножения), 15) A ∩ B = ¯ A ∪ ¯ B, A ∪ B = ¯ A ∩ ¯ B (законы де Моргана), 16) A\B = A ∩ ¯ B. 17) A ∩ ¯ A = , 18) A ∪ ¯ A = U . В справедливости перечисленных свойств можно убедиться различными способами. Например, нарисовать диаграммы Эйлера для левой и правой части и убедиться, что они совпадают. Или провести формальное рассуж- дение для каждого из равенств. Кроме того, с помощью перечисленных свойств можно доказывать или выводить сочетание более сложных опера- ций. Свойства симметрической разности. 1. Симметрическая разность коммутативна. 2. Симметрическая разность ассоциативна. 3. Пересечение множеств дистрибутивно относительно симметрической разности. A ∩ (B 4 C) = (A ∩ B) 4 (A ∩ C). 4. Пустое множество является нейтральным элементом симметрической разности. 5. Любое множество обратно само себе относительно операции симмет- рической разности. Лекция 2. Отношения на множествах. Основные виды отношений. Отношения на множествах. Свойства отношений. Бинарные отношения. Прямое произведение множеств. Отношение эквивалентности и разбиения. Отображения. Типы отображений (инъекция, сюръекция, биекция). Литература: 1. Аляев Ю.А., Тюрин С.Ф. Дискретная математика и математическая логика. — М.: Финансы и статистика, 2006. — 368 с. 5 2. Андерсон Дж. А. Дискретная математика и комбинаторика: пер. с англ. — М.: Издательский дом «Вильямс», 2004. — 960 с. 3. Новиков Ф.А. Дискретная математика для программистов. — СПб.: Питер, 2000. — 304 с. 4. Ерусалимский Я.М. Дискретная математика: теория, задачи, прило- жения. 3-е издание. — М.: Вузовская книга, 2000. — 280 с. Множество всех подмножеств множества A, или булеан множества A, обозначаемый P(A), есть множество, состоящее из всех подмножеств мно- жества A. Например, булеан множетсва A = {a, b, c} есть множество P(A) = {Ø, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}}. Декартово произведение множеств A и B, обозначаемое A × B, есть множество {(a, b)|a ∈ A, b ∈ B}. Объект (a, b) называется упорядоченной парой с первой компонентой a и второй компонентой b. Отношением R множеств A и B называется произвольное подмноже- ство A × B. Если (a, b) ∈ R, это записывают как aRb; при этом говорят, что a и b находятся в отношении R, или просто, a относится к b. Если A = B, то отношение есть подмножество A × A; такое отношение называют бинарным отношением на A. Областью определения бинарного отношения R называется множество, состоящее из таких x, для которых (x, y) ∈ R хотя бы для одного y. Область определения бинарного отношения обозначают δ R Областью значений бинарного отношения R называется множество всех y, для которых (x, y) ∈ R хотя бы для одного x. Область значений бинар- ного отношения обозначают ρ R Бинарное отношение R на непустом множестве A называется рефлексив- ным, если (x, x) ∈ R для всех x ∈ A. Иррефлексивным, если (x, x) / ∈ R для всех x ∈ A. Бинарное отношение R на непустом множестве A называется симмет- ричным, если (x, y) ∈ R ⇒ (y, x) ∈ R, антисимметричным, если (x, y) ∈ R и (y, x) ∈ R ⇒ x = y. Бинарное отношение R на непустом множестве A называется транзи- тивным, если (x, y) ∈ R и (y, z) ∈ R ⇒ (x, z) ∈ R. Рефлексивное, транзитивное и симметричное бинарное отношение R на множестве A называется эквивалентностью на A. Пусть R ⊆ A × B — отношение на A × B, а S ⊆ B × C — отношение на B × C. Композицией отношений S и R называется отношение T ⊆ A × C, 6 определенное таким образом: T = {(a, c)|существует такой элемент b из B, что (a, b) ∈ R, (b, c) ∈ S}. Это множество обозначается T = S ◦ R. Отображения множеств. Соответсвие f , сопоставляющее каждому элементу x множества X один и только один элемент множества Y , называется отображением множества X во множество Y . Элемент множества Y , соответсвующий при отображении f элементу x ∈ X, обозначают f (x) и называют образом элемента x при этом отображении. Если f (x) = y, то элемент x называют прообразом элемента y при отоб- ражении f . Совокупность всех прообразов элемента y при отображении f называ- ется полным прообразом этого элемента и обозначается f −1 (y), т.е. f −1 = {x|f (x) = y}. 7 |