Отношения. Дискретная математика

Отношения
Упорядоченные наборы
Произведение множеств
Бинарные отношения
Представление отношений
Функциональные отношения
Отношения эквивалентности
Отношения порядка
Вопросы

Отношения. Упорядоченные наборы
Положение шахматной фигуры однозначно определяется двумя символами: c4 – белый конь, e2 – черный король и т.д.
Положение общежития однозначно определяется двумя данными:
название улицы + номер дома.

Отношения. Упорядоченные наборы
Местоположение любого объекта однозначно определяется координатами:
(X, Y, Z)
(10, -5, 3) ≠ (3, 10, -5)

Отношения. Упорядоченные наборы
Данные о человеке однозначно определяются:
Фамилия
Имя
Отчество
Дата рождения (чч.мм.гггг)
Место рождения
Паспортные данные (серия, номер, кем выдан, когда выдан)

Отношения. Упорядоченные наборы
Упорядоченный набор (кортеж, n-ка) данных – последовательность из n объектов a1, a2,… , an ,
где a1 ∈ A1, a2 ∈ A2, … , an ∈ An.
Обозначение: (a1, a2,… , an)
Теорема: Два набора одной длины равны, если равны их соответствующие элементы:
(a1, a2,… , an) = (b1, b2,… , bn) ⟺ ∀k ( ak = bk ), k = 1..n.
Пример:
(РФ, УР, г.Ижевск, ул.Студенческая, 42) – адрес корпуса 3 ИжГТУ;
(1,5,3) – координаты вектора в пространстве;
0101001101 – битовая шкала, двоичное представление числа 333.

Отношения. Прямое произведение множеств
Прямое произведение множеств A 1, A 2, … , A n есть множество всех упорядоченных наборов вида (a1, a2,… , an), где a1 ∈ A1, a2 ∈ A2, … , an ∈ An.
Обозначение:
A1×A2× … × An={ (a1, a2,… , an)| ai ∈ Ai , i = 1..n }
Пример:
Пусть A = { 1, 3, 5 }, D = { x, y }, N = { 4 }.
Тогда A × N = { (1, 4), (3, 4), (5, 4) };
A × D = { (1, x), (3, x), (5, x), (1, y), (3, y), (5, y)};
D × A = { (x, 1), (x, 3), (x, 5), (y, 1), (y, 3), (y, 5)};
A × D × N = { (1, x, 4), (3, x, 4), (5, x, 4), (1, y, 4), (3, y, 4), (5, y, 4)}.

Отношения. Прямое произведение множеств
Теорема: Для конечных множеств A и B |A×B|=|A|×|B|.
Лемма: (A × B) × C ∼A × (B×C).
Степенью множества A называется n-кратное прямое произведение самого на себя.
Обозначение: An = A × A × … × A
Соответственно: А0 = {Λ}; А1 = A; А2 = A × A; … ; Аn = A × An-1.
Следствие: |An| = |A|n.
Пример: Пусть B = { 0, 1 } – булево множество. Тогда
Bn={ (x1, … ,xn)|xi ∈ B, i=1..n } – множество битовых шкал (слов длины n).

Бинарные отношения
Бинарным отношением между множествами A и B называется подмножество R прямого произведения A × B.
Если A = B, то говорят об отношении на множестве A.
Обозначение: R ⊂ A × B или R : A → B
R = { (x, y)| x ∈ A, y ∈ B, xRy },
xRy – элемент x находится в отношении R к элементу y.
A - область отправления B - область прибытия
Область определения отношения R:
Dom R = {x ∈ A | ∃y ∈ B: (x, y) ∈ R }
Область значения отношения R:
Im R = {y ∈ B | ∃x ∈ A: (x, y) ∈ R }

Бинарные отношения
Пример: Семья Weasley.
Отношение R = {(x, y)| x – отец y }.
Тогда A = B – семья Weasley
R = {(Arthur, Bill), (Arthur, George), (Arthur, Ron),
(Bill, Victoire), (Bill, Louis), (George, Fred), (George, Roxanne) }
Dom R = {Arthur, Bill, George }
Im R = {Bill, George, Ron,
Victoire, Louis,
Fred, Roxanne}

Бинарные отношения
Пример: Семья Weasley.
Отношение R = {(x, y)| x – сестра y }.
Тогда A = B – семья Weasley
R = { (Victoire, Louis), (Roxanne, Fred) }
Dom R = {Victoire, Roxanne }
Im R = {Louis, Fred}

Бинарные отношения
Особые виды отношений
Пусть R - отношение между множествами A и B.
Обратное отношение
R-1 = { (a, b) | (b, a) ∈ R } ⊂ B × A
Дополнение отношение
R = { (a, b) | (a, b) ∉ R } ⊂ A × B
Тождественное отношение (диагональ множества)
Id = I = { (a, a) | a ∈ A } ⊂ A 2
Универсальное отношение
U = { (a, b) | a ∈ A и b ∈ B } = A × B

Операции над отношениями
Отношение – это некоторое множество ⟹ допустимы все теоретико-множественные операции
Пример: ℕ - на множестве натуральных чисел, тогда
если < - отношение «… меньше …»
= - отношение «… равно …»
| - отношение «… делит …», то
Бинарные отношения

Композиция отношений
Пусть R1 : A → B и R2 : B → C.
Композиция отношений R1 и R2 - отношение R : A → C, определяемое по правилу:
R = { (a, c) | ∃b ∈ B : (a, b) ∈ R1 и (b, c) ∈ R2 }
Обозначение: R = R1 ⃘ R2
Пример: ℕ - на множестве натуральных чисел, тогда
если < - отношение «… меньше …»
| - отношение «… делит …», то
Бинарные отношения

Бинарные отношения
Свойства отношений
Пусть R - отношение на множестве A.
Рефлексивность ∀x ∈ A ⇒ (x, x) ∈ R
Симметричность ∀x, y ∈ A ⇒ ( (x, y) ∈ R ⇒ (y, x) ∈ R)
Транзитивность ∀x, y, z ∈ A ⇒ ( (x, y) ∈ R и (y, z) ∈ R ⇒ (x, z) ∈ R
Линейность ∀x, y ∈ A ⇒ ( (x, y) ∈ R или (y, x) ∈ R или x = y)

Бинарные отношения
Свойства отношений
Теорема: Если R ⊂ A2 - отношение на множестве А, то
R - рефлексивно ⇔ Id ⊂ R;
R - симметрично ⇔ R = R-1;
R - транзитивно ⇔ R ⃘ R ⊂ R;
R - антирефлексивно ⇔ R ∩ Id = ∅;
R - антисимметрично ⇔ R ∩ R-1 ⊂ Id;
R – линейно ⇔ R ∪ R-1 ∪ Id = U.

Представление отношений
прямым перечислением всех пар
в виде графа
графиком
матрицей (машинное представление)
Пусть R ⊂ A × B - отношение между множествами A и B или R : A → B,
A = {a1, a2,… , an}, B = {b1, b2,… , bm}.
Матрица отношения– это прямоугольная булева матрица Sn×m = (Sij) ? = 1..n,
j = 1..m, у которой строки соответствуют множеству A, столбцы – множеству B, а элемент Sij = aiSbj.
Программно ее можно описать:

Представление отношений
Пример: Пусть X = { a, b, c }, Y = { 1, 2, 3, 4 }.
R = {(a, 1),(a, 3), (a, 4),(b, 2), (b,4),(c,2)} — отношение из X в Y.
Тогда:
Граф отношения График отношения Матрица отношения

Представление отношений
Пример: Пусть A = { 1, 2, 3, 4, 5 }.
R = { (x, y) | x, y ∈ A, y ⋮ x } — отношение на A.
y ⋮ x - y делится на x без остатка. Тогда
R = {(1, 1),(1, 2),(1, 3), (1, 4),(1, 5), (2, 2), (2, 4),(3, 3), (4, 4),(5, 5)}.
Граф отношения График отношения Матрица отношения

Пусть f - отношение между множествами A и B.
Отношение называется функциональным (функцией), если
∀x ∈ A ⇒ ( ((x, y) ∈ R и (x, z) ∈ R)) ⇒ y = z)
Обозначение: f : A → B или y = f (x)
y – значение функции x – аргумент
Dom f = {x ∈ A | ∃y ∈ B: y = f (x) } - область определения функции
Im f = {y ∈ B | ∃x ∈ A: y = f (x)} - область значения функции
Свойства:
инъективность: если y = f (x1) и y = f (x2) ⇒ x1 = x2;
сюръективность: если ∀y ∈ B (∃x ∈ A: y = f (x));
биективность: если функция инъективна
и сюръективна.
Функции

Функции

Теорема: Если f : A → B - тотальная биекция, то отношение
f-1 ⊂ B × A (обратная функция) тоже является биекцией.
Следствие: Если f : A → B - инъективная функция, то отношение f-1 ⊂ B × A тоже является функцией (возможно, частичной), т.е. f-1 : B → A.
Теорема: Если f : A → B - функция, то F : 2f(A) → 2f(B) (переход к образам) и F-1 : 2f(B) → 2f(A) (переход к прообразам) - тоже функция.
Функции

Композиция функций называется суперпозицией
Обозначение: если f : A → B и g : B → C, то
(f ∘g)(x) = f(g(x)) – суперпозиция функций f и g
Теорема: Суперпозиция функций является функцией.
Пример:
Функции

Отношения эквивалентности
Отношение эквивалентности – рефлексивное, симметричное, транзитивное отношение.
Если R - отношение эквивалентности, то говорят, что
элемент x эквивалентен элементу y ⟺ xRy.
Обозначение: x ∼ y или x ≡ y

Отношения эквивалентности
Теорема: отношение эквивалентности на некотором множестве A порождает его разбиение на классы эквивалентности – множества элементов, эквивалентных между собой.
Класс эквивалентности для x : Ex = [x] = { y ∈ A | x ∼ y }
Свойства:
∀a ∈ A [a] ≠ ∅
a ∼ b ⟹ [a] = [b]
a ∼ b ⟹ [a] ∩ [b] = ∅
Фактормножество множества A относительно эквивалентности R - множество всех классов эквивалентности

Отношения порядка
Отношение порядка – антисимметричное, транзитивное отношение.
Обозначение: R – отношение порядка на множестве A
R ∼ ≺ или xRy ⟺ x ≺ y ⟺ x предшествует y
предок
потомок
ПОРЯДОК
(R антисимметрично, транзитивно)
Линейный
( R линейно)
Частичный
(R нелинейно)
Строгий
(R антирефлексивно)
Нестрогий
(R рефлексивно)
Строгий
(R антирефлексивно)
Нестрогий
(R рефлексивно)

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

Отношения порядка
Диаграммы Хассе
R – отношение частичного порядка на A. Говорят:
x ∈ A является непосредственным предком для y, если
∀z ∈ A (x ≺ z и z ≺ y) ⟹ (x = z или z = y) Обозначение: x ≼ y
x ∈ A называется минимальным, если у него нет предков
x ∈ A называется максимальным, если у него нет потомков