Методы бикластеризации для анализа интернет-данных


Частично упорядоченные множества и решётки


Определение 2.1   Бинарное отношение

на некотором множестве

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

:

  1. (рефлексивность);

  2. и

    , то

    (антисимметричность);

  3. и

    , то

    (транзитивность).

Множество S с определённым на нем отношением частичного порядка

(частично упорядоченное множество) обозначается

. Если

, то говорят, что элемент

меньше, чем

,

или равен ему. Если для

не существует

, такого что

, то

называют максимальным элементом

(относительно

).

Если

и

, то пишут

и говорят, что

строго меньше, чем

.

Определение 2.2   Пусть

— частично упорядоченное множество. Элемент

называется соседом снизу элемента

, если

и

. В этом случае

называется соседом сверху

(обозначается

). Направленный граф отношения

называется графом покрытия.

Конечное частично упорядоченное множество

может быть графически представлено с помощью диаграммы Хассе (или просто диаграммы [1]). Элементы

изображаются в виде точек. Если

, то

размещается "над"

(вертикальная координата

больше вертикальной координаты

), и две точки соединяются линией.

Определение 2.3   Верхней гранью подмножества

в упорядоченном множестве

называется элемент

, такой что

для всех

. Точная верхняя грань множества

(называемая также наименьшей верхней гранью или супремумом) множества

(обозначается sup

) есть верхняя грань

такая, что

для любой верхней грани

подмножества

. Двойственным образом (с заменой

на

) определяется понятие точной (наибольшей) нижней грани или инфимума inf

.

Определение 2.4   Бинарная операция

называется полурешёточной, если для некоторого

и любых

:

  1. (идемпотентность);

  2. (коммутативность);

  3. (ассоциативность);

  4. .

Для

и

мы пишем

вместо

. Если

, то

.

Определение 2.5   Множество

с определённой на нем полурешёточной операцией

называется полурешёткой

.

Полурешёточная операция

задает два частичных порядка

и

на

(

):

    и

Тогда множество с определённой на нем полурешёточной операцией




Начало  Назад  Вперед



Книжный магазин