Поможем в ✍️ написании учебной работы

Имя

Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой

Выберите тип работыЧасть дипломаДипломная работаКурсовая работаКонтрольная работаРешение задачРефератНаучно - исследовательская работаОтчет по практикеОтветы на билетыТест/экзамен onlineМонографияЭссеДокладКомпьютерный набор текстаКомпьютерный чертежРецензияПереводРепетиторБизнес-планКонспектыПроверка качестваЭкзамен на сайтеАспирантский рефератМагистерская работаНаучная статьяНаучный трудТехническая редакция текстаЧертеж от рукиДиаграммы, таблицыПрезентация к защитеТезисный планРечь к дипломуДоработка заказа клиентаОтзыв на дипломПубликация статьи в ВАКПубликация статьи в ScopusДипломная работа MBAПовышение оригинальностиКопирайтингДругое

Нажимая кнопку "Продолжить", я принимаю политику конфиденциальности

Будем рассматривать бинарные отношения, заданные на непустом множестве А. Свойства бинарных отношений и некоторые определения, относящиеся к отношениям сведены в Табл.1

Таблица 1 Свойства бинарных отношений.

Понятие теории отношений	Определение	Ткеоретико-множественное описание и некоторые зависимости
Горизонтальное сечение по х0	{(x0y) | "y:х0rу}	({x0}´А) Ç r
Вертикальное сечение по у0	{(x,y0) |"х: хrу0 }	r Ç (A´{y0})
Горизонтальная проекция r	{x | $у: (х,у) Î r}	dom r
Вертикальная проекция r	{y | $ х: (х,у) Î r}	rng r
Пересечение отношений	{(x,y) | (х,у) Î r1 Ç r2}	r1 Ç r2
Объединение отношений	{(x,y) | (х,у) Î r1 È r2}	r1 È r2
Обратное отношение	{(y,х) | (х,у) Î r}	r-1
Композиция отношений	{(x,y) | $z: хrz, zrу }	r · g
Рефлексивность	"х Î А: (х,х) Î r	iA Í r
Симметричность	" х,у Î А: х r у Þ у r х	r = r-1
Транзитивность	" х,у,zÎА: хrz и zrу Þ х r у	r · r= r
Иррефлексивность	"х Î А: (х,х) Ï r	iA Ç r = Æ
Асимметричность	" х,у: х r у Þ ù (у r х )	r Ç r-1 = Æ
Антисимметричность	" х,у: х rу и у rх Þ х = у	r Ç r-1 Í iA

 

Специальные свойства бинарных отношений удобно представить Табл. 2.

Название свойства	Характеристическое свойство	Теоретико-множественное определение	Граф свойства
Рефлексивность
Симметричность
Тран-итивн1ст0

Отношение эквивалентности

Бинарное отношение называется эквивалентностью, если оно рефлексивно, симметрично и транзитивно. Эквивалентность обозначается символом ~, например, х ~ y. Граф отношения эквивалентности есть полный граф, заданный на множестве А, т.е. множество ребер графа отношения эквивалентности либо равно А², либо несвязный граф, каждая компонента связности которого является полным подграфом графа А² на некотором подмножестве вершин графа, образующем класс эквивалентности для данного отношения. Вообще, классом эквивалентности для отношения ~ на множестве А по элементу а называется множество, определенное следующим образом: [x]_~ или

X({a})={x | x~а, xÎA }.

Разумеется, элемент а, для которого класс эквивалентности определен таким образом, также входит в этот класс в силу рефлексивности отношения эквивалентности.

Множество классов эквивалентности связано с разбиением несущего множества. Вообще разбиением множества М называется множество, элементами которого являются подмножества М за исключением пустого множества, которое в разбиение не входит. Объединение этих подмножеств равно М, а пересечения попарно пусты.

Таблица 2 Свойства отношения эквивалентности

Понятие	Свойство или определение	Пояснение
~ - отношение эквивалентности на А	· ~Í А´А · ~ рефлексивно в А · ~ транзитивно в А · ~ симметрично в А	iAÍ ~ dom ~ = rng ~ = A ~ · ~ = ~ ~ = ~-1.
Aa- класс эквивалентности отношения ~ по элементу а	[a]~ = {x | (a,x) Î ~ }	Множество всех элементов, таких, что x ~ a. Каждый класс эквивалентности определен заданием одного элемента.
Разбиение множества А	Z={Z1,Z2, …, ZN}, Æ Ï Z,	Разложение множества А на непересекающиеся непустые подмножества, так что каждый элемент из А принадлежит одному и только одному из этих подмножеств.

Можно доказать, что отношение эквивалентности “~” на А образует разбиение А/ ~ множества А, причем элементами разбиения являются классы эквивалентности. Разбиение называется максимальным, если в каждый класс эквивалентности входит по одному элементу. Примером такого отношения является отношение х ~   у Û х=у, х,у Î N.  Разбиение называется минимальным, если оно образует единственный класс эквивалентности, в который входят все элементы А.

Множество классов эквивалентности в множестве А по эквивалентности “~” называется фактор-множеством А по “~”, обозначается A/~.

Примеры о тношений эквивалентности.

1. Отношение конгруентности треугольников.

2. Отношение тождества на множестве алгебраических выражений.

3. Отношение параллельности на множестве прямых.

4. Отношение учиться в одной группе на множестве студентов.

5. Отношение получить одну и ту же оценку по математике на экзамене.

6. Сравнимости чисел по модулю m (это отношение определяет множества чисел, дающих одинаковый остаток при делении на m). Например, отношение иметь одинаковый остаток при делении на 7 на множестве целых чисел Z:

7. Отношения равенства чисел (образует максимальное разбиение),

8. Конгруэнтности треугольников (классы эквивалентности включают все конгруэнтные треугольники),

9. Равенства множеств,

10. Равномощности множеств,.

Теорема. Если “~” – отношение эквивалентности, заданное на произвольном непустом множестве А, то существует разбиение, равное фактор множеству множества А по отношению ~,  A/~ = {[x]_~ | "xÎ A$yÎA: x~y Û x,yÎ[x]_~} такое, что каковы бы ни были x,yÎ A, x ~ y тогда и только тогда, когда х и у принадлежат к одному и тому же классу разбиения.

§ Пусть ~ - эквивалентность на А и A/~= {[x]_~ | "x: xÎ A}- фактор-множество А по отношению ~. Докажем существование разбиения R_~, равного фактор множеству A/~.

· Пусть aÎA – произвольный элемент А. Обозначим A_a= [a]_~ = {x | x Î A, x ~ a} – класс эквивалентности по элементу а. Тогда, аÎА_а, и, следовательно,   Так как элемент а выбирается произвольно, и каждый класс эквивалентности содержит только элементы множества А, то Из существования двух включений следует, что . Следовательно, объединение классов эквивалентности равно А.

· Докажем теперь, что попарные пересечения классов эквивалентности пусты. Пусть a,b Î A, aÎ A_a, b Î A_b, A_a и A_b –два класса эквивалентности. Пусть А_a Ç A_b ¹Æ. Тогда существует хотя бы один элемент сÎА такой, что с Î А_a и с Î А_b, т.е. с ~ a и c ~ b. Пусть z – произвольный элемент множества А_а. Тогда z ~ a и а ~ с. По свойству транзитивности отношения эквивалентности получаем z ~ c. Но с ~ b, следовательно, по свойству транзитивности z ~ b. Следовательно, z Î A_b. Следовательно, A_a Í A_b. Обратное включение доказывается аналогично. Следовательно, пересечение A_a и A_b не пусто тогда и только тогда, когда это одно и то же множество.

Таким образом, доказано, что множество классов эквивалентности образуют разбиение множества А. ¨

 

Отношения порядка

Бинарное отношение на А называется предпорядком на А, если оно рефлексивно и транзитивно, но не антисимметрично (например, отношение «х делитель у» на множестве целых чисел).

Частичным порядком на А называется бинарное отношение рефлексивное, транзитивное и антисимметричное. Частичный порядок часто обозначается символом “£”. Порядок £^-1 называется двойственным к £ и обозначается символом “³”. Будем писать x<y, если x<y и x¹y. Частичный порядок £ на множестве А называется линейным, если два любые элемента из А сравнимы между собой по £, т.е. x£y или y£x для любых х,у ÎА. Множество А с заданным на нем частичным (линейным) порядком называется частично (линейно) упорядоченным.

Рисунок 6 Диаграмма Хассе для отношений не полного и полного частичного порядка и

Часто частично упорядоченное множество (ЧУМ) изображают в виде графа H=(V,£), из которого удалены все петли и транзитивно замыкающие дуги. Такой граф называется диаграммой Хассе. Диаграмма Хассе известна с конца XIX века. В течение многих лет ее применяли в генеалогии для задания родства.

Понятие непосредственного старшего легко задается в ЧУМ следующим определением: x покрывает у тогда и только тогда, когда y<x и не найдется такого элемента z, что y<z<x.

Таблица 3 Свойства отношений порядка

Понятие	Свойство или определение	Пояснения
Рефлексивный ЧП в А (£) (Нестрогий порядок)	· £ Í A´A, · £ рефлексивно в А, · £ транзитивно в А, · £ антисимметрично в А.	iAÍ £, £·£=£, x£y и y£x Û x=y.
Иррефлексивный ЧП в А (<) (Строгий порядок)	· < Í A2, · < иррефлексивный, транзитивный, асимметричный.	На множестве N отношение < не является ЧП, так как пары (n,n+1) не принадлежат отношению <. iA Ç < = Æ, <·<Ì<, <·<-1=Æ
£- ЧП в А, В Í А, B минимальный элемент в В: b = min B d – максимальный элемент в В: d = max B	· "x: xÎB Þ b £ x, bÎB, · "x:xÎB Þ x £ d, bÎB.	Элементы b и d сравнимы со всеми элементами из В.
£ – ЧП в А, ВÍА, а,bÎА. {а} – нижняя грань В, {b} – верхняя грань В.	· "x: xÎB Þ a £ x, · "x: xÎB Þ x £ b.	В отличие от минимального и максимального элемента В а и b не обязательно принадлежат В.
£ – ЧП в А, ВÍА; u, oÎA. u=inf B (точная нижняя граница В), o=sup B (точная верхняя граница В).	· u – максимальный элемент нижней грани, · о – минимальный элемент верхней грани.	Точная верхняя и нижняя границы не всегда существуют.
£ – ЧП в А, ВÍА; В - цепь в А	"x,y: x,yÎBÞx£y или y£x.	В линейно упорядочено отношением В2 Ç £.

 

Подмножество В множества А, частично упорядоченного отношением £, называется цепью в А, если оно линейно упорядочено отношением £ Ç В².

Если А – ЧУМ, sup A, inf AÎB, то sup A называется единицей ЧУМ А (обозначается 1), а inf A – нулем ЧУМ А(обозначается 0).

Отношением частичного порядка является отношение включения «Í » на булеане конечного множества; примером линейного порядка является отношение £ на множестве чисел.

Линейный порядок £ на множестве А назовем полным, если каждое подмножество множества А имеет наименьший элемент. В этом случае множество А называется вполне упорядоченным.

Пусть А и В – частично упорядоченные множества и f – функция из А в В. f называется монотонным отображением, если их x₁£x₂ следует, что f(x₁) £ f(x₂), для любых x₁, x₂ Î A.

Если f и f^-1 – монотонные отображения, то f называется изоморфизмом  частично упорядоченных множеств А и В, а множества А и В называются изоморфными.

Операции над отношениями

Основным компонентом реляционной модели базы данных является реляционная алгебра, которая состоит из восьми операторов, составляющих две группы по четыре оператора:

1) Традиционные операции над множествами: объединение (UNION), пересечение (INTERSECT), разность (MINUS) и декартово произведение (TIMES). Все операции модифицированы, с учетом того, что их операндами являются отношения, а не произвольные множества.

2) Специальные реляционные операции: ограничение (WHERE) , проекция (PROJECT), соединение (JOIN) и деление (DIVIDE BY).

3) Результат выполнения любой операции реляционной алгебры над отношениями также является отношением. Эта особенность принято называть свойством реляционной замкнутости.

Булева алгебра

Частично упорядоченное множество А с заданными на нем операциями типа умножения Ç (И) и типа сложения È (ИЛИ) называется решеткой, если каждая пара сравнимых элементов имеет наибольший и наименьший элемент, причем inf(a,b)=aÇb, sup(a, b)=aÈb, и выполняются аксиомы решетки: коммутативности, ассоциативности и поглощения – для операций типа сложения È и типа умножения Ç.

Если в решетке выполняются аксиомы дистрибутивности, то решетка называется дистрибутивной.

Если для введенного на решетке отношения частичного порядка £ существуют наибольший и наименьший элементы, они называются единичным и нулевым элементами решетки. Сама решетка при этом называется решеткой с 0 и 1. Если для каждого элемента а решетки существует обратный элемент а^-1, такой что аÇa^-1=0, aÈ`а =1, то а<sup>-1</sup> (`а ) называется дополнением а, а решетка называется решеткой с дополнениями.

Если в решетке выполняется аксиома дистрибутивности, она называется булевой алгеброй.

Примером булевой алгебры является алгебра Кантора.

 

Отображения и функции

Отображение (синоним – функция). Уточним понятия отображения как тройки объектов: двух множеств и правила, сопоставляющего элементам первого множества элементы второго множества. Отношение f называется функцией из А в В (из А на В), если dom f = A, rng fÍ B (rng f = B), и для всех х, у₁, у₂ из (х,у₁)Îf и (x,y₂)Îf следует у₁ = у_2.  Т.е. каждый элемент первого множества (А) участвует в образовании пар ( x, y), где у ÎВ  Функция f из А в В обозначается f:A®B. Если f – функция, пишем y = f(x) вместо (x,y) Î f и называем y значением аргумента функции f при значении аргумента x.

Если при этом rngf=B, то говорят, что а – отображение множества А на множество В. Это обозначается   

Множество всех функций из А в В обозначается Таким образом,  Очевидно, что

Для любого множества А определяем i_A: A®A следующим образом: i_A(x) = x. Отображение i_A называется диагональю множества А².

Функция f называется 1-1 функцией, если для любых x₁, x₂, y из того, что y = f(x₁) и y = f(x₂) , следует x₁ = x₂. Иначе

Функция f:A®B осуществляет взаимно однозначное соответствие между А и В, если dom f = A, rng f = B и f есть 1-1 – функция.

Взаимно однозначное соответствие f:A®A называется подстановкой множества А.

n-местным отношением на А назовем любое подмножество множества Aⁿ. Функцию f: Aⁿ ®B назовем n-местной функцией из А в В и будем писать f(x₁, … , x_n) = y и называть у значением функции f при значении аргументов x₁, …, x_n. n-местной операцией на А называется отображение f: Aⁿ ® A. Ей соответствует n+1 – местное отношение на А.

В общем случае отображение f:M®N может быть представлено тройкой (M, N, f).

Пусть f: M ® N, и B Í N.

Образом множества А при отображении f  называют множество  определяемое следующим образом:

Прообразом  множества В при отображении f называют множество  определяемое как

Свойства образов и прообразов

Пусть f: M ® N,  Тогда имеют место соотношения:

1. 
2. 
3. 
4. 

Докажем первое свойство

ªПусть

Û

Û  или  или

                ¨

 

Математические модели

Физические процессы описываются в терминах операций, связывающих физические объекты. Сложность физических ситуаций требует упрощенных описаний с помощью словесных, математических и даже физических моделей, которые абстрагируют подходящим образом выбранные существенные свойства физических объектов и ситуаций. Математическая модель охватывает класс неопределяемых математических объектов, какими являются числа, векторы, и отношения между ними. Многие отношения могут быть описаны с помощью математических операций, связывающих один или несколько объектов (операндов) с другим объектом или множеством объектов (результатом операции).

Абстрактная модель с ее объектами произвольной природы, отношениями и операциями определяется непротиворечивым набором правил (аксиом), вводящих операции, которыми можно пользоваться, и устанавливающих общие отношения между их результатами. Современная (абстрактная) алгебра имеет дело с математическими моделями, определяемых в терминах бинарных операций, обычно представляющих собою различные типы сложения и умножения, которые связывают пары математических объектов (операндов) с результатом операции.