Множества и операции со множествами. Понятие множества и мультимножества



Скачать 144.44 Kb.
Дата23.11.2012
Размер144.44 Kb.
ТипДокументы
Множества и операции со множествами.

Понятие множества и мультимножества. Множество - это целое, состоящее из различных частей. Ясно, что такое словесное описание трудно посчитать четким определением. Дело в том, что множество, являясь понятием категориальным, не поддается четкому определению; его от­сутствие восполняют различного рода описания. Цель таких описаний - отразить важнейшие (атрибутные) свойства множества, а именно: разли­чимость всех частей множества, неупорядоченность частей множества и целостность множества.

Различают два типа частей множества — элементы и подмножества. Элемент понимают как неделимую и непустую часть множества, все иные его части считают подмножествами. Каждый элемент множества можно рассматривать как его одноэлементное подмножество. Особо выделяют часть, которую называют пустым множеством (т.е. не содержащим ни одного элемента) и обозначают ∅. Считается, что каждое множество обладает такой частью.

Отказ от различимости элементов множества приводит к понятию мультимножества, т.е. совокупности элементов, среди которых могут быть и одинаковые (неразличимые). Всякое мультимножество можно представить его основанием, т.е. множеством всех его различных элементов, и кратностями — числом повторений каждого элемента основания этого мультимножества.

Одна и та же горсть мелочи может быть и множеством, и мультимножеством: если в ней есть монеты одинакового достоинства, то для тратящего между ними нет разницы, т.е. для него это мультимножество, в то время как нумизмату интересны и даты выпуска монет, и если они на монетах одинакового достоинства различны, то для него эта горсть монет — множество.

Обозначения. Если а является элементом множества А, то говорят, что а принадлежит множеству А, и записывают а А; в противном случае пишут а А. В случае, когда В является подмножеством А, пишут В А. Включение множеств С обладает свойством рефлексивности А) и транзитивности (если В А и А ⊆ С, то В ⊆ С). Если А В и В А,то A = В. Подмножество В называется собственным подмножеством А, если В А и В А. Этому соответствует запись В А.

Простейшей численной характеристикой множества как целого являет­ся указание количества его элементов, т.е. мощность множества. Множест­во А является конечным, если его мощность есть целое неотрицательное число, которое обозначается |А|. Если число элементов множества не ограничено, то такое множество называется бесконечным. Пусть |А| = п и |В| = m; тогда если В А, то m ≤ п, причем если В А, то m < п.


Задавать множество можно списком его элементов А ={a1, a2, …}, причем порядок аi -x несуществен. Однако столь явный способ задания множества либо не всегда осуществим, либо неудобен. Так, множество всех натуральных чисел N не допускает явного задания списком, посколь­ку N бесконечно. В таких случаях множество задается описанием свойств, однозначно определяющих принадлежность элементов данному множест­ву. Этому способу задания множества А соответствует запись А = {а: а об­ладает свойством R}, которая означает, что множество А состоит из всех тех и только тех а, которые обладают свойством R (а) = R. Например, если свойство R (а) состоит в том, что а — простое число, то А — множест­во всех простых чисел (т.е. непредставимых суммой одинаковых слагае­мых, отличных от самого числа и единицы). Возможно также рекурсив­ное задание множества, при котором каждый последующий элемент описы­вается через предыдущие. Так, заданию множества натуральных чисел N может соответствовать запись:

N = {i: если целое i ∈ N, то i + 1 ∈ N, i ≥ 1 ∈ N).

Способы задания мультимножества аналогичны заданию множества. Например, мультимножество А = {a, a, b, b, b, с} имеет основание {a, b, с} и кратности k(a) = 2, k(b) = 3, k(c) = 1. Кратности элементов основания мультимножества иногда записываются в виде показателей, тогда зада­нию мультимножества А соответствует запись А = {a2, b3, с1}. Список кратностей мультимножества А = {av, bw, …} называется его первичной спецификацией и обозначается [А] = [v, w, …]. Согласно этому опреде­лению первичная спецификация тоже может быть мультимножеством, состоящим из натуральных чисел. Вторичной спецификацией мультимно­жества A = {av, bw, …} называется первичная спецификация его первич­ной спецификации, т.е. [[А]] = [ [v, w, . . . ]]. Отсюда следует, что если А - множество, состоящее из m элементов, то [А] = [1m], [[А]] = [[1т]] = {т}.

В заключение важно заметить, что любое задание множества должно быть корректным. Несоблюдение последнего может привести к трудно­стям типа парадокса Б. Рассела. Этот парадокс обычно иллюстрируется на примере парикмахера, определившего множество людей, которых он бреет, как совокупность всех жителей своего городка, не бреющихся самостоятельно. При таком задании множества остается неясным - принадлежит сам парикмахер этому множеству или нет? Следовательно, любой способ задания множества, должен обеспечивать его целостность, будь то задание его элементами, подмножествами, с помощью операций и т.п.

Операции со множествами. Пересечение множеств X и Y есть мно­жество X Y, состоящее из всех тех элементов, которые принадлежат и X, и Y, т.е. X Y = {х: х X и х Y}. Например, для X = {1, 2, 3}, Y = {2, 3, 4} X Y = {2, 3}, а для А = {1, 2}, В = {3,4} А B = ∅ - такие множества А и В называются непересекающимися. Ясно, что X ∩ ∅ = ∅. Пересечение двух и более множеств коммутативно: (X ∩ Y) = (Y X) , и ассоциативно:

(X ∩ Y) ∩ Z = X ∩ (Y ∩ Z) = X ∩ Y ∩ Z.

Объединение множеств X и Y есть множество X Y, состоящее из всех тех элементов, которые принадлежат X либо Y, т.е. X U Y ={х: х X или х Y}. Например, если X = {1, 2, 3}, Y = {2, 3, 4}, то X Y ={1, 2, 3,4}; ясно, что X ∪ ∅ = X. Объединение двух или более множеств коммутатив­но: X Y = Y X, и ассоциативно:

(X Y) Z = X (Y Z) = X Y Z.

Дистрибутивность - это важное свойство, которым обладают операции объединения и пересечения:

X (Y Z) = (X Y) (X Y), X (Y Z) = (X Y) (X Z).

Разность множеств X и Y есть множество Х\Y, состоящее из всех тех элементов X, которые не принадлежат Y, т.е. X\Y = {х: х X и х Y}. Например, если X = {1, 2, 3}, Y = {2, 3, 4}, то X\Y = {1}; ясно, что X\∅ = X и ∅\X = ∅. Из определения разности следует что (Х\Y) (X Y) = X.

Симметрическая разность множеств X и Y есть множество XY, состоящее из всех тех элементов X, которые не принадлежат Y, и всех тех элементов Y, которые не принадлежат X, т.е. ХY = {х: х X и х Y или .х ∈ Y и х X}. Например, если X = {1, 2, 3}, Y = {2, 3, 4}, то XY = {1, 4}; ясно, что ∅Х = Х = X. Из определения симметрической разности следует: XY = X Y \ X Y.

Дополнение множества Y относительно множества X определяется только тогда, когда Y X, и в этом случае это есть множество = X\Y. Например, для Y = {2, 3}, X = { 1, 2, 3} дополнением Y относительно X является множество = X\Y ={1}.

Законы де Моргана: _если X и Y - подмножества некоторого множества Z, то

Покрытие множества X образуют множества Xl, X2, …, если X множества Xi в этом случае называют блоками покрытия. Например, покрытием множества натуральных чисел является {1,2, …}⊂.

Разбиение множества X есть представление его непересекающимися множествами: X = Х1 X2 ∪ …, Xi Xj = (i j). Например, {1, 2, …} =. Множества Xi называются блоками или частями разбиения. Если число блоков разбиения конечно, то это число называется рангом разбиения. Изображать разбиения принято списком его блоков, ибо по определению список представляет его однозначно, и поэтому такой список также называется разбиением. Например, для множества X = = (а, b, с} запись (a, bc) обозначает разбиение множества X на две части, а и bc, отделяемые друг от друга запятой.

Спецификацией или типом разбиения X = Х1 X2 ∪ … ∪ Xr называется список мощностей его блоков [|Х1|, |Х2|, ... , |Хr|]. Так, разбиение (a, bc) имеет тип [1, 2]. Подразбиением (или расщеплением) некоторого разбиения называется разбиение, полученное разбиением блоков исходного разбиения. Так, разбиение (а, b, с) есть расщепление разбиения (a, be). Иными словами, путем объединения блоков из расщепления всегда можно "склеить" исходное разбиение. Наконец различают разбиения упорядоченные и неупорядоченные — в зависимости от того учитывается или не учитывается очередность их блоков, причем все возможные спецификации, отличные от обычного (неупорядоченного) разбиения, оговариваются особо.

Правило суммы следует из определения разбиения множества: для каждого разбиения конечного множества X = Х1 X2 ∪ … ∪ Xr , Xi Xj = ∅ (i j) справедливо равенство |X| = |X1| + ... + |Xr|.

Обобщенное правило суммы выполняется для покрытия конечного множества X Х1 X2 ∪ … ∪ Xr и имеет вид |X| ≤ |X1| + ... + |Xr|.

Произведением множеств Х1, …, Xr называется множество , состоящее из всех упорядоченных списков (x1, x2, …, xr), где xi Xi (i = 1, 2, ...,r). Такое произведение мно­жеств называется прямым или декартовым. Пусть X = {1, 2} и Y = {2, 3}, тогда XY = {(1, 2), (1, 3), (2, 2), (2, 3)}. Следовательно, каждый элемент прямого произведения (x1, x2, …, xr) можно рассматривать как r-мерный вектор, где хiХi является i-и координатой этого вектора (i = 1, 2, . . . , r). Принято считать, что X = ∅, Декартово произведение X . . . X с п сомножителями называется nдекартовой степенью множества X и обозначается Х(n). Так, если X = {1,2}, то X(3) = {(1, 1, 1), (1, 1, 2), (1, 2, 1), (2, 1, 1), (1, 2, 2), (2, 1, 2), (2, 2, 1), (2,2,2)}.

Правило произведения (выполняет важную роль для перечислительных комбинаторных задач): для любых конечных множеств Х1, Х2,..., Хп справедливо равенство |Хг ∙ Х2 ... ∙ Хп| = |Х1|г|... |Хп|.

Булеан есть множество всех подмножеств множества X, включая пустое множество ∅ и само множество X. Таким образом, элементами булеана как множества являются подмножества множества X. Например, булеан множества X = {1, 2, 3} состоит из множеств {0}, {!}, {2}, {3}, {1, 2}, {1, 3}, (2, 3}, {1, 2, 3}. Обозначается булеан 2X или P(X); обозначение 2X используется в связи с тем, что если X конечно, то | 2X | = 2|X|. В бу-леане естественно выделяются подмножества, состоящие из подмножеств множества X, имеющих одинаковую мощность: Ck(X) = {S X: |S| =k}. В этих обозначениях, очевидно, P (Х) = . Множества Ck (X) имеют мощность, равную значению биномиального коэффициента: если |Х| = n, то |Сk(Х)| =.

Графом на множестве вершин Sn = {a1, ..., ап} называется любое подмножество G множества С2(Sn), так что элементами графа G C2(Sn) являются двухэлементные подмножества вершин Sn именуемые ребрами графа G, Таким образом, каждый граф на множестве вершин Sn = {a1, …, ап} можно представить списком его ребер G = {(ai, aj), (ak, al)} где (ai, aj) G тогда и только тогда, когда вершины ai и aj соединены ребром в графе G, Значит, каждую пару (ai, aj) из такого списка можно интерпретировать как ребро.

Полный граф - это граф Кп = С2(Sn), так что |Кп|=.

Цикл - это граф вида G = {(a1, а2), 2, а3),…, (ak-1, ak), (ak, a1)}; обычно цикл обозначают через Ck; ясно, что |Ck| = k.

Путь - это граф вида G = {(a1, а2), 2, а3),…, (ak-1, ak)}; обычно путь обозначают Рk; ясно, что |Pk|= k - 1.

Графы изображают обычно графически: вершины Sn - точками, а ребра — линиями, соединяющими те пары вершин, которые образуют ребро графа, например, на рис. 1.1 для п = 5 представлен граф G = {(a1, а4), 2, а3), (a2, а4), (a3, а5)}. В этом графе имеются полный подграф К3 (он же цикл С3) на трех вершинах а1, а2, а4 и пути Р5, например, путь, последовательно проходящий через вершины а5, a3,a2, a1, a4.

Существует много различных модификаций графов.
Ориентированный граф: ребра G суть упорядоченные пары вершин.

Мультиграф: ребра G могут повторяться.

Гиперграф: гиперграфом на множестве вершин Sn = {a1, …, ап} называется любое подмножество G множества P (Sn), так что элементами гиперграфа G P (Sn) являются подмножествами вершин .Sn именуемые гиперребрами графа G, значит, гиперребра G могут иметь мощность, большую двух.

k-однородный гиперграф или k-граф: все ребра G имеют мощность, равную k.

Важными численными характеристиками графа являются

степень вершины: если a Sn, то dG (а) = |{е G: а е}|, т.е. степень вершины — это число ребер графа, содержащих в себе эту вершину, иначе — инцидентных этой вершине;

валентность: для множества вершин S и целого неотрицательного q валентность v(S, q, G) = |{е G: |S е| = q}| есть число ребер графа, пересекающихся с этим множеством вершин S по фиксированному числу вершин q; ясно, что v(a, 1, G) = dG(a). Эйлер установил, что во всяком графе степени удовлетворяют следующему тождеству: .

Упорядоченные разбиения — это разбиения, в которых порядок блоков существен, например, если X = (а, b, с}, то все упорядоченные разбиения множества X составляют разбиения:

с одним блоком: (abc);

с двумя блоками: (a, bc), (b, ас), (с, ab), (bc, а), (ас, b), (ab, с);

с тремя блоками: (а, b, с), (а, с, b), (с, a, b), (b, а, с), (b, с, а), (с, b, а).

Множество всех упорядоченных разбиений множества X будем обозначать через Т(Х), а его мощность — через Т(|Х|). Через Tk (X) обозначим множество всех упорядоченных разбиений, состоящих из k блоков, а через Tk(|X|) - мощность этого множества. Тогда если |Х| = п, то

.

Для упорядоченных разбиений по-прежнему корректно понятие типа как последовательности, состоящей из объемов блоков, поэтому через Т [п1, …, пr] будем обозначать множество всех упорядоченных разбиений типа [п1, …, пr], т.е. с объемами блоков п1, …, пr соответственно. Так, приведенное выше множество упорядоченных разбиений множест­ва X = {а, b, с} с двумя блоками состоит из множеств T[1, 2] и T[2, 1], имеющих по 3 (= T(1, 2) = T(2,1)) разбиения в каждом из этих множеств. Мощность множества T [п1, …, пr] будем обозначать через T(п1, …, пr).

Тогда если |X|=n=, то

T r(Х)=,



Здесь суммирование и объединение производятся по всем типам разбиений ранга r.

Эти численные характеристики упорядоченных разбиений могут вычисляться при помощи следующих формул:

где - полиномиальный коэффициент;

;

.

Беллиан есть множество всех разбиений множества X. Например, если X = {а, b, с}, то беллиан множества X состоит из разбиений

ранга один: (abc);

ранга два: (a, bc), (b, ас), (с, ab);

ранга три: (а, b, с).

Здесь подразделения на блоки разделяются запятыми. Предполагается, что блоки разбиений в беллиане не упорядочены, т.е. разбиения (с, ab) и (ab, с) понимаются как одинаковые. Беллиан будем обозначать через В(X), его мощность — через В(п), множество всех разбиений с точно k блоками - через Bk (X), а его мощность - через Bk(п), так что если |X| = n, то



Множество всех разбиений типа [п1, …, пr] обозначаем через В [п1, …, пr], а число разбиений множества Х (|X| = п) типа [п1, …, пr], где п = , обозначаем через B(п1, …, пr), так что Br(X) = U В(Х1, …, Xr), Вr(п) = ∑В(п1, …, пr), где объединение и суммирование производятся по всем возможным типам разбиений на n блоков.

Эти численные характеристики беллиана могут вычисляться при помощи следующих формул:





где σ(n, k) – число Стирлинга второго рода.





B(n) – число Белла,





- формула Дробинского.

Похожие:

Множества и операции со множествами. Понятие множества и мультимножества iconЭкзаменационные вопросы понятие множества, подмножество, дополнение к множеству. Операции с множествами, свойства операций
Понятие множества, подмножество, дополнение к множеству. Операции с множествами, свойства операций
Множества и операции со множествами. Понятие множества и мультимножества iconПрограмма курса "дискретная математика"
Дискретные множества. Характеристический век­тор множества и операции над множествами. Мощность прямого произведения множеств. Число...
Множества и операции со множествами. Понятие множества и мультимножества iconМатематический анализ
Понятие множества. Операции над множествами. Законы Моргана. Понятие отображения
Множества и операции со множествами. Понятие множества и мультимножества iconТеоретические вопросы из билетов к зачету (I семестр): (
...
Множества и операции со множествами. Понятие множества и мультимножества iconОперации над множествами и обозначения
А – дополнение множества а (до универсума). В данных методических указаниях при доказательстве тождеств и упрощениях выражений операция...
Множества и операции со множествами. Понятие множества и мультимножества iconБилет №1. Понятие множеств. Способы задания множеств. Основные числовые множества
Понятие множества является одним из неопределенных понятий. Существуют определяемые и неопределяемые множества. По числу элементов...
Множества и операции со множествами. Понятие множества и мультимножества iconВопросы по курсу «Дискретная математика»
Множества (конечные и бесконечные). Подмножества, включение. Операции над множествами и их свойства. Геометрическое изображение....
Множества и операции со множествами. Понятие множества и мультимножества iconВопросы к зачету по дисциплине «Математика»
Понятие множества и элемента множества. Способы задания множеств. Отношения между множествами и изображение их при помощи кругов...
Множества и операции со множествами. Понятие множества и мультимножества iconПрограмма курса «Дискретная математика»
Понятие множества. Равенство и включение множеств. Пустое и универсальное множества. Булевы операции, их свойства. Упорядоченные...
Множества и операции со множествами. Понятие множества и мультимножества iconПрограмма вступительного экзамена в аспирантуру по специальности 08. 00. 13 «Математические и инструментальные методы экономики»
Понятие множества. Способы задания множеств. Операции над множествами и их свойства
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org