Логика. Множества. Вероятность. Лексаченко В.А. - 55 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

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

Рубрика: 

Otnoxenie (
R|
X
, X, B
) nazyvaets sueniem otnoxeni
(
R, A, B)
na X , a (
R, A, B) — prodoleniem otnoxeni
(R
|
X
, X, B
)
.
Vmesto (x, y)∈
R qasto pixut
xRy
i govort ”lement
x∈
A
nahodits v otnoxenii R k lementu
y
∈B ”. Oboznaqenie xRy
obsnets tradicionno$i zapis~ izvestnyh binarnyh otnoxe-
ni$i v
R :
x =
y, x
6
= y, x
6
y, x>
y, x < y, x > y .
Mnoestvo binarnyh otnoxeni$i (R, A, B)
, vlets bulevo$i
algebro$i s operacimi
∪
,
∩
,
s nulem —
nul~-otnoxeniem
(∅
, A, B
)
i edinice$i —
universal~nym otnoxeniem
(
A×
B, A, B)
.
Opredelenie 2.2 (Obrawenie otnoxeni$i).
Obratnym k otnoxe-
ni (R, A, B
) nazyvaets otnoxenie
(
R
−1
, B, A), gde
R
−
1
{
(
x, y) ∈ B
×
A
:
yRx
}
.
sno, qto xR
−1
y = yRx ,
Dom R
−1
= Im R ,
Im R
−
1
= Dom
R
.
Esli otnoxenie R opredeleno v mnoestve de$istvitel~nyh qi-
sel, to svz~ grafikov otnoxeni$i
R
i
R
−
1
mono predsta-
vit~ nagldno, a imenno: grafiki R
−
1
i
R simmetriqny ot-
nositel~no bissektrisy, prohodwe$i qerez naqalo koordinat,
pervy$i i treti$i kvadranty koordinatno$i ploskosti.
Opredelenie 2.3 (Kompozici otnoxeni$i).
Kompozicie$i otno-
xeni$i
(R, A, B
) i (
S, B, C
)
nazyvaets otnoxenie (
R
◦
S, A, C)
,
opredelemoe formulo$i R
◦ S
{(
x, y
)
∈ A
×
C
: (∃
z
∈ B)(xRz
∧
zSy
)}.
Teorema 2.1 (Svo$istva kompozicii i obraweni otnoxeni$i).
Pust~ (
R, A, B),
(S, B, C),
(T, C, D
)
— binarnye otnoxeni. Togda
:
1) (
R
◦ S
) ◦
T
= R ◦
(S
◦ T ) , 2) (R
◦ S)
−
1
=
S
−
1
◦
R
−1
,
3) (R
−
1
)
−1
=
R , 4) R
= ∆
A
◦ R = R
◦ ∆
B
gde
∆
A
{
(x, y)
∈
A
×
A
:
x = y} — diagonal~ v mnoestve A
.
D o k a z a t e l ~ s t v o . 1. [
x
(
R◦S)
◦T
y]∼[(∃
u
∈ C)
x(
R
◦S)
u∧
uT y
]
∼
∼
[(
∃u
∈ C)
(
∃v
∈ B)(
xRv∧vSu)∧uT y
]
∼[(
∃
u
∈ C)(
∃
v
∈
B
)
(xRv∧vSu
)
∧
∧uT y
]
∼[(
∃
v ∈ B)(∃
u
∈
C
)
xRv∧
(vSu
∧uT y)
]
∼[(
∃v ∈
B)
xRv∧(∃
u
∈
C)(
vSu∧uT y)
]
∼[(
∃
v ∈ B
)
xRv∧
(v(
S ◦
T ))
y
]
∼
[
x
R ◦
(S ◦
T )
y]
.
2
. [x
(R
◦ S
)
−1
]
y
∼
[
y(
R
◦ S)x
]
∼
[(∃v
∈
B
)(
yRv
∧
vSx)] ∼[(∃v
∈
B)(
vSx
∧
∧
yRv)]
∼
[(∃v ∈ B
)(
xS
−
1
v
∧vR
−
1
y
)]
∼[
x
(
S
−1
◦
R
−
1
)
y].
3.
[
x(R
−
1
)
−
1
y] ∼
[
yR
−1
x]∼
[
xRy]
. J
Iz teoremy 2.1 sleduet, qto kompozici binarnyh otnoxe-
ni$i associativna. V obwem sluqae kompozici nekommutativna.
Opredelenie 2.4 (Obrazy i proobrazy mnoestv). Pust~ X⊆
A,
Y ⊆
B , R
⊆A
×
B — binarnoe otnoxenie. Obrazom mnoestva
X
pri R
nazyvaets mnoestvo Rh
X
i
pr
2
R
|
X
= pr
2
((
X×B) ∩
R
),
proobrazom mnoestva
Y pri R nazyvaets obraz mnoestva
Y pri otnoxenii R
−1
— mnoestvo
R
−
1
hY
i
=pr
1
((
A
×
Y
) ∩ R)
.
55

Страницы