Определение 2.1 Бинарное отношение
на некотором множестве
называется отношением (нестрогого) частичного порядка, если для
:
(рефлексивность);
и
, то
(антисимметричность);
и
, то
(транзитивность).
Множество S с определённым на нем отношением частичного порядка
(частично упорядоченное множество) обозначается
. Если
, то говорят, что элемент
меньше, чем
или равен ему. Если для
не существует
, такого что
, то
называют максимальным элементом
(относительно
).
Если
и
, то пишут
и говорят, что
строго меньше, чем
.
Определение 2.2 Пусть
— частично упорядоченное множество. Элемент
называется соседом снизу элемента
, если
и
. В этом случае
называется соседом сверху
(обозначается
). Направленный граф отношения
называется графом покрытия.
Конечное частично упорядоченное множество
может быть графически представлено с помощью диаграммы Хассе (или просто диаграммы [1]). Элементы
изображаются в виде точек. Если
, то
размещается "над"
(вертикальная координата
больше вертикальной координаты
), и две точки соединяются линией.
Определение 2.3 Верхней гранью подмножества
в упорядоченном множестве
называется элемент
, такой что
для всех
. Точная верхняя грань множества
(называемая также наименьшей верхней гранью или супремумом) множества
(обозначается sup
) есть верхняя грань
такая, что
для любой верхней грани
подмножества
. Двойственным образом (с заменой
на
) определяется понятие точной (наибольшей) нижней грани или инфимума inf
.
Определение 2.4 Бинарная операция
называется полурешёточной, если для некоторого
и любых
:
(идемпотентность);
(коммутативность);
(ассоциативность);
.
Для
и
мы пишем
вместо
. Если
, то
.
Определение 2.5 Множество
с определённой на нем полурешёточной операцией
называется полурешёткой
.
Полурешёточная операция
задает два частичных порядка
и
на
(
):
Тогда множество с определённой на нем полурешёточной операцией