| |||||
МЕНЮ
| Большая коллекция шпор для МАТАНа (1 семестр 1 курс)Большая коллекция шпор для МАТАНа (1 семестр 1 курс)|ЭЛЕМЕНТЫ ТЕОРИИ |СЧЕТНОЕ МНОЖЕСТВО | | |МНОЖЕСТВ |- множество | | |(с) |равномощное множеству| | |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 – |элемент a1, берем | | |обозначения. |остаток A\a1?Ш, | | |Множества A и В |выбираем a2, | | |считаются равными, |повторяем операцию | | |если они состоят из |сколько-то раз | | |одинаковых элементов |A\a1\a2?0 ( a3… | | |А=В. |Получаем | | |{1,2,3}={2,1,3}=2,1,. 1) множество |счетное множество. | | |всех множеств |2) любое бесконечное | | |содержащих сами себя |подмножество B | | |- множество всех |множества А счетно. | | |множеств, 2) |Док-во: BcA, мощность| | |множества, которые не||B|?|A|. По теореме 1| | |содержат себя как |=> CcBcA, | | |элемент. Рассмотрим ||N|?|B|?|A|, |C|=|N|.| | |множество второго |По условию | | |типа: A=x. Если||N|?|B|?|A|=|N|, | | |А себя не содержит, ||B|=|N|. | | |то это одно из таких |3) объединением | | |множеств, значит оно |конечного или | | |должно содержаться в |счетного семейства | | |А – парадокс рассела.|счетных множеств – | | | |есть счетное | | | |множество. A(инд.i) | | |СООТНОШЕНИЕ МНОЖСТВ |U[сверху ?, снизу | | |AcB, если все |i=1] A. A1 счетно, | | |элементы А являются |A1= . 1 индекс – | | |В (А содержит В), А |номер множества, 2 | | |является |индекс – номер | | |подмножеством В. Если|элемента.Берем значит| | |1.АсВ, 2. А?В, то |матрицу бесконечную | | |АсВ, то А является |двумерную и соединяем| | |подмножеством В |линиями элементы в | | |{1,2}c{1,2,3}, |следующем порядке | | |{1}c{1,2}. Множество,|B= т.к. удалось | | |элементов называется |перегруппировать, то | | |пустым и обозначается|теорема доказана. | | |Ш. Считается, что |4) мощность булеана | | |пустое множество |множества больше | | |является |мощности самого | | |подмножеством любого |множества. | | |множества AшcA. ||M| | | |называется множеством|McB(M). | | |– степенью или |2. |M|?|B(M)|. | | |булеаном. А{1,2,3}, |допустим |M|=|B(M)| | | |B(A)={{Ш},{1},{2},{3}|=> существует | | |,{1,2},{1,3},{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Є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. |5) мощность булеана | | |AcAUB, BcAUB. |счетного множества | | |Пересечением множеств|равна мощности | | |A?B называют |континиума. | | |множество, все ||B(N)|=|[0,1]|. | | |элементы которого |A=[0,1] – все | | |являются элементами |действительные числа | | |обоих множеств А и В.|0-1, B=[0,2], | | |A?B=x, ||A|=|B|, y=2x. | | |A?BcA, A?BcB (рис.3).| | | |Дополнением множества|ОСНОВНЫЕ СООТНОШЕНИЯ | | |А называют множество |КОМБИНАТОРИКИ | | |эементов, не |Упорядоченные выборки| | |принадлежащих |n из n элементов, где| | |множеству А. |все элементы различны| | |А=xўA (рис.4). |называются | | |Симметричная разность|перестановками из n | | |– A+B=(A\B)U(B\A) |элементов Pn=n!. | | |(рис.5). Вычитание – |Упорядоченные выборки| | |множество принадлежит|объемом m из n | | |В и не принадлежит А.|элементов (m называется |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 пары и |=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=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(инд.?)1] x(c.n)y(c.m-n-1)= . Областью|=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(инд.?)=. |-1)=…пиздец…=C[0;m]x(| | |Примеры: |c.0)y(c.m)+S[n=1;m-1]| | |1.C[n;m]x(c.n)y(c.m-n)., | | | |D(инд.?)={1,2,3,2}= ={2,3,1}, |РАЗБИЕНИЕ МНОЖЕСТВА | | |R(инд.?)={2,4,3,1}=,2,3,4. Отношение |множества. Надо | | |равенства на |разбить r1,r2…,r | | |множестве |(инд.m) элементов. n!| | |действительных чисел:|– количество | | |x=y, |подмножеств. | | | |Сочетания с | | |УПОРЯДОЧЕННАЯ |повторениями: | | |ПОСЛЕДОВАТЕЛЬНОСТЬ |C(инд.n+r-1)(с.n). | | |x1,x2…,xn |Множество всех вершин| | |называются |V={v1,v2…}. | | |упорядоченные группы |Ребра: X={x1,x2…}. | | |или пары. |Ребро такое может | | |n-нарным отношением |быть | | |называется множество |обозначено | | |n-нок. Пусть даны |x1={v1,v2}. Если в | | |n-множества A1,A2…An.|графе есть петли | | |Множество всех n-нок |и/или кратные ребра, | | | таких, что |то это псевдограф. | | |x1ЄA1…., xnЄAn. |Псевдограф без петель| | |A1xA2x…xAn=П[сверху –|– мультиграф. | | |i, снизу – |Мультиграф, в котором| | |i=1]A(инд.i); Ai=A. |не одно ребро не | | |Обратным отношением |имеет кратность | | |для отношения |больше 1 называется | | |?=Є? |графом. Если | | |называется отношение |упорядоченная пара | | | |v1,v2, если все пары | | |?(c.-1)=. Композицией |упорядоченными, то | | |отношений ?1 и ?2 |граф называется | | |называется отношение |ориентированным | | |?=o?1=существу |дугами и обозначаются| | | |круглыми скобками. | | |СВОЙСТВА БИНАРНЫХ |Неорграф 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 – | | |Єf, Є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) | | | |называются | | |=gof, Є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 путем | | |покрывают Ш. |последовательного | | |Множество |применения интеграции| | |Х= . 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] |
ИНТЕРЕСНОЕ | |||
|