Упорядоченное бинарное отношение

Глава 2. Множества и отношения

Тема 2.1. Понятие множества

Тема 2.2. Способы задания множеств

Тема 2.3. Операции над множествами

Тема 2.4. Мощность множества

Тема 2.5. Отношения на множествах

Тема 2.6. Композиция отношений

Тема 2.7. Свойства отношений

Тема 2.8. Функции

 

Тема 2.1. Понятие множества

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

Дадим следующее интуитивное определение понятия множества:

Множество– определенная совокупность объектов.

Объекты, из которых состоит множество, называютсяэлементами множества.

ПРИМЕР

Множество домов на данной улице, множество натуральных чисел, множество студентов группы и т. д.

Множества обычно обозначают заглавными латинскими буквами А, В, С, D, X, Y…, элементы множества строчными латинскими буквами – a, b, c, d, x, y…

Для обозначения того, что объект x является элементом множества A, используют символику:  xА (читается: x принадлежит А ), запись xА обозначает, что объект x не является элементом множества A (читается: x не принадлежит А).

Множество не содержащее ни одного элемента называетсяпустым (обозначается: Ø).

Множества из элементов которого составляем конкретное множество называетсяуниверсальным (обозначается: U).

ПРИМЕР

U – множество людей на земле,   А – студенты группы Эп-305.

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

ПРИМЕР

 

Тема 2.2. Способы задания множеств

Чтобы задать множество, нужно указать, какие элементы ему принадлежат. Это можно сделать различными способами:

1)          Перечислением всех элементов множества в фигурных скобках.

ПРИМЕР

A = {Оля, Маша, Саша}

2)         Характеристическим предикатом, который описывает свойство всех элементов, входящих в множество. Характеристический предикат записывается после двоеточия или символа « | ».

ПРИМЕР

Р(x) = xNx < 8 -характеристический предикат.

M = {x : Р(x)}  или  M = {x : xN  x < 8}.

Множество M можно задать и перечислением его элементов:

M = {1, 2, 3, 4, 5, 6, 7}

ПРИМЕР

В = {x | x - четное натуральное число} = {2, 4, 6, 8, …}

Если множество состоит из небольшого количества элементов, то его удобно задавать перечислением всех элементов, если же элементов много или множество имеет бесконечное число элементов, то оно задается с помощью характеристического предиката.

Из курса школы известны следующие числовые множества:

N – множество натуральных чисел,

N = {1, 2, 3, 4,…};

Z – множество целых чисел,

Z = {…, – 3,  – 2, –1, 0, 1, 2, 3, 4,…};

Q – множество рациональных чисел,

R или (– ¥; ¥) множество действительных (вещественных) чисел;

I множество иррациональных чисел,

Известны также следующие обозначения:

- отрезок

Тема 2.3. Операции над множествами

1)         Сравнение множеств

Множество А называется подмножеством множества В, если все элементы множества А содержатся во множестве В.

  

Два множества называются равными, если они содержат одинаковые наборы элементов.

  

ТЕОРЕМА

#  Пустое множество Ø является подмножеством всех множеств.

#    Универсальное множество U  содержит все множества.

#      Если , то В надмножество А.

ПРИМЕР

   А={0, 1, 2, 3},    В={0, 1},

         

2)         Объединением  двух множеств  называется множество, содержащее все элементы обоих множеств.

ПРИМЕР

    А={К, А, Т, Я},   В={К, О, С, Т, Я}, 

 .

         

3)         Пересечением  двух множеств называется множество, состоящее из общих элементов обоих множеств.

ПРИМЕР

А={К, А, Т, Я},   В={К, О, С, Т, Я},    ={К, Т, Я}.

 

4) Разностью множествА и В называется множество, состоящее из всех элементов множества А не содержащихся в В.

ПРИМЕР

      А={К, А, Т, Я},    В={К, О, С, Т, Я},    А \ В={A},    В \ А ={О, С}.

                

5) Симметрической разностью множествА и В называется множество, состоящее из всех элементов множества А не содержащихся в В и всех элементов множества В не содержащихся в А.

                       

ПРИМЕР

      А={К, А, Т, Я},    В={К, О, С, Т, Я},    А Δ В={A,О,С}.

 

6)         Дополнением   (дополнением   до универсального множества) множества А называется множество, состоящее из всех элементов универсального множества не содержащихся в А.

7)    Прямым или декартовым произведением множеств A и B, называется множество всех упорядоченных пар (a, b), где первый элемент a из множества A,  а второй элемент b из множества B.

ПРИМЕР

,

Степенью множества называется декартовое произведение множества A само на себя n раз.

ПРИМЕР

, .

Свойства операций над множествами

1)          Коммутативность.

2)          Ассоциативность.

3)          Дистрибутивность.

4)          Закон поглощения.

5)          Идемпотентность.

6)          Инволютивность.

7)          Свойство нуля.

АØ=А

АØ= Ø

8)          Свойство единицы.

9)           Закон де Моргана

Тема 2.4. Мощность множества

Мощностью конечного множества называется число его элементов.

Мощность множества  X обозначается:  | X |

ПРИМЕР

  X ={1,3,6}, 

 | X | = 3

Принцип включения и исключения

Принципом включения и исключения называется формула, позволяющая вычислить мощность объединения множеств, если известны их мощности и мощности всех пересечений.

Рассмотрим частные случаи этой формулы для двух и трех множеств:

Справедливы аналогичные формулы и для пересечения множеств:

 

Тема 2.5. Отношения на множествах

Когда говорят о родстве двух человек, Маша и Саша, то подразумевают, что есть некая семья, к членам которой они относятся. Упорядоченная пара (Маша, Саша) отличается от других упорядоченных пар людей тем, что между Машей и Сашей есть некое родство (кузина, отец, и т. д.). В математике среди всех упоря­доченных пар декартового произведения А´В двух множеств А и В тоже выделяются некоторые пары в связи с тем, что между их компонентами есть некоторые «родственные» отношения, которых нет у других.

В качестве примера рассмотрим множество S студентов какого-нибудь техникума и множество D изучаемых там дисциплин. В декартовом произведении S´D можно выделить большое подмножество упорядоченных пар (s, d),обладающих свойством: студент s изучает дисциплину d. Построенное подмножество отражает отношение «изучает», естественно возникающее между множествами студентов и дисциплин.

Для строгого математического описания любых связей между элементами двух множеств вводится понятие бинарного отноше­ния, которое часто появляется как в ма­тематике, так и в информатике. Отношения между элементами не­скольких множеств (n-арные отношения) применяются для описания простой системы управления базами данных.

Отношением (бинарным отношением, двуместным отношением)из множества A в множество Bназывается некоторое подмножество декартового произведения  

Отношения в дальнейшем будем упорядоченное бинарное отношение обозначать

 

(читается  отношение из A в B)

Если   и , то говорят,  что a находится в отношении с b. Используется также запись

 

ПРИМЕР

  Если  отношение из  A  в  A   (), то говорят  бинарное отношение на множестве A.

ПРИМЕР

n-арным отношением на множестве А, называется некоторое подмножество n-ой степени множества A.

ПРИМЕР

,     −   n-арное отношение на множестве А.

 

Виды бинарных отношений на множестве A

1)          Обратное отношение  .

2)          Дополнение                 .

3)          Тождественные             .

4)     Универсальные              .

 

Тема 2.6. Композиция отношений

Пусть  - отношение из A в C ,  и  - отношение из         C в B, ,  тогда композицией  отношений  называется отношение

    .

ПРИМЕР

,   .

Пусть    ( отношение из А в В).  Ядром отношения  называется композиция отношения  и обратного для  него отношения , т.е.   .

ПРИМЕР

Пусть  A={0,1},    B={К, Л, О}, 

  ,

р={(0,К),(0,Л),(1,К),(1,О)}. Найти ядро отношения , т.е. .

РЕШЕНИЕ

Тема 2.7. Свойства отношений

Пусть , т.е.  - бинарное отношение на множестве A.

1)  - рефлексивное отношение, если   

ЧИТАЕТСЯ: для всякого элемента из множества А пара (а,а) принадлежит отношению , что означает что всякий элемент из множества А находится в отношении сам с собой.

Например, рассмотрим отношение 

 A – множество студентов техникума, тогда условие    означает, что любой студент техникума является одногруппником самого себя, что очевидно не верно, значит, отношение  не является рефлексивным.

Рассмотрим отношение

  ,  ,

A – множество всех действительных чисел, тогда условие

    

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

2)  -симметричное отношение, если

  .

ЧИТАЕТСЯ: для всяких элементов из множества А, если пара  принадлежит отношению , то  и пара  принадлежит отношению ,  что означает что если элемент a находится в отношении  c b, то и  элемент b находится в отношении  c  a.

Рассмотрим отношение

 ,

A – множество студентов техникума, тогда условие

   означает, что если студент техникума  a является одногруппником студента b, то студент   b является одногруппником студента a, что очевидно  верно, значит отношение   является симметричным.

Рассмотрим отношение

,

A – множество всех действительных чисел, тогда условие

    означает, что если выполняется условие , то  выполняется и условие , что не  верно, значит отношение   не является симметричным.

3)  - антисимметричное отношение, если 

  .

ЧИТАЕТСЯ: для всяких элементов из множества А, если пара  принадлежит отношению  и пара  принадлежит отношению , то ,  что означает что отношение   не может содержать пару  одновременно с парой , если элемент a отличен от элементаb.

Рассмотрим отношение

,

A – множество всех действительных чисел, тогда условие тогда условие

   означает, что если выполняются условия  и , то  выполняется  условие , что,  верно, значит, отношение    является антисимметричным.

Рассмотрим отношение

,

A – множество всех действительных чисел, тогда условие тогда условие

   означает, что если выполняются условия  и , то  выполняется  условие , что  не верно, значит, отношение     не является антисимметричным.

4)  - транзитивное отношение, если

   .

ЧИТАЕТСЯ:  для всяких элементов из множества А, если пара  принадлежит отношению  и пара  принадлежит отношению , то  и пара  принадлежит отношению , что означает что если элемент aнаходится в отношении  c  b и элемент b находится в отношении  c  с, то и  элемент a  находится в отношении  c  с.

Рассмотрим отношение 

 ,

A – множество студентов техникума, тогда условие

    означает, что если студент техникума  a является одногруппником студента b и студент  b является одногруппником студента с, то студент  а является одногруппником студента с, что очевидно  верно,  значит, отношение   является транзитивным.

ПРИМЕР

 

5)  - полное или линейное отношение, если

    .

ЧИТАЕТСЯ:  для всяких элементов из множества А, если , то пара  принадлежит отношению  или пара  принадлежит отношению ,  что означает что для любых двух различных элементов a находится в отношении  c  b или элемент b находится в отношении  c   a.

Рассмотрим отношение 

,

A – множество студентов техникума, тогда условие

     означает, что для любых двух студентов техникума  a и b, или студент a является одногруппником студента b или студент  b является одногруппником студента a,  что очевидно  не верно,  значит, отношение   не является полным.

Рассмотрим отношение

,

 A – множество всех действительных чисел, тогда условие тогда условие

     означает, что для любых двух различных чисел  a и b либо выполняется условие , либо  выполняется и условие , что,   верно, значит, отношение    является полным.

 

Тема 2.8. Функции

Отношение из множества A в множество B   ,  называется функцией из А в В если

.

Тот факт, что f – функция из множества A в множество B записывается f:   или  .

Вместо записи будем использовать .

Такое свойство отношения называется однозначностью, или функциональностью.

Если то  называют аргументом, а  - значением функции.

Пусть

, тогда  называется областью определения функции.

Пусть

,тогда называется областью значений функции.

Если , то функция называется тотальной, а если  - частичной.

Сужениемфункции  на множество  называется функция , определяется следующим образом: 

.

 называется функцией  аргументов, или  -местнойфункцией.

Свойства функции

Пусть

. Тогда функция  называется:

Инъективной,

 если 

Сюръективной,

если 

.

Биективной, если она инъективная и  сюръективная.

Вперед                 НАЗАД      Пройти тест


Поделись с друзьями



Рекомендуем посмотреть ещё:


Закрыть ... [X]

Бинарные отношения. отношение порядка Откуда пошла одежда



Упорядоченное бинарное отношение Бинарное отношение Викиконспекты
Упорядоченное бинарное отношение Упорядоченные множества MathHelpPlanet
Упорядоченное бинарное отношение Глава 2 Множества и отношения
Упорядоченное бинарное отношение Find and follow posts tagged mitch lucker on Tumblr
Упорядоченное бинарное отношение Анекдоты про богатырей, Анекдоты про Илью Муромца, Анекдоты
Упорядоченное бинарное отношение ВСН
Упорядоченное бинарное отношение Вяжем свитер -шарф МирТесен - рекомендательная социальная сеть
Упорядоченное бинарное отношение Для отцов не любящих своих детей. (Наталья Щиголева) / Стихи. ру
Упорядоченное бинарное отношение Как проявляется действие порчи на полное одиночество - практическая магия
Модная техника окрашивания AIR TOUCH 2017 Новый фанфик : Домик сказочницы : @дневники: асоциальная сеть Оптимальная спецодежда для современного автосервиса Плетение из газетных трубочек кузовка Хорошая ИДЕЯ Пословицы о служении родине пословицы про Прыщи - От чего могут появиться мелкие прыщики на губах Серия для химической завивки волос Станок для педикюра - как пользоваться, советы при выборе и Статусы пользователей - Совместные покупки на МамаСК - MamaSK

ШОКИРУЮЩИЕ НОВОСТИ