Bài tập quan hệ Toán rời rạc có lời giải

Bạn đang quan tâm đến Bài Tập Toán Rời Rạc Chương Quan Hệ, Toán Rời Rạc, Chương 3 phải không? Vậy hãy cùng Xettuyentrungcap.edu.vn đón xem bài viết này ngay sau đây nhé!

XEM VIDEO Bài Tập Toán Rời Rạc Chương Quan Hệ, Toán Rời Rạc, Chương 3 tại đây.

Bài giảng “Toán rời rạc – Chương 3: Quan hệ” cung cấp cho người đọc các kiến thức: Quan hệ hai ngôi trên một tập hợp và các tính chất, biểu diễn quan hệ hai ngôi, quan hệ tương đương, lớp tương đương, sự phân hoạch thành các lớp tương đương,… Mời các bạn cùng tham khảo nội dung chi tiết.

Đang xem: Toán rời rạc chương quan hệ

Chương 3. Quan hệ 3.1. Quan hệ hai ngôi trên một tập hợp và cáctính chất. Biểu diễn quan hệ hai ngôi.3.2. Quan hệ tương đương. Lớp tương đương.Sự phân hoạch thành các lớp tương đương.3.3. Quan hệ thứ tự. Thứ tự toàn phần và bánphần. Biểu đồ Hasse. Phần tử min và max.Các phần tử tối tiểu và tối đại. 1 Quan hệ hai ngôi1. Định nghĩa: Cho hai tập A, B. Ta gọi tập R là một quanhệ hai ngôi từ A đến B nếu R  A x B. Nếu [a, b]R thì ta nói a có quan hệ R với b và ký hiệua R b; ngược lại nếu [a, b] R thì ta kí hiệu a R b. Khi A = B, ta gọi R là một quan hệ hai ngôi trên A.Ví dụ: Ā A B a1 b1 a2 b2 a3 b3 R = { [a1, b1], [a1, b3], [a3, b3] } 2 Quan hệ hai ngôi1. Định nghĩa.Ví dụ: Cho A = {1, 2, 3, 4}, R là một quan hệ [hai ngôi] trên A và R = {[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]} 3 Quan hệ hai ngôi2. Các tính chất của quan hệ.Định nghĩa: Giả sử R là một quan hệ hai ngôi trên tập A. [a] Ta nói quan hệ R có tính phản xạ nếu và chỉ nếu a R a , a 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 4 Quan hệ hai ngôi2. Các tính chất của quan hệVí dụ: – Quan hệ ≤ trên Z phản xạ vì a ≤ a, a  Z. – Quan hệ > trên Z không phản xạ vì 1 không lớn hơn 1. – Quan hệ “ | ” [“ước số”] trên Z+ là phản xạ vì mọi sốnguyên dương a là ước của chính nó. 5 Quan hệ hai ngôi2. Các tính chất của quan hệ.Định nghĩa: Giả sử R là một quan hệ hai ngôi trên tập A. [b] Ta nói quan hệ R có tính đối xứng nếu và chỉ nếu a R b  b R a , a, b  A. [c] Ta nói quan hệ R có tính phản xứng nếu và chỉ nếu [a R b  b R a]  a = b ,  a, b  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, tuy nhiên nó phảnxứng vì [a ≤ b]  [b ≤ a]  [a = b]. – Quan hệ“ | ” [“ước số”] trên Z+ không đối xứng, tuynhiên nó có tính phản xứng vì [a | b]  [b | a]  [a = b]. 6 Quan hệ hai ngôi2. Các tính chất của quan hệĐịnh nghĩa: Giả sử R là một quan hệ hai ngôi trên tập A. [d] Ta nói quan hệ R có tính bắc cầu [truyền] nếu vàchỉ nếu [a R b  b R c]  a R c , a,b,c A.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à “|”trên Z có tính bắc cầu vì [a ≤ b]  [b ≤ c]  [a ≤ c] [a | b]  [b | c]  [a | c] 7 Quan hệ hai ngôi3. Biểu diễn quan hệĐịnh nghĩa.

XEM THÊM:  Muôn Mặt Cuộc Đời ” - Xem Phim Muôn Mặt Cuộc Đời

Xem thêm: Các Cách Dạy Em Gái Bướng Bỉnh “Một Phát Nghe Ngay” Không Cần Quát Mắng

Xem thêm: Sinh Năm 1995 Mệnh Gì, Tuổi Gì, Hợp Màu Gì, Hợp Tuổi Nào, Hướng Nào?

Cho R là quan hệ từ A = {1,2,3,4} đến B = {u,v,w},R = {[1,u],[1,v],[2,w],[3,w],[4,u]}. Khi đó R có thể biễu diễn như sau Đây là ma trận cấp 4×3 biễu diễn cho quan hệ R 8 Quan hệ hai ngôi3. Biểu diễn Quan hệ Định nghĩa. Cho R là quan hệ từ A = {a1, a2, …, am} đến B = {b1, b2, …, bn}. Ma trận biểu diễn của R là ma trận MR = mxn xác định bởi: Ví dụ: Cho R là quan hệ từ A = {1, 2, 3} đến B = {1, 2}: a R b  a > b. Khi đó ma trận biểu diễn của R là: 9 Quan hệ hai ngôi3. Biểu diễn quan hệVí dụ: Cho R là quan hệ từ A = {a1, a2, a3} đến B = {b1, b2,b3, b4, b5} được biễu diễn bởi ma trận Khi đó R gồm các cặp:{[a1, b2], [a2, b1], [a2, b3], [a2, b4], [a3, b1], [a3, b3], [a3, b5]}. 10 Quan hệ hai ngôi3. Biểu diễn quan hệCho 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éocủa MR đều bằng1: mii = 1, i. 11 Quan hệ hai ngôi3. Biểu diễn quan hệ+] R là đối xứng nếu MR là đối xứng mij = mji ,  i, j. 12 Quan hệ hai ngôi3. Biểu diễn quan hệ+] R là phản xứng nếu MR thỏa: mij = 0 hoặc mji = 0 nếu i ≠ j 13 Quan hệ tương đương1. Định nghĩa.Ví dụ: Cho S = {sinh viên của lớp}, gọi R là mộtquan hệ trên S với R = {[a,b]: a có cùng họ với b}. 14 Quan hệ tương đương1. Định nghĩa: Quan hệ R trên tập A được gọi làtương đương nếu và chỉ nếu nó có tính chất phảnxạ, đối xứng và bắc cầu.Ví dụ: Quan hệ R trên tập các chuỗi ký tự xác địnhbở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 tập R sao cho aRb  a – bZKhi đó R là quan hệ tương đương. 15 Quan hệ tương đương1. Định nghĩa.Ví dụ: Cho m là số nguyên dương và R là quan hệ trên Z : aRb  [a – b] chia hết mKhi đó 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ínhchất bắc cầu.- Quan hệ này được gọi là đồng dư modulo m và chúngta viết a  b [mod m] thay vì aRb.Ví dụ: Cho | là quan hệ trên Z được xác định như sau: a | b  kZ: b = kaQuan hệ | có là quan hệ tương đương? 16 Quan hệ tương đương2. Lớp tương đươngĐịnh nghĩa. Cho R là quan hệ tương đương trênA và a  A . Lớp tương đương chứa a theo quanhệ R được ký hiệu bởi R hoặc là tập hợp tấtcả những phần tử có quan hệ R với a. R = {b  A| b R a}•Mỗi phần tử xR được gọi là một phần tử đại diện củalớp tương đương R .•Tập thương của A theo quan hệ R, ký hiệu là A/R, đượcđịnh nghĩa là tập tất cả các lớp tương đương của các phầntử thuộc A, nghĩa là A/R = { R |aA} 17 Quan hệ tương đương2. Lớp tương đươngVí dụ: Tìm các lớp tương đương modulo 8 chứa 0và 1?Giải: Lớp tương đương modulo 8 chứa 0 gồm tấtcả các số nguyên a chia hết cho 8. Do đó 8 ={ …, – 16, – 8, 0, 8, 16, … }Tương tự 8 = {a | a chia 8 dư 1} = { …, – 15, – 7, 1, 9,17, … } 18 Quan hệ tương đương3. Sự phân hoạch thành các lớp tương đươngNhận xét: Trong ví dụ cuối, các lớp tương đương 8 và8 là rời nhau.Mệnh đề. Cho R là quan hệ tương đương trên tập A. Vớimọi a,bA các điều kiện sau đây tương đương với nhau[i]a R b[ii]R = R[iii] R  R ≠ Chú ý: Từ mệnh đề trên ta thấy rằng các lớp tương đươngcủa các phần tử của tập A hoặc trùng nhau, hoặc rời nhau.Hơn nữa, hợp của tất cả các lớp tương đương này trùng vớiA, cho nên tập A là hợp rời rạc của các lớp tương đương.Tacũng nói rằng tập A được phân hoạch thành các lớp tươngđương theo quan hệ R. 19 Quan hệ tương đương3. Sự phân hoạch thành các lớp tương đươngChú ý: Cho {A1, A2, … } là phân hoạch A thành các tập conkhô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.Thật vậy với mỗi a, b  A, ta đặt a R b nếu có tập con Aisao cho a, b  Ai .Dễ dàng chứng minh rằng R là quan hệ tương đương trênA và R = Ai nếu a  Ai . 20

Vậy là đến đây bài viết về Bài Tập Toán Rời Rạc Chương Quan Hệ, Toán Rời Rạc, Chương 3 đã dừng lại rồi. Hy vọng bạn luôn theo dõi và đọc những bài viết hay của chúng tôi trên website Xettuyentrungcap.edu.vn

Chúc các bạn luôn gặt hái nhiều thành công trong cuộc sống!

Full PDF PackageDownload Full PDF Package

This Paper

A short summary of this paper

37 Full PDFs related to this paper

Download

PDF Pack

Download bài tập Toán rời rạc có đáp án PDF ✓ Bài tập Toán rời rạc có lời giải chương 1, 2, 3, 4, 5, 6, 7 ✓ Các dạng bài tập toán rời rạc có lời giải ✓ File PDF ✓ Tải xuống miễn phí các bài tập toán rời rạc có lời giải PDF link Google Drive

File tài liệu tổng hợp các dạng bài tập Toán rời rạc có đáp án, lời giải chi tiết được soạn sẵn file PDF là tài liệu để sinh viên học cao đẳng, đại học học tập, ôn thi, giúp các bạn chuẩn bị tốt cho kỳ thi kết thúc học phần, thi cuối kỳ môn môn Toán rời rạc sắp đến. 

Nội dung bài tập Toán rời rạc có lời giải gồm có:

• Bài tập chương 1: Cơ sở logic 
• Bài tập chương 2: Tập hợp và ánh xạ 
• Bài tập chương 3: Phương pháp đếm
• Bài tập chương 4: Hệ thức đệ qui
• Bài tập chương 5: Quan hệ hai ngôi
• Bài tập chương 6: Hàm Bool
• Bài tập chương 7: Đại cương về đồ thị
• Hướng dẫn giải bài tập Toán rời rạc theo từng chương

XEM TRƯỚC 11 TRANG

TẢI FULL TÀI LIỆU

>> Xem thêm tài liệu Toán rời rạc

• Giáo trình toán rời rạc PDF
• Toán rời rạc Nguyễn Hữu Anh PDF