20. Множества и бинарные отношения, их свойства. Булевы алгебры. Пример.

В широком смысле, множество – это совокупность объектов (элементов), которые понимаются как единое целое (по тем или иным признакам, критериям или обстоятельствам).

Обычно множества обозначаются большими латинскими буквами A, B, C,..., X, Y, Z (как вариант, с подстрочными индексами: A_1, A_2 и т.п.), а его элементы записываются в фигурных скобках, например:

– множество букв русского алфавита;

– множество натуральных чисел;

Множество A является конечным (состоящим из конечного числа элементов), а множество N – это пример бесконечного множества.

Кроме того, в теории и на практике рассматривается так называемое пустое множество ∅ – множество, в котором нет ни одного элемента.

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

Например:

– множество всех натуральных чисел, меньших ста.

Множество G является подмножеством множества A, если каждый элемент множества G принадлежит множеству A.

Иными словами, множество G содержится во множестве A.

G ⊂ A

Этот значок называют значком включения.

Операции над множествами

Объединением A ∪ B множеств A и B называется множество элементов x таких, что x принадлежит хотя бы одному из двух множеств A или B.

Пересечением A ⋂ B множеств A и B называется множество, состоящее из элементов x, которые принадлежат и множеству A и множеству B.

Разностью A\B множеств A и B называется множество всех тех элементов множества A, которые не принадлежат множеству B.

Абсолютным дополнением множества называется множество всех элементов, не принадлежащих A, т.е. множество U\A, где U – универсальное множество.

Бинарные отношения

Пусть A и B два конечных множества. Декартовым произведением множеств A и B называют множество A x B состоящее из всех упорядоченных пар, где

Бинарным отношением между элементами множества A и B называется любое подмножество множества R, то есть

Высказывание: «элементы x и y связаны бинарным отношением R» записывают в виде

xRy

Таким образом,

Свойства бинарных отношений

Бинарное отношение R на некотором множестве M может обладать различными свойствами, например:

Рефлексивность — если любой элемент x из M, находится сам с собой в отношении R.

Антирефлексивность — если любой элемент x из M, не находится сам с собой в отношении R.

Симметричность — если для любой пары элементов x, y из M, выполнение отношения xRy (x находится в отношении R с y), и влечёт выполнение отношения yRx.

Антисимметричность —если для любой пары элементов x, y из M, из выполнения отношений xRy и yRx следует равенство x и y.

Несимметричность — не является симметричным и антисимметричным.
Транзитивность — если для любых трёх элементов x, y, z из M, из выполнения отношений xRy и yRz следует выполнение отношения xRz.

Примеры:

Виды отношений

Рефлексивное симметричное транзитивное отношение называется отношением эквивалентности
Рефлексивное антисимметричное транзитивное отношение называется отношением (частичного) порядка
Антирефлексивное антисимметричное транзитивное отношение называется отношением строгого порядка

Операции над отношениями

Пересечение. Пересечением двух бинарных отношений (A и B) является отношение, которое определяется пересечением соответствующих подмножеств. Очевидно, что отношение A ⋂ B выполнимо только в том случае, когда некоторые x и y связаны как первым, так и вторым отношением (xAy и xBy).

Например, пересечением отношения «не меньше» и «не равно» является отношение «больше».

Объединение. Объединением двух бинарных отношений (A и B) является отношение, которое определяется объединением соответствующих подмножеств. Отношение A ∪ B выполнимо только в том случае, когда некоторые x и y связаны хотя бы одним из двух отношений хотя бы одно из отношений(xAy или xBy).

Например, объединением отношения «больше» и отношения «равно» является отношение «больше, либо равно».

Включение. Обозначается A ⊆ B. Первое отношение включено во второе, если все те пары, для которых выполняется первое отношение, являются подмножеством пар, для которых выполняется второе отношение. Если A ⊆ B, то, A != B. Если A ⊆ B, то, когда любые два элемента из множества, на котором выполняется отношение A, связаны этим отношением, они связаны отношением B.

Булевы алгебры

Булевой алгеброй называется непустое множество A с заданными на нем двумя бинарными операциями (a ∨ b - булево сложение (аналог конъюнкции), a ∧ b булево умножение (аналог дизъюнкции)), одной унарной операцией (¬a булево дополнение (аналог отрицания)) и универсальными границами (0 и 1) такими, что для любых a, b из множ��ства А верны следующие аксиомы:

коммутативность

a ∨ b = b ∨ a
a ∧ b = b ∧ a

ассоциативность

a ∨ (b ∨ с) = (a ∨ b) ∨ с
a ∧ (b ∧ с) = (a ∧ b) ∧ с

законы поглощения

a ∨ (a ∧ b) = a
a ∧ (a ∨ b) = a

дистрибутивность

a ∨ (b ∧ с) = (a ∨ b) ∧ (a ∨ c)
a ∧ (b ∨ с) = (a ∧ b) ∨ (a ∧ c)

дополнительность

a ∧ ¬a = 0
a ∨ ¬a = 1