Теоретико-множественные понятия: Методические указания к практическим занятиям и СРС по курсу «Дискретная математика», страница 3

;

;

;

.

·  Обратное

; ; ;

; ; .

·  Двойственное ; ;

; .

·  Композиция отношений

, ,   

 .

·  ; ; ; …

Транзитивное замыкание –

.

Рефлексивное замыкание –

.

Отношения эквивалентности («~»).

·  Разбиение - , , .

; .

·  Рефлексивность, ; симметричность, ;

Транзитивность, .

·   - класс эквивалентности: ; , .

·  Теорема. 1)  - разбиение,

2)разбиение определяет отношение эквивалентности.

·  Пример: , ; ; .

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

·  Порядок (линейный порядок):

рефлексивность , антисимметричность , транзитивность , дихотомия .

·  частичный порядок, частично упорядоченное множество:

рефлексивность, антисимметричность, транзитивность.

·  Строгий порядок: ; ;  

Антирефлексивность  (); транзитивность ;

;

·  Строгий линейный порядок: дополнительно условие трихотомии: .

·  ,    - верхняя граница   ;

 - нижняя граница   ;

,  - верхняя граница   ;

 - множество верхних границ.

 - нижняя граница   ; 

 - множество нижних границ.

·   - верхняя грань;

 - нижняя грань.

Существование верхней и нижней грани.

, , , , .

Задачи

1.  Доказать, что среди любых 6 человек найдутся либо трое попарно знакомых, либо трое попарно незнакомых.

2.  Доказать, что если  не зависит от индексации, то .

3.  Доказать: , .

4.  Доказать: ; .

5.   - действительная ось,  - отношение «меньше»,  - отношение «больше». Найти .

6.  Доказать .,

7.  Сколько отношений эквивалентности существует на 3-х элементном множестве?

8.  Ã. Найти все элементы отношения «».

9.  Определить свойства отношения на : .

10.   - разбиение . Доказать .

11.  ;   .  - порядок?

12.  ;   .  - порядок?

13.  Доказать .

14.  Доказать упорядоченная пара  может быть определена как множество .

15.  Для бинарного отношения  найти область определения и область значений.

16.  Пусть , . Для бинарного отношения   найти область определения и область значений.

17.  Какими свойствами обладает отношение , определенное на множестве действительных чисел?

18.  Какими свойствами обладает отношение , определенное на множестве всех прямых плоскости:  пересекает ?

19.  Какими свойствами обладает отношение , определенное на множестве всех прямых плоскости:  не пересекает ?

20.   - отношение на . Доказать а)  - симметрично  ; б) - транзитивно ; в) - рефлексивно ; г)  - рефлексивно и транзитивно .

21.  ; . Найти .

22.  ; . Найти .

23.   - бинарные отношения. Доказать .

24.  Пусть . Найти .

25.  Пусть  определено на множестве:. Доказать, что  - отношение эквивалентности.

26.  Если  - отношения эквивалентности, то - также отношение эквивалентности. Доказать.

27.  Если  - отношения эквивалентности, то - также отношение эквивалентности тогда и только тогда, когда . Доказать.

28.   - разбиение множества . Перечислить все элементы отношения эквивалентности, соответствующего разбиению множества .

29.  Доказать, что отношение делимости на множестве натуральных чисел является отношением частичного порядка. Будет ли это отношение линейным порядком? Является ли частичным порядком отношение делимости на множестве целых чисел?

30.  Построить линейный порядок на множестве всех конечных последовательностей натуральных чисел.

31.   - бинарное отношение на множестве подмножеств множества целых чисел, . Какими свойствами обладает отношение?

32.  Для бинарного отношения  между элементами множеств ,  . Найти область определения и область значений отношения.

33.  Найти отношения для бинарного отношения , определенного на множестве действительных чисел.

34.  На множестве действительных чисел определено отношение . Доказать, что это отношение эквивалентности и найти классы эквивалентности.

35.  Какими свойствами оно обладает бинарное отношение  делится нацело на , определенное на множестве положительных целых чисел?