Компьютерная математика: Часть 1. Теория множеств и комбинаторика. Волченская Т.В - 31 стр.

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

31
Пример 1. Пусть A={1, 2, 3, 4, 5, 6, 7, 8, 9, 10}.
Тогда R={(x, y): x, y
∈ A, где x – делитель y и x ≤ 5}.
В явном виде R = {(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6),
(1, 7), (1, 8), (1, 9), (1, 10), (2, 2), (2, 4), (2, 6), (2, 8), (2, 10), (3, 3), (3, 6), (3, 9),
(4, 4), (4, 8), (5, 5), (5, 10)}.
Пример 2 (шахматы). Пусть F = {a, b, c, d, e, f, g, h }, R = {1, 2, 3, 4, 5,
6, 7, 8 } и пусть S = F
×R.
Таким образом, S – множество всех клеток, обозначаемых парами (x,
y), где x
∈ F, y ∈ R.
Определим бинарное отношение C для ладьи на множестве S так, что
(s, t)
∈ C тогда и только тогда, когда s и t – элементы S и ладья может прой-
ти от s к t одним ходом на пустой доске.
C
⊆ S×S и C = {((f
s
, r
s
), (f
t
, r
t
)) : (f
s
=f
t
и r
s
≠ r
t
) или (f
s
≠ f
t
и r
s
=r
t
)}.
Напомним, что ладья может изменять либо горизонтальную коорди-
нату, либо вертикальную, но не обе одновременно.
В общем случае ряд различных отношений на множестве A зависит от
|A|. Большая часть этих отношений не представляет интереса, но отдельные
оказываются полезными.
Определение 1.
Для любого множества A определим тождественное
отношение I
A
и универсальное отношение U
A
следующим образом:
I = {(a, a) : a
∈ A}, U = {(a, b) : a ∈ A, b ∈ А}.
Таким образом, U
A
= A
2
. Так как ∅ ⊆ A
2
, то ∅ является отношением
на A и называется пустым отношением.
Пусть отношение R определено в соответствии с изображением на
рис. 27. Свяжем с каждым бинарным отношением R между A и B – область
определения D(R) и область значений
ℜ(R). Они определяются следую-
щим образом.
Определение 2
. Область определения – это множество значений x,
таких, что пара (x, y) принадлежит отношению R:
D(R) = {x : (x, y)
∈ R }, а область значений ℜ(R) это множество значений
y, таких, что пара (x, y) принадлежит отношению R:
ℜ(R) = {y : (x, y) ∈ R}. 
        Пример 1. Пусть A={1, 2, 3, 4, 5, 6, 7, 8, 9, 10}.
        Тогда R={(x, y): x, y ∈ A, где x – делитель y и x ≤ 5}.
В явном виде R = {(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6),
(1, 7), (1, 8), (1, 9), (1, 10), (2, 2), (2, 4), (2, 6), (2, 8), (2, 10), (3, 3), (3, 6), (3, 9),
(4, 4), (4, 8), (5, 5), (5, 10)}.
        Пример 2 (шахматы). Пусть F = {a, b, c, d, e, f, g, h }, R = {1, 2, 3, 4, 5,
6, 7, 8 } и пусть S = F×R.
        Таким образом, S – множество всех клеток, обозначаемых парами (x,
y), где x ∈ F, y ∈ R.
        Определим бинарное отношение C для ладьи на множестве S так, что
(s, t) ∈ C тогда и только тогда, когда s и t – элементы S и ладья может прой-
ти от s к t одним ходом на пустой доске.
        C ⊆ S×S и C = {((fs, rs), (ft, rt)) : (fs=ft и rs≠ rt) или (fs≠ ft и rs=rt)}.
        Напомним, что ладья может изменять либо горизонтальную коорди-
нату, либо вертикальную, но не обе одновременно.
        В общем случае ряд различных отношений на множестве A зависит от
|A|. Большая часть этих отношений не представляет интереса, но отдельные
оказываются полезными.
        Определение 1. Для любого множества A определим тождественное
отношение IA и универсальное отношение UA следующим образом:
                        I = {(a, a) : a ∈ A}, U = {(a, b) : a ∈ A, b ∈ А}.
        Таким образом, UA = A2. Так как ∅ ⊆ A2, то ∅ является отношением
на A и называется пустым отношением.
        Пусть отношение R определено в соответствии с изображением на
рис. 27. Свяжем с каждым бинарным отношением R между A и B – область
определения D(R) и область значений ℜ(R). Они определяются следую-
щим образом.
        Определение 2. Область определения – это множество значений x,
таких,       что       пара       (x,      y)      принадлежит           отношению            R:
D(R) = {x : (x, y) ∈ R }, а область значений ℜ(R) это множество значений
y, таких, что пара (x, y) принадлежит отношению R: ℜ(R) = {y : (x, y) ∈ R}.




                                             31

Страницы