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