Bài giảng Toán rời rạc: Chương 4 - ThS. Trần Quang Khải

Bài giảng Toán rời rạc: Chương 4 Hàm và Quan hệ, cung cấp cho người học những kiến thức như: Hàm; Quan hệ: Quan hệ trên một tập hợp; Các tính chất của quan hệ; Quan hệ n-ngôi; Biểu diễn quan hệ; Tính bao đóng của quan hệ; Quan hệ tương đương. Mời các bạn cùng tham khảo!
Nội dung trích xuất từ tài liệu:
Bài giảng Toán rời rạc: Chương 4 - ThS. Trần Quang KhảiTOÁN RỜI RẠC Chương 4:Hàm & Quan hệ Giảng viên: ThS. Trần Quang Khải Nội dung 1. Hàm. 2. Quan hệ. a) Quan hệ trên một tập hợp. b) Các tính chất của quan hệ. c) Quan hệ n-ngôi. d) Biểu diễn quan hệ. e) Tính bao đóng của quan hệ. f) Quan hệ tương đương.Toán rời rạc: 2011-2012 Chương 4: Hàm & Quan hệ 2 Review: Hàm Hàm là gì? Đơn ánh? Toàn ánh? Song ánh? Toán rời rạc: 2011-2012 Chương 4: Hàm & Quan hệ 3 Khái niệm “hàm” trong lập trình Để mô tả một function: Input: các dữ liệu đầu vào. Output: các dữ liệu đầu ra. Các bước thực thi để xử lý input  tạo ra output.  Quá trình mô hình hóa vấn đề/bài toán. Toán rời rạc: 2011-2012 Chương 4: Hàm & Quan hệ 4 Giới thiệu Điểm yếu của hàm: Không thể biểu diễn trường hợp một phần tử thuộc tập này tương ứng với nhiều phần tử thuộc tập khác.Ví dụ: Một ông vua có 100 bà vợ. Một nhân viên cùng lúc đảm trách nhiều chức vụ. Một con vịt xòe ra hai cái cánh? Toán rời rạc: 2011-2012 Chương 4: Hàm & Quan hệ 5 Quan hệ - Ví dụ Quan hệ giữa một nhân viên và tiền lương của anh ta. Quan hệ giữa cấp quản lý và cấp dưới. Quan hệ giữa chương trình và biến của nó. Quan hệ giữa giá trị hàng hóa và tỉ lệ khuyến mãi. Quan hệ về vị trí/đường đi giữa các thành phố. Cải tiến/Tối ưu hoạt động của doanh nghiệp. Cải tiến/Tối ưu hoạt động của chương trình. Tối ưu thiết kế cơ sở dữ liệu. Toán rời rạc: 2011-2012 Chương 4: Hàm & Quan hệ 6 Định nghĩaCho hai tập hợp A và B. Một quan hệ haingôi (binary relation) từ A đến B là mộttập con của A×B. R  A×BKý hiệu: Quan hệ: R aRb để chỉ (a,b) R aRb để chỉ (a,b) RToán rời rạc: 2011-2012 Chương 4: Hàm & Quan hệ 7 Quan hệ hai ngôiVí dụ: Cho tập sinh viên S  {a, b, c} và tập các chương của môn Toán Rời Rạc D  {l , c, s, g} Các sinh viên này ôn thi như thế nào? Toán rời rạc: 2011-2012 Chương 4: Hàm & Quan hệ 8 Quan hệ trên một tập hợp Quan hệ từ một tập hợp đến chính nó (tập con của A×A). Ví dụ: cho tập A  {1, 5, 3, 6} Cặp nào thuộc quan hệ R  {(a, b) | a  b} R  {(1,1), (5,1), (5,5), (3,1), (3,3), (6,1), (6,3), (6,6)} Toán rời rạc: 2011-2012 Chương 4: Hàm & Quan hệ 9 Quan hệ trên một tập hợp Có bao nhiêu quan hệ trên một tập hợp có n phần tử? | A  A | n 2 Nếu | S | m thì | P( S ) | 2m n2 Vậy số quan hệ là 2 Toán rời rạc: 2011-2012 Chương 4: Hàm & Quan hệ 10 Các tính chất của quan hệ 1. Tính phản xạ. 2. Tính đối xứng – Phản đối xứng. 3. Tính bắc cầu.Toán rời rạc: 2011-2012 Chương 4: Hàm & Quan hệ 11 Tính phản xạ Định nghĩa: (a,a )  R với mọi a  A Ví dụ: xét tập A  {1, 2, 3} và các quan hệ R1  {(1,1), (2,2), (3,3), (1,2), (3,2} R2  {(1,2), (2,2), (2,3), (3,3)} Quan hệ nào là có tính phản xạ? Toán rời rạc: 2011-2012 Chương 4: Hàm & Quan hệ 12 Tính đối xứng Định nghĩa: (b, a)  R khi (a, b)  R với a, b  A Ví dụ: A  {1, 2, 3} R1  {(1,2), (2,2), (2,3), (3,3), (3,2), (2,1)} R2  {(1,2), (1,1), (2,1), (2,2), (3,3)} Phản đối xứng: (b, a)  R và (a, b)  R chỉ khi a  b Toán rời rạc: 2011-2012 Chương 4: Hàm & Quan hệ 13 Tính bắc cầu Định nghĩa: nếu (a,b)  R và (b,c)  R thì (a,c)  R với a,b, c  A Ví dụ: A  {1, 2, 3} R  {(1,2), (2,2), (2,3), (1,3)} Toán rời rạc: 2011-2012 Chương 4: Hàm & Quan hệ 14 Ví dụ Tìm tính chất của các quan hệ sau: Toán rời rạc: 2011-2012 Chương 4: Hàm & Quan hệ 15 Tổng hợp Phản xạ Đối xứngPhản đối xứng Bắc cầuToán rời rạc: 2011-2012 Chương 4: Hàm & Quan hệ 16 Quan hệ n-ngôi Binary relation: quan hệ trên hai tập hợp. n-ary relation: quan hệ trên nhiều tập hợp.Quan hệ n-ngôi trên các tập hợp A1 , A2 ... An là một tậpcon của tích Decartes A1  A2  ...  An Ví dụ: xét quan hệ R gồm các bộ ba (a,b,c) trên tập các số nguyên dương sao cho a < b < c (1,2,3)  R (2,1,3)  R Toán rời rạc: 2011-2012 Chương 4: Hàm & Quan hệ 17 Ứng dụng của quan hệ n-ngôi Cơ sở dữ liệu quan hệ. Mã phòng Mã Họ tên Mã N ...