Ktl-icon-tai-lieu

Toán rời rạc

Được đăng lên bởi yen461202
Số trang: 56 trang   |   Lượt xem: 2137 lần   |   Lượt tải: 1 lần
Chương
LOGO3

Lê Văn Luyện
email: lvluyen@yahoo.com

TOÁN RỜI RẠC


Chương 3

QUAN HỆ

3

I. Quan hệ

1. Định nghĩa và tính chất
2. Biểu diễn quan hệ
3. Quan hệ tương đương. Đồng dư
4. Quan hệ thứ tự, biểu đồ Hass

4

1. Định nghĩa
Một quan hệ hai ngôi từ tập A đến tập B là tập con của tích Đề
các R  A x B. Chúng ta sẽ viết a R b thay cho (a, b)  R.

Quan hệ từ A đến chính nó được gọi là quan hệ trên A

R = { (a1, b1), (a1, b3), (a3, b3) }

5

1. Định nghĩa
Ví dụ. A = tập sinh viên; B = các lớp học.
R = {(a, b) | sinh viên a học lớp b}

6

1. Định nghĩa
Ví dụ. Cho A = {1, 2, 3, 4}, và
R = {(a, b) | a là ước của b}
Khi đó
R = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 4), (3, 3), (4,4)}

1

2

3

4

1

2

3

4

2. Các tính chất của Quan hệ
Định nghĩa. Quan hệ R trên A được gọi là phản xạ nếu:

a  A, a R a
Ví dụ. Trên tập A = {1, 2, 3, 4}, quan hệ:
 R1 = {(1,1), (1,2), (2,1), (2, 2), (3, 4), (4, 1), (4, 4)}
không phản xạ vì (3, 3)  R1

 R2 = {(1,1), (1,2), (1,4), (2, 2), (3, 3), (4, 1), (4, 4)} phản
xạ vì (1,1), (2, 2), (3, 3), (4, 4)  R2

7

 Quan hệ  trên Z phản xạ vì a  a với mọi a Z
 Quan hệ > trên Z không phản xạ vì 1 > 1
Quan hệ“ | ” (“ước số”) trên Z + là phản xạ vì mọi số
nguyên a là ước của chính nó .

Chú ý. Quan hệ R trên tập A là phản xạ nếu nó chứa đường
chéo của A × A :
 = {(a, a); a  A}
4
3
2
1
1

2

3

4
8

9

2. Các tính chất của Quan hệ
Định nghĩa. Quan hệ R trên A được gọi là đối xứng nếu:
a  A b  A (a R b)  (b R a)
Quan hệ R được gọi là phản xứng nếu
 a  A b  A (a R b)  (b R a)  (a = b)
Ví dụ.
 Quan hệ R1 = {(1,1), (1,2), (2,1)} trên tập
A = {1, 2, 3, 4} là đối xứng
Quan hệ  trên Z không đối xứng.
Tuy nhiên nó phản xứng vì
(a  b)  (b  a)  (a = b)


10

2. Các tính chất của Quan hệ
 Quan hệ“ | ” (“ước số”) trên Z +. không đối xứng
Tuy nhiên nó có tính phản xứng vì
(a | b)  (b | a)  (a = b)
Chú ý. Quan hệ R trên A là đối xứng nếu nó đối xứng nhau
qua đường chéo  của A × A.
Quan hệ R là phản xứng nếu chỉ có các phần tử nằm trên
đường chéo là đối xứng qua  của A × A.
4

4

3

3

2

2

1

1
1

2

3

4

*

*

*
1

2

3

4

11

2. Các tính chất của Quan hệ
Định nghĩa. Quan hệ R trên A có tính bắc cầu (truyền) nếu
a, b,c A,(a R b)  (b R c)  (a R c)

Ví dụ.
Quan hệ R = {(1,1), (1,2), (2,1), (2, 2), (1, 3), (2, 3)}
trên tập A = {1, 2, 3, 4} có tính bắc cầu.
Quan hệ  và “|”trên Z có tính bắc cầu
(a  b)  (b  c)  (a  c)
(a | b)  (b | c)  (a | c)

12

3. B...
LOGO
TOÁN RỜI RẠC
Lê Văn Luyn
email: lvluyen@yahoo.com
www.math.hcmus.edu.vn/~lvluyen/trr
Chương 3
Toán rời rạc - Trang 2
Để xem tài liệu đầy đủ. Xin vui lòng
Toán rời rạc - Người đăng: yen461202
5 Tài liệu rất hay! Được đăng lên bởi - 1 giờ trước Đúng là cái mình đang tìm. Rất hay và bổ ích. Cảm ơn bạn!
56 Vietnamese
Toán rời rạc 9 10 781