ример 4. Отношение «меньше» (<) на множестве натуральных чисел, очевидно, обладает свойством транзитивности, но не является ни рефлексивным, ни симметричным.

Показать, что t отношение эквивалентности, указать соответствующее ему разбиение множества А.

Матрица С_t имеет клеточную структуру. Рассмотрим соответствующее ей разбиение множества А: , где . Согласно теореме 2 данное разбиение задает отношение эквивалентности, которое, как легко видеть, совпадает с отношением t.

2.6. Отношение порядка. Упорядоченные множества.

Определение 10. Бинарное отношение j, заданное на множестве А, называется отношением порядка, если оно обладает свойствами:

1) рефлексивности (для любого а Î А а j а);

2) транзитивности (если a j b и bj c, то a j c);

3) антисимметричности (если a j b и b j a, то a = b).

Отношение порядка играет важную роль в математике, для него принято специальное обозначение «£». В этих обозначениях свойства рефлексивности, транзитивности и антисимметричности записываются следующим образом:

1) для всех а а £ а;

2) если a £ b и b £ c, то a £ c;

3) если a £ b и b £ a, то а = b.

Запись a £ b означает, что пара (a, b) принадлежит отношению порядка j ((a, b) Î j Í A ´ A). Про элемент а при этом говорят, что он меньше либо равен (не превосходит) b или, что он содержится в b. Отношение j ^{– 1}, обратное к отношению порядка j (а j ^{– 1} b Û b j a), само является отношением порядка. Порядок (£)^–1 называют двойственным к £ и обозначают символом ³. Будем писать a < b, если a £ b и а ¹ b. Таким образом, мы задали отношение строгого порядка, которое обладает только свойством транзитивности.

Определение 11. Частично упорядоченным множеством называется множество, на котором задано отношение порядка.

Таким образом, частично упорядоченное множество определяется двумя объектами: самим множеством А и определенным на нем отношением порядка – < А,£>. При этом на одном и том же множестве порядок можно задать различными способами, т. е. получить различные частично упорядоченные множества. В частности, таким образом получается так называемое двойственное частично упорядоченное множество < А,(£) ^{– 1}>.

Пример 10. Множество натуральных чисел N с обычным отношением порядка £ (a £ b Û b – a ³ 0) является частично упорядоченным множеством.

Пример 11. Множество натуральных чисел N будет частично упорядоченным множеством, если отношение порядка задать следующим образом: a £ b означает «b делится без остатка на а».

Легко убедиться, что данное отношение является отношением порядка, т.е. удовлетворяет условиям 1) – 3) определения 9.

Пример 12. Рассмотрим множество М = { a, b, c, 0, 1}. Бинарное отношение R на нем зададим перечислением пар: R = {(0, 0), (0, a), (0, b), (0, 1), (a, a), (a, 1), (b, b), (b, 1), (c, c), (c, 1), (1, 1)}. Свойства рефлексивности, транзитивности и антисимметричности очевидно выполняются, следовательно, это отношение порядка. Система < М, R > является частично упорядоченным множеством.

Отметим, что в примерах 9 и 10 мы имеем дело с одним и тем же множеством N, но с различными частично упорядоченными множествами.

С другой стороны, если на множестве А = {2, 4, 6, 10, 60} отношение порядка определено также, как в примере10, то достаточно очевидно, что это частично упорядоченное множество устроено (ведет себя) также, как и множество в примере 11 в смысле отношения порядка. Фактически, если переобозначить элементы множества А (2 «0, 4 «a, 6 «b, 10 «c, 60«1), то получим упорядоченное множество из примера 11. Такое переобозначение можно сделать не единственным образом, но суть его состоит в том, что мы нашли взаимно однозначное соответствие между множествами А и М, причем такое которое «сохраняет» отношение порядка. Таким образом, мы приходим к понятию изоморфизма упорядоченных множеств.

Пусть А и А¢ – два частично упорядоченных множества и g – взаимно однозначное отображение А на А¢. Отображение g называется сохраняющим порядок, если из того, что a £ b (a, b Î A), следует, что g (a)£ g (b).

Определение 12. Взаимно однозначное отображение g частично упорядоченного множества А на А¢ называется изоморфизмом, а сами частично упорядоченные множества А и А¢ изоморфными, если g (a) £ g (b) тогда и только тогда, когда a £ b (a, b Î A).

Пусть А – частично упорядоченное множество из примера 9, а А¢ – из примера 10. Взаимно однозначное отображение g, которое каждому натуральному числу n ставит в соответствие его само (g (n)= n), будет сохранять порядок, но не будет изоморфизмом. Действительно, если m делится на n без остатка (n £ m (n, m Î A)), то очевидно, что m – n = g (m) – g (п) ³ 0, т.е. g (n) £ g (m), следовательно g сохраняет порядок. Однако, отображение g не является изоморфизмом частично упорядоченных множеств примеров 9 и 10 хотя бы в силу того, что в частично упорядоченном множестве А не любая пара его элементов сравнима (например, m = 5, n = 3), а в множестве А¢ любая пара элементов сравнима, так как для любых натуральных чисел m и n либо m £ n, либо n £ m.

Изоморфизм частично упорядоченных множеств является отношением эквивалентности на некоторой совокупности частично упорядоченных множеств и разбивает эту совокупность на классы изоморфных между собой множеств. В том случае, когда нас интересует не природа элементов частично упорядоченных множеств, а только отношения порядка на них, можно отождествлять изоморфные между собой частично упорядоченные множеств.

Рассмотрим частные случаи упорядоченных множеств.

Определение 13. Частично упорядоченное множество < А, £> называется линейно упорядоченным, если в нем сравнимы любые два элемента, т.е. для любых a и b из А либо a £ b, либо b £ a.

В примере 9 множество линейно упорядочено, а в примерах 10 и 11 множества таковыми не являются. В условиях примера 10 натуральное число 2 несравнимо с любым натуральным нечетным числом. В примере 11 – несравнимы между собой элементы a, b, c.

Любое подмножество линейно упорядоченного множества само является таковым.

Для линейно упорядоченных множеств как для любого частично упорядоченного множества применимо понятие отображения, сохраняющего порядок, и, в частности, понятие изоморфизма.

Введем еще более узкое, но весьма важное понятие полной упорядоченности. Для этого определим минимальный элемент частично упорядоченного множества. Элемент а частично упорядоченного множества А называется минимальным (наименьшим), если из b £ а следует, что b = a. По аналогии элемент с частично упорядоченного множества А называется максимальным (наибольшим), если из с £ b следует. что b = c.

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

Множество всех рациональных чисел по отношению к естественному порядку является линейно упорядоченным, но не вполне упорядоченным, так как в нем нет минимального (и максимального) элемента.

Множество всех рациональных чисел отрезка [0, 1] (с естественным отношением порядка) имеет минимальный элемент – 0 и максимальный элемент – 1, но не является вполне упорядоченным множеством, так как, например, его подмножество положительных рациональных чисел наименьшего элемента не имеет.

Множество натуральных чисел N (с естественным отношением порядка) не имеет наибольшего элемента, но имеет наименьший элемент – 1. В силу того, что любое его непустое подмножество обладает наименьшим элементом, N является не только линейно упорядоченным, но и вполне упорядоченным множеством.

Ясно, что всякое (непустое) подмножество вполне упорядоченного множества само вполне упорядочено.

Частично упорядоченные множества можно изобразить графически (как бинарное отношение), но поскольку любое отношение порядка рефлексивно и транзитивно, то из соответствующей диаграммы удаляют все петли и транзитивно замыкающие дуги. Такие диаграммы, задающие частично упорядоченные множества, называются диаграммами Хассе. Диаграммы Хассе известны с конца XIX века, их применяли в генеалогии для задания родства.

Пример 13. Пусть А = {1, 2, 3, 5, 30}. Рассмотрим два упорядоченных множества: < A;£> и < А; j >. В первом задан естественный порядок, а во втором – aj b Û b делится на а без остатка. Изобразим соответствующие им диаграммы Хассе.

· 30

· 5

· 3

· 2

· 1

Рис. 5а.

· 30

2· 3· ·5

· 1

Рис. 5

Очевидно, что эти два частично упорядоченных множества неизоморфны.

2.7. Функции и отображения.

Определение 15. Функцией из А в В называется однозначное бинарное отношение f Í А ´ В, т.е. (a, b) Î f и (a, с) Î f Þ b = c.

Поскольку, любая функция являются бинарным отношением т.е. множеством, то, применяя интуитивный принцип объемности, получаем:две функции f и g равны (f = g), если они состоят из одних и тех же элементов. Область определения и область значения функции обозначаются и определяются так же как для бинарного отношения.

Если f – функция из Х в Y, то вместо (x, y) Î f привычно пишут у = f (x) и говорят, что у – значение, соответствующее аргументу х, или у – образ элемента х при отображении f. При этом х называют прообразом элемента у. Функцию f из X в Y (f Í X ´ Y) называют одноместной или функцией одной переменной. Это понятие можно обобщить на случай функции нескольких переменных следующим образом.

Функция f из Хⁿ в Y (f Î Хⁿ ´ Y) называется n-местной функцией из Х в Y или функцией n переменных и обозначается у = f (x ₁, x ₂, ..., x_n).

Определение 16. Функция f Í А ´ В, у которой область определения D_f совпадает с множеством А, называется отображением множества А в множество В или всюду определенной функцией.

Если при этом область значений Е_f совпадает с В (Е_f = B), то f – отображение А на множество В. Иногда говорят, что отображение f устанавливает однозначное соответствие между множествами А и В. Отображение обозначают: f: А ® В или .

Пусть f – отображение множества М в множество В. Совокупность всех элементов из М, образом которых является данный элемент b Î В, называется прообразом (или, точнее, полным прообразом) элемента b и обозначается f ^{– 1}(b), т.е. f ^{– 1}(b)={ m| m Î M и f (m)= b }.

Если А Í М, то образом множества А при отображении f называется множество f (A) = { x| x Î B, x = f (a) для всех а Î А }, т.е. совокупность образов всех элементов множества А. В свою очередь для каждого подмножества C из B множество f ^{– 1}(C) = { m| m = f ^{– 1}(c) для всех c Î C } называется прообразом множества C, т.е. f ^{– 1}(C) – совокупность всех тех элементов из М, образы которых принадлежат C. Если ни один элемент c из C не имеет прообраза, то полный прообраз f ^{– 1}(C)=Æ.

Сформулируем основные самые общие свойства отображений.

Теорема 3. Прообраз объединения двух множеств равен объединению их прообразов:

f ^{– 1}(А È В)= f ^{– 1}(А)È f ^{– 1}(В).

Прообраз пересечения двух множеств равен пересечению их прообразов:

f ^{– 1}(А Ç В)= f ^{– 1}(А)Ç f ^{– 1}(В).

Теорема 3 остается в силе для объединений и пересечений любого (конечного или бесконечного) числа множеств.

Теорема 4.Образ объединения двух множеств равен объединению их образов:

f (А È В)= f (А)È f (В).

Утверждение аналогичное теореме 4 для пересечений не имеет места, т.е. в общем случае образ объединения двух множеств не совпадает с пересечением их образов.

Например, если отображение f – это проектирование плоскости на ось Ох, то множество А = {0 £ х £ 1, у = 0} и множество В={0 £ х £ 1, у = 1} не пересекаются (А Ç В = Æ), а их образы, очевидно, совпадают (f (A)= f (B)).

2.8. Операции. Понятие алгебры.

Рассмотрим важный частный случай отображений – операции.

Определение 17. Отображение f из А в A называется операцией на множестве А.

В этом случае f (a) Î A и операцию f называют унарной.

На множестве действительных чисел R примерамиунарных операций являются:

1) операция нахождения обратного числа: f (x)= x^{– 1}, x ¹ 0, или в других обозначениях: f ={(x, x^{– 1}) | x Î R, x ¹0};

2) операция нахождения противоположного числа: f (x)= – x, или иначе: f ={(x, –x) | x Î R };

3) операция f ={(x,0) | x Î R }, которая любое действительное число х отображает в 0.

Определение 18. Отображение из Аⁿ в А называется n-местной (n-арной) операцией на множестве А.

В случае n = 2 операция называется бинарной, а при n = 3 – тернарной. На множестве векторов трехмерного пространства R ₃векторное умножение векторов – бинарная операция, а двойное векторное произведение – тернарная.

Операции сложения и умножения действительных чисел являются бинарными на множестве действительных чисел R. Например, операция сложения: f = {((x, y), x + y) | x, y Î R }.

Определение 19. Алгеброй называется совокупность двух множеств: некоторого множества А и множества F – операций, определенных на А.

Алгебры принято обозначать готическими буквами: Á, Â и т.д. Для алгебры Â =< А, F > множество А называется носителем алгебры, а множество F ее сигнатурой.

Пример 14. Множество натуральных чисел N c определенными на нем бинарными операциями сложения (+), умножения (´) является алгебрoй: < N; +, ´>. Сигнатура этой алгебры состоит из двух бинарных операций: F = {+, ´}.

Алгебры отличаются одна от другой носителям, сигнатурами и, наконец, свойствами, которыми обладают операции в этой алгебре.

Множество всех подмножеств (булеан) некоторого множества М с определенными на нем бинарными операциями объединения и пресечения и унарной операцией дополнения является алгеброй: Â_K = < S (М); È,Ç, ¢>. Иногда считают, что сигнатура данной алгебры кроме указанных трех операций содержит две нульарны (0-арные) операции: выделено пустое множество Æ и само множество М. Как мы видели в 1.4. эти операции удовлетворяют определенным свойствам (1–9).

Алгебра Â_K =< S (М);È, Ç, ¢,Æ, М > называется алгеброй Канто ра. Существуют алгебры с другими носителями, на которых определены две бинарные, одна унарная операция и выделены два элемента, но которые обладают теми же свойствами, что и алгебра Кантора. Рассматривая все такие алгебры, мы приходим к понятию абстрактной булевой алгебры. Алгебры Буля находят широкое применение в прикладных задачах.

Определение 20. Булевой алгеброй называется непустое множество В с двумя бинарными операциями Ú, Ù, двумя отмеченными элементами 0, I и одной унарной операцией`, причем для любых a, b, cÎB выполняются следующие равенства:

(А1) а Ú b = b Ú a,

а Ù b = b Ù a (коммутативность);

(A2) a Ú(b Ú c) = (a Úb)Ú c,

a Ú(b Ú c) = (a Ú b)Ú c (ассоциативность);

(A3): а Ú(b Ù c) = (a Ú b)Ù(a Ú c),

а Ù(b Ú c) = (a Ù b)Ú(a Ù c) (дистрибутивность);

(A4): a Ù a = a,

a Ú a = a (идемпотентность);

(А5): а Ù(а Ú b) = a,

а Ú(а Ù b) = a (поглощение);

(А6): а Ù0 = 0, а Ú0 = а,

а Ù I = а, а Ú I = I (универсальные границы);

(А7): а Ù = 0, a Ú = 0 (дополнение);

(А8): = a (двойное дополнение или инволютивность);

(А9): ,

(законы де Моргана).

Отметим, что это определение носит аксиоматический характер. Мы считаем заданными пять операций на множестве В (две бинарные: Ú и Ù, одна унарная` , и две нульарные: 0, I) и перечисляем 19 тождеств, сгруппированные в девять аксиом (постулатов). Алгебра считается булевой алгеброй тогда и только тогда, когда она имеет такой набор операций (сигнатуру) и в ней выполняются все выписанные аксиомы. Очевидно, что способ обозначения операций не играет роли. Операции Ú и Ù называют соответственно булевой суммой, или объединением, и булевым произведением, или пересечением.

Абстрактная булева алгебра может быть задана другим списком аксиом. В частности приведенный выше набор аксиом является избыточным, т.е. некоторые аксиомы можно исключить, так как они являются следствием других. В нашем случае, например, аксиомы А1, А8, А9 следуют из остальных шести. С другой стороны список аксиом можно пополнить следствиями из них. Например, в любой булевой алгебре справедливы тождества:

а Ù(b Ú(a Ù c))=(a Ù b)Ú(a Ù c),

а Ú(b Ù(a Ú c))=(a Ú b)Ù(a Ú c),

которые называются законами модулярности и могут быть получены из аксиом А 1 – А5. Действительно, пользуясь последовательно аксиомами А3, А2, А5 и А3, получаем

а Ù(b Ú(a Ù c)) = а Ù((b Ú a)Ù(b Ú c)) = (а Ù(b Ú a))Ù(b Úc) =

= а Ù(b Ú c) = (а Ù b)Ú(a Ù c).

Очевидно, что доказательство второго закона модулярности получается из доказательства первого заменой всех символов Ù на Ú и наоборот. Последнее замечание является частным случаем, более общего принципа двойственности, который можно сформулировать следующим образом:

любое утверждение верное в булевой алгебре, в формулировке которого встречаются только операции Ù, Ú и` , остается справедливым, если в его формулировке всюду заменить Ù на Ú и наоборот.

Это следует из того, что множество аксиом А1 – А9 в целом не меняется при замене Ù на Ú и Ú на Ù. Поэтому при такой замене всякое доказательство превращается в доказательство двойственного утверждения.