Бинарные отношения

Пусть a,b – два произвольных объекта.
Упорядоченная пара: (a,b).
Если a≠b, то (a,b)≠(b,a).
Упорядоченная последовательность n объектов: (a1,a2,…,an).
Прямое (декартово) произведение множеств A×B – это множество упорядоченных пар элементов из этих множеств:
A×B={(a,b)|a∈A, b∈B).
Если А≠B, то B≠A.
Прямое произведение n множеств: A1×A2×…An= {(a1,a2,…,an)|a1∈A1,a2∈A2,…,an∈An}
A×A×…A= An
1. Прямое произведение множеств

Утверждение. |A|=m, |B|=n ⇒ |A×B|=m×n
Доказательство:
Выбрать первый элемент пары – m способов;
выбрать первый элемент пары – n способов;
по правилу умножения всего m×n способов.
1. Прямое произведение множеств

Пусть A,B – произвольные множества.
Бинарное отношение ρ из множества A в множество B – это всякое подмножество прямого произведения A×B.
ρ ⊆ A×B
Если A=B, то говорят о бинарном отношении на множестве A.
Форма записи: префиксная (a,b) ∈ ρ
инфиксная aρb
n-арное отношение – подмножество прямого произведения
n множеств: ρ ⊆ A1×A2×…An.
График бинарного отношения – множество точек плоскости, координаты которых (a,b) образуют упорядоченные пары этого отношения.
2. Бинарные отношения

2. Бинарные отношения

Утверждение. ρ1 ⊆ A×C, ρ2⊆ C×B ⇒ (ρ1○ρ2)-1 = ρ2-1○ρ1-1
Доказательство:
(a,b)∈(ρ1○ρ2)-1 ⇒
⇒ (b,a)∈ρ1○ρ2 ⇒
⇒ ∃c∈C: (b,c)∈ρ1 & (c,a)∈ρ2 ⇒
⇒ (c,b)∈ρ2-1 & (a,c)∈ρ1-1
2. Бинарные отношения

Утверждение. ρ1 ⊆ A×C, ρ2= ⊆ C×B ⇒ (ρ1○ρ2)-1 = ρ2-1○ρ1-1
Доказательство:
(a,b)∈(ρ1○ρ2)-1 ⇒
⇒ (b,a)∈ρ1○ρ2 ⇒
⇒ ∃c∈C: (b,c)∈ρ1 & (c,a)∈ρ2 ⇒
⇒ (a,c)∈ρ1-1 & (c,b)∈ρ2-1 ⇒
⇒ (a,b)∈ρ2-1○ρ1-1.
2. Бинарные отношения

Утверждение. ρ1 ⊆ A×C, ρ2⊆ C×B ⇒ (ρ1○ρ2)-1 = ρ2-1○ρ1-1
Доказательство:
(a,b)∈(ρ1○ρ2)-1 ⇔ ⇔ (b,a)∈ρ1○ρ2 ⇔
⇔ ∃c∈C: (b,c)∈ρ1 & (c,a)∈ρ2 ⇔
⇔ (a,c)∈ρ1-1 & (c,b)∈ρ2-1 ⇔
⇔ (a,b)∈ρ2-1○ρ1-1.
2. Бинарные отношения

Пусть ρ ⊆ A×A.
Рефлексивное отношение:
(∀a∈A): (a,a)∈ρ.
Антирефлексивное отношение:
(∀a∈A): (a,a)∉ρ.
Симметричное отношение: (∀a,b∈A, a≠b): (a,b)∈ρ ⇒ (b,a)∈ρ.
Антисимметричное отношение:
(∀a,b∈A): ((a,b)∈ρ, (b,a)∈ρ ⇒ a=b).
Транзитивное отношение:
(∀a,b,с∈A): ((a,b)∈ρ, (b,с)∈ρ ⇒ (a,с)∈ρ ).
Полное отношение:
(∀a,b,с∈A): (∀a,b∈A, a≠b): (a,b)∈ρ или (b,a)∈ρ.
2. Бинарные отношения

Отношение ρ ⊆ A×A:
рефлексивно ⇔ I ⊆ ρ;
симметрично ⇔ ρ =ρ-1;
транзитивно ⇔ ρ○ρ ⊆ ρ;
антирефлексивно ⇔ ρ∩I =∅;
антисимметрично ⇔ ρ∩ρ-1⊆I;
полно ⇔ ρ ∪ρ-1∪I =U.
3. Теорема о свойствах бинарного отношения

Утверждение 1. ρ ⊆ A×A рефлексивно ⇔ I ⊆ ρ.
Доказательство:
ρ рефлексивно ⇔
⇔ (∀a∈A): (a, a) ∈ ρ ⇔
⇔ I ⊆ ρ.
3. Теорема о свойствах бинарного отношения

Утверждение 2. ρ ⊆ A×A симметрично ⇔ ρ =ρ-1.
Доказательство:
ρ симметрично ⇔
⇔ [(∀a,b∈A, a≠b): (a,b)∈ρ ⇔ (b,a)∈ρ ] ⇔
⇔ (a,b)∈ρ -1 и (b,a)∈ρ -1 ⇔
⇔ (a,b)∈ρ -1 и (a,b)∈ρ ⇔
⇔ ρ ⊆ ρ-1 и ρ -1 ⊆ρ ⇔
⇔ ρ =ρ-1.
3. Теорема о свойствах бинарного отношения

Утверждение 3. ρ ⊆ A×A транзитивно ⇔ ρ○ρ ⊆ ρ.
Доказательство:
А) ρ транзитивно ⇒
⇒ [(∀a,b,c∈A): (a,b)∈ρ и (b,c)∈ρ ⇒(a,c)∈ρ ]
(a,c)∈ρ○ρ ⇒
⇒ ∃b: (a,b)∈ρ и (b,c)∈ρ ⇒(a,c)∈ρ
Б) ρ○ρ ⊆ρ.
Пусть (a,b)∈ρ и (b,c)∈ρ ⇒
⇒(a,c)∈ρ○ρ ⇒
⇒ ρ транзитивно.
3. Теорема о свойствах бинарного отношения
ρ○ρ ⊆ ρ.
⇒
⇒

Утверждение 4. ρ ⊆ A×A антирефлексивно ⇔ ρ∩I =∅.
Доказательство:
ρ антирефлексивно ⇔
⇔ (∀a∈A): (a, a) ∉ ρ ⇔
⇔ρ∩I =∅.
3. Теорема о свойствах бинарного отношения

Утверждение 5. ρ ⊆ A×A антисимметрично ⇔ ρ∩ρ-1⊆I.
Доказательство:
ρ антисимметрично ⇔
⇔ [(∀a,b∈A): (a,b)∈ρ и (b,a)∈ρ ⇒ a=b] ⇔
⇔ [(a≠b и (a,b)∈ρ )⇔ (a,b)∈ρ и (b,a)∈ρ -1]⇔
⇔ ρ∩ρ-1⊆I.
3. Теорема о свойствах бинарного отношения

Утверждение 6. ρ ⊆ A×A полно ⇔ ρ ∪ρ-1∪I =U.
Доказательство:
ρ полно ⇔
⇔ (∀a,b∈A,a≠b): (a,b)∈ρ или (b,a)∈ρ ⇔
⇔ (b,a)∈ρ -1 или (a,b)∈ρ -1⇔
⇔ (a,b)∈ ρ ∪ρ-1 и (b,a)∈ ρ ∪ρ-1 ⇔
⇔ ρ ∪ρ-1 =ρ ∪ρ-1∪I =U.
3. Теорема о свойствах бинарного отношения

Для бинарного отношения ρ ⊆ A×A:
рефлексивное замыкание ρr = ρ∪I;
симметричное замыкание ρs = ρ∪ρ-1;
транзитивное замыкание ρt = ρ∪ρ2∪ρ3∪…∪ρn∪… .
При этом:
ρr - рефлексивное бинарное отношение;
ρs - симметричное бинарное отношение;
ρt - транзитивное бинарное отношение.
4. Замыкание отношений