1. R рефлексивно  I  r;

2. R симметрично  R = R^–1;

3. R транзитивно  r◦r  r;

4. R антисимметрично  r  r–1  I;

5. R полно  R  I  R^–1 = U;

Доказательство:

1.  R рефлексивно  aA выполняется aRa, т.е. (a,a)R. Но множество всех таких a составляет I  IR.  IR  aA {(a,a)}=I  (a,a)R, т.е. R рефлексивно.

2.  R симметрично  a,bA | (a,b)R  (b,a)R. Но если (a,b)R  (b,a)R^–1 по определению обратного отношения. Поскольку это справедливо для любых a,b, то R  R^–1 и R^–1  R  R^–1 = R.  R^–1 = R  RR^–1 и R^–1R  a,bA | (a,b)R  (a,b)R^–1 и (a,b)R^–1  (a,b)R. Если (a,b)R, то по определению (b,a)R^–1, значит, (b,a)R, т.е. a,bA | (a,b)R (b,a)R, что и означает симметричность.

3.  R транзитивно  a,b,cA | (a,b)R и (b,c)R  (a,c)R. Но по определению композиции R◦R {(a,b) |  cA | (a,c)R и (c,b)R}  по определению транзитивности, эта пара (a,b)R, т.е. R◦RR.  Если R◦RR, то это значит, что a,bA | (a,b)R◦R эта пара (a,b)R. По определению композиции, R◦R {(a,b) |  cA | (a,c)R и (c,b)R}, но было показано, что (a,b)R,  R транзитивно.

4.  От противного. Пусть R  R^–1  I. Значит,  ab| (a,b)R и (a,b)R^–1, т.е. в пересечении существует общий элемент (a,b). Но если (a,b)R^–1, то (b,a)R. Получили, что  ab | (a,b)R и (b,a)R. По условию, R антисимметрично  a,bA | (a,b)R и (b,a)R  a=b. Получено противоречие:  ab … a=b.  R  R^–1  I  (a,bA | (a,b)R и (a,b)R^–1  (a,b)I  a=b). Но (a,b)R^–1(b,a)R  ((a,b)R и (b,a)R  a=b)  антисимметричность.

5. Доказать самостоятельно. 

4. Представление отношений в ЭВМ

Удобным способом представления отношений в ЭВМ является матричная форма. Рассмотрим два конечных множества A={a₁,a₂,…,a_m}, B={b₁,b₂,…,b_n} и бинарное отношение P  AB . Определим матрицу [P] = (p_ij) бинарного отношения P по следующему правилу: Полученная матрица содержит полную информацию о связях между элементами и позволяет представлять эту информацию на компьютере.

• Заметим, что любая матрица, состоящая из нулей и единиц, является матрицей некоторого бинарного отношения.

16. Рассмотрим отношение P на множестве A², где A={1,2,3} (см. иллюстрацию). Матрица этого отношения

Основные свойства матриц бинарных отношений:

1. Если бинарные отношения P,Q  AB, [P] =(p_ij), [Q] = (q_ij), то [PQ] = (p_ij+q_ij), [PQ] = (p_ij·q_ij), где умножение осуществляется обычным образом, а сложение – по логическим формулам (т.е. 0+0=0, во всех остальных случаях 1). Итак: [PQ] = [P]+[Q], [PQ] = [P]*[Q].

17. Пусть отношения P и Q заданы: . Тогда матрица их суммы [PQ] = [P]+[Q] = , матрица произведения: [PQ] = [P]*[Q] = .

2. Если бинарные отношения P  AB, Q  BC, то [P◦Q] = [P]·[Q] , где умножение матриц [P] и [Q] осуществляется по обычному правилу, а произведение и сумма элементов из [P] и [Q] – по правилам пункта 1.

3. Матрица обратного отношения P^–1 равна транспонированной матрице отношения P: [P^–1]=[P]^T.

4. Если PQ, [P]=(p_ij), [Q]=(q_ij), то p_ij  q_ij. i,j.

5. Матрица тождественного отношения единична: [I_A] = (I_ij) :  I_ij =1  i=j.

6. Пусть R – бинарное отношение на A². Отношение R называется рефлексивным, если xA (x,x)R, т.е. I_AR (на главной диагонали R стоят единицы). Отношение R называется симметричным, если x,yA (x,y)R  (y,x)R, т.е. R^–1=R, или [R]=[R]^T (матрица симметрична относительно главной диагонали). Отношение R называется антисимметричным, если R R^–1 I_A, т.е. в матрице [R R^–1]=[R]*[R]^T вне главной диагонали все элементы равны 0. Отношение R наз. транзитивным, если (x,y)R, (y,z)R (x,z)R, т.е. R◦RR.

18. Пусть отношение P на множестве A², где A={1,2,3}, задано матрицей . Поскольку на главной диагонали есть нулевые элементы, отношение не рефлексивно. Поскольку матрица не симметрична, отношение тоже не является симметричным. Проверим его антисимметричность, для чего возьмем транспонированную матрицу и вычислим [PP^–1] = [P]*[P]^T =. Все элементы вне главной диагонали равны 0,  отношение антисимметрично. Проверим транзитивность по матрице: выполняется ли [P◦P]  [P]? [P◦P] =  отношение транзитивно.

5. Отношение эквивалентности

Бинарное отношение R на множестве А называется отношением эквивалентности, если оно является рефлексивным, симметричным и транзитивным. Обычно отношение эквивалентности обозначают через  или ~.

19. 1. Отношения равенства чисел и множеств, равномощности множеств являются отношениями эквивалентности. 2. Отношение подобия на множестве треугольников является тривиальным отношением эквивалентности. 3. Отношение эквивалентности – на множестве программ: {(a,b) | программы a, b вычисляют одну и ту же функцию на определенной машине}.

Пусть R – отношение эквивалентности на множестве А. Определим класс эквивалентности [x] для xA: [x] = {y | xRy}, т.е. это множество всех элементов A, которые R-эквивалентны x.

Пусть E – эквивалентность на множестве M. Тогда семейство классов эквивалентности множества M называется фактормножеством множества M по отношению E и обозначается M /E ={E(x)| xM}.

20. Для отношения принадлежности к одной студенческой группе классом эквивалентности является множество студентов одной группы. Тогда фактормножество множества всех студентов СибГУТИ по этому отношению эквивалентности представляет собой множество всех студ. групп СибГУТИ.

Утверждение 1.1. Всякое отношение эквивалентности на множестве M определяет разбиение множества M, причем среди элементов разбиения нет пустых; и обратно, всякое разбиение множества M, не содержащее пустых элементов, определяет отношение эквивалентности на множестве M:

  M²   ß= {B_i | B_i  M, B_i  , M = B_i и  i,j ij  B_iB_j=}.

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

Бинарное отношение R на множестве А называется отношением порядка, если оно антисимметрично и транзитивно.

Отношение порядка может быть рефлексивным, и тогда оно называется отношением нестрогого порядка (обычно обозначается ). Если отношение порядка антирефлексивно, то оно называется отношением строгого порядка и обозначается обычно <.

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

Обычно отношение порядка в общем случае обозначают <, и вместо aRb или (a,b)  R пишут a<b. Для отношения < обратным является >.

21. 1. Свойство «быть ровесником» можно считать отношением эквивалентности на множестве всех студентов 1-го курса СибГУТИ. Свойство «быть старше» является отношением частичного порядка на множестве всех студентов института. 2. Отношение < на множестве чисел является отношением строгого полного порядка, отношение  – нестрогого полного порядка. Следовательно, множество чисел является линейно упорядоченным. Отношение  на булеане P(M) является отношением нестрого частичного порядка. 3. Отношение подчиненности на предприятии является отношением частичного порядка – сотрудники разных лабораторий несравнимы.

Пусть дано ч.у.м. M с отношением порядка : Ữ= {M,}. Тогда: Элемент a ч.у.м. Ữ называется максимальным, если yM | ay  a=y; или если во всем множестве нет элемента, большего чем a. Элемент a называется минимальным, если yM | y a  a=y (т.е. во всем множестве нет элемента меньшего чем a).

Элемент b ч.у.м. Ữ называется наибольшим, если x  b xM (т.е. любой другой элемент множества меньше либо равен b). Элемент b называется наименьшим, если b  x xM (т.е. любой другой элемент множества больше либо равен b). Наибольший (наименьший) элемент ч.у.м. Ữ обычно обозначают max Ữ (min Ữ).

Наибольший (наименьший) элемент обычно называют единицей, а наименьший – нулем множества M.

• Заметим, что всякий наибольший элемент (если он существует) является максимальным, а всякий наименьший – минимальным. Обратное утверждение неверно. Максимальных (минимальных) элементов может быть несколько.

22. 1. Пустое множество является минимальным элементом булеана по включению. 2. Пусть ч.у.м. A содержит три элемента, условно обозначенные 1, 2 и 3 (см. рисунок). Отношение порядка задано парами: 11, 12, 22, 32, 33 (показано стрелками). Видно, что элемент 2 является наибольшим, т.к. он больше всех остальных элементов, а элементы 1 и 3 – минимальными (для каждого из них нет ни одного элемента, меньшего чем он), но не наименьшими, т.к. они не сравнимы между собой.

Для ч.у.м. M с отношением порядка  и подмножеством AM элемент aM называется верхней гранью множества A, если xA x  a. Элемент aM называется точной верхней гранью множества A и обозначается sup A, если a является верхней гранью и для любого другого элемента a’, являющегося верхней гранью, верно a  a’. Наибольший элемент множества A, если он существует, является sup A.

Аналогично, элемент bM называется нижней гранью множества A, если yA b y. Элемент bM называется точной нижней гранью множества A и обозначается inf A, если b является нижней гранью и для любого другого элемента b’, являющегося нижней гранью, верно b’ b. Наименьший элемент множества A, если он существует, является inf A.

Утверждение 1.2. Во всяком конечном непустом частично упорядоченном множестве существует минимальный элемент.

Замкнутость множества означает, что многократное повторение допустимых шагов не выводит за пределы этого множества.

Пусть R и R’ – отношения на множестве M. Тогда отношение R’ называется замыканием отношения R относительно свойства С, если:

1. R’ обладает свойством С: С(R’);

2. R’ является надмножеством R: R  R’;

3. R’ является наименьшим: С(R’’), R  R’’  R’  R’’.

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

Пусть A – вполне упорядоченное множество с отношением порядка . Введем отношение  на множестве упорядоченных наборов из A следующим образом:

(a₁,…,a_m)  (b₁,…,b_n)  m  n и i = 1,..,m a_i= b_i или  k  min(n,m) | a_k  b_k и a_i= b_i i < k, т.е. первые элементы совпадают, а k-й меньше.

Такое отношение называется лексикографическим, или алфавитным порядком.

24. Выполняются следующие соотношения: (2,4,5)(2,4,5,2), т.к. меньший набор является началом большего, (2,4,3,2,1)(2,4,5,2), т.к. начало набора совпадает, а следующий символ в первом наборе меньше.

1. Контрольные вопросы

1. Что такое набор из n элементов? Является ли n-кой последовательность (3, 4, 3, 1)? Являются ли различными наборы (1, 3, 2), (2, 1, 3)?

2. Что такое декартово произведение множеств?

3. Определите результаты операций А  B и B², если A = {a, b, c}, B = {1, 2}.

4. Что такое N-местное отношение?

5. Чем отличается унарное отношение от бинарного?

6. Как можно задать бинарное отношение?

7. Какие существуют способы графического представления бинарных отношений?

8. Что такое обратное отношение? Как будет выглядеть обратное отношение для R = {(a,b),(a,c),(b,c),(a,a)}?

9. Что такое область определения и множество значений отношения? Определите _R и _R для отношения R из предыдущего вопроса.

10. Как определяется композиция отношений?

11. Какое отношение называется рефлексивным? А антирефлексивным?

12. Определить, являются симметричными или антисимметричными отношения P = {(a,a), (a,b), (b,a)}, R = {(a,b), (a,a), (b,c)}, S = {(a,b), (b,c), (b,a), (c,b)}?

13. Как определяется транзитивность отношения?

14. Каким образом можно задать отношение для представления его в ЭВМ?

15. Как по матрице бинарного отношения проверить его свойства? Например, симметричность? Антисимметричность? Рефлексивность? Транзитивность?

16. Какое отношение называется отношением эквивалентности?

17. Какими свойствами обладает отношение, называемое отношением порядка?

18. Что такое частично упорядоченное множество?

19. В чем отличие максимального элемента от наибольшего? Могут ли они совпадать?

20. Верно ли какое-то из утверждений: «любой минимальный элемент является наименьшим»? «любой наименьший элемент является минимальным»?

21. Какой из элементов – наибольший или наименьший – называется единицей множества? А какой называется нулем множества?

22. В чем различие между верхней гранью и точной верхней гранью множества?

23. Какое множество называется замкнутым?

24. Что такое лексикографический порядок? Какой из наборов согласно этому порядку будет меньшим: (1,2,3) или (2,1,3)? (3,1) или (2,1,3)?

4. Функции

   1. Определение функции

Бинарное отношение R между множествами А и B называется однозначным, если из его выполнения для a, b и a, c (aA, b,cB) следует, что b и c совпадают.  a  , b,cB aRb и aRc  b = c (одному элементу множества A не могут соответствовать разные элементы, находящиеся с ним в отношении R).

Однозначное отношение f между множествами А и B, заданное для каждого элемента множества A, называется отображением множества A в множество B, или функцией из A в B: f : A  B.

Формально: Отношение f между элементами множеств A и B называется функцией из A в B и обозначается f : A  B, если оно обладает следующими двумя свойствами:

а) xA  y  B | (x,y)f; б) если (x, y)  f и (x, z)  f  y = z.

Для функции f обычно вместо записи (x,y)  f используется т.н. префиксная форма: y = f(x). При этом x называется аргументом, а y – значением функции f.

Для f : A  B область определения Dom(f)  {x  A |  y B | y = f(x)}, область значений Codom(f)  {y  B |  x A | y = f(x)}.

Если Dom(f) =A, то функция называется тотальной, а если Dom(f)  A – частичной. Сужением функции f : A  B на множество M  A называется функция f |_M, определяемая следующим образом: f |_M  {(x,y) |  y = f(x), xM}.

Для тотальной функции ее сужение на множество Dom(f) совпадает с самой функцией f.

Для f : A  B и x  A: если y = f(x), то y называется образом элемента x, а x – прообразом элемента y. Для любого непустого подмножества C  A его образом относительно f называется множество f(C) = {f(x) | xC}.

Функция f : A₁A₂…A_n  B называется функцией n аргументов, или n-местной функцией.

2. Классификация функций

Отображение f : A  B называется (см. рисунок ниже):

• инъективным (инъекцией), если любым различным значениям аргумента соответствуют различные значения функции: f(x₁) = f(x₂)  x₁ = x₂;

• сюръективным, сюръекцией, или отображением на, если любому элементу y множества B соответствует элемент x множества A, такой, что f(x) = y: yB  xA | f(x) = y;

• биективным, биекцией, или взаимно однозначным соответствием, если оно является одновременно инъекцией и сюръекцией;

• перестановкой множества A, если A = B и функция f : A  A является взаимно однозначным соответствием.

Если функция I : A  A определена как I(a)=a aA, то I называется тождественной функцией на множестве A.

Множество называется счетным, если его элементы можно пронумеровать, т.е. если существует взаимно однозначное соответствие между элементами этого множества и множеством натуральных чисел.

25. Всякое конечное множество счетно. Множество четных натуральных чисел счетно.

Утверждение 1.4. 1. Всякое подмножество счетного множества конечно или счетно. 2. Сумма любого конечного или счетного числа счетных множеств есть счетное множество.

Обратное отношение f^–1, которое определялось ранее, может не быть функцией, даже если f является функцией из A в B. Если обратное отношение f^–1 является функцией, то ее называют обращением функции, или обратной функцией.

Теорема 1.3 (об обратной функции):

Если функция f : A  B является биекцией, то обратное отношение f^–1 также является функцией из B в A, причем биекцией. Обратно, если f^–1 – функция из B в A, то f является биекцией.

Доказательство:

 Для доказательства того, что  f^–1– функция из B в A, нужно убедиться, что областью определения  f^–1 является B, и что если (b,a)  f^–1 и (b,a’)  f^–1, то a = a’. Поскольку f сюръективна (т.е. отображение на), то bB  aA | f(a)=b. Значит, (b,a)  f^–1, и B является областью определения f^–1. Пусть теперь (b,a)  f^–1 и (b,a’)  f^–1, тогда (a,b) и (a’,b) принадлежат f. Поскольку f инъективна, то a=a’. Значит, f^–1– функция.

Теперь покажем, что она является биекцией, т.е. сюръективна и инъективна.

Поскольку f – функция, то aA  bB| f(a)=b, т.е. (a,b)f. Тогда (b,a) f^–1, и элемент a принадлежит области значений функции f^–1. Значит, A представляет собой область значений f^–1, и сама функция f^–1 сюръективна. Для доказательства инъективности возьмем (b,a)  f^–1 и (b’,a)  f^–1, т.е. a = f^–1(b) и a = f^–1(b’). Тогда

f(a) = b  и f(a) = b’  b’= b, т.к. f – функция.

 Для доказательства обратного утверждения нужно провести аналогичные рассуждения, заменив f^–1 на f. 

Теорема 1.4: Если функция f : A  B является биекцией, то:

а)  b B f(f^–1(b))=b, б)  a A f^–1(f(a))=a.

Доказательство: Возьмем  b  B. Поскольку f – биекция, то  aA | a= f^–1(b). Тогда f(a)=b. Но поскольку a = f^–1(b),  f(f^–1(b)) = f(a) = b 

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

Теорема 1.5: Если функция f : A  A и I – тождественная функция на A, то I◦ f = f  ◦ I = f. Если для f существует обратная функция, то f^–1◦ f = f ◦ f^–1= I.

Теорема 1.6: Пусть функции g : A  B и f : B  C. Тогда: