Bài giảng "Toán rời rạc - Chương 4: Quan hệ" cung cấp cho người học các kiến thức: Định nghĩa và tính chất, biểu diễn quan hệ, quan hệ tương đương – Đồng dư, quan hệ thứ tự - Biểu đồ Hass. Cuối mỗi phần đều có phần bài tập đề người học ôn tập và củng cố kiến thức. | Bài giảng Toán rời rạc: Chương 4 - Nguyễn Lê Minh TOÁN RỜI RẠC Chương 4: QUAN HỆ GV: NGUYỄN LÊ MINH Bộ môn Công nghệ thông tin Nội dung Định nghĩa và tính chất Biểu diễn quan hệ Quan hệ tương đương – Đồng dư Quan hệ thứ tự - Biểu đồ Hass Bài tập 2 Đị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 Descart R A x B. Được 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) } 3 Đị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} 3 Đị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 3 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 3 Các tính chất của quan hệ 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 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 : 4 3 = {(a, a); a A} 2 1 3 1 2 3 4 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) 3 Các tính chất của quan hệ 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. 3 Các tính chất
