Bài giảng Toán rời rạc 1 - Chương II.2: Quan hệ - Võ Văn Phúc
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ầnNhắ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, .
Trang 1
Trang 2
Trang 3
Trang 4
Trang 5
Trang 6
Trang 7
Trang 8
Trang 9
Trang 10
Tải về để xem bản đầy đủ
Bạn đang xem 10 trang mẫu của tài liệu "Bài giảng Toán rời rạc 1 - Chương II.2: Quan hệ - Võ Văn Phúc", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
Tóm tắt nội dung tài liệu: Bài giảng Toán rời rạc 1 - Chương II.2: Quan hệ - Võ Văn Phúc
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) | a A, b A, 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) | a A, b A, 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: a A, b A, 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, 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à quan hệ ước số ("|") trên Z có tính bắc cầu 3. Biểu diễn quan hệ Định nghĩa: Cho R là quan hệ từ tập hợp A = {a1, a2, ..., am} đến tập hợp B = {b1, b2, ..., bn} Ma trận biểu diễn của R là ma trận cấp mxn được xác định như sau: 3. Biểu diễn quan hệ Ví dụ 3.1: Cho R là quan hệ từ A = {1,2,3,4} đến B = {u,v,w} như sau: R = {(1,u),(1,v),(2,w),(3,w),(4,u)}. Ta có: |A| = 4; |B| = 3 Khi đó R có thể biễu diễn như một ma trận 4x3 : 3. Biểu diễn quan hệ Ví dụ 3.2: Nếu R là quan hệ từ A = {1, 2, 3} đến B = {1, 2} sao cho a R b nếu a > b. Khi đó ma trận biểu diễn của R là? 3. Biểu diễn quan hệ Nhận xét: Nếu R là quan hệ trên tập A, khi đó MR là ma trận vuông R là phản xạ nếu tất cả các phần tử trên đường chéo chính của MR đều bằng 1 (mii = 1 i) R là đối xứng nếu MR đối xứng qua đường chéo chính Nội dung đã học 1. Giới thiệu Quan hệ 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 3. Biểu diễn quan hệ 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 4. Quan hệ tương đương Xét ví dụ: Cho S = {sinh viên của lớp} Gọi R = {(a,b)| a có cùng họ với b} Có Hỏi: R phản xạ? Có R đối xứng? Có R bắc cầu? 4. Quan hệ tương đương Định nghĩa: Quan hệ R trên tập A được gọi là tương đương nếu nó có tính chất: - Phản xạ - Đối xứng - Bắc cầu 4. Quan hệ tương đương Ví dụ: Quan hệ R trên các chuỗi ký tự xác định bởi a R b nếu a và b có cùng độ dài. Khi đó R là quan hệ tương đương Cho R là quan hệ trên tập số thực sao cho a R b nếu a – b là số nguyên. Khi đó R là quan hệ tương đương 4. Quan hệ tương đương Lớp tương đương: Cho R là quan hệ tương đương trên A và phần tử a A. Lớp tương đương chứa a được ký hiệu bởi [a]R hoặc [a] là tập: [a]R = {b A | b R a} 4. Quan hệ tương đương Ví dụ: Tìm các lớp tương đương modulo 8 chứa 0 và modulo 8 chứa 1? Giải: - Lớp tương đương modulo 8 chứa 0 gồm tất cả các số nguyên a chia hết cho 8. Ta có: [0]8 = {..., -16, -8, 0, 8, 16, ...} - Lớp tương đương modulo 8 chứa 1 gồm tất cả các số nguyên a chia 8 dư 1. Ta có: [1]8 = {..., -15, -7, 1, 9, 17, ...} 5. Quan hệ thứ tự Xét ví dụ: Cho R là quan hệ trên tập số thực: a R b nếu a b Hỏi: Có + R phản xạ ? Có + R phản xứng ? Không + R đối xứng ? Có + R bắc cầu ? 5. Quan hệ thứ tự Định nghĩa: Quan hệ R trên tập A là quan hệ thứ tự nếu nó có tính chất: - Phản xạ - Phản đối xứng - Bắc cầu Khi đó, ta nói A là một tập hợp sắp thứ tự Ký hiệu: Cặp (A, ) 5. Quan hệ thứ tự Ví dụ: + (R, ) là một tập hợp có thư tự. + (Z, |) là một tập hợp có thư tự. (|: ước) 6. Quan hệ toàn phần Định nghĩa: Các phần tử a và b của cặp (S, ) gọi là so sánh được nếu a b hay b a Định nghĩa: Cho (S, ), nếu hai phần tử tùy ý của S đều so sánh được với nhau thì ta gọi nó là tập sắp thứ tự toàn phần. Ta cũng nói rằng là thứ tự toàn phần hay thứ tự tuyến tính trên S. 6. Quan hệ toàn phần Ví dụ: Quan hệ “ ” trên tập số nguyên dương Z+ là thứ tự toàn phần Quan hệ ước số “|” trên tập hợp số nguyên dương không là thứ tự toàn phần, vì các số 5 và 7 là không so sánh được. Bài tập
File đính kèm:
- bai_giang_toan_roi_rac_1_chuong_ii_2_quan_he_vo_van_phuc.pdf