intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Bài giảng Toán rời rạc: Chương 4 - Nguyễn Lê Minh

Chia sẻ: Minh Nguyệt | Ngày: | Loại File: PDF | Số trang:43

Thêm vào BST
Báo xấu
56
lượt xem 5
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Toán rời rạc: Chương 4 - Nguyễn Lê Minh

  1. 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
  2. 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
  3. Đị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
  4. Đị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
  5. Đị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
  6. 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
  7. 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
  8. 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
  9. 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
  10. Các tính chất của quan hệ 4 4 * 3 3 2 2 * * 1 1 1 2 3 4 1 2 3 4 3
  11. Các tính chất của quan hệ Định nghĩa. 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. 3
  12. Tóm lại R phản xạ : aRa R đối xứng: aRb  bRa R phản xứng: aRb và bRa  a=b R bắc cầu: aRb và bRc  aRc 3
  13. Quan hệ tương đương Ví dụ. Xét quan hệ trên tập {1,2,3,4} Các quan hệ sau, quan hệ nào là phản xạ, đối xứng, bắc cầu 3
  14. Quan hệ tương đương Ví dụ. Xét quan hệ sau trên tập số nguyên Quan hệ nào là phản xạ, đối xứng, bắc cầu ? 3
  15. 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 và bắc cầu : Ví dụ. Quan hệ R trên các chuỗi ký tự xác định bởi aRb nếu a và b có cùng độ dài. Khi đó R là quan hệ tương đương. Ví dụ. Cho R là quan hệ trên R sao cho aRb nếu a – b nguyên. Khi đó R là quan hệ tương đương 3
  16. Quan hệ tương đương Cho a và b là hai số nguyên. a được gọi là ước của b hay b chia hết cho a nếu tồn tại số nguyên k sao cho b = ka Ví dụ. Cho m là số nguyên dương và R quan hệ trên Z sao cho aRb nếu a – b chia hết cho m, khi đó R là quan hệ tương đương. - Rõ ràng quan hệ này có tính phản xạ và đối xứng. - Cho a, b, c sao cho a – b và b – c chia hết cho m, khi đó a – c = a – b + b – c cũng chia hết cho m. Suy ra R có tính chất bắc cầu. - Quan hệ này được gọi là đồng dư modulo m và được viết viết a  b (mod m) thay vì aRb 3
  17. Lớp tương đương Định nghĩa. Cho R là quan hệ tương đương trên A và phần tử x  A . Lớp tương đương chứa x được ký hiệu bởi [x]R hoặc [x] là tập hợp con [x]R = {b  A| x R a} 3
  18. Lớp tương đương Ví dụ. Tìm các lớp tương đương modulo 8 chứa 0 và 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. Do đó [0]8 ={ …, – 16, – 8, 0, 8, 16, … } Tương tự [1]8 = {a | a chia 8 dư 1} = { …, – 15, – 7, 1, 9, 17, … } 3
  19. Lớp tương đương Chú ý. Trong ví dụ cuối, các lớp tương đương [0]8 và [1]8 là rời nhau. Tổng quát, chúng ta có Định lý. Cho R là quan hệ tương đương trên tập A và a, b  A, Khi đó (i) a R b nếu [a]R = [b]R (ii) [a]R  [b]R nếu [a]R  [b]R =  Chú ý. Các lớp tương đương theo một quan hệ tương đương trên A tạo nên một phân họach trên A, nghĩa là chúng chia tập A thành các tập con rời nhau. 3
  20. Lớp tương đương Chú ý. Cho {A1, A2, … } là phân họach A thành các tập con không rỗng, rời nhau. Khi đó có duy nhất quan hệ tương đương trên A sao cho mỗi Ai là một lớp tương đương. a A1 A2 A3 A4 b A5 3
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2