Xem mẫu
- CHƯƠNG 2
- Nội dung bài học
- Nhắc lại các khái niệm về tập hợp
- Mục tiêu bài học
1. Giới thiệu Quan hệ
2. Các tính chất của quan hệ.
3. Biểu diễn quan hệ
4. Quan hệ tương đương.
5. Quan hệ thứ tự.
6. Quan hệ toàn phần
- Nhắc lại các khái niệm về tập hợp
Tập hợp: có thể hiểu tổng quát là một sự tụ tập của một
số hữu hạn hay vô hạn các đối tượng nào đó.
Các đối tượng này được gọi là các phần tử của tập hợp
Ký hiệu:
Tập hợp: Dùng chữ cái HOA: A, B, C, ...
Phần tử của tập hợp: Dùng chữ cái thường:
a, b, x, y, ...
- Nhắc lại các khái niệm về tập hợp
Nếu a là 1 phần tử của tập hợp A thì ta viết a A.
Ngược lại viết a A
Ví dụ về tập hợp:
A = {x N | x là số nguyên tố}
B = {x Z | x2 < 15}
C = {-2, -1, 0, 1, 2}
Nếu tập A có n phần tử, ta ký hiệu: |A| = n
- Nhắc lại các khái niệm về tập hợp
Tập hợp con:
Tập hợp A là một tập con (hay tập hợp con) của tập hợp B
nếu A "được chứa" trong B.
Nếu A và B là các tập hợp và mọi phần tử của A cũng là
phần tử của B, thì:
A là tập con của B (hay A chứa trong B), ký hiệu A B
B là tập cha của A (hay B chứa A), ký hiệu B A
A B {a| a A a B}
- Nhắc lại các khái niệm về tập hợp
Tập hợp rỗng: kí hiệu là , là tập hợp không chứa
phần tử nào
Tích Descartes (Đề-các) của hai tập hợp A và B, ký hiệu
là A×B, là một tập hợp chứa tất cả các bộ có dạng (a, b)
với a là một phần tử của A và b là một phần tử của B.
AxB = {(a,b)| a A, b B}
Nếu tập |A| = n và |B| = m thì |AxB| = n x m
- Nhắc lại các khái niệm về tập hợp
Ví dụ:
Nếu: A = {1,2}; B = {p,q,r} thì:
A×B = {(1,p),(1,q),(1,r),(2,p),(2,q),(2,r)}
và:
B×A = {(p,1),(q,1),(r,1),(p,2),(q,2),(r,2)}
- Nội dung bài học
- Nhắc lại các khái niệm về tập hợp
- Mục tiêu của bài học
1. Giới thiệu Quan hệ
2. Các tính chất của quan hệ.
3. Biểu diễn quan hệ
4. Quan hệ tương đương.
5. Quan hệ thứ tự.
6. Quan hệ toàn phần
- Mục tiêu của bài học
Nắm được các kiến thức về quan hệ trên tập hợp.
Nội dung bài học là cơ sở cho các nội dung như đại số
Bool, Đại số quan hệ (Môn cơ sở dữ liệu), Lập trình
nâng cao (Xử lý ảnh, Computer Vision, Khai phá dữ
liệu…)
- 1. Giới thiệu Quan hệ
Định nghĩa:
Một quan hệ giữa tập hợp A và tập hợp B là một tập
con của tích Descartes AxB.
Nếu (a,b) , ta viết: ab
Quan hệ từ A đến A (chính nó) gọi là quan hệ trên A
- 1. Giới thiệu Quan hệ
Ví dụ 1: Một cách biểu diễn quan hệ:
- 1. Giới thiệu Quan hệ
Ví dụ 2: A = tập sinh viên; B = tập lớp học.
R = {(a, b) | sinh viên a học lớp b}
- 1. Giới thiệu Quan hệ
Ví dụ 3: Cho A = {1, 2, 3, 4}, và
R = {(a, b) | aA, bA, a là ước của b}
Khi đó:
R = {(1, 1), (1, 2), (1, 3), (1, 4),
(2, 2), (2, 4), (3, 3), (4,4)}
Biểu diễn:
- 2. Các tính chất của quan hệ
Tính phản xạ
Tính đối xứng
Tính phản đối xứng
Tính bắc cầu
- 2. Các tính chất của quan hệ
Tính phản xạ:
Quan hệ R trên A được gọi là phản xạ nếu: a A, a R a
Ví dụ: Xét tập A = {1, 2, 3, 4} với quan hệ ước số:
R = {(a, b) | aA, bA, a là ước của b}
R1 = {(1, 1), (1, 2), (1, 3), (1, 4),
(2, 2), (2, 4), (3, 3), (4,4)}
R1 phản xạ vì: (1,1) R1, (2,2) R1,
(3,3) R1, (4,4) R1
- 2. Các tính chất của quan hệ
Ví dụ: Cho tập A = {1, 2, 3, 4},
Xét 2 quan hệ sau:
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
- 2. Các tính chất của quan hệ
Ví dụ:
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
- 2. Các tính chất của quan hệ
Tính đối xứng:
Quan hệ R trên A được gọi là đối xứng nếu: aA,
bA, a R b b R a
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
- 2. Các tính chất của quan hệ
Tính phản đối xứng:
Một quan hệ R trên tập A được gọi là phản xứng nếu:
x, y A, (x R y) (y R x) x = y
Ví dụ:
+ Quan hệ “” là phản đối xứng
+ Quan hệ đồng nhất “” là phản đối xứng
+ Quan hệ song song “” là phản đối xứng
- 2. Các tính chất của quan hệ
Tính bắc cầu:
Quan hệ R trên A có tính bắc cầu (truyền) nếu
a, b, cA, (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à quan hệ ước số ("|") trên Z có tính bắc cầu
nguon tai.lieu . vn
