Шпаргалка «Экзаменационная» по Дискретной математике (Дьячков А. М.)

Кирилл Николоев вс, 03.04.2016 21:20

1.Понятие множества. Основные операции. Множеством принято называть набор, совокупность нек-х объектов. Объекты, из кот-х состоит то или иное множ-во, наз-ся элементами этого множ-ва. Множества обозначаются большими латинскими буквами, элементы этих множеств – маленькими, пустое множество – символом Ø.Если любой элемент х нек-го множ-ва А явл-ся элементом множ-ва В, то говорят, что множ-во А явл-ся подмножеством множества В: В  А. Пустое множ-во – подмножество любого множ-ва. Само множество A и пустое множ-во Ø называют несобственными подмножествами множ-ва А. Все остальные подмножества называются собственными.

Множество, относительно которого все множества, рассматриваемые в данной задаче, являются подмножествами, называется универсальным – U. Основные операции - сложение (объединение), умножение (пересечение) и вычитание.

Объединением (или суммой) двух мн-в A и B называется мн-во, содержащее все такие и только такие элементы, кот-ые явл-ся элементами хотя бы одного из этих мн-в. Объединение мн-в A и B обозначают как A  B.

Пересечением (или умножением) двух мн-в A и B называется мно-во, состоящее из тех и только тех элементов, которые принадлежат мн-ву A и мн-ву В одновременно. Пересечение мн-в A и B обозначают как A  B.

Разностью мн-в A и B называется мн-во, состоящее из тех и только тех элементов мн-ва A и которые не принадлежат мн-ву В. Разность мн-в A и B обозначают как A \ B. Операция, при помощи которой находится разность мн-в, называется вычитанием.

Если В  А, то разность A \ B называется дополнением мн-ва B до мн-ва A. Если мн-во B является подмножеством универсального мн-ва U, то дополнение B до U обозначается , то есть = U \ B. При отсутствии скобок операции выполняются по приоритету: 1)ˉ 2)  3)  и \

A  Ø = Ø A  Ø = A A  A = A A  A = A A Ā= Ø A Ā= U A = A A\Ā = Ø A  B = B  A – коммутативность пересечения A  B = B  A – коммутативность объединения A  (B С) = (A  B)  С – ассоциативность пересечения

A  (B С) = (A  B)  С – ассоциативность объединения A  (B С) = (A  B)  (A  С) – дистрибутивность объединения относительно пересечения; A  (B С) = (A  B)  (A  С) – дистрибутивность пересечения относительно объединения

A  (A  B) = A A  (A  B) = A A\(B  C) = ( A\B )  ( A\C ) A\ ( B  C) = ( A \ B)  ( A\ C ) 2. Соответствия и функции. Мощность множества. Счетные множества. Декартовым (прямым) произведением множеств называется множество упорядоченных пар вида

Степенью декартового произведения называется число множеств n, входящих в это декартово произведение. Соответствием на мн-ах А и В наз-ся произвольное подмножество G  А х В. Проекцией Р_АG cоответствия G на А наз-ся множество {a є A| cущ-ет (a,b) є G)}. Аналогично, проекция Р_вG = {bєB| сущ-ет (a,b) є G)}.

Соответствие G  А х В наз-ся: 1)всюду определенным, если Р_АG=А,т.е. любому эл-ту А сопоставлен хоть один элемент из В;в противном случае оно наз-ся частично определенным; 2)сюръективным(или соответствием «на»), если Р_вG=В; 3)инъективным(или соответствием «в»), если при любом b є Р_вG cущ-ет! a є A| (a,b) є G,т.е. всякому эл-ту, который чему-то сопоставлен соответствует единств. элемент А такой что между А и В есть соответствие; 4)функциональным или (функцией), если при любом a є Р_АG cущ-ет! b є B|(a,b) є G; 5)взаимно однозначным(биекцией), если оно всюду определенно, сюръективно, инъективно и функционально.

Мн-ва бывают конечные и бесконечные(Мн-во, равномощное отрезку натурального ряда, а также пустое мн-во, наз-ся конечным. Мн-во, не являющееся конечным, наз-ся бесконечным). Мощностью конечного мн-ва А называется число его элементов и обозначается через |А|.

Два мн-ва наз-ся равномощными, если сущ-ет взаимно однозначное соответствие между их элементами(биекция). Это понятие применимо к конечным и бесконечным мн-м. Мн-во, равномощное мн-ву натуральных чисел, называется счетным. Другими словами, счетное мн-во - это такое мн-во, элементы которого можно перенумеровать при помощи натуральных чисел так, чтобы при этом все числа были использованы и различные элементы всегда имели бы различные номера. Т.О., счетное множество A всегда можно записать в виде A{a1,a2, ,an, }

3. Континуум. Фактор-множество, его мощность. Теорема Кантора. КОНТИНУУМ (от лат. continuum - непрерывное) множество, равномощное множеству вещественных чисел. Например, совокупность всех точек отрезка прямой или множество всех иррациональных чисел.

Пусть X - множество и R - отношение эквивалентности на нем. Из свойства транзитивности отношения эквивалентности следует, что любой класс эквивалентности является множеством всех элементов, эквивалентных произвольному элементу из этого класса. Таким образом, из теоремы следует, что отношение эквивалентности позволяет данное множество X представить в виде объединения взаимно непересекающихся классов эквивалентности.

Скачать файлы

Похожие документы