реферат, рефераты скачать Информационно-образоательный портал
Рефераты, курсовые, дипломы, научные работы,
реферат, рефераты скачать
реферат, рефераты скачать
МЕНЮ|
реферат, рефераты скачать
поиск
Большая коллекция шпор для МАТАНа (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]



© 2003-2013
Рефераты бесплатно, рефераты литература, курсовые работы, реферат, доклады, рефераты медицина, рефераты на тему, сочинения, реферат бесплатно, рефераты авиация, курсовые, рефераты биология, большая бибилиотека рефератов, дипломы, научные работы, рефераты право, рефераты, рефераты скачать, рефераты психология, рефераты математика, рефераты кулинария, рефераты логистика, рефераты анатомия, рефераты маркетинг, рефераты релиния, рефераты социология, рефераты менеджемент.