Đang chuẩn bị liên kết để tải về tài liệu:
Chương 3: Quan Hệ

Toán học rời rạc là tên chung của nhiều ngành toán học có đối tượng nghiên cứu là các tập hợp rời rạc, các ngành này được tập hợp lại từ khi xuất hiện khoa học máy tính làm thành cơ sở toán học của khoa học máy tính. Nó còn được gọi là toán học dành cho máy tính. Người ta thường kể đến trong toán học rời rạc lý thuyết tổ hợp, lý thuyết đồ thị, lý thuyết độ phức tạp, đại số Boole | Chương 3 Quan Hệ 1 Mục lục 2 3 Quan hệ thứ tự 1 4 1.Quan hệ thứ tự Có Không Có Có 1.Quan hệ thứ tự 5 1.Quan hệ thứ tự 6 1.Quan hệ thứ tự 7 1.Quan hệ thứ tự 8 1.Quan hệ thứ tự 9 Thứ tự toàn phần và bán phần 2 10 2.Thứ tự toàn phần và bán phần 11 2.Thứ tự toàn phần và bán phần 12 Phần tử tối tiểu và tối đại 3 13 3.Phần tử tối tiểu và tối đại 14 3.Phần tử tối tiểu và tối đại Ví dụ: a) (R, £) không có phần tử tối tiểu và tối đại. b) Cho E = {a, b, c} và A = P(E) \ {Æ, E}. Khi đó (A, Ì) có: các phần tử tối tiểu là:{a},{b},{c} các phần tử tối đại là:{a,b},{b,c},{a,c} c) Cho A = {2; 4; 5; 6; 8; 12}. Khi đó (A, | ) có các phần tử tối tiểu là 2 và 5 các phần tử tối đại là 5, 8 và 12 15 Phần tử nhỏ nhất và lớn nhất 4 16 4.Phần tử nhỏ nhất và lớn nhất 17 4.Phần tử nhỏ nhất và lớn nhất Định lý: Cho tập hợp có thứ tự (A,p ) và Æ ¹ X Ì A. Khi đó: a) Nếu X có phần tử lớn nhất ( nhỏ nhất) là a thì a là phần tử tối đại ( tối tiểu) duy nhất của X. b) Nếu X được bởi sắp thứ tự toàn phần bởi quan hệ p thì phần tử a Î X là phần tử lớn nhất ( nhỏ nhất) của X khi và chỉ khi a là phần tử tối đại (tối tiểu) của X. 18 Biểu đồ hasse 5 19 5.Biểu đồ Hasse 20 5.Biểu đồ Hasse 21 5.Biểu đồ Hasse 22 5.Biểu đồ Hasse 23 24 | Chương 3 Quan Hệ 1 Mục lục 2 3 Quan hệ thứ tự 1 4 1.Quan hệ thứ tự Có Không Có Có 1.Quan hệ thứ tự 5 1.Quan hệ thứ tự 6 1.Quan hệ thứ tự 7 1.Quan hệ thứ tự 8 1.Quan hệ thứ tự 9 Thứ tự toàn phần và bán phần 2 10 2.Thứ tự toàn phần và bán phần 11 2.Thứ tự toàn phần và bán phần 12 Phần tử tối tiểu và tối đại 3 13 3.Phần tử tối tiểu và tối đại 14 3.Phần tử tối tiểu và tối đại Ví dụ: a) (R, £) không có phần tử tối tiểu và tối đại. b) Cho E = {a, b, c} và A = P(E) \ {Æ, E}. Khi đó (A, Ì) có: các phần tử tối tiểu là:{a},{b},{c} các phần tử tối đại là:{a,b},{b,c},{a,c} c) Cho A = {2; 4; 5; 6; 8; 12}. Khi đó (A, | ) có các phần tử tối tiểu là 2 và 5 các phần tử tối đại là 5, 8 và 12 15 Phần tử nhỏ nhất và lớn nhất 4 16 4.Phần tử nhỏ nhất và lớn nhất 17 4.Phần tử nhỏ nhất và lớn nhất Định lý: Cho tập hợp có thứ tự (A,p ) và Æ ¹ X Ì A. Khi đó: a) Nếu X có phần tử lớn nhất ( nhỏ nhất) là a thì a là phần tử tối đại ( tối tiểu) duy nhất của X. b) Nếu X được bởi sắp thứ tự toàn phần bởi quan hệ p thì phần tử a Î X là phần tử lớn nhất ( nhỏ nhất) của X khi và chỉ khi a là phần tử tối đại (tối tiểu) của X. 18 Biểu đồ hasse 5 19 5.Biểu đồ Hasse 20 5.Biểu đồ Hasse 21 5.Biểu đồ Hasse 22 5.Biểu đồ Hasse 23 . | Chương 3 Quan Hệ 1 Mục lục 2 3 Quan hệ thứ tự 1 4 1.Quan hệ thứ tự Có Không Có Có 1.Quan hệ thứ tự 5 1.Quan hệ thứ tự 6 1.Quan hệ thứ tự 7 1.Quan hệ thứ tự 8 1.Quan hệ thứ tự 9 Thứ tự toàn phần và bán phần 2 10 2.Thứ tự toàn phần và bán phần 11 2.Thứ tự toàn phần và bán phần 12 Phần tử tối tiểu và tối đại 3 13 3.Phần tử tối tiểu và tối đại 14 3.Phần tử tối tiểu và tối đại Ví dụ: a) (R, £) không có phần tử tối tiểu và tối đại. b) Cho E = {a, b, c} và A = P(E) \ {Æ, E}. Khi đó (A, Ì) có: các phần tử tối tiểu là:{a},{b},{c} các phần tử tối đại là:{a,b},{b,c},{a,c} c) Cho A = {2; 4; 5; 6; 8; 12}. Khi đó (A, | ) có các phần tử tối tiểu là 2 và 5 các phần tử tối đại là 5, 8 và 12 15 Phần tử nhỏ nhất và lớn nhất 4 16 4.Phần tử nhỏ nhất và lớn nhất 17 4.Phần tử nhỏ nhất và lớn nhất Định lý: Cho tập hợp có thứ tự (A,p ) và Æ ¹ X Ì A. Khi đó: a) Nếu X có phần tử lớn nhất ( nhỏ nhất) là a thì a là phần tử tối đại ( tối tiểu) duy nhất của X. b) Nếu X được bởi sắp thứ tự