6.5 Отношение порядка

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

рефлексивное, антисимметричное, транзитивное бинарное отношение. Если это отноше-

ние является, кроме того, полным,то оно называется линейным порядком.

Пример 27

• Отношение ? на множестве R является линейным порядком.

• Пример частичного порядка - покомпонентный порядок в Rn

:

?x = (x1, . . . , xn), y = (y1, . . . , yn) ? R

n

x ? y ?? x1 ? y1, . . . xn ? yn

Если в определении отношения порядка заменить свойство рефлексивности на антире-

флексивность, то получится отношение строгого порядка (обозначается <).

Множество M, на котором задано отношение порядка R называется полностью упо-

рядоченным, если любые 2 элемента этого множества сравнимы, т.е. ?a, b ? M aRb или

bRa

Пример 28 Лексикографический порядок полностью упорядочивает слова в словаре16 Кустицкая Т.А. Дискретная математика

7 Алгебраические системы

Отображение ? : Mn = M * M * · · · * M ? M называется n-арной операцией.

7.1 Бинарные алгебраические операции

Операция ? : M * M ? M называется бинарной операцией и записывается в следующей

форме: a?b.

Бинарные операции могут являться:

1. коммутативными ?a, b ? Ma?b = b?a

Сложение, умножение на множестве R коммутативны, вычитание и деление - нет

2. ассоциативными ?a, b, c ? M(a?b)?c = a?(b?c)

Сложение, умножение - ассоциативны, вычитание, деление, возведение в степень - нет

3. дистрибутивными. Операция ? дистрибутивна слева относительно операции ?,

если ?a, b, c ? M a?(b?c) = (a?b)?(a?c)

Операция ? дистрибутивна справа относительно операции ?, если

?a, b, c ? M (a?b)?c) = (a?c)?(b?c)

Дистрибутивные операции - умножение относительно сложения. Возведение в степень

дистрибутивно относительно умножения справа, но не слева (ab)

c = a

c

·b

c

, a

bc =6 a

b

·a

c

Определение 22 Алгебраической системой называется некоторое множество G

(носитель) с заданным на нем набором операций и отношений.

Определение 23 Пусть ? = (?1, . . . , ?m) - совокупность операций, заданных на множе-

стве M. Система A = (M; ?1, . . . , ?m) называется алгеброй.

Алгебра является частным случаем алгебраической системы с пустым множеством отно-

шений.

Определение 24 Множество M0 ? M называется замкнутым относительно операции

?, если ?a, b ? M0

a?b ? M0

.

Если M0

замкнуто относительно всех операций ?1, . . . , ?m алгебры, то система A0 =

(M0

; ?1, . . . , ?m) называется подалгеброй алгебры A.

Пример 29

1. Алгебра (R, +, ·) называется полем действительных чисел. Подалгебра - поле рацио-

нальных чисел.

Все конечные подмножества, кроме {?} незамкнуты относительно обеих операций.

2. Пусть задано множество M и его булеан - 2M. (2M, ?, ?,?) - булева алгебра мно-

жеств над M.