Элементы теории множеств и отношений

Министерство общего и профессионального образования Российской федерации Тверской государственный технический университет Кафедра электронных вычислительных машин Элементы теории множеств и отношений Методические указания для практических занятий. Для студентов специальности 22.01 (Вычислительные машины, системы, комплексы и сети) Тверь 2002 Методические указания содержат сведения об основных положениях теории множеств и отношений. Методические указания предназначены для студентов специальности ЭВМ, изучающих курс "Дискретная математика", а также для использования при курсовом проектировании элементов вычислительной техники. Методические указания рассмотрены на заседании кафедры № от и рекомендованы к изданию в электронном варианте. Составитель АСЕЕВА Т.В  Тверской государственный технический университет, 2002 Введение 3 Алгебра множеств 4 Основные определения 4 Основные операции над множествами 5 Аксиомы и тождества алгебры Кантора 5 Законы для разности множеств 6 Подмножества и доказательства 6 Декартово произведение множеств 8 Элементы комбинаторики 10 Отношения и функции 14 Специальные бинарные отношения 16 Отношение эквивалентности 16 Отношения порядка 18 Отображения и функции 19 Математические модели 19 Операции над множествами и их свойства 19 Алгебра моделей с одной определяющей операцией 20 Алгебра моделей с двумя операциями 21 Решетки и булевы алгебры 21 Введение Дискретная математика и математическая логика являются фундаментом, на котором воздвигается все здание специальности «Вычислительные машины, комплексы, системы и сети». Некоторые рекомендации, относящиеся к подготовке специалистов, способных создавать и обслуживать информационные системы, отвечающие ожиданиям пользователей, содержатся в работе Бертрана Мейера1. В статье отмечается, что математические дисциплины, изучаемые в процессе подготовки инженера-системотехника, специалиста по ЭВМ, должны включать математический анализ, дискретную математику и основы математической логики. Студенты, научившиеся применять математическое мышление к разработке программного обеспечения, имеют безусловные преимущества по сравнению с теми, кто этими навыками не обладает. Общая тенденция сводится к необходимости отделять специалистов по программному обеспечению от программистов-любителей. Эти тенденции имеют важные последствия для вузов. Вопрос в том, стоит ли обучать будущих профессионалов фундаментальным методам мышления, которые будут применяться ими в течение всей карьеры и которые помогут добиваться успеха в столь быстро меняющейся области. Успех сопутствует тем, кто способен выйти за рамки инструментария, популярного в какой-то момент, и развиваться в соответствии с динамикой прикладной дисциплины. В любой инженерной дисциплине инструментарий составляет важную часть профессиональных навыков. Но нельзя ограничиваться только ими. Следует изучать фундаментальные концепции, которые не изменились практически с момента своего появления. Дискретная математика и математическая логика содержат формальные основания для понимания всего остального. Алгебра множеств Основные определения Понятие множества является понятием первичным, т.е. не определяемым через другие элементарные понятия. Множество состоит из элементов. Отношение включения элемента х в множество М обозначается Запись означает, что элемент х не принадлежит множеству М. Существует несколько способов задания множеств, применение которых обусловлено контекстом. Ниже перечислены способы основные способы задания множеств: • Перечислением элементов, которые указываются через запятую и заключаются в фигурные скобки. Например, запись M={x,y,z} означает трехэлементное множество. Очевидно, такой способ применим для не слишком больших множеств. • Указанием характеристического свойства, например, M={x | x N (N – множество натуральных чисел), 2 m. ПЕРЕСТАНОВКИ Это слова длины n в алфавите объемом n, в которых одна и та же буква не может повторяться. Т.е. это размещения без повторений из n по n. Число перестановок обозначается Рn. Теорема: Pn = n! Доказательство автоматически следует из выражения для числа размещений без повторений. По определению 0!=1. СОЧЕТАНИЯ ИЗ n ЭЛЕМЕНТОВ ПО m Это слова длины m в алфавите объемом n, различающиеся составом букв, но не их порядком, причем буквы в словах могут появляться не более одного раза. Число таких соединений обозначается как Теорема: Доказательство. В соответствии с определением, сочетания есть размещения без повторений из n элементов по m, в которых слова с одинаковыми наборами букв являются одним и тем же словом сочетаний. Поэтому их число может быть определено как Q(m)=. Следствия 1. - следует из определения. 2. - так как все пустые слова одинаковы. 3.  Возможно следующее доказательство этого свойства. Известно, что где это биномиальные коэффициенты, определяющие число слагаемых вида xiyn-i в сумме. В частном случае, когда х=1 и у=1 получаем непосредственно требуемое выражение  4.  Доказывается аналогично доказательству свойства 3 в предположении, что х=1, у=-1.  Задача: Доказать что мощность булеана конечного множества А равна 2|A|.  Мощность булеана конечного n- элементного множества есть число всех его подмножеств. Ранее мы без доказательства ввели утверждение, что |P(A)| = 2|A|. Так как есть не что иное, как число m-элементных подмножеств n-элементного множества, то указанная сумма действительно определяет число всех возможных подмножеств конечного множества. Треугольник Паскаля Рассмотрим рекуррентную по n процедуру определения биномиальных коэффициентов, т.е. определение если известно Пусть число r- элементных подмножеств (n+1)-элементного множества равно и известно, как определить И пусть А  = n и мощность множества А  {a0} равна n + 1.Тогда r- элементные подмножества множества А  {a0} будут состоять из подмножеств двух типов: тех, которые не содержат элемент а0, число их будет равно , и тех, которые содержат элемент а0. Последние можно получить, взяв все (r-1) - элементные подмножества множества А, и добавив к каждому из них а0. Тогда число r - элементных подмножеств (n + 1)-элементного множества определится, как Это рекуррентное соотношение используется для построения таблицы биномиальных коэффициентов, в которой коэффициенты расположены рядами друг над другом. Строки следуют в порядке возрастания n, а позиция коэффициента в ряду указывает число m подмножеств ранга 0,1,2,…,n, причем 0  m  n, 0  n  N. Таблица биномиальных коэффициентов приводится в математических справочниках и имеет вид, представленный на Рис. 1. Рисунок 1 Треугольник Паскаля ФОРМУЛА ВКЛЮЧЕНИЙ /ИСКЛЮЧЕНИЙ Мощность объединения конечного числа конечных множеств A1, A2, …, An равна Доказательство производится методом математической индукции по числу множеств n, участвующих в объединении. Отношения и функции Отношение является фундаментальным понятием дискретной математики, которое используют для обозначения связи между объектами или понятиями. Например, отношение включения элемента во множество, отношение включения подмножества во множество, отношение параллельности и перпендикулярности прямых, отношение равенства чисел и множеств. Общим для всех отношений является то, что они ставят в соответствие друг другу объекты из разных множеств или из одного и того же множества. В общем случае отношение можно определить как некоторое утверждение, относительно которого можно сказать, что оно является истинным или ложным. В дискретной математике такое утверждение называется предикатом. Например, предикат x>y может быть истинным или ложным в зависимости от того, какие значения примут входящие в него переменные x и y. Понятие предиката непосредственно вытекает из понятия отношения. Если предикат устанавливает какое- либо соответствие между двумя объектами, то эту пару объектов можно рассматривать как элемент декартова произведения двух множеств, элементами которых и являются эти объекты. В силу последнего обстоятельства объекты, входящие в пары, могут принимать различные сочетания значений. При некоторых из них предикат будет истинным, при других ложным. Подмножество декартова произведения двух множеств, для каждого из элементов которого данный предикат будет истинным, называется двуместным (бинарным) отношением между элементами двух множеств. В общем случае n - местным отношением между элементами множеств А1, A2, ..., An называется любое подмножество декартова произведения этих множеств. Соответственно бинарное отношение - это любое подмножество декартова произведения двух множеств (возможно, одного и того же множества). При n =1 отношение называется одноместным или унарным и обозначает просто свойство на множестве. Например, ={x  х положительное целое число} задает множество положительных целых чисел. Для обозначения отношений принято использовать строчные буквы латинского или греческого алфавита. Будем обозначать n - местное отношение между элементами множеств А1 , А2, ..., А n как (n)  А1А2...Аn. Верхний индекс определяет местность отношения. Таким образом, n-местное отношение – это множество упорядоченных n-ок, элементы которых принадлежат соответствующим множествам, участвующим в декартовом произведении и порождающим универсум для этого отношения. Поэтому, например, если требуется определить все бинарные отношения на множестве {0,1}, то надо вначале найти декартов квадрат этого множества, который и будет универсумом для всех возможных отношений. Мощность множества {0,1}2 равна 4. Следовательно, искомая мощность множества всех возможных отношений равна мощности булеана множества {00, 01, 10, 11}, т.е. 16. Наиболее часто встречаются бинарные отношения вида   АВ или   А2. В последнем случае множество А называется несущим множеством, на котором задано отношение . В приведенном выше примере несущим множеством для всех бинарных отношений на множестве {0,1} является множество {00, 01, 10, 11}. С каждым бинарным отношением связывают два множества: область определения dom  и область значений rng , которые определяются как проекции отношения  на первую и вторую координаты соответственно, т.е. dom  ={x y: (x,y)  }, rng ={x  у: )(у,х)  }. Очевидно, каждое бинарное отношение задано на множестве (dom   rng ). Для обозначения бинарных отношений   А2 часто используют следующие записи: • ху , читается "х находится в отношении  с у"; • (х,у)  , читается "элемент (х,у) принадлежит отношению "; • у  (х). Множество элементов отношения  называется графиком отношения . Отношение является множеством, следовательно, к нему применимы любые операции, определенные для множеств. Кроме того, для отношений определены также следующие операции: • обратное отношение -1 , которое определяется как -1={(x,y)  (y,x) }. Например, для отношения ху  х  у, заданного на множестве А={1,2,3},  = {(1,1), (2,1), (2,2), (3,1), (3,2), (3,3)}, обратное отношение -1={(x,y)|yx}; график обратного отношения получается простой перестановкой первого и второго элементов в каждой паре, участвующей в : -1 = {(1,1), (1,2), (2,2), (1,3), (2,3), (3,3)}; • дополнение отношения , которое определяется как дополнение  до универсального отношения:  = {(x,y)  (x,y)  А2\ }; • композиция отношений , таких что и . Композиция отношений – это бинарное отношение, которое определяется следующим образом На рис.2 приведен композиции двух бинарных отношений. Рисунок 2 Композиция бинарных отношений Отношение не обладает свойством коммутативности. Легко показать, что композиция отношений ассоциативна, а также, что Для визуализации отношений можно использовать различные способы: 1. Задание отношения перечислением элементов. 2. Графиком отношения в декартовой системе координат. 3. Изображением связей в виде стрелок, связывающих элементы множеств, участвующих в отношении, стрелками, направление которых задает отношение. 4. Графом отношения. 5. Фактор - множеством, в котором перечисляются окрестности каждого из элементов несущего множества. Рассмотрим различные способы на примере отношения ху  x > y, x,y  {1, 2, 3, 4, 5}. 1. Перечислением элементов:  = {(2,1), (3,1), (3,2), (4,1), (4,2), (4,3), (5,1), (5,2), (5,3), (5,4)}. Это множество называется также графиком отношения. 2. Графиком отношения, т.е. указанием всех точек плоскости, в которых указанное отношение истинно. Для изображения графика отношения введем декартовы координаты, примем, что ось абсцисс - это ось х, а ось ординат - это ось у. Точки, находящиеся в пересечениях всех горизонталей и вертикалей, проведенных через точки координатных осей, изображающие элементы несущего множества, дадут "универсум", т.е. множество, мощность которого равна в данном случае 25. В этом множестве выделим точки, принадлежащие отношению, Рис.2. 3. Изображение отношения с использованием координатных осей и стрелок очевидно из Рис. 3, a, b. 4. Изображение отношения с помощью графа. Множество элементов несущего множества используется в качестве имен вершин графа отношения. Ребрами ориентированного графа являются элементы отношения, Рис. 4. 5. При изображении отношения с помощью фактор -множества каждому элементу несущего множества сопоставляется его окрестность, определенная следующим образом: О(vi)={vj  (vi,vj)  , vi, vj A}, где А - несущее множество. Фактор - множество записывается в виде заключенной в фигурные скобки последовательности элементов несущего множества, под каждым из которых указывается его окрестность, т.е. множество вершин, смежных с данной вершиной. В рассматриваемом случае . Для любого множества А определим тождественное отношение IA, которое называется также диагональю А, и универсальное отношение 1 следующим образом: IA = {(xx) x А}. 1 = А2. Так как   А2, то  является отношением на А и называется пустым отношением. Специальные бинарные отношения Будем рассматривать бинарные отношения, заданные на непустом множестве А. Свойства бинарных отношений и некоторые определения, относящиеся к отношениям сведены в Табл.1 Таблица 1 Свойства бинарных отношений. Понятие теории отношений Определение Ткеоретико-множественное описание и некоторые зависимости Горизонтальное сечение по х0 {(x0y)  y:х0у} ({x0}А)   Вертикальное сечение по у0 {(x,y0) х: ху0 }   (A{y0}) Горизонтальная проекция  {x  у: (х,у)  } dom  Вертикальная проекция  {y   х: (х,у)  } rng  Пересечение отношений {(x,y)  (х,у)  1  2} 1  2 Объединение отношений {(x,y)  (х,у)  1  2} 1  2 Обратное отношение {(y,х)  (х,у)  } -1 Композиция отношений {(x,y)  z: хz, zу }   g Рефлексивность х  А: (х,х)   iA   Симметричность  х,у  А: х  у  у  х  = -1 Транзитивность  х,у,zА: хz и zу  х  у   =  Иррефлексивность х  А: (х,х)   iA   =  Асимметричность  х,у: х  у   (у  х )   -1 =  Антисимметричность  х,у: х у и у х  х = у   -1  iA Специальные свойства бинарных отношений удобно представить Табл. 2. Название свойства Характеристическое свойство Теоретико-множественное определение Граф свойства Рефлексивность Симметричность Тран-итивн1ст0 Отношение эквивалентности Бинарное отношение называется эквивалентностью, если оно рефлексивно, симметрично и транзитивно. Эквивалентность обозначается символом ~, например, х ~ y. Граф отношения эквивалентности есть полный граф, заданный на множестве А, т.е. множество ребер графа отношения эквивалентности либо равно А2, либо несвязный граф, каждая компонента связности которого является полным подграфом графа А2 на некотором подмножестве вершин графа, образующем класс эквивалентности для данного отношения. Вообще, классом эквивалентности для отношения ~ на множестве А по элементу а называется множество, определенное следующим образом: [x]~ или X({a})={x  x~а, xA }. Разумеется, элемент а, для которого класс эквивалентности определен таким образом, также входит в этот класс в силу рефлексивности отношения эквивалентности. Множество классов эквивалентности связано с разбиением несущего множества. Вообще разбиением множества М называется множество, элементами которого являются подмножества М за исключением пустого множества, которое в разбиение не входит. Объединение этих подмножеств равно М, а пересечения попарно пусты. Таблица 2 Свойства отношения эквивалентности Понятие Свойство или определение Пояснение ~ - отношение эквивалентности на А • ~ АА • ~ рефлексивно в А • ~ транзитивно в А • ~ симметрично в А iA ~ dom ~ = rng ~ = A ~  ~ = ~ ~ = ~-1. Aa- класс эквивалентности отношения ~ по элементу а [a]~ = {x | (a,x)  ~ } Множество всех элементов, таких, что x ~ a. Каждый класс эквивалентности определен заданием одного элемента. Разбиение множества А Z={Z1,Z2, …, ZN},   Z, Разложение множества А на непересекающиеся непустые подмножества, так что каждый элемент из А принадлежит одному и только одному из этих подмножеств. Можно доказать, что отношение эквивалентности “~” на А образует разбиение А/ ~ множества А, причем элементами разбиения являются классы эквивалентности. Разбиение называется максимальным, если в каждый класс эквивалентности входит по одному элементу. Примером такого отношения является отношение х ~ у  х=у, х,у  N. Разбиение называется минимальным, если оно образует единственный класс эквивалентности, в который входят все элементы А. Множество классов эквивалентности в множестве А по эквивалентности “~” называется фактор-множеством А по “~”, обозначается A/~. Примеры отношений эквивалентности. 1. Отношение конгруентности треугольников. 2. Отношение тождества на множестве алгебраических выражений. 3. Отношение параллельности на множестве прямых. 4. Отношение учиться в одной группе на множестве студентов. 5. Отношение получить одну и ту же оценку по математике на экзамене. 6. Сравнимости чисел по модулю m (это отношение определяет множества чисел, дающих одинаковый остаток при делении на m). Например, отношение иметь одинаковый остаток при делении на 7 на множестве целых чисел Z: 7. Отношения равенства чисел (образует максимальное разбиение), 8. Конгруэнтности треугольников (классы эквивалентности включают все конгруэнтные треугольники), 9. Равенства множеств, 10. Равномощности множеств,. Теорема. Если “~” – отношение эквивалентности, заданное на произвольном непустом множестве А, то существует разбиение, равное фактор множеству множества А по отношению ~, A/~ = {[x]~ | x AyA: x~y  x,y[x]~} такое, что каковы бы ни были x,y A, x ~ y тогда и только тогда, когда х и у принадлежат к одному и тому же классу разбиения.  Пусть ~ - эквивалентность на А и A/~= {[x]~ | x: x A}- фактор-множество А по отношению ~. Докажем существование разбиения R~, равного фактор множеству A/~. • Пусть aA – произвольный элемент А. Обозначим Aa= [a]~ = {x | x  A, x ~ a} – класс эквивалентности по элементу а. Тогда, аАа, и, следовательно, Так как элемент а выбирается произвольно, и каждый класс эквивалентности содержит только элементы множества А, то Из существования двух включений следует, что . Следовательно, объединение классов эквивалентности равно А. • Докажем теперь, что попарные пересечения классов эквивалентности пусты. Пусть a,b  A, a Aa, b  Ab, Aa и Ab –два класса эквивалентности. Пусть Аa  Ab . Тогда существует хотя бы один элемент сА такой, что с  Аa и с  Аb, т.е. с ~ a и c ~ b. Пусть z – произвольный элемент множества Аа. Тогда z ~ a и а ~ с. По свойству транзитивности отношения эквивалентности получаем z ~ c. Но с ~ b, следовательно, по свойству транзитивности z ~ b. Следовательно, z  Ab. Следовательно, Aa  Ab. Обратное включение доказывается аналогично. Следовательно, пересечение Aa и Ab не пусто тогда и только тогда, когда это одно и то же множество. Таким образом, доказано, что множество классов эквивалентности образуют разбиение множества А.  Отношения порядка Бинарное отношение на А называется предпорядком на А, если оно рефлексивно и транзитивно, но не антисимметрично (например, отношение «х делитель у» на множестве целых чисел). Частичным порядком на А называется бинарное отношение рефлексивное, транзитивное и антисимметричное. Частичный порядок часто обозначается символом “”. Порядок -1 называется двойственным к  и обозначается символом “”. Будем писать x