Пусть P – бинарное отношение на множестве A, P⊆AxA=A2
1) Опр: P – рефлексивноó∀x∈A (x,x) ∈P, т.е. тождественное отношение idA⊆P илиóкогда главная диагональ ||P|| матрицы бинарного отношения состоит только из единиц
2) Опр: P – симметричноóP-1=Pó||P||T=||P||óматрица бинарного отношения ||P|| симметрична относительно главной диагонали
3) Опр: P – антисимметричноóP∩P-1⊆idAó||P∩P-1||=||P||*||P||T причем ||P∩P-1|| все элементы вне главной диагонали будут нулевыми, а на главной диагонали могут быть нули
4) Опр: P – транзитивно ó P○P⊆Pó∀i,j qij<=pij, где ||P○P||=(qij), ||P||=(pij)
Зам: Свойство не симметричности не совпадает со свойством антисимметричности
6) Отношение Эквивалентности.
Опр. Бинарное отношение на не пустом множестве А называется отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно(≈,≅,≣,∃)
Примеры:
1) Отношение равенства на числовых множествах
2) Параллельность прямых на плоскости.
3) Подобие треугольника на плоскости
Пусть дано А≠∅, а∊А и задано P-отношение эквивалентности
Опр. Классом эквивалентности порождённым элементом a из множества A называется множество элементов, которые находятся с элементом a в отношением Р
a/p={x|x∊A, x∊PA}=
Def: Множество всех классов эквивалентности, по отношению к Р (отношение эквивалентности) называется фактор-множеством
A/p={x/p|∀x∊A}
Def: Любой элемент класса эквивалентности называется его представителем.
Опр. Разбиением непустого множества А называется совокупность его непустых подмножеств, таких что объединение всех подмножеств есть множество, а пересечение 2 любых различных подмножеств будет пустым
T1 (о разбиение множества на классы)
Пусть Р - отношение эквивалентности на А≠∅. Тогда фактор-множество А\Р является разбиением множества А.
■Т.к Р - отношение эквивалентности, то Р – рефлексивно=> ∀a∊A =>aPa=>(a,a)∊P
a∊a/p={x|x∊A, xPa}=>a/p≠∅
Таким образом =A
Осталось доказать что любые 2 класса эквивалентности не пересекаются.
Достаточно доказать, что если 2 класса имеют хотя бы один общий элемент, то они совпадают.
Пусть c∊a\p, c∊b\p. Возмем ∀x∊a\p. Покажем что x∊b\p
c∊a\p =>cPa, т.к P-симметрично=>aPc
xPa и aPc, т.к. P – транзитивно=>xPc
c∊b/p=>cPb
xPc и cPb, т.к Р транзитивно=>xPb=>x∊b\p
∀x∊a\p=>x∊b\p=>a\p⊆b\p
Аналогично b\p⊆a\p=>a\p≡b\p=>
Таким образом по определению разбиения множествава на классы A\p является разбиением множества А. ■
T2. S-разбиение множества A≠∅
Rs - бинарное отношением на А определенное следующим образом: (x,y)∊Rsóкогда эл-ты x,y∊разбиению S.
Тогда Rs соответствующее разбиению S является отношением эквивалентности на А причём А\Rs≡S
■ Необходимо проверить что Rs является отношение эквивалентности, т.е. выполняются 3 свойства.
1)∀a∊A=>∃Mi∊S:a∊Mi=>a, a∊Mi=>(a,a)∊RsилиaRsa=>Rs =>рефлексивно
2)∀a,b∊A и aRsbó ∃Mj∊S: a,b∊Mj=>b,a∊Mj=>bRsa=>Rs-симметрично
3)∀a,b,c∊A, aRsb и bRscó∃Mi и Mj∊S: a,b∊Mi, b,c∊ Mj=>b∊Mi∩Mj=>Mi=Mj, т.к Mi и Mj∊S-разбиение Mi∩Mj=∅=>a,c∊Mi=>aRsc=>Rs- транзитивно
Т.о. Rs является отношением эквивалентности => по определению и Т1 фактор множества A/Rs=S■
7) Отношение порядка. Диаграммы Хассе. Примеры.
Def: бинарное отношение Р с= А2, где А – не пусто, обладающие свойствами рефлексивности и транзитивности называются предпорядком.
Def: Р с= А2называется частичным порядком, если Р – рефлексивно, транзитивно и антисимметрично, т.е частичный порядок – антисимметричный предпорядок.
Def: отношение меньше называется строгим порядком, если определяется след образом: x<yóx≤y и x≠у. Строгий порядок не является частичным порядком, т.к не рефлексивен.
Def: Если во множестве А есть элементы х и у, о которых нельзя сказать, что х≤у или у≤х, то такие элем называются несравнимыми. Def: частичный порядок называется линейным порядком, если любые 2 элемента х,уєА сравнимы.
Def: Если на непустом множестве А зафиксирован некоторый частичный (линейный) порядок называется частично(линейно)-упорядоченным множеством.
Def:аєА, где А-ЧУМ называется max(min), если х єА из того, что а≤х(х≤а) =>а=х. Def:аєА, где А-ЧУМ называется наибольшим(наименьшим), если х≤а (а≤х) для всех х є А.
Замечание: Всякий наибольший (наименьший) элемент является max(min). Всякое ЧУМ имеет maxи min.
Def: Верхней (нижней) гранью под В, ЧУМ А наз всякий элема єА: b≤а (а≤b)для всех b є B, т.е В с А, А-ЧУМ, а є А=>а – верх грань В.
Def: Точная верхняя (нижняя) грань В с А называется наименьшая верхняя (наибольшая нижняя) грань для В.
Def: Линейный порядок (≤) на множестве А называется полным, если каждое непустое подмножество множества А имеет наименьший элемент. В этом случае множества А – называется вполне упорядоченным (ВУМ)
Диаграммы Хассе.
Рассмотрим непустое множество А, конечное, ЧУМ <A,≤>.
Def: Говорят, что у покрывает эл х, если х≤у и не существует такого элем z: x<z<y. Если х<y, то существует х1,х2,…,xn, что х=x1<x2<…<xn=y, где xi+1 покрывает xi.
Def: Любое конечное ЧУМ можно представить в виде схемы, в кот каждый элемент изображается точкой на плоскости и если у покрывает х, то точки х и у соединяются отрезком, причем х располагают ниже у. Такие схемы наз диаграммами Хассе.
Замечание: диаграмма Хассе для конечного ЧУМ ясно показывает наибольший (наименьший) элемент, а также все max и min элементы.
От наибольшего (наименьшего) элемента можно по нисходящей(восходящей) линии перейти к любому элементу. Из min либо только восходящие линии, либо это изолированная точка. Из max не выходят восход линии.
Утверждение: конечное, непустое ЧУМ А содержит по крайней мере один max(min) элемент и если он единственный, то он наибольший (наименьший).
Из диаграммы Хассе для ЛУМ легко выделить цепи, т.е части, которые состоят из одной линии без разветвлений.
8) Отображения и их виды. Свойства функций. Примеры.
Опр: Бинарное отношение f называют функцией или отображением из множества А в множество B.
Dom f= A – область определения (ООФ)
Im f ⊆ B – область значения (ОЗФ)
∀ x ∈ Dom f=A ∃ y ∈ Im f ⊆ B: (x,y) ∈ f
Обозначение: f:A→B
Единственный y называют значением функции для аргумента х.
y=f(x): f:x→y
Области определения и значения функции определяются как и для бинарных отношений.
Опр: ООФ– область определения бинарного отношения f. Dom f = {x|∃y: (x,y) ∈f}
Опр: ОЗФ – область значения бинарного отношения f. Im f = {y|∃x: (x,y)∈f}
Опр: Функции f и g называются равными ó они равны как множества. Т.е. f=g ó((x,y) ∈ f ó (x,y) ∈ g)
Примеры:
1)Тождественные отношения являются функциями.
2) f={(x,y) | y - площадь x} это отображение является функцией.
3) f={(x,y) |y – фигура с площадью х} Не выполняется единственность y => f не является функцией.
Виды отображений.
Любая функция является отображением, но не любое отображение является функцией.
Опр: Бинарное отношение f называется отображением из A в B если Dom f⊆A и Im f⊆B
Опр: Бинарное отношение f называется отображением A в B если Dom f=A и Im f⊆B
Опр: Бинарное отношение f называется отображением A на B если Dom f=A и Im f=B
Опр: Образом множества А при отображении f из А в B называют f(A)={f(x) | x∈A}, A⊆B
Опр: Прообразом образа А при отображении f:A→B называют f -1 (B)={x | x∈Dom A f(x)∈B}
Опр: Отображение называется инъективным если:
1) ∀ x1,x2 ∈ Dom f из x1≠x2 => f(x1)≠f(x2)
2) ∀ x1,x2 ∈ Dom f из f(x1)=f(x2) =>x1=x2
3) ∀y∈Im f ∃!x ∈ Dom f, (x,y) ∈ f (f(x)=y)
Любой элемент из области значения имеет единственный прообраз.
Опр: f:A→B называется сюрьективным если:
1) Im f=B
2) Для любого элемента из B имеется хотя бы один прообраз из А.
Опр: Отображение f называется биекцией (взаимно-однозначное отображение) если оно инъективно и сюрьективно.
Опр: f:A→A называется подстановкой множества А в А
Простейшим примером подстановки являетcя тождественное отношение idA
Свойства функций:
1) Композиция двух функций является функцией. f:A→B; g:B→C; f○g:A→C
2) Композиция двух биективных функций – биекция. f:A↔B; g:B↔C; f○g:A↔C
3) f:A→B имеет обратное отображение f -1 :B→A ó f – биекция.
9) Комбинаторика. Основные опр-я. Правило суммы и произведения. Метод включений и исключений.
Подмножество из r эл-в выбранного из мн-ва состоящего из n эл-ов наз. Из n по r выборкой (n,r), где r- объем выборки.
Выборка наз. упорядоченной, если порядок следования эл-ов в ней задан.
2 упорядоченные выборки, различающиеся только лишь порядком следования эл-ов считаются различными.
Если порядок следования эл-ов не является существенным, то выборка наз. не упорядоченной
Упорядоченная (n,n) выборка, в которой эл-ты могут повторяться назыв. Перестановкой с повторениями из n по n. Перестановка с повторениями = =
Если эл-ты упорядочены (n,n) – выборка попарно различны, то она наз. (n,n) – без повторений
Перестановка без повторений: =n!
Упорядоченная (n,r) – выборка, в которой эл-ты могут повторяться называется размещением с повторениями из n эл-ов по r =
Если эл-ты упорядочены (n,r) выборки попарно различны, то она наз (n,r) размещением без повторений =
Неупорядоченная выборка (n,r) в которой эл-ты попарно различны наз. сочетанием без повторений =
Если эл-ты неупорядочены (n,r) выборке могут повторяться, то она наз. сочетанием с повторениями =
Правило суммы: Если объект А может быть выбран m-способами, а объект B n-способами при условии, что одновременный выбор A и B не возможен, то выбор «A или B» осуществить (m+n) – способами
Правило произведения: Если A может быть выбран m-способами, и после каждого из таких выборов B в свою очередь может быть выбран n-способами, то «A и B» в указанном порядке m n
n(A
n(A
10) Бином Ньютона. Основные свойства биномиальных коэффициентов. Треугольник Паскаля. Полиномиальная теорема.
Def: всякий двучлен наз биномом, т.е это сумма или разность 2 алгебраич выражений, называемых членами бинома.Известны формулы сокращенного умножения, позволяющие сразу же ввести бином во 2,3 … степени.
(а+b)n=∑Cnk ak bn-k= Cn0 a0 bn + Cn1 a1 bn-1 + Cn2 a2 bn-2 + … + Cnn-1 an-1 b1 + Cnn an b0 - формула Бином Ньютона, а числа сочетания (n,k) наз биноминальными коэффициентами. Теорема Бином Ньютона.
(а+b)n=∑Cnk ak bn-k
При n=1. (а+b)1=∑C1k ak bk-1= C10 a0 b1 + C11 a1 b0=b+a.
При n=j. (а+b)j=∑Cjk aj bn-j
При n=j+1. (а+b)j+1 = (a+b)j(a+b) = (∑Cjk ak bj-k)(a+b) = ∑Cjk ak+1 bj-k + ∑Cjk ak bj+1-k = ∑Cjk ak+1 bj-k + Cjk aj+1 b0 + Cj0 a0 bj-k+1 + ∑Cjk ak bj+1-k = Cj0 a1 bj + Cj1 a2 bj-1 + Cj2 a3 bj-2 +…+ Cjj-1 aj b1 + Cjj aj+1 b0 + Cj0 a0 bj+1 + Cj1 a1 bj + Cj2 a2 bj+1 +…+ Cjj aj b1 = Cj0 a0 bj+1 + ∑(Cjk + Cjk+1)ak+1 bj-k + Cjj aj+1 b0 = Cj0 a0 bj+1 + ∑Cj+1k+1 ak+1 bj-k + Cjj aj+1
Следствия ∑Cnk=2n – сумма всех биноминальных коэфф = 2n.