Intro1l дискретная математика

Отношения эквивалентности: примеры

Свойства эквивалентности:

Пример

Отношение D3 равенства остатков при делении на 3 :

D3 = f(x; y) j xmod 3 = ymod 3g.

1)(x; x) 2 D3;

2)(x; y) 2 D3 , (y; x) 2 D3;

3)(x; y); (y; z) 2 D3 ) (x; z) 2 D3. Классы эквивалентности:

[0]D3 = fx j x mod 3 = 0g, [1]D3 = fx j x mod 3 = 1g, [2]D3 = fx j x mod 3 = 2g

Отношения эквивалентности: примеры

Свойства эквивалентности:

Пример

Отношение D3 равенства остатков при делении на 3 :

D3 = f(x; y) j xmod 3 = ymod 3g.

1)(x; x) 2 D3;

2)(x; y) 2 D3 , (y; x) 2 D3;

3)(x; y); (y; z) 2 D3 ) (x; z) 2 D3. Классы эквивалентности:

[0]D3 = fx j x mod 3 = 0g, [1]D3 = fx j x mod 3 = 1g, [2]D3 = fx j x mod 3 = 2g

7 2 [1]D3 , 48 2 [0]D3 , 23 2 [2]D3

Отношения эквивалентности: примеры

Пример

Пусть St – множество студентов 1-го курса Ф ПМ и К. Рассмотрим отношение УЧАТСЯ-ВМЕСТЕ St St

УЧАТСЯ-ВМЕСТЕ =

f(s; s0) j студент s учится в одной группе группе с s0g.

Отношения эквивалентности: примеры

Пример

Пусть St – множество студентов 1-го курса Ф ПМ и К. Рассмотрим отношение УЧАТСЯ-ВМЕСТЕ St St

УЧАТСЯ-ВМЕСТЕ =

f(s; s0) j студент s учится в одной группе группе с s0g.

Проверим, что УЧАТСЯ-ВМЕСТЕ отношение эквивалентности

Отношения эквивалентности: примеры

Пример

Пусть St – множество студентов 1-го курса Ф ПМ и К. Рассмотрим отношение УЧАТСЯ-ВМЕСТЕ St St

УЧАТСЯ-ВМЕСТЕ =

f(s; s0) j студент s учится в одной группе группе с s0g.

Проверим, что УЧАТСЯ-ВМЕСТЕ отношение эквивалентности

Для каждого студента s 2 St его класс эквивалентности [s]УЧАТСЯ-ВМЕСТЕ это все студенты его группы.

Таким образом имеется 4 класса эквивалентности:

Группа 11, Группа 12, Группа 14 и Группа 16.

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

Отношение R на множестве A называется отношением частичного порядка, если для него выполнены следующие условия: 1)антирефлексивность: для любого a 2 A (a; a) 2= R;

2)антисимметричность: для любых a; b из A, если (a; b) 2 R и

(b; a) 2 R, то a = b;

3)транзитивность: для любых трех элементов a; b; c из A, если

(a; b) 2 R и (b; c) 2 R, то и (a; c) 2 R.

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

Отношение R на множестве A называется отношением частичного порядка, если для него выполнены следующие условия: 1)антирефлексивность: для любого a 2 A (a; a) 2= R;

2)антисимметричность: для любых a; b из A, если (a; b) 2 R и

(b; a) 2 R, то a = b;

3)транзитивность: для любых трех элементов a; b; c из A, если

(a; b) 2 R и (b; c) 2 R, то и (a; c) 2 R.

R отношение линейного порядка, если для него выполнены условия 1–3 и

4)линейность: для любых a; b из A либо (a; b) 2 R, либо (b; a) 2 R:

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

1)антирефлексивность: для любого a 2 A (a; a) 2= R;

2)антисимметричность: для любых a; b из A, если (a; b) 2 R и

(b; a) 2 R, то a = b;

3)транзитивность: (a; b) 2 R и (b; c) 2 R ) (a; c) 2 R.

Пример

Отношение строгого включения X Y на множестве 2A всех подмножеств некоторого множества A.

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

1)антирефлексивность: для любого a 2 A (a; a) 2= R;

2)антисимметричность: для любых a; b из A, если (a; b) 2 R и

(b; a) 2 R, то a = b;

3)транзитивность: (a; b) 2 R и (b; c) 2 R ) (a; c) 2 R.

Пример

Отношение строгого включения X Y на множестве 2A всех подмножеств некоторого множества A.

1)X 6 X ;

2)X Y ) Y 6 X ;

3)X Y ; Y Z ) X Z :

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

1)антирефлексивность: для любого a 2 A (a; a) 2= R;

2)антисимметричность: для любых a; b из A, если (a; b) 2 R и

(b; a) 2 R, то a = b;

3)транзитивность: (a; b) 2 R и (b; c) 2 R ) (a; c) 2 R.

Пример

Пусть P – множество целочисленных точек положительного квадранта плоскости, т.е. P = f(x; y) j x 2 N; y 2 Ng.

Пусть отношение на P:

(x1; y1) (x2; y2) , (x1 < x2) и (y1 < y2):