Определение свойств бинарного отношения с помощью матрицы




Пусть 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, то существует х12,…,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.



Поделиться:




Поиск по сайту

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2016-08-20 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту: