кер. Лекция №1. Лекция 1 Множества Определение множества, способы задания, операции над множествами
 Скачать 116.14 Kb.
|
|
Лекция №1: Множества Определение множества, способы задания, операции над множествамиТеория множеств опирается на три первичных понятия: множество; элемент; принадлежность. Строгого определения этим понятиям не дается, описывается только их применение. На рисунке 1.1 буквой  обозначено множество, элементами которого являются точки заштрихованной части плоскости, при этом точка  принадлежит множеству  , точка  не принадлежит множеству  . Рис. 1.1. Способы задания множества Множество можно задать, перечислив все его элементы:   . Порядок записи элементов множества произволен. Часто задают множество, указав его характеристическое свойство, которое для каждого элемента позволяет выяснить, принадлежит он множеству или нет.Например,  , .В дальнейшем для известных числовых множеств будут использоваться обозначения:  – множество натуральных чисел; – множество целых чисел; – множество рациональных чисел; – множество действительных чисел.Основные определения Пустым множеством называется множество  , не содержащие ни одного элемента, т.е. для любого элемента x выполняется  .Универсальным множеством называется множество  всех элементов, рассматриваемых в данной задаче.Пример 1.1. Пусть  и требуется найти все решения уравнения  . Множеством  решений этой задачи есть пустое множество:  .Пусть теперь  . Тогда множество решений уравнения не пусто:  .Будем говорить, что множество включается во множество  , если каждый элемент множества является элементом множества  (говорят также, что является подмножеством множества ). Из определения включения следуют свойства: для любого множества ;Если  и  , то  ; для любого множества ; для любого множества .Определим понятие равенства множеств:  тогда и только тогда, когда одновременно выполняются два включения и  , т.е. каждый элемент множества является элементом множества и каждый элемент множества является элементом множества .Диаграммы Эйлера – Венна Эти диаграммы применяются для наглядного изображения множеств и их взаимного расположения. Универсальное множество изображается в виде прямоугольника, а произвольные множества – подмножества универсального – в виде кругов (рис. 1.2). Рис. 1.2. Диаграмма Эйлера-Венна Операции над множествами Объединением множеств и называется множество  , состоящее из тех и только тех элементов, которые принадлежат хотя бы одному из множеств или (рис. 1.3, а).Пример 1.2. Если  ,  , то  .Пересечением множеств и называется  , состоящее из тех и только тех элементов, которые принадлежат одновременно и множеству , и множеству (рис. 1.3, б).Пример 1.3. Если , , то  . Рис. 1.3. Операции над множествами: объединение множеств и ;пересечение множеств и .Разностью множеств и называется множество  тех и только тех элементов, которые принадлежат множеству и не принадлежат множеству (рис. 1.4, а).Пример 1.4.  ;  .Дополнением множества до универсального назыается множесто  (рис. 1.4, б).Пример 1.5. Если ,  , то  . Рис. 1.4. Операции над множествами: разность множеств и ;дополнение множества .Системы множеств Элементы множества сами могут быть множествами:  ; в таком случае удобно говорить о системе множеств. Рассмотрим такие системы множеств, как булеан и разбиение множеств.Булеаном  множества  называется множество всех подмножеств множества . Например, для множества  булеаном является множество  .Разбиением  множества называется система его непустых непересекающихся подмножеств, в объединении дающая множество (рис. 1.5).Например, для множества  можно построить разбиение  , состоящие из двух элементов (они называются блоками разбиения), или разбиение  – из четырех блоков, возможны и другие разбиения этого множества . Рис. 1.5. Разбиение множества  Законы алгебры множеств Так же, как операции обычной алгебры, операции над множествами выполняются по законам (табл. 1.1), которые доказываются на основе введенных выше определений. Особенностью алгебры множеств является закон идемпотентности, благодаря которому в алгебре множеств нет числовых коэффициентов и степеней. Таблица 1.1: Законы алгебры множеств
Бинарное отношениеДекартовым произведением  двух множеств и  называется множество всех упорядоченных пар  таких, что  , а  .Пример 1.6. Пусть  ,  . Тогда , Очевидно, что  , т.е. для операции декартова произведения множеств закон коммутативности не выполняется.Наглядно декартово произведение множеств можно представить в виде графика. На рис. 1.6 звездочками отмечены элементы множества  .Декартовым произведением множеств  будем называть множество  всех упорядоченных наборов  таких, что  . Рис. 1.6. График декартова произведения Определение бинарного отношения Пусть среди трех людей (назовем их Андрей, Василий и Сергей) двое знакомы друг с другом (Андрей и Василий) и знают третьего (Сергея), но тот их не знает. Как описать отношение между этими людьми? Имеем множество  , из элементов которого составлены упорядоченные пары:  ,  ,  ,  , т.е. выделено некоторое подмножество декартова произведения  . Это подмножество и описывает связи между элементами множества .Определение. Говорят, что на множестве задано бинарное отношение , если задано подмножество декартова произведения (т.е.  ).Пример 1.7. Пусть  . Зададим на следующие отношения: – отношение равенства; – отношение предшествования; – отношение делимости.Все эти отношения заданы с помощью характеристического свойства. Ниже перечислены элементы этих отношений:  ; ; .Тот факт, что пара принадлежит данному отношению , будем записывать:  или  . Например, для отношения запись  означает, что 4 на 2 нацело, т.е.  .Областью определения  бинарного отношения называется множество  .Областью значений  называется множество  .Так, для отношения  из примера 1.7 областью определения является множество  , а областью значений –  .Способы задания бинарного отношения Бинарное отношение можно задать, указав характеристическое свойство или перечислив все его элементы. Существуют и более наглядные способы задания бинарного отношения: график отношения, схема отношения, граф отношения, матрица отношения. График отношения изображается в декартовой системе координат; на горизонтальной оси отмечается область определения, на вертикальной – область значений отношения; элементу отношения соответствует точка плоскости с этими координатами. На рис. 1.7, а приведен график отношения примера 1.7. Рис. 1.7. График отношения (а) и схема отношения (б)Схема отношения изображается с помощью двух вертикальных прямых, левая из которых соответствует области определения отношения, а правая – множеству значений отношения. Если элемент принадлежит отношению , то соответствующие точки из и соединяются прямой. На рис. 1.7, б приведена схема отношения из примера 1.7.Граф отношения строится следующим образом. На плоскости в произвольном порядке изображаются точки – элементы множества . Пара точек  и  соединяется дугой (линией со стрелкой) тогда и только тогда, когда пара принадлежит отношению . На рис. 1.8, а приведен граф отношения примера 1.7.Матрица отношения – это квадратная таблица, каждая строка и столбец которой соответствует некоторому элементу множества . На пересечении строки и столбца ставится 1, если пара ; все остальные элементы матрицы заполняются нулями. Элементы матрицы нумеруются двумя индексами, первый равен номеру строки, второй – номеру столбца. Пусть  . Тогда матрица отношения имеет  строк и столбцов, а ее элемент  определяется по правилу: На рис. 1.8, б приведена матрица отношения примера 1.7. Рис. 1.8. Граф отношения (а) и матрица отношения (б)Свойства бинарных отношений Бинарные отношения делятся на типы в зависимости от свойств, которыми они обладают. Рассмотрим следующие отношения на множестве  : ; ; ; .Отношение на множестве называется рефлексивным, если для всех выполняется условие  . Среди приведенных выше отношений рефлексивными являются отношение  (т.к. неравенство  справедливо при всех ) и отношение (т.к. разность  делится на 3, значит, пара  принадлежит отношению при всех ).Отношение на множестве называется антирефлексивным, если условие не выполняется ни при одном . Примером антирефлексивного отношения является отношение  (неравенство  не выполняется ни при каких значениях , следовательно, ни одна пара не принадлежит отношению ). Отметим, что отношение  не является рефлексивным  и не является антирефлексивным  .Отношение на множестве называется симметричным, если из условия следует  . Симметричными являются отношения (если  делится на 3, то и  делится на 3) и (если  , то и  ).Отношение на множестве называется несимметричным, если для любых  из условия следует  . Несимметричным является отношение , т.к. условия  и  не могут выполняться одновременно (только одна из пар или  принадлежит отношению ).Отношение на множестве называется антисимметричным, если для любых из условия и следует  . Антисимметричным является отношение , т.к. из одновременного выполнения  и  следует .Отношение на множестве называется транзитивным, если для любых  из одновременного выполнения условий и  следует  . Отношения , , являются транзитивными, а отношение нетранзитивно: если  , то  и  , но  , то есть выполняются условия  и  , но  .Отношения эквивалентности Рассмотрим три отношения: ,  ,  . Отношение . Отношение введем на множестве всех треугольников следующим образом: этому отношению принадлежат пары треугольников такие, что площадь треугольника равна площади треугольника .Отношение действует на множестве жителей г. Томска и содержит пары такие, что и носят шляпы одинакового размера.Свойства этих трех отношений приведены в таблице 1.2, где Р означает рефлексивность, АР – антирефлексивность, С – симметричность, АС – антисимметричность, НС – несимметричность, Т – транзитивность отношения. В качестве упражнения проверьте правильность заполнения таблицы, пользуясь определениями свойств бинарных операций. Таблица 1.2: Свойства отношений
Мы видим, что отношения обладают одинаковыми свойствами, поэтому их относят к одному типу. Определение. Отношение на множестве называется отношением эквивалентности, если оно обладает свойствами рефлексивности, симметричности, транзитивности.Таким образом, отношения , , являются отношениями эквивалентности на соответствующих множествах . Важной особенностью отношений эквивалентности является то, что они разбивают все множество на непересекающиеся подмножества – классы эквивалентности.Определение. Классом эквивалентности, порожденным элементом , называется подмножество  множества , для элементов которого выполняется условие  . Таким образом, класс эквивалентности  .Так, отношение разбивает множество на три класса эквивалентности:  . Класс, порожденный элементом 4, совпадает с классом  ;  .Классы эквивалентности образуют систему непустых непересекающихся подмножеств множества , в объединении дающую все множество – т.е. образует разбиение множества .Отношение эквивалентности обозначают  ,поэтому определение класса эквивалентности можно записать так:  .Отношение порядка Рассмотрим отношение , : ; , отношение и отношение включения  на множестве всех подмножеств целых чисел ( – булеан множества  ):  .Таблица 1.3: Свойства отношений
Мы видим, что по свойствам эти отношения разделились на два типа. Определение. Отношение на множестве , обладающее свойствами рефлексивности, антисимметричности, транзитивности, называется отношением порядка на множестве (обозначается  ).Определение. Отношение на множестве , обладающее свойствами антирефлексивности, несимметричности, транзитивности, называется отношением строгого порядка (обозначается  ).Таким образом, отношения , , являются отношениями порядка на соответствующих множествах, а отношение – отношением строгого порядка. |
; 
; 
; 
; 
; 
;
;
; 
; 
; 