Сологуб Г.Б. Элементы дискретной математики

Теория множеств.Множество – это первичное неопределяемое понятиематематики (как, например, точка в геометрии). Слова «набор»,«совокупность», «семейство» употребляют в качестве егосинонимов.Пример 1. Множествами являются:– набор из десяти арабских цифр;– совокупность учащихся института;– семейство бобовых;– множество людей на Земле;– множество действительных чисел.Множество может состоять из любых различимых объектов(чисел, букв, людей, растений…). Эти объекты называютсяэлементами данного множества. Если данный объект x являетсяэлементом множества X, то говорят, что x принадлежит X(обозначается: x ∈ X). В противном случае говорят, что x непринадлежит X (обозначается: x∉X). Множество, не содержащеени одного элемента, называется пустым (обозначается: ∅ ).Множества, состоящие из конечного числа элементов, называютсяконечными (например, первые 4 множества из примера 1).Аналогично, множества, состоящие из бесконечного числаэлементов, называются бесконечными (например, последнеемножество из примера 1).

Мы будем рассматривать, в основном,конечные множества.Способы задания множества:1) перечислить все элементы этого множества;2) указать свойство, которым обладают только элементы этогомножества (характеристическое свойство);3) описать метод (алгоритм) построения этого множества(порождающую процедуру).Пример 2. Множество С сигналов светофора можно задать 1-мспособом, просто выписав их названия, неважно в каком порядке.Будем делать это так: С = {красный, желтый, зеленый}.Пример 3.

Множество K квадратов можно задать 2-м способом,указав, что это совокупность всех прямоугольников, у которыхдлины всех сторон равны. Формальная запись такова:K = { Прямоугольники | Длины всех сторон равны }.Пример 4. Множество X корней уравнения x2-5x+6=0 можнозадать 3-м способом, описав метод нахождения его элементов,например, графический: построить график функции f(x)=x2-5x+6 вкоординатной плоскости Oxy и найти точки его пересечения сосью Ox.

Множество X можно задать и первыми двумя способами:1) X = {2,3}; 2) множество чисел, при подстановке каждого изкоторых вместо x, уравнение x2-5x+6=0 превращается в верноеравенство; формально это выглядит так: X = {x | x2-5x+6=0}.Множества A и B называются равными, если их элементысовпадают (обозначается: A=B, в противном случае – A≠B).Множество A называется подмножеством множества B, есликаждый элемент множества А является элементом множества B(обозначается: A ⊆ B). При этом говорят, что A содержится в B, аB включает A.

Если A ⊆ B и A≠B, то A называется собственнымподмножеством B (обозначается: A ⊂ B). Пустое множествосодержится в любом множестве. Любое множество является своимподмножеством (несобственным). Теперь можно дать другоеопределение равенства множеств: A=B, если A ⊆ B и B ⊆ A.Обычно, в каждом конкретном случае берется некотороемножество U (универсум), которое включает все рассматриваемыемножества. В следующих 4-х определениях предполагается A ⊆ U,B ⊆ U.Пересечением множеств A и B называется множество, каждыйэлемент которого принадлежит и A, и B одновременно(обозначается A ∩ B).

A ∩ B = {x | x ∈ A и x ∈ B}.Обычно дают следующую графическуюинтерпретацию этого определения. Универсумизображают в виде прямоугольника, внутрикоторого кругами изображают рассматриваемыеРис.1множества. Точки, лежащие внутри круговможно рассматривать как элементы соответствующих множеств.Пересечением множеств будет заштрихованная область, общая дляобоих кругов (см. рис.1). Полученное изображение называютдиаграммой Эйлера-Венна.Объединением множеств A и B называетсямножество,каждыйэлементкоторогопринадлежит хотя бы одному из множеств A и B(обозначается: A ∪ B) (рис.2).A ∪ B = {x | x ∈ A или x ∈ B}.Рис.2Дополнением (до U) множества A называетсямножество, состоящее из всех элементов U, непринадлежащих A (обозначается: A ) (рис.3).A = {x | x ∈ U и x∉A}.Рис.3Эти три операции называют булевымиоперациями над множествами.Разностью множеств A и B называетсямножество, состоящее из всех элементов A, непринадлежащих B (обозначается: A\B) (рис.4).A\B = {x | x ∈ A и x∉B}.Утверждение: A\B = A ∩ B .Рис.4Пример 7.

Пусть U = { 1, 2, 3, 4, 5, 6, 7, 8 } –универсум.A = { 2, 3, 5, 7 }, B = { 3, 4, 6, 7 }.Тогда: A ∩ B = { 3, 7 }, A ∪ B = { 2, 3, 5, 7, 4, 6 }.A = { 1, 4, 6, 8 }, B = { 1, 2, 5, 8 }, A\B = { 2, 5 }, B\A = { 4, 6 }.Свойства операций над множествами.1. A=A.2. Свойства дополнения:A∩ A =∅A ∪ A =U3. Идемпотентность:A ∩ A=AA ∪ A=A4. Коммутативность:A ∩ B=B ∩ AA ∪ B=B ∪ A5. Ассоциативность:(A ∩ B) ∩ C=A ∩ (B ∩ C)(A ∪ B) ∪ C=A ∪ (B ∪ C)6. Дистрибутивность:A ∩ (B ∪ C)=(A ∩ B) ∪ (A ∩ C)A ∪ (B ∩ C)=(A ∪ B) ∩ (A ∪ C)7.

Поглощение:A ∩ (B ∪ A)=AA ∪ (B ∩ A)=A8. Свойства U:A ∩ U=AA ∪ U=U9. Свойства ∅ :A∩ ∅=∅A ∪ ∅ =A10. Законы де Моргана:A∩ B = A ∪ B A∪ B = A ∩ B11. Инволютивность:A =A12. Связь U с ∅ :U =∅∅ =UБинарные отношения.Пусть A и B – произвольные множества. Возьмем по одномуэлементу из каждого множества, a из A, b из B и запишем их так:<a, b> (сначала элемент первого множества, затем элемент второгомножества – т.е. нам важен порядок, в котором берутся элементы).Такой объект будем называть упорядоченной парой. Равнымибудем считать только те пары, у которых элементы с одинаковыминомерами равны. <a, b> = <c, d>, если a = c и b = d.

Очевидно, чтоесли a ≠ b, то <a, b> ≠ <b, a>.Декартовым произведением произвольных множеств A и B(обозначается: A × B) называется множество, состоящее из всехвозможных упорядоченных пар, первый элемент которыхпринадлежит A, а второй принадлежит B. По определению:A × B = {<a, b> | a ∈ A и b ∈ B}. Очевидно, что если A≠B, то A × B ≠B × A.

Декартово произведение множества A само на себя n разназывается декартовой степенью A (обозначается: An).Пример 5. Пусть A = {x, y} и B = {1, 2, 3}.A × B = {<x, 1>, <x, 2>, <x, 3>, <y, 1>, <y, 2>, <y, 3>}.B × A = {<1, x>, <2, x>, <3, x>, <1, y>, <2, y>, <3, y>}.A × A = A2 = {<x, x>, <x, y>, <y, x>, <y, y>}.B × B = B2 = {<1, 1>, <1, 2>, <1, 3>, <2, 1>, <2, 2>, <2, 3>, <3, 1>,<3, 2>, <3, 3>}.Бинарным отношением на множестве M называется множествонекоторых упорядоченных пар элементов множества M.

Если ρ –бинарное отношение и пара <x, y> принадлежит этомуотношению, то пишут: <x, y> ∈ ρ или x ρ y. Очевидно, ρ ⊆ M2.Пример 6. Множество {<1, 2>, <2, 2>, <3, 4>, <5, 2>, <2, 4>}является бинарным отношением на множестве {1, 2, 3, 4, 5}.Пример 7. Отношение ≥ на множестве целых чисел являетсябинарнымотношением.Этобесконечноемножествоупорядоченных пар вида <x, y>, где x ≥ y, x и y – целые числа.Этому отношению принадлежат, например, пары <5, 3>, <2, 2>,<324, -23> и не принадлежат пары <5, 7>, <-3, 2>.Пример 8. Отношение равенства на множестве A являетсябинарным отношением: IA = {<x, x> | x ∈ A}.

IA называетсядиагональю множества A.Поскольку бинарные отношения являются множествами, то кним применимы операции объединения, пересечения, дополненияи разности.Областью определения бинарного отношения ρ называетсямножество D(ρ) = { x | существует такое y, что xρy }. Областьюзначений бинарного отношения ρ называется множествоR(ρ) = { y | существует такое x, что xρy }.Отношением, обратным к бинарному отношению ρ ⊆ M2,называется бинарное отношение ρ-1 = {<y, x> | <x, y> ∈ ρ}.Очевидно, что D(ρ-1) = R(ρ), R(ρ-1) = D(ρ), ρ-1 ⊆ M2.Композицией бинарных отношений ρ1 и ρ2, заданных намножестве M, называется бинарное отношение ρ2 o ρ1 ={ <x, z> | существует y такое, что <x, y> ∈ ρ1 и <y, z> ⊆ ρ2 }.Очевидно, что ρ2 o ρ1 ⊆ M2.Пример 9. Пусть бинарное отношение ρ задано на множествеM = {a, b, c, d}, ρ = {<a, b>, <a, c>, <c, c>, <c, d>}.

ТогдаD(ρ) = {a, c}, R(ρ) = {b, c, d}, ρ-1 = {<b, a>, <c, a>, <c, c>, <d, c>},ρ o ρ = {<a, c>, <a, d>, <c, c>, <c, d>}, ρ-1 o ρ = {<a, a>, <a, c>,<c, a>, <c, c>}, ρ o ρ-1 = {<b, b>, <b, c>, <c, b>, <c, c>, <c, d>,<d, c>, <d, d>}.Пусть ρ – бинарное отношение на множестве M. Отношение ρназывается рефлексивным, если x ρ x для любого x ∈ M.Отношение ρ называется симметричным, если вместе с каждойпарой <x, y> оно содержит и пару <y, x>. Отношение ρ называетсятранзитивным, если из того, что x ρ y и y ρ z следует, что x ρ z.Отношение ρ называется антисимметричным, если оно несодержит одновременно пары <x, y> и <y, x> различных элементовx ≠ y множества M.Укажем критерии выполнения этих свойств.Бинарное отношение ρ на множестве M рефлексивно тогда итолько тогда, когда IM ⊆ ρ.Бинарное отношение ρ симметрично тогда и только тогда,когда ρ = ρ-1.Бинарное отношение ρ на множестве M антисимметричнотогда и только тогда, когда ρ ∩ ρ-1 = IM.Бинарное отношение ρ транзитивно тогда и только тогда, когдаρ o ρ ⊆ ρ.Пример10.Отношениеизпримера6являетсяантисимметричным, но не является симметричным, рефлексивными транзитивным.

Отношение из примера 7 является рефлексивным,антисимметричнымитранзитивным,нонеявляетсясимметричным. Отношение IA обладает всеми четырьмярассматриваемыми свойствами. Отношенияρ-1 o ρ и ρ o ρ-1являются симметричными, транзитивными, но не являютсяантисимметричными и рефлексивными.Отношением эквивалентности на множестве M называетсятранзитивное, симметричное и рефлексивное на М бинарноеотношение.Отношением частичного порядка на множестве М называетсятранзитивное, антисимметричное и рефлексивное на М бинарноеотношение ρ.Пример 11. Отношение из примера 7 является отношениемчастичного порядка. Отношение IA является отношениемэквивалентностиичастичногопорядка.Отношениепараллельности на множестве прямых является отношениемэквивалентности.Другие способы задания отношений.

Теория графов.Произвольное множество точек координатной плоскостиможно рассматривать как изображение некоторого бинарногоотношения и называть его графиком этого отношения.И наоборот, любое бинарное отношение ρ, заданное намножестве A, можно изобразить на координатной плоскостиследующим образом: на координатных осях отмечают элементымножества A и для каждой пары <x,y>∈ρ, x,y∈A на плоскостиставят точку (x,y).Пример 12. Пусть бинарное отношение ρ задано на множествеA = {1, 2, 3, 4}, ρ = {<1, 1>, <1, 3>, <3, 1>, <3, 4>, <4,2>}.Изобразим его на координатной плоскости:A4321123A4Пример 13.