Сологуб Г.Б. Элементы дискретной математики (1015585)
Текст из файла
Теория множеств.Множество – это первичное неопределяемое понятиематематики (как, например, точка в геометрии). Слова «набор»,«совокупность», «семейство» употребляют в качестве егосинонимов.Пример 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.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
