|ЭЛЕМЕНТЫ ТЕОРИИ |СЧЕТНОЕ МНОЖЕСТВО | |
|МНОЖЕСТВ |- множество | |
|(с) |равномощное множеству| |
|http://karatel.nm.ru |натуральных чисел. | |
|Под множеством S |A={0, ±1, ±2,…}. | |
|будем понимать любое |f: A(N (должно быть | |
|собрвние определенных|взаимно однозначное | |
|и различных между |соответствие), | |
|собой объектов |a={i/2, i четное; | |
|мыслимое как единое |(1-i)/2. |A|=|N|. | |
|целое. Эти объекты |ТЕОРЕМА О СЧЕТНЫХ | |
|называются элементами|МНОЖЕСТВАХ: | |
|множества S. Для |1) любое бесконечное | |
|любого объекта можно |множество содержит | |
|установить |счетное подмножество.| |
|принадлежит он |Док-во: А?Ш, т.к. оно| |
|множеству или нет. |бесконечно. Можно | |
|A={1,2,3..}, |выбрать произвольный | |
|A={x|p(x)} – |элемент a1, берем | |
|обозначения. |остаток Aa1?Ш, | |
|Множества A и В |выбираем a2, | |
|считаются равными, |повторяем операцию | |
|если они состоят из |сколько-то раз | |
|одинаковых элементов |Aa1a2?0 ( a3… | |
|А=В. |Получаем | |
|{1,2,3}={2,1,3}={2,1,|бесконечность и т.д.,| |
|1,1,3}. 1) множество |счетное множество. | |
|всех множеств |2) любое бесконечное | |
|содержащих сами себя |подмножество B | |
|- множество всех |множества А счетно. | |
|множеств, 2) |Док-во: BcA, мощность| |
|множества, которые не||B|?|A|. По теореме 1| |
|содержат себя как |=> CcBcA, | |
|элемент. Рассмотрим ||N|?|B|?|A|, |C|=|N|.| |
|множество второго |По условию | |
|типа: A={x|xўx}. Если||N|?|B|?|A|=|N|, | |
|А себя не содержит, ||B|=|N|. | |
|то это одно из таких |3) объединением | |
|множеств, значит оно |конечного или | |
|должно содержаться в |счетного семейства | |
|А – парадокс рассела.|счетных множеств – | |
| |есть счетное | |
| |множество. A(инд.i) | |
|СООТНОШЕНИЕ МНОЖСТВ |U[сверху ?, снизу | |
|AcB, если все |i=1] A. A1 счетно, | |
|элементы А являются |A1={a11, a12, a13, | |
|элементами множества |a14…}. 1 индекс – | |
|В (А содержит В), А |номер множества, 2 | |
|является |индекс – номер | |
|подмножеством В. Если|элемента.Берем значит| |
|1.АсВ, 2. А?В, то |матрицу бесконечную | |
|АсВ, то А является |двумерную и соединяем| |
|подмножеством В |линиями элементы в | |
|{1,2}c{1,2,3}, |следующем порядке | |
|{1}c{1,2}. Множество,|B={a11, a21, a12, | |
|не содержащее |a13….} т.к. удалось | |
|элементов называется |перегруппировать, то | |
|пустым и обозначается|теорема доказана. | |
|Ш. Считается, что |4) мощность булеана | |
|пустое множество |множества больше | |
|является |мощности самого | |
|подмножеством любого |множества. | |
|множества AшcA. ||M|<|B(M)|. Док-во: | |
|Множество всех |надо доказать, что 1.| |
|подмножеств А ||M|?|B(M)| <=> | |
|называется множеством|McB(M). | |
|– степенью или |2. |M|?|B(M)|. | |
|булеаном. А{1,2,3}, |допустим |M|=|B(M)| | |
|B(A)={{Ш},{1},{2},{3}|=> существует | |
|,{1,2},{1,3},{2,3},{1|некоторая функция f: | |
|,2,3}} – булеан. |M(B(M). Рассматриваем| |
|УТВЕРЖДЕНИЕ: если |2 ситуации: а) | |
|множество А состоит |xЄf(X), б) xўf(x), | |
|из n элементов, то |xЄM, f(x)ЄB(M). | |
|булеан от А состоит |Остановимся на б) – | |
|из 2(c.n) элементов. |рассмотрим множество | |
|Док-во: 1-входит, 0 –|P={x|xЄf(x)}, ШЄB(M) | |
|не входит, 0..2(c.n) |булеану. Существует | |
|и Ш, всего 2(c.n). |х: Ш=f(x), xўШ. P – | |
| |подмножество | |
|ДЕЙСТВИЯ НАД |множества M => | |
|МНОЖЕСТВАМИ |PЄB(M), существует y:| |
|Объединием AUB |P=f(y). Разберемся | |
|называется |yЄP или yўP => | |
|множество, все |yЄf(y)=P | |
|элементы |противоречие, а | |
|которого являются |оттуда => yўf(y)=P | |
|элементами А или В |противоречие => | |
|(рис.2). |допущение неверно. | |
|AUB={x|xЄA или xЄB}. |5) мощность булеана | |
|AcAUB, BcAUB. |счетного множества | |
|Пересечением множеств|равна мощности | |
|A?B называют |континиума. | |
|множество, все ||B(N)|=|[0,1]|. | |
|элементы которого |A=[0,1] – все | |
|являются элементами |действительные числа | |
|обоих множеств А и В.|0-1, B=[0,2], | |
|A?B={x|xЄA и xЄB}, ||A|=|B|, y=2x. | |
|A?BcA, A?BcB (рис.3).| | |
|Дополнением множества|ОСНОВНЫЕ СООТНОШЕНИЯ | |
|А называют множество |КОМБИНАТОРИКИ | |
|эементов, не |Упорядоченные выборки| |
|принадлежащих |n из n элементов, где| |
|множеству А. |все элементы различны| |
|А={x|xўA} (рис.4). |называются | |
|Симметричная разность|перестановками из n | |
|– A+B=(AB)U(BA) |элементов Pn=n!. | |
|(рис.5). Вычитание – |Упорядоченные выборки| |
|множество принадлежит|объемом m из n | |
|В и не принадлежит А.|элементов (m<n), где | |
|BA={x|xЄB и |все элементы | |
|xўA}=B?A(вектор). |различны, называются | |
| |размещениями. Их | |
|СВОЙСТВА |число=A(c.m)(инд.n)=n| |
|1) AUB=BUA — |!/(n-m)!. Пример: | |
|свойства |группа из 15ти | |
|коммутативности |человек выиграла 3 | |
|(объединения), 1') |различных книги. | |
|A?B=B?A — |Сколькими способами | |
|коммутативный |эти книги можно | |
|перенос, 2) |распределить среди | |
|ассоциативность |группы? | |
|AU(BUC)=(AUB)UC, 2') |Неупорядоченные | |
|A?(B?C)=(A?B)?C, 3) |выборки объемом m из | |
|дистрибутивность: |n элементов (m<n) | |
|AU(B?C)=(AUB)?(AUC), |называются | |
|3') |сочетаниями. Их число| |
|A?(BUC)=(A?B)U(A?C) |C(c.m)(инд.n)=n!/m!(n| |
|Пример: a(b+c)=ab+ac |-m)! Пример: группа | |
|– алгебра чисел, |из 15 человек | |
|a+bc?(a+b)(a+c)… 4) |выигрыла 3 одинаковых| |
|AUШ=A, 4’)A?U=A, |книги. Сколькими | |
|5)AUA(надчеркнутое)=U|способами можно | |
|, 5’) |распределить эти | |
|A?A(надчеркн)=Ш, 6) |книги? Размещения с | |
|AUA=A, 6’) A?A=A, 7) |повторениями: | |
|AUU=U, 7’)A?Ш=Ш, 8) |упорядоченные выборки| |
|[AUB](надчеркнутое)=A|объемом m из n | |
|(надч)UB(надч) – |элементов, где | |
|закон де Моргана, 8’)|элементы могут | |
|тоже что и прошлое, |повторяться. Их число| |
|только ?. |A(c.m)(инд.n)(n)=n(c.| |
|[c+(ab)](надчерк)=c(н|m). Пример: кодовый | |
|адч)(a(надч)+b(надч))|замок состояит из 4х | |
|. 9) закон |разрядов, в каждом | |
|поглощения: |разряде независимо от| |
|AU(A?B)=A, 9’) |других могут быть | |
|A?(AUB)=A, |выбраны цифры от 0 до| |
|a+ab=a(U+b)=aU=a, |9. Сколько возможных | |
|a(a+b)=aa+ab=a+ab, |комбинаций (10(c.4))?| |
|(a+b)(a+c)=aa+ac+ab+b| | |
|c=a+ac+ab+bc=…=a+bc. |СВОЙСТВО | |
| |биноминального | |
|ОТНОШЕНИЕ ФУНКЦИИ |коэффициента | |
|Упорядоченной парой |(С[степень, индекс]):| |
|<x,y> называется |1) 0!=1, 2) | |
|совокупность, |C[0;m]=C[m;m]=1, 3) | |
|состоящая из 2х |C[m-n; m]=C[n;m], | |
|элементов х и y, |C[m-n; | |
|расположенные в |m]=m!/(m-n)!(m-(m-n))| |
|определенном порядке.|!= | |
|2 пары <x,y> и <u,v> |=m!/(m-n)!n!=C[r;m], | |
|считаются равными т. |4) C[n;m]=C[n;m-1] + | |
|и т.т., к. х=U, y=v. |C[n-1;m-1], | |
|Бинарным или |C[i;n]C[i;m]= | |
|двуместным отношением|=C[m;n]C[i-m;n-m]. | |
|? называется |БИНОМ НЬЮТОНА: | |
|множество |(x+y)(c.m)=S[m;n=0]C[| |
|упорядоченных пар, |n;m] * | |
|элементы пар |*x(c.n)*y(c.m-n). | |
|называются |Док-во: методом | |
|координатами или |математической | |
|компонентами |индукции: m=1, | |
|отношения ?. <x,y>Є? |x+y=1x’+1y’, m-1, | |
|<=> x?y. ОПРЕДЕЛЕНИЕ |покажем, что | |
|2: обастью |соотношение верно и | |
|определения бинарного|для m. | |
|отношения ? называют |(x+y)(c.m)=(x+y)(x+y)| |
|множество |(c.m-1)=(x+y)S[n=0;m-| |
|D(инд.?){x|существует|1] x(c.n)y(c.m-n-1)= | |
|y: <x,y>Є?}. Областью|=xS[n=0;m-1]C[n;m-1] | |
|значения ? называется|x(c.n)y(c.m-n-1)+yS[n| |
|множество: |=0;m-1]C[n;m-n]x(c.n)| |
|R(инд.?)={y|существуе|y(c.m-n- | |
|т х, <x,y>Є?}. |-1)=…пиздец…=C[0;m]x(| |
|Примеры: |c.0)y(c.m)+S[n=1;m-1]| |
|1.{<1,2>,<2,4>,<3,3>,|C[n;m]x(c.n)y(c.m-n).| |
|<2,1>}, | | |
|D(инд.?)={1,2,3,2}={1| | |
|,2,3}={2,3,1}, |РАЗБИЕНИЕ МНОЖЕСТВА | |
|R(инд.?)={2,4,3,1}={1|n-элементов | |
|,2,3,4}. Отношение |множества. Надо | |
|равенства на |разбить r1,r2…,r | |
|множестве |(инд.m) элементов. n!| |
|действительных чисел:|– количество | |
|{<x,y>|x,y – |перестановок. | |
|действительные и |n!/r1!…r (инд.n)! | |
|x=y}, {<x,y>|x,y – |– количество | |
|целые и существует |вариантов | |
|z>0: x+z=y} |подмножеств. | |
| |Сочетания с | |
|УПОРЯДОЧЕННАЯ |повторениями: | |
|ПОСЛЕДОВАТЕЛЬНОСТЬ |C(инд.n+r-1)(с.n). | |
|x1,x2…,xn |Множество всех вершин| |
|называются |V={v1,v2…}. | |
|упорядоченные группы |Ребра: X={x1,x2…}. | |
|или пары. <x1,x2…xn> |Ребро такое может | |
|n-нарным отношением |быть | |
|называется множество |обозначено | |
|n-нок. Пусть даны |x1={v1,v2}. Если в | |
|n-множества A1,A2…An.|графе есть петли | |
|Множество всех n-нок |и/или кратные ребра, | |
|<x1…xn> таких, что |то это псевдограф. | |
|x1ЄA1…., xnЄAn. |Псевдограф без петель| |
|A1xA2x…xAn=П[сверху –|– мультиграф. | |
|i, снизу – |Мультиграф, в котором| |
|i=1]A(инд.i); Ai=A. |не одно ребро не | |
|Обратным отношением |имеет кратность | |
|для отношения |больше 1 называется | |
|?={<x,y>|<x,y>Є?} |графом. Если | |
|называется отношение |упорядоченная пара | |
| |v1,v2, если все пары | |
|?(c.-1)={<y,x>|<x,y>Є|являются | |
|?}. Композицией |упорядоченными, то | |
|отношений ?1 и ?2 |граф называется | |
|называется отношение |ориентированным | |
|?=o?1={<x,y>|существу|(орграф). Ребра | |
|ет z: <x,y>Є?1 и |орграфов называются | |
|<z,y>Є?2} |дугами и обозначаются| |
| |круглыми скобками. | |
|СВОЙСТВА БИНАРНЫХ |Неорграф G1,G2… | |
|ОТНОШЕНИЙ |Орграф D1,D2… | |
|1) (?(с.-1))(с.-1)=?,| | |
|2) (?2 o |ПОНЯТИЕ СМЕЖНОСТИ, | |
|?1)(c.-1)=?1(c.-1) o |ИНЦЕНДЕНТНОСТИ | |
|?2(c.-1); Бинарное |x={v,w} – ребро | |
|отношение f |неорграфа, тогда v,w | |
|называется функцией, |– концы ребра. Пусть | |
|если из того, что |x(v,w) орграф, v – | |
|<x,y>Єf, <x,z>Єf => |начало, w – конец. | |
|y=z. 2 функции |ОПРЕДЕЛЕНИЕ: если | |
|называются равными, |вершина v является | |
|если они состоят из |концом ребра х | |
|одних и тех же |неорграфа (началом | |
|элементов. |или концом дуги х | |
|D(инд.f)=X, |орграфа), то v и х | |
|R(инд.f)=Y. Говорят, |называется | |
|что функция f |инцидентными. | |
|осуществляет |Вершины v,w | |
|отображение множества|называются смежными, | |
|f: X(Y, X((стрелка с |если есть ребро | |
|перечеркнутым |{v,w}=x, соединяющее | |
|надчеркиванием)Y; |эти вершины. Степенью| |
| |вершины v графа g – | |
|n-местной функцией |число ?(v) ребер | |
|называют отношение f,|графа G, инцедентных | |
|если f: x(c.n)(Y или |вершине v. Вершина | |
|Y=f(x1,…,xn(c.n)). |графа имеет степень | |
|ОПРЕДЕЛЕНИЕ1: функция|0, называется | |
|f: X(Y называется |изолированной, а | |
|инъективной, если для|степень 1 висячей. В | |
|любого x1,x2ЄX, |неориентированном | |
|Y=f(x1), Y=f(x0) |псевдографе вклад | |
|=>x1=x2. |каждой петли | |
|ОПРЕДЕЛЕНИЕ2: функция|инцидентной вершины v| |
|f: X(Y называется |в степень этой | |
|сюръективной, если |вершины =2. Для | |
|для любого yЄY |орграфа: полустепенью| |
|существует x, f(x)=y.|исхода (захода) | |
|ОПРЕДЕЛЕНИТЕ3: |вершины v орграфа D | |
|функция называется |называется число | |
|биективной, если она |?(с.+)(v) – исход, | |
|одновременно и |?(с. -)(v) – заход. | |
|инъективная и |В случае псевдографа | |
|сюръективная. |вклад каждой петли | |
|СЛЕДСТВИЕ: говорят, |смежной вершины v | |
|что биективная |равен 1. | |
|функция f |n(G) – количество | |
|осуществляет |вершин неорграфа, | |
|однозначное |m(G) – количество | |
|отображение множества|ребер неорграфа, n(D)| |
|Х на множество Y. |для орграфа, m(D) – | |
|ПРИМЕРЫ: X=R |количество дуг | |
|(действительные R), |орграфа. Для каждого | |
|Y=R, y=e(c.x). |псевдографа D | |
|Монотонность функции |выполняется следующее| |
|говорит о |равенство S[vЄV] | |
|инъективности – |?(v)=2m(G), | |
|монотонно возрастает.|S[vЄV] | |
|y=x(c.3)-x – |?(с.+)(v)=S[vЄV] | |
|сюрьективная, |?(с.-)(v)=m(D). | |
|y=x(c.3) – | | |
|биективная. |ИЗОМОРФИЗМ. | |
|Композиция 2х функций|ГОМЕОМОРФИЗМ. | |
|– это функция gof. |G1(V1,X1), G2(V2,X2) | |
| |называются | |
|<x,y>=gof, <x,z>Єgof}|изоморфными, если | |
|=> существует |существует | |
|некоторая функция, |биективное | |
|что существует U: xfu|(взаимооднозначное) | |
|и ugy |отображение ?:V1(V2, | |
|y=g[f(x)] |сохраняющее | |
|существует V: xfV |смежность, т.е. если | |
|=>U=V и Vgz =>y=z, |{v,w}ЄX1 <=> | |
|z=g[f(x)]. |{?(v),?(w)}ЄX2. | |
|УТВЕРЖДЕНИЕ: |Орграфы D1(V1,X1), | |
|композиция 2х |D2=(V2,X2) называются| |
|биективных функций – |изоморфными, если | |
|есть биективная |существует | |
|функция. ОПРЕДЕЛЕНИЕ:|отображение ?:V1(V2, | |
|тождественным |(v,w)ЄX1 <=> | |
|отображением |(?(v),?(w))ЄX2. | |
|множества Х в себя |Свойства изоморфных | |
|называется |графов: — если G1,G2 | |
|отображение e(инд.x):|– изоморфны и ?:V1(V2| |
|X(x, такое, что для |– для любого vЄV1, | |
|любых xЄX существует |?(v)=?(?(v)), — | |
|значение функции |m(G1)=m(G2), | |
|e(инд.x)(x)=x, |n(G1)=n(G2). Для | |
|foe(инд.x)=f, |орграфа свойства | |
|e(с.y)of=f. |аналогичны, для | |
|УТВЕРЖДЕНИЕ: |любого vЄV1, | |
|отображение f: X(Y |?(с.-)(v)=?(инд.-)(?(| |
|имеет обратное |v)) | |
| |, | |
|ОТНОШЕНИЕ ЧАСТИЧНОГО |?(с.+)(v)=?(с.+)(?(v)| |
|ПОРЯДКА |), m(D1)=m(D2), | |
|на множестве х, для |n(D1)=n(D2). Примеры | |
|которого 2 любые |изоморфных графов см.| |
|элементы сравнимы |на рисунке. | |
|называется отношением|УТВЕРЖДЕНИЕ: | |
|линейного порядка. |изоморфизм групп | |
|Любые x,yЄX либо x?y |является отношением | |
|либо y?x. |эквивалентности на | |
|Определение: говорят,|множестве | |
|что элемент х |графов или орграфов. | |
|покрывает элемент y, |ОПРЕДЕЛЕНИЕ: | |
|если x?y и |операцией по | |
|существует такое, что|разбиению дуги (u,v) | |
|x?z?y. |в орграфе D(v,x) | |
| |называется | |
|ДИАГРАММА ХАССЕ |операция, которая | |
|ПРИМЕРЫ: некое |состоит из удаления | |
|множество A={1,2,3} |добавления к V | |
|и его булеан |вешины w. Орграф D2 | |
|B(A)={Ш,{1},{2},{3}, |называется разбиением| |
|{1,2}, |орграфа D1 | |
|{1,3}, {2,3}, |, если D2 получается | |
|{1,2,3}}=X. 1,2,3 |из D1 путем | |
|покрывают Ш. |последовательного | |
|Множество |применения интеграции| |
|Х={1,2,3,5,6,10,15,30|дуг. Орграфы | |
|}. y делится |D1,D2(G1,G2) | |
|нацель на х. |называются | |
|Диаграммы ХАССЕ на |гомеоморфными, если | |
|рисунке. |существует их | |
|Если порядок |подразделение, | |
|линейный, то просто |которое является | |
|линия будет. |изоморным. Если | |
|Определение: 2 |степени всех вершин | |
|частично |равны k, то граф | |
|упорядоченных |называется регулярным| |
|множества Х,Y |в степени k. Граф | |
|называются |исходящий из 1 | |
|изоморфными, если |вершины называется | |
|существует биективная|тривиальным. | |
|функция, ?*Х(Y, |Двудольным называется| |
|сохраняющая частичный|граф G(V,X), | |
|порядок, т.е. для |такой, что он разбит | |
|любых x,yЄX, x?y => |V1,V2(v1Uv2=v, | |
|?(x)??(y). |v1?v2?Ш), | |
| |каждое ребро | |
|СРАВНЕНИЕ МНОЖЕСТВ |инцедентно вершине из| |
|ОПРЕДЕЛЕНИЕ: |v1 и v2. | |
|множества А и В | | |
|называются | | |
|равномощными, если | | |
|между АиВ существуют | | |
|взаимно однозначные | | |
|соответствия. 1. A(B,| | |
||A|=|B|. УТВЕРЖДЕНИЕ:| | |
|отношение | | |
|равномощности | | |
|множеств является | | |
|отношением | | |
|эквивалентности. | | |
|Реплексивность – | | |
|можно установить | | |
|соответствие – сам с | | |
|собой. Симметрия – | | |
|хоть так, хоть эдак. | | |
|СЛУЧАЙ 1: АиВ | | |
|конечное множество: | | |
|утверждение: | | |
|множества А и В | | |
|равномощны т. и т.т.,| | |
|к. количество | | |
|элементов в А равно | | |
|количеству элементов | | |
|в В. Докажем: | | |
|допустим 2 множества | | |
|имеют одинаковые | | |
|элементы, имеют | | |
|одинаковые индексы | | |
|соответствующих друг | | |
|другу значений. | | |
|Множества равномощны.| | |
|Обратно: допустим | | |
|множества равномощны | | |
|=> существуют взаимно| | |
|однозначные | | |
|соответствия. | | |
|Мощность равна | | |
|количеству элементов,| | |
|для конечных | | |
|множеств. СЛУЧАЙ2: | | |
|бесконечное | | |
|множество: | | |
|N={1,2,3..}. Пример: | | |
|множество всех | | |
|натуральных чисел. И | | |
|множество всех четных| | |
|чисел: M={2,3,4..}. | | |
|Теперь установим | | |
|равномощность | | |
|m(инд.i)=2n(инд.i). | | |
|Говорят, что мощность| | |
|множества А не | | |
|превосходит мощность | | |
|множества В. | | |
||A|?|B|, если | | |
|существует множество | | |
|B1cB, что |A|=|B1|. | | |
|Мощность А < мощности| | |
|В, при 1) |A|?|B|, 2.| | |
||A|?|B|. ТЕОРЕМА: | | |
|отношения |A|?|B|, | | |
||A|<|B| являются | | |
|отношениями линейного| | |
|порядка. УТВЕРЖДЕНИЕ:| | |
|ТЕОРЕМА КОНТОрА: | | |
|пусть N={1,2..} | | |
|множество всех | | |
|натуральных чисел, а | | |
|А=[0,1] множество | | |
|всех чисел ближайших | | |
|отрезку [0,1], тогда | | |
||N|?|A| и докажем: 1)| | |
|докажем |N|?|A|, | | |
|берем действительные | | |
|числа a(инд.i)=(1/i),| | |
|i=1,2,3.. все они | | |
|лежат на отрезке | | |
|[0,1] значит |N|?|A|.| | |
|2) допустим, что | | |
||N|=|A|, то f:N(A, | | |
|тогда | | |
|f(1)=0.a11a12a13, | | |
|f(2)=0.a21a22a23,… | | |
|f(n)=0.an1an2an3. | | |
|Число b=0.b1b2b3, | | |
|b(инд.i)={1, aij?1; | | |
|2, aij=1. | | |————————
[pic][pic]
[pic]
[pic]
[pic]
[pic]
