Упорядоченные множества и универсальная алгебра (вводный курс). Гуров С.И. - 13 стр.

UptoLike

ВУЗ: 

МГУ | Москва

Составители: 

Рубрика: 

Пусть ρ ⊆
n
Q
i=1
A
i
= A. Отношение ρ = A называют полным; мы будем обозначать его
O
A
.
Через P r
1
ρ обозначают совокупность всех таких элементов a
1
∈ A
1
для которых
найдутся такие a
2
∈ A
2
, . . . , a
k
∈ A
k
, что (a
1
, a
2
, . . . , a
k
) ∈ ρ. P r
1
ρ называют проекци-
ей отношения ρ на множество A
1
или первой проекцией. Аналогично определяются
вторые, третьи и т.д. проекции.
Отношение на A
1
× A
2
× . . . × A
k
называется полным, если его первая проекция
совпадает с A
1
, вторая — с A
2
и т.д.
Отношения можно рассматривать как предикаты, т.е. функции, принимающие два
значения: «истина» и «ложь»: считают, что ρ (a
1
, . . . , a
n
) истинно, если (a
1
, . . . , a
n
) ∈ ρ
и ложно в противном случае. Поэтому к отношениям можно применять операции алгеб-
ры логики: дизъюнкции ( ∨ ), конъюнкции ( ∧ ), отрицания ( ¬ ), тождества ( ≡ ), импли-
кации (
¡
¢
) и др. При чтении соответствующих формул следует иметь в виду, что, по-
скольку приоритет отношений выше приоритета операций алгебры логики, скобки вокруг
отношений, как правило, опускают.
Унарные отношения на некотором множестве определяют те или иные свойства его
элементов.
Бинарные отношения на декартовом произведении множеств A и B называют отно-
шениями между A и B или соответствиями между данными множествами. Для со-
ответствия ρ ⊆ A × B удобно пользоваться обозначением aρb, если (a, b) ∈ ρ.
Поскольку отношения суть подмножества, то для бинарных отношений определена
тотальная алгебра h P(A × B), ∪, ∩,
−
, ∅, A × B i. Ясно, что теоретико-множественные
операции, применённые к соответствиям α, β ⊆ A × B, имеют следующие свойства:
1) a
(
α
∪
β
)
b
⇔
aαb
∨
aβb
⇔
(
a, b
)
∈
α
или
(
a, b
)
∈
β
;
2) a(α ∩ β)b ⇔ aαb ∧ aβb ⇔ (a, b) ∈ α и (a, b) ∈ β ;
3) aα b ⇔ ¬(aαb) ⇔ (a, b) /∈ α .
Существует удобный способ представления соответствий конечных множеств в виде
(0,1)-матриц M(ρ). Пусть A = { a
1
, . . . , a
m
}, B = { b
1
, . . . , b
n
} и ρ ⊆ A × B. Зафик-
сируем указанный порядок следования элементов в множествах A и B. Тогда матрица
отношения ρ имеет размеры m×n и определяется следующим образом: её элемент m
i,j
равен 1, если справедливо a
i
ρb
j
и 0, если иначе.
Множество всех (0,1)-матриц размера m×n будем обозначать M
m×n
, опуская индекс,
когда соответствующий размер подразумевается. Во введённом множестве выделяются
матрица, у которой всё элементы равны 1 и матрица, у которой всё элементы равны
0. Их называют универсальной и нуль-матрицей и обозначают I и O соответственно.
К матрицам из M можно поэлементно применять логические операции ∨, ∧, ¬. Легко
видеть, что АС h M, ∨, ∧, ¬, O, I i является булевой алгеброй, изоморфной тотальной
алгебре h P(A × B), ∪, ∩,
−
, ∅, A × B i. Изоморфизм следует из следующих равенств,
очевидно справедливых для любых соответствий α и β между A и B :
1) M(α ∪ β) = M(α) ∨ M(β) ;
2) M(α ∩ β) = M(α) ∧ M(β) ;
3) M(α) = ¬ M(α) .
13
                Q
                n
   Пусть ρ ⊆          Ai = A. Отношение ρ = A называют полным; мы будем обозначать его
                i=1
OA .
    Через P r1 ρ обозначают совокупность всех таких элементов a1 ∈ A1 для которых
найдутся такие a2 ∈ A2 , . . . , ak ∈ Ak , что (a1 , a2 , . . . , ak ) ∈ ρ. P r1 ρ называют проекци-
ей отношения ρ на множество A1 или первой проекцией. Аналогично определяются
вторые, третьи и т.д. проекции.
    Отношение на A1 × A2 × . . . × Ak называется полным, если его первая проекция
совпадает с A1 , вторая — с A2 и т.д.
    Отношения можно рассматривать как предикаты, т.е. функции, принимающие два
значения: «истина» и «ложь»: считают, что ρ (a1 , . . . , an ) истинно, если (a1 , . . . , an ) ∈ ρ
и ложно в противном случае. Поэтому к отношениям можно применять операции алгеб-
ры логики: дизъюнкции ( ∨ ), конъюнкции ( ∧ ), отрицания ( ¬ ), тождества ( ≡ ), импли-
кации ( ¡¢ ) и др. При чтении соответствующих формул следует иметь в виду, что, по-
скольку приоритет отношений выше приоритета операций алгебры логики, скобки вокруг
отношений, как правило, опускают.
    Унарные отношения на некотором множестве определяют те или иные свойства его
элементов.
    Бинарные отношения на декартовом произведении множеств A и B называют отно-
шениями между A и B или соответствиями между данными множествами. Для со-
ответствия ρ ⊆ A × B удобно пользоваться обозначением aρb, если (a, b) ∈ ρ.
    Поскольку отношения суть подмножества, то для бинарных отношений определена
тотальная алгебра h P(A × B), ∪, ∩, − , ∅, A × B i. Ясно, что теоретико-множественные
операции, применённые к соответствиям α, β ⊆ A × B, имеют следующие свойства:

  1) a(α ∪ β)b ⇔ aαb ∨ aβb ⇔ (a, b) ∈ α или (a, b) ∈ β ;

  2) a(α ∩ β)b ⇔ aαb ∧ aβb ⇔ (a, b) ∈ α и (a, b) ∈ β ;

  3) aαb ⇔ ¬(aαb) ⇔ (a, b) ∈
                           / α.

    Существует удобный способ представления соответствий конечных множеств в виде
(0,1)-матриц M (ρ). Пусть A = { a1 , . . . , am }, B = { b1 , . . . , bn } и ρ ⊆ A × B. Зафик-
сируем указанный порядок следования элементов в множествах A и B. Тогда матрица
отношения ρ имеет размеры m × n и определяется следующим образом: её элемент mi,j
равен 1, если справедливо ai ρbj и 0, если иначе.
    Множество всех (0,1)-матриц размера m×n будем обозначать Mm×n , опуская индекс,
когда соответствующий размер подразумевается. Во введённом множестве выделяются
матрица, у которой всё элементы равны 1 и матрица, у которой всё элементы равны
0. Их называют универсальной и нуль-матрицей и обозначают I и O соответственно.
К матрицам из M можно поэлементно применять логические операции ∨, ∧, ¬. Легко
видеть, что АС h M, ∨, ∧, ¬, O, I i является булевой алгеброй, изоморфной тотальной
алгебре h P(A × B), ∪, ∩, − , ∅, A × B i. Изоморфизм следует из следующих равенств,
очевидно справедливых для любых соответствий α и β между A и B :

 1) M (α ∪ β) = M (α) ∨ M (β) ;

 2) M (α ∩ β) = M (α) ∧ M (β) ;

 3) M (α) = ¬ M (α) .




                                                13

Страницы