Новиков Ф.А. Дискретная математика для программистов (860615), страница 6
Текст из файла (страница 6)
. . , z};М : = {х \ Р{х)} ;М: = {х | х: = /}.При задании множеств перечислением обозначения элементов разделяют запятыми. Характеристический предикат — это некоторое условие, выраженноев форме логического утверждения или процедуры, возвращающей логическое26Глава 1. Множества и отношениязначение, и позволяющее проверить, принадлежит ли любой данный элементмножеству. Если для данного элемента условие выполнено, то он принадлежитопределяемому множеству, в противном случае — пе принадлежит. Порождающая процедура — это процедура, которая в процессе работы порождает объекты,являющиеся элементами определяемого множества.Примеры1.
М 9 : = { 1,2,3,4,5,6,7,8,9}.2. М9: = {п | п £ N & п < 10}.3. Мд : = {п | п: = 0; for i from 1 to 9 do n : = n + 1; yield n end for}.При задании множеств перечислением обозначения элементов иногда снабжаютиндексами и указывают множество, из которого берутся индексы. В частности, запись {ai] k i=l означает то же, что { a i , . . . , a^}, а запись М = {М а } а ( - Аозначает, что М является семейством, элементами которого являются множества Ма, причём индекс а «пробегает» множество А. Знак многоточия ( . . .
) ,который употребляется при задании множеств, является сокращённой формойзаписи, в которой порождающая процедура для множества индексов считаетсяочевидной.Пример{ai,a2,a3,...} = {oi}2i-ЗАМЕЧАНИЕМножество целых чисел в диапазоне от m до п в этой книге обозначается так: тп..п. Тоестьm..n=Г {к € Z | т ^ к к к < п} = {А: € Z | for к from т t o п do yield к end f o r } .Перечислением элементов можно задавать только конечные множества. Бесконечные множества задаются характеристическим предикатом или порождающейпроцедурой.ПримерN = f {п | п: = 0; while true do п: = п + 1; yield n end while}.1.1.3.
Парадокс РасселаВозможность задания множеств характеристическим предикатом зависит от предиката. Использование некоторых предикатов для этой цели может приводитьк противоречиям. Например, все рассмотренные в примерах множества не содержат себя в качестве элемента. Рассмотрим множество Y всех множеств, песодержащих себя в качестве элемента:УD={X\X$X}.271.1. МножестваЕсли множество У существует, то мы должны иметь возможность ответить наследующий вопрос: У € У? Пусть У е У, тогда Y £ Y.
Пусть Y & Y, тогдаY е Y. Получается неустранимое логическое противоречие, которое известнокак парадокс Рассела1. Вот три способа избежать этого конкретного парадокса.1. Ограничить используемые характеристические предикаты видомР{х) = х е A kQ(x),где А — известное, заведомо существующее множество (универсум). Обычнопри этом используют обозначение {х е А | Q(z)}. Для Y универсум не указан,а потому Y множеством не является.2. Теория типов. Объекты имеют тип 0, множества элементов типа 0 имеют тип 1,множества элементов типа 0 и 1 — тип 2 и т. д. У не имеет типа и множествомне является.3. Явный запрет принадлежности множества самому себе: X е X — недопустимый предикат.
При аксиоматическом построении теории множеств соответствующая аксиома называется аксиомой регулярности.ОТСТУПЛЕНИЕСуществование и анализ парадоксов в теории множеств способствовали развитию такназываемого конструктивизма — направления в математике, в рамках которого рассматриваются только такие объекты, для которых известны процедуры (алгоритмы) их порождения. В конструктивной математике исключаются из рассмотрения те понятия и методыклассической математики, которые не заданы алгоритмически.Парадокса Рассела можно избежать, ограничив рассматриваемые множества. Например, достаточно запретить рассматривать в качестве множеств классы, содержащие самих себя. При этом, однако, нет полной уверенности в том, что пеобнаружатся другие противоречия. Полноценным выходом из ситуации являлосьбы аксиоматическое построение теории множеств и доказательство непротиворечивости построенной формальной теории.
Однако исследование парадоксов инепротиворечивости систем аксиом является технически трудной задачей и уводит далеко в сторону от программистской практики, для которой важнейшимиявляются конечные множества. Поэтому формальная аксиоматика теории множеств здесь не приводится. Мы излагаем необходимые сведения полуформально,опираясь везде, где это возможно, на программистскую интуицию читателя.1.1.4. МультимножестваВ множестве все элементы различны, а значит, входят в множество ровно одинраз. В некоторых случаях оказывается полезным рассматривать совокупностиэлементов, в которые элементы входят по несколько раз.1Бертран Рассел (1872-1970).28Глава 1. Множества и отношенияПримерраз.В штатном расписании одна и та же должность встречается несколькоПусть X — { x i , . .
. , хп} — некоторое (конечное) множество и пусть с ц , . . . , ап —неотрицательные целые числа. Тогда мультимножеством X (над множеством X)называется совокупность элементов множества X, в которую элемент Xi входитщ раз, cii ^ 0. Мультимножество обозначается одним из следующих способов:х = [ж"1, • • • 1ХпП] ~ 4•••v'а\•4• • i ХП1 • • • ,Хп) = (^l(^l)) • • •v'апХп)).Пример Пусть X = {а, Ь, с}.
Тогда X = [а°Ь3с4] = (Ь, 6,6; с, с, с, с) == (0(a), 3(6), 4(c)).ЗАМЕЧАНИЕЭлементы мультимножества, равно как и элементы множества, считаются неупорядоченными.Пусть Х = (ai(xi),..., а п (х п )) — мультимножество над множеством Х = {х\,... ,х п }.Тогда число а* называется показателем элемента Xi, множество X — носителеммультимножества X, число т = а\ + ... + ап — мощностью мультимножества X,а множество X — {xi е X \ а{ > 0} называется составом мультимножества X.Пример Пусть X — [а°Ь3с4] — мультимножество над множеством X = {а, 6, с}.Тогда Х = {Ь, с}.Мультимножество X — (ai(a;i),...
,а п (ж п )) над множеством X = {х\:...называется индикатором, если Vг € 1 ..п (а^ = 0 V а^ = 1).,хп}Пример Мультимножество X = (6; с) является индикатором над множествомX — {a, Ь, с}, причём Х_ — {Ь, с}.1.2. Алгебра подмножествСамого по себе понятия множества ещё недостаточно — нужно определить способы конструирования новых множеств из уже имеющихся, то есть определитьоперации над множествами.1.2.1. Сравнение множествМножество А содержится в множестве В (множество В включает множество А),если каждый элемент множества А есть элемент множества В:AcBD=xeA^xeB.291.2. Алгебра подмножествВ этом случае А называется подмножеством В, В — надмножеством А.
Поопределению VM ( 0 с М).ЗАМЕЧАНИЕНетрудно видеть, что понятие подмножества множества X равнообъёмно понятию ин-дикатора над множеством X. Действительно, если X = {xi,...,xn}— множество, аY — любое подмножество множества X, Y с X, то существует единственный индикаторY = ( a i ( x i ) , . . . , ап(хп)) над множеством X, такой, что Vг € \..п (а,г = 1 <*=>• Xi £ Y).Два множества равны, если они являются подмножествами друг друга:А = B=f АсВ к В с А.ТЕОРЕМА Включение множеств обладает следующими свойствами:1.
УЛ (А с А).2. У А, В (А с В к В с А =>• А = В).3. V А, В, С {АсВкВсС=^А с С).ДОКАЗАТЕЛЬСТВО[ 1 ] Имеем х £ А[2]х е А, и значит, АсА.По определению.[ 3 ] Если х £ Аи значит, Ас С.х £ В их с Вх £ С, то х £ А = > х £ С,•Если А с В и А ф В, то множество А называется собственным подмножествоммножества В, а В — собственным надмножеством множества А.ЗАМЕЧАНИЕЕсли требуется различать собственные и несобственные подмножества, то для обозначения включения собственных подмножеств используется знакСЛЕДСТВИЕЛД в с са для несобственных — С.Age.1.2.2. Равномощные множестваГоворят, что между множествами А и В установлено взаимно-однозначное соответствие, если каждому элементу множества А поставлен в соответствие одини только один элемент множества В и для каждого элемента множества В одини только один элемент множества А поставлен в соответствие этому элементумножества В.
В этом случае говорят также, что множества А и В изоморфны, ииспользуют обозначение А ~ В. Если при заданном соответствии элементу а £ Асоответствует элемент Ь £ В, то данное обстоятельство обозначают следующимобразом: a i—• Ь.30Глава 1. Множества и отношенияЗАМЕЧАНИЕВесьма общее понятие соответствия в этом учебнике трактуется с программистских позиций. Если сказано, что между множествами А и В установлено соответствие, то подразумевается, что задан способ по любому элементу а € А определить соответствующийему элемент b e В. Способ может быть любым, если возможность его применения невызывает сомнений.
Например, это может быть массив array [A] o f В, или процедура типа ргос (Л) : В, или же выражение, зависящее от переменной типа А и доставляющеезначение типа В.Пример Соответствие п > 2п устанавливает взаимпо-одпозпачпое соответствие между множеством натуральных чисел N и множеством чётных натуральных чисел 2N, N ~ 2N.Нетрудно видеть, что:1) любое множество взаимно-однозначно соответствует самому себе: А ~ А —достаточно рассмотреть соответствие а и а , где а € А;2) если А ~ В, то В ~ А — достаточно использовать соответствие апостроения соответствия b у-> а, где a G A,b G В;b для3) если Л ~ В и Б ~ С, т о А ~ С — соответствие устанавливается с использованием промежуточного элемента b 6 В: а н-> b н-• с, где а е A, be В, се С.Если между двумя множествами А и В может быть установлено взаимно-однозначиое соответствие, то говорят, что множества имеют одинаковую мощность,или что множества равномощны, и записывают это так: \А\ = |5|.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
