Файл: Тема. Соотношения. Соответствия. Бинарные отношения.pdf

Пример 2.14. Каков индекс разбиения и мощности классов эквивалентности по отношению ρ, если ρ – отношение равенства (тождества) на любом множестве Все классы эквивалентности по отношению равенства R = {(a, b) | a= b} на любом множестве А состоят из одного элемента. Индекс разбиения А по отношению равенства равен мощности множества, те. Пример 2.15. Каков индекс разбиения и мощности классов эквивалентности по отношению ρ, если ρ – отношение иметь один и тот же остаток отделения на 5» на множестве натуральных чисел N? Индекс разбиения множества N по заданному отношению ρ равен 5. Множества натуральных чисел, составляющие каждый класс эквивалентности, счетны. Определение 2.28. Транзитивное замыкание R
0
состоит из таких и только таких пар элементов a, b из А, для которых в А существует цепочка из k+2 элементов А, k≥0, а, c
1
, c
2
, c
3
, …, b, между соседними элементами которой выполняется ρ, те. Например, если R – отношение быть сыном, то R
0
– быть прямым потомком. Если отношение R транзитивно, то R = Пример 2.16. Пусть R – отношение быть руководителем на множестве А. Определить R, R
-1
, R
0
. Каковы свойства отношений
R – не быть руководителем
R
-1
– быть подчиненным
R
0
= R – быть руководителем, т. к. R – транзитивно. Отношение R – быть руководителем
 не является рефлексивным, т. к. выражение быть руководителем по отношению к самому себе вряд ли имеет смысл
 антирефлексивно, ткни для какого члена организации не выполняется «A – руководитель A»;
 несимметрично, т. к. если A – руководитель B , тоне может быть руководителем A;
 антисимметрично, ткни для каких членов организации не выполняется одновременно «A – руководитель B» и «B – руководитель A»;
 транзитивно, т. к. если A – руководитель B и B – руководитель C, то
A – руководитель C. Таким образом, отношение быть руководителем антирефлексивно, антисимметрично и транзитивно, те. является отношением строгого частичного порядка на множестве M сотрудников фирмы.
2.5. Операции. Понятие алгебры Важный частный случай отображений – операции.

Определение 2.29. Отображение f из А в А называется операцией на множестве А. В этом случае f (а) ∈ Аи операцию называют унарной. На множестве действительных чисел R примерами унарных операций являются
1) операция нахождения обратного числа f(x) = x
-1
, x≠0, или в других обозначениях f(x)={(x,x
-1
) | x ∈ R, x≠0};
2) операция нахождения противоположного числа f(x) = -x, или иначе f(x)={(x,-x) | x ∈ R}; З) операция f(x)={(x,0) | x ∈ R}, которая любое действительное число x отображает в 0. Определение 2.30. Отображение из А в А называется местной (n- арной) операцией на множестве А. В случае n = 2 операция называется бинарной, а при З — тернарной. Например, на множестве векторов трехмерного пространства векторное умножение векторов бинарная операция, а двойное векторное произведение – тернарная. Операции сложения и умножения действительных чисел являются бинарными на множестве действительных чисел R. Например, операция сложения f = {((x,y),x+y) | x, y ∈ R} Определение 2.31. Алгеброй называется совокупность двух множеств некоторого множества Аи множества F – операций, определенных на А. Алгебры принято обозначать готическими буквами
J, K, и т. д. Для алгебры
K =⟨A; F⟩ множество А называется носителем алгебры, а множество F
– ее сигнатурой. Например, множество натуральных чисел N с двумя бинарными операциями сложения (+) , умножения (x) является алгеброй
K = ⟨N; +, x⟩. Сигнатура этой алгебры F = {+, х. Алгебры отличаются одна от другой носителями, сигнатурами и, наконец, свойствами, которыми обладают операции в этой алгебре. Множество всех подмножеств (булеан) некоторого множества Мс определенными на нем бинарными операциями объединения и пересечения и унарной операцией дополнения является алгеброй
K
K
= ⟨S(M); ⋃, ⋂, ⎺⟩. Иногда считают, что сигнатура данной алгебры кроме указанных трех операций содержит две нульарные (0-арные) операции выделено пустое множество
 и само множество М. Алгебра
K
K
= ⟨S(M); ⋃, ⋂, ⎺, , М называется алгеброй Кантора. Существуют алгебры с другими носителями, с двумя бинарными, одной унарной операциями и двумя выделенными элементами, причем они обладают теми же свойствами, что и алгебра Кантора. Рассматривая все такие алгебры,

мы приходим к понятию абстрактной булевой алгебры. Алгебры Буля находят широкое применение в прикладных задачах. Определение 2.32. Булевой алгеброй называется непустое множество В с двумя бинарными операциями
, , двумя отмеченными элементами 0, 1 и одной унарной операцией ⎺ , причем для любых а, b, c ∈ В выполняются следующие равенства
1) коммутативность a
b=ba, ab=ba
2) ассоциативность (a
b)c=a(bc), (ab)c=a(bc)
3) дистрибутивность a
(bc)=(ab)(ac), a(bc)=(ab)(ac)
4) идемпотентность: a
a=a, aa=a
5) поглощение a
(ab)=a, a(ab)=a
6) законы нуля и единицы a
0=0, a0=a, a1=a, a1=1 7) a
a=0, aa=1 8) двойное дополнение или инволютивность: a=a
9) законы де Моргана ab=ab, ab=ab Отметим, что это определение носит аксиоматический характер. Мы считаем заданными пять операций на множестве В (две бинарные, одна унарная и две нульарные) и перечисляем 19 тождеств, сгруппированные в девять аксиом постулатов. Алгебра считается булевой алгеброй тогда и только тогда, когда она имеет такой набор операций (сигнатуру) ив ней выполняются все выписанные аксиомы. Очевидно, что способ обозначения операций не играет роли. Абстрактная булева алгебра может быть задана другим списком аксиом. В частности приведенный выше набор аксиом является избыточным, те. некоторые аксиомы можно исключить, так как они являются следствием других. С другой стороны, список аксиом можно пополнить следствиями из них. Например, в любой булевой алгебре справедливы тождества которые называются законами модулярности и могут быть получены из аксиом 1)-5). Сформулируем общий принцип двойственности для булевой алгебры любое утверждение верное в булевой алгебре, в формулировке которого встречаются только операции
,  и ⎺, остается справедливым, если в его формулировке всюду заменить
 на  и наоборот. Определение 2.33. Изоморфизмом алгебр
K
1
= ⟨A1; F1⟩ и
K
2
= ⟨A2; F2⟩ называется взаимно однозначное соответствие  между элементами носителей и сигнатур такое, что где a
1
, a
2
, …, a n
, a ∈ A1, f m
∈ F1, (a
1
), …, (a n
), (a) ∈ A2, (f m
) ∈ F2. При этом алгебры
K
1 и
K
2
называются изоморфными. Все законы алгебры
K
1
справедливы ив изоморфной ей алгебре
K
2

Алгебру Кантора
K
K
= ⟨S(M); ⋃, ⋂, ⎺, , М, очевидно, можно рассматривать как модель (интерпретацию) абстрактной булевой алгебры, считая, что ⋂
↔, ⋃
↔, 
↔0, М. Более того, любую конечную булеву алгебру можно рассматривать как алгебру Кантора для некоторого конечного множества М. Теорема. Любая конечная булева алгебра изоморфна алгебре всех подмножеств некоторого множества. Вопросы для самопроверки
1. Дайте определение соотношению, графику соотношения, образу, прообразу.
2. Дайте определение отображения.
3. Назовите виды функциональных соотношений.
4. Дайте определение бинарного отношения.
5. Перечислите свойства бинарных отношений.
6. Определите понятие операции и алгебры, перечислите свойства и виды алгебр.