рефераты рефераты
 

Главная

Разделы

Новости

О сайте

Контакты

 
рефераты

Авиация и космонавтика
Административное право
Арбитражный процесс
Архитектура
Астрология
Астрономия
Банковское дело
Безопасность жизнедеятельности
Бизнес-план
Биология
Бухучет управленчучет
Водоснабжение водоотведение
Военная кафедра
География и геология
Геодезия
Государственное регулирование и налогообложение
Гражданское право
Гражданское процессуальное право
Животные
Жилищное право
Иностранные языки и языкознание
История и исторические личности
Коммуникации связь цифровые приборы и радиоэлектроника
Краеведение и этнография
Кулинария и продукты питания
Культура и искусство
Литература
Логика
Логистика
Маркетинг
Масс-медиа и реклама
Математика
Медицина
Международное и Римское право
Уголовное право уголовный процесс
Трудовое право
Журналистика
Химия
География
Иностранные языки
Без категории
Физкультура и спорт
Философия
Финансы
Фотография
Химия
Хозяйственное право
Цифровые устройства
Таможенная система
Теория государства и права
Теория организации
Теплотехника
Технология
Товароведение
Транспорт
Трудовое право
Туризм
Уголовное право и процесс
Управление
Радиоэлектроника
Религия и мифология
Риторика
Социология
Статистика
Страхование
Строительство
Схемотехника
История
Компьютеры ЭВМ
Культурология
Сельское лесное хозяйство и землепользование
Социальная работа
Социология и обществознание

рефераты
рефераты

НАУЧНАЯ БИБЛИОТЕКА - РЕФЕРАТЫ - Большая коллекция шпор для МАТАНа (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]

рефераты
© РЕФЕРАТЫ, 2012

рефераты