Рис. 3. Граф отношения r₄(x_i;x_j) для Х={2;3;4;5;6;8;10}.

Анализ различных бинарных отношений позволяет выделить наиболее характерные свойства, что необходимо для классификации всего множества отношений. Такими свойствами являются: рефликсивность, симметричность и транзитивность.

Бинарное отношение рефликсивно, если для любого х_i имеем r(x_i;x_i)=1. При матричном задании такого отношения это означает, что на главной диагонали матрицы находятся только “1”, а при графическом представлении - петли при каждой вершине графа (см. рис. 4(а)).

Бинарное отношение антирефлексивно, если для любого х_i имеем r(x_i;x_i)=0, т.е. отношение имеет значение “ложь” применительно к одному элементу х_i. При матричном задании такого отношения это означает, что на главной диагонали матрицы находятся только “0”, а при графическом представлении -отсутствие петель при каждой вершине графа (см. рис. 4(б)).

Бинарное отношение симметрично, если для любой пары (x_i;x_j) имеем r(x_i;x_j)=r(x_j;x_i)=1. При матричном задании такого отношения это означает симметричное расположение “1” относительно главной диагонали, при графическом представлении - отсутствие стрелок на линиях, соединяющих вершины x_i и x_j, или их наличия, но в обе стороны (см. рис. 4(в)).

Бинарное отношение антисимметрично, если для любой пары (x_i;x_j) при ij имеем r(x_i;x_j)r(x_j;x_i), а при i=j r(x_i;x_i)=1. При матричном задании такого отношения это означает несимметричное расположение “1” относительно главной диагонали, но наличие их на главной диагонали, при графическом представлении - наличие стрелок на линиях, соединяющих вершины x_i и x_j и наличие петель у вершин графа (см. рис. 4(г)).

Бинарное отношение транзитивно, если для любых трех элементов x_i,x_j,x_k имеем r(x_i;x_j)=1 только при условии r(x_i;x_k)=1 и r(x_k;x_j)=1. При матричном представлении это означает, что если r(x_i;x_k)=1 и r(x_k;x_j)=1, то это же отношение можно установить между вершинами x_i и x_j через промежуточную вершину x_k, т.е. найти r(x_i;x_j)=1; при графическом представлении -наличие пути из вершины x_i в вершину x_j через промежуточную вершину x_k, используя ребра (x_i;x_k) и (x_k;x_j)) (см. рис. 4(д)).

а)

Рис. 3. Матрицы и графы, раскрывающие свойства отношений.

Свойства отношений позволяют классифицировать множество отношений на типы. Наиболее изученными являются отношения эквиваленции и отношения порядка. Отношение эквиваленции позволяют разбить заданное множество элементов на непересекающиеся подмножества, а отношение порядка -установить порядок между элементами заданного множества.

Бинарное отношение R(XX), удовлетворяющее условиям рефлексивности, симметричности, транзитивности называют отношением эквиваленции.

Так на рис. 5а) приведены матрица и граф для двух классов эквиваленции, на рис. 5б) -для одного класса эквиваленции, на рис. 5в) -для трех классов эквиваленции. Анализ матриц показывает, что классу эквиваленции соответствует блок, выделенный на рисунках пунктирной линией, все элементы которого содержат только 1.

а)

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

Бинарные отношения R(XX), удовлетворяющие условиям рефлексивности, антисимметричности и транзитивности называют отношением порядка. Использование отношения порядка на одном множестве Х позволяет упорядочить элементы этого множества, т.е., рассматривая отношение на каждой паре элементов множества, устанавливать частичный порядок на всём множестве X. Примерами частично упорядоченных множеств являются множество целых чисел с заданным отношением порядка, т.е. {1;2;3...}, множество действительных чисел, в том числе положительных и отрицательных, счетные множества нематематических объектов, упорядоченные по значениям индексов, т.е. Х₁, Х₂, ...,. На рис. 5а) дан пример частичного порядка.

Бинарное отношение R_(XX), удовлетворяющее условиям антирефлексивности, асимметричности и транзитивности называют отношением строго порядка. Использование отношения строго порядка формирует линейную упорядоченность элементов множества Х. На рис. 5б) дан пример отношения строгого порядка.

а)

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

Задания

1. Задать произвольные бинарные соответствия между множествами S и T

• с помощью графика;

• с помощью матрицы.

2. Установить свойства следующих отношений на множестве Z:

а)Z₁ + Z₂ - четно; б) Z₁ + Z₂  100; в) Z₁Z₂ - нечетно.

3. Задать отношение на S

• рефлексивное;

• антирефлексивное

• симметричное;

• транзитивное;

• антисимметричное.

4. Задать функцию из S в T

• произвольную;

• инъективную;

• сюръективную;

• биективную.

5. Пусть Z - множество целых чисел. Установить свойства функций, заданных следующими отображениями:

a) z  Z²; б) Z  -Z; в) Z  2Z; г) Z  Z + 1; д) Z  Z

Варианты заданий.

1) S={a,b,c} T={b,c,f}

2) S={d,f,g} T={d,g,h}

3) S={a,b,c,d} T={d,e,f,g}

4) S={h,g,d} T={a,b,d,g}

5) S={g,d,b,c} T={b,c,d}

6) S={g,d,f,a} T={b,c,e}

7) S={a,b,e,f} T={сe,f,g}

8) S=u T={c,k,b,h}

9) S={a,b,c,k} T={k,b,c,f}

10) S={d,f,g,k} T={k,d,g,h}

11) S={a,b,c,d,k} T={k,d,e,f,g}

12) S={h,g,d,k} T={k,a,b,d,g}

13) S={g,d,b,c,k} T={k,b,c,d}

14) S={g,d,f,a,k} T={k,b,c,e}

15) S={a,b,e,f,k} T={k,b,c,f}

16) S={k,a,b,c} T={b,c,f,k}

17) S={k,d,f,g} T={d,g,h,k}

18) S={k,a,b,c,d} T={d,e,f,g,k}

19) S={k,h,g,d} T={a,b,d,g,k}

20) S={k,g,d,b,c} T={b,c,d,k}

21) S={k,g,d,f,a} T={b,c,e,k}

22) S={a,b,k} T={b,k,f}

23) S={a,b,k,d} T={d,e,f,g}

24) S={g,d,b,k} T={b,k,d}

25) S={d,k,g} T={d,g,h}

26) S={g,d,k,a} T={b,k,e}

27) S={k,g,d} T={a,b,d,g}

28) S={a,b,k,f} T={e,f,g}

Контрольный тест

1. 1. Задать отношение R= :

на множествах А= и В= в явном виде

• R= {(1,2), (4,1),(2,3),(3,2),(0,5),(5,0)}

• R= {(1,4),(2,3),(3,2),(4,1),(5,0)}

• R= {(1,4),(2,3),(3,4),(4,5)}

3. 2. Задать отношения R= на множестве в виде матрицы

4. 3. Определить область определения отношения R={(x,y):2+y - нечетное} , заданных на множестве A={1,2,3,4,5}

• D_{R =} (1,2,3,4,5};

• D_{R =;}{1,3,5}

• D_{R =}{2,4}

6. 4. Найти композицию отношений на множестве А = {1,2,3,4}

R = {(1,4), (2,3), (3,2), (4,1)} и Q = {(2,1), (3,2), (4,3)}

• R*Q = ;

• R*Q = {(1,1), (2,2), (3,3)};

• R*Q = {(1,3), (2,2), (3,1)}

7. 5. Определить свойства отношения R на множестве A={1,2,3,4,5}

R = {(1,2), (1,3), (2,2), (2,3), (4,4), (4,5)}

• антисимметрично;

• антисимметрично, транзитивно;

• рефлексивно

8. 6. Определить свойство отношения R = {(x,y): x+2y=10} на множестве Z

• антисимметрично;

• антисимметрично, транзитивно;

• рефлексивно

9. 7. Отношение R = {(x,y): 2x>y} на множестве Z является

• эквивалентностью;

• порядком;

• ни тем, ни другим

11. 8. Какие из приведенных отношений на множестве Z является функцией?

R = {(x,y): x>y} , P = {(x,y): x+2y=15}, Q = {(x,y): x+y²=26}

• R;

• P,Q;

• P

12. 9. Отношение R = {(x,y): 2x+4y=10} на множестве Z является

• инъективным отображением;

• сюръективным отображением;

• биективной функцией

10. Функция на множестве R является:

• биективным отображением;

• сюръективной функцией;

• инъективной функцией

11.Функция на множестве А = А = {1,2,3,4} задана матрицей определить ее свойства:

• биективная;

• инъективная;

• сюръективная

12. Какие из приведенных функций на множестве Z является инъективным?

R = {(x,y): 5x²+y=7} , P = {(x,y): x+8y=3} Q = {(x,y): x/y=5}

• P, Q

• R, P

• R, Q

13. Из приведенных отношений на множество R выбрать функции

P = R = {(x,y): xy=10} , Q = {(x,y): x²y=1} , R = {(x,y): xy²=25}

• P, Q;

• Q, R;

• R, P

14. Из приведенных отношений на множестве R выбрать отображения

P = {(x,y): |x|=y} , Q = {(x,y): x=|y|} , R = {(x,y): |x|=|y|}

• R;

• P, Q;

• Q

15. На множестве людей задано отношение: x и y находятся в отношении R, если они одного роста. Это отношение является?

• эквивалентностью;

• порядком;

• ни тем, ни другим

Лабораторная работа № 4 Алгебраические структуры

Цель работы:

Теоретические сведения

При изучении алгебраических структур определяющим понятием является понятие операции.

Операцией над множеством S называется функция f : Sⁿ  S , n  N.

Операция Sⁿ  S имеет порядок n. При n=1 операции называются унарными. Например, операция перемены знака на Z : x  y : x + y = 0 , x, y  Z. При n = 2 операции называются бинарными. Например, операция сложения на Z.

Операции, определенные на конечных множествах удобно задавать в виде таблиц. Введем произвольную операцию  на множестве {a, b, c}.

Следовательно a  b = a, b  b = a, c  b = b, и т.д.

Свойства операций.

1. Бинарная операция  на множестве А коммутативна, если a  b = b  a, для всех a, b  А.

Очевидно, что обычная операция сложения на Z коммутативна, а вычитания - нет.

2. Бинарная операция  на множестве А ассоциативна, если (a  b)  с = а  (b  с ), для всех a, b  А.

Очевидно, что обычная операция сложения на Z ассоциативна, а вычитания - нет.

3. Пусть  - бинарная операция на множестве А и l, r, e  A такие, что l  a = a, a  r = a, e  a = a  e = a, тогда l называют левой единицей, r - правой единицей, е - единицей по отношению к  на А. Единица на множестве должна быть единственной.

Рассмотрим множество Z - целых чисел. Здесь 0 является правой единицей по отношению к вычитанию и единицей по отношению к сложению.

4. Пусть  - операция на А с единицей е и x  y = e. Тогда говорят, что х - обратный элемент к у, у- обратный элемент к х. Для каждого элемента существует единственный обратный элемент.

Алгебраической cтруктурой называется пара элементов (А,σ), где А – несущее множество, а σ-сигнатура: операции и отношения, заданные на множестве А.

Если сигнатура содержит только отношения, то алгебраическая структура называется моделью. Наиболее широко известным примером модели являются графы.

Если сигнатура содержит только операции, то алгебраическая структура называется алгеброй.

Рассмотрим сначала алгебры , которые имеют только одну бинарную операцию.

1. Полугруппой называется множество S с бинарной операцией Ä , которая удовлетворяет только требованию ассоциативности:

x Ä (y Ä z) = (x Ä y) Ä z " x,y,z є S.

2. Моноидом называется множество S вместе с бинарной операцией Ä такой , что Ä ассоциативна:

$ u М : u Ä x = x = x Ä u " x  S

(u – наз. единицей по отношению к Ä )

3. Группой называется множество S с бинарной операции Ä:

1) Ä ассоциативна, т.е. x Ä (y Ä z) = (x Ä y) Ä z " x,y,z є S.

2) существует элемент u Î S ( единица по отношению к Ä)

u Ä x = x = x Ä u " x Î S

3) существуют обратные элементы : " x Î S соответствует y Î S: x Ä y = u = y Ä x.

4. Абелевой группой называется группа, в которой операция Ä - коммутативная, т.е. x Ä y = y Ä x , " x,y є S