Файл: 1 Кодирование текстовых и символьных данных.doc

, пересечения и дополнения иногда называются законами алгебры множеств. Эти законы аналогичны правилам для равносильностей в булевой алгебре (1.13.1)—(1.13.3).

Часто элементы разных множеств связаны различными соотношениями, например, соотношениями порядка. -местным отношением или -местным предикатом на множествах называется любое подмножество декартова произведения . Обозначение -местного отношения . При отношение называется унарным и является подмножеством множества . Бинарным (или двуместным при ) отношением называется множество упорядоченных пар. Элементы называются координатами или компонентами отношения .

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

Рассмотрим два конечных множества , и бинарное отношение . Введем матрицу бинарного отношения

---

следующим образом:

.

Эта матрица содержит полную информацию о связях между элементами множеств и и позволяет представить эту информацию в графическом виде.

Матрица любого бинарного отношения обладает следующими свойствами:

• 
  если и , то ; , причем сложение элементов матрицы осуществляется по правилам 0 + 0 = 0, 1 + 1 = 1, 1 + 0 = 0 + 1 = 1, а умножение осуществляется почленно обычным образом, т. е. по правилам , ;
  
• 
  , где  — матрица обратного отношения ;
  
• 
  если , то и .
  

Пример 1. Бинарное отношение , изображено на рис. 1.12. Его матрица имеет вид:

.

Пусть

,

тогда

, .

Р
ис. 1.12.

---

Бинарное отношение ,

Пусть  — бинарное отношение на множестве , . Отношение на множестве называется рефлексивным, если , , т. е.

,

где звездочкой обозначены нули или единицы. Отношение называется иррефлексивным, если , . Отношение на множестве называется симметричным, если и из условия следует, что . Это значит, что . Отношение называется антисимметричным, если из условий и следует, что , или

---

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

Рефлексивное, транзитивное и симметричное отношение на множестве называется эквивалентностью на . Эквивалентность обозначается символами или , например, , .

Пример 2. Докажем, что на множестве отношение является отношением эквивалентности, если .

Если отношение рефлексивно на , то . В нашем случае роль играет множество , а роль элемента играет пара . Тогда отношение рефлексивно на

---

, если . По определению , но , следовательно, рефлексивно.

Аналогично, если , то и , так как из следует, что . Таким образом, симметрично.

Наконец, если , , то , так как и . Тогда , т. е. транзитивно.

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

---