Bài giảng Toán rời rạc: Chương 5 - Lê Văn Luyện

Bài giảng "Toán rời rạc - Chương 5: Quan hệ" cung cấp cho người học các kiến thức: Quan hệ hai ngôi, quan hệ tương đương, quan hệ thứ tự. Đây là một tài liệu hữu ích dành cho các bạn sinh viên đang theo học môn này và những ai quan tâm dùng làm tài liệu học tập và nghiên cứu.
Nội dung trích xuất từ tài liệu:
Bài giảng Toán rời rạc: Chương 5 - Lê Văn LuyệnTOÁN RỜI RẠC - HK1 - NĂM 2015 -2016Chương 5QUAN HỆlvluyen@hcmus.edu.vnhttp://www.math.hcmus.edu.vn/∼luyen/trrFB: fb.com/trr2015Trường Đại Học Khoa học Tự nhiên TP Hồ Chí Minhlvluyen@hcmus.edu.vnChương 5. Quan hệ14/12/20151/39Nội dungChương 5. QUAN HỆ1. Quan hệ hai ngôi2. Quan hệ tương đương3. Quan hệ thứ tựlvluyen@hcmus.edu.vnChương 5. Quan hệ14/12/20152/395.1. Quan hệ hai ngôi1Định nghĩa2Các tính chất của quan hệlvluyen@hcmus.edu.vnChương 5. Quan hệ14/12/20153/395.1.1. Định nghĩaĐịnh nghĩa. Một quan hệ hai ngôi từ tập A đến tập B là tập conR của tích Descartes A × B.Quan hệ từ A đến chính nó được gọi là quan hệ hai ngôi (hay quanhệ ) trên A.Ví dụ. Cho A = {0, 1, 2} và B = {a, b}. Khi đóR = {(0, a), (0, b), (1, a), (2, b)}là một quan hệ từ A vào B. Quan hệ này được mô tả bằnglvluyen@hcmus.edu.vnChương 5. Quan hệ14/12/20154/39Ví dụ. Cho A = {1, 2, 3, 4}, và R = {(a, b) | a là ước của b}. Khi đó Rlà một quan hệ trên A. Hãy tìm R?Giải. R = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 4), (3, 3), (4, 4)}.Ví dụ. Cho A = {1, 2, 3, 4}. Hỏi ta có thể xây dựng được bao nhiêuqua hệ trên A?Giải. Vì |A| = 4 nên |A × A| = 16. Do mỗi quan hệ trên A là một tậpcon của |A × A| nên số quan hệ trên A là 216 .Ví dụ.(tự làm) Cho A = {1, 2, 3}. Hãy tìm số quan hệ hai ngôi trên Aa) chứa (1, 1).b) có đúng 5 phần tử.c) có ít nhất 7 phần tử.lvluyen@hcmus.edu.vnChương 5. Quan hệ14/12/20155/39