Gọi A, B và C là các tập hợp, và đặt R là một quan hệ từ A đến B và gọi S là một quan hệ từ B đến C. Nghĩa là, R là một tập con của A × B và S là một tập hợp con của B × C. Khi đó R và S tạo ra một quan hệ từ A đến C được chỉ ra bởi R◦S và được xác định bởi:
- a (R◦S) c nếu với b ∈ B nào đó ta có aRb và bSc.
- Là,
- R ◦ S = {(a, c) | tồn tại b ∈ B mà (a, b) ∈ R và (b, c) ∈ S}
Các bài viết liên quan:
Quan hệ R◦S được biết đến là thành phần của R và S; nó đôi khi được ký hiệu đơn giản bằng RS.
Gọi R là một quan hệ trên tập A, nghĩa là R là một quan hệ từ tập A đến chính nó. Khi đó R◦R, thành phần của R với chính nó, luôn được biểu diễn. Ngoài ra, R◦R đôi khi được ký hiệu là R2. Tương tự, R3 = R2◦R = R◦R◦R, v.v. Do đó Rn được xác định với mọi n dương.
Ví dụ 1: Cho X = {4, 5, 6}, Y = {a, b, c} và Z = {l, m, n}. Hãy xem xét Relations R1 từ X đến Y và R2 từ Y đến Z.
R1 = {(4, a), (4, b), (5, c), (6, a), (6, c)}
R2 = {(a, l), (a, n), (b, l), (b, m), (c, l), (c, m), (c, n)}
Tìm thành phần của quan hệ (i) R1 o R2 (ii) R1o R1-1
(i) Quan hệ thành phần R1 o R2 như trong hình:
R1 o R2 = {(4, l), (4, n), (4, m), (5, l), (5, m), (5, n), (6, l), (6, m), (6, n)}
(ii) Quan hệ thành phần R1o R1-1 như trong hình:
R1o R1-1 = {(4, 4), (5, 5), (5, 6), (6, 4), (6, 5), (4, 6), (6, 6)}
Thành phần của các Relations và ma trận
Có một cách khác để tìm R◦S. Gọi MR và MS lần lượt là biểu diễn ma trận của các quan hệ R và S. Khi đó
Ví dụ
Cho P = {2, 3, 4, 5}. Xem xét Relations R và S trên P được xác định bởi
R = {(2, 2), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 5), (5, 3) }
S = {(2, 3), (2, 5), (3, 4), (3, 5), (4, 2), (4, 3), (4, 5), (5, 2) , (5, 5)}.
Tìm các ma trận của các quan hệ trên.
Sử dụng ma trận để tìm thành phần sau của quan hệ R và S.
(i) RoS (ii) RoR (iii) SoR
Lời giải: Các ma trận của quan hệ R và S là một ma trận được hiển thị trong hình:
(i) Để có được thành phần của quan hệ R và S. Đầu tiên nhân MR với MS để thu được ma trận MR x MS như trong hình:
Các mục khác 0 trong ma trận MR x MS cho biết các phần tử liên quan trong RoS. Cho nên,
Do đó thành phần R o S của Relations R và S là
R o S = {(2, 2), (2, 3), (2, 4), (3, 2), (3, 3), (4, 2), (4, 5), (5, 2), (5, 3), (5, 4), (5, 5)}.
(ii) Đầu tiên, nhân ma trận MR với chính nó, như thể hiện trong hình
Do đó thành phần R o R của Relations R và S là
R o R = {(2, 2), (3, 2), (3, 3), (3, 4), (4, 2), (4, 5), (5, 2), (5, 3), (5, 5)}
(iii) Nhân ma trận MS với MR để thu được ma trận MS x MR như trong hình:
Các mục khác 0 trong ma trận MS x MR cho biết các phần tử liên quan trong S o R.
Do đó thành phần S o R của quan hệ S và R là
S o R = {(2, 4), (2, 5), (3, 3), (3, 4), (3, 5), (4, 2), (4, 4), (4, 5), (5, 2), (5, 3), (5, 4), (5, 5)}.
