- Đinh nghĩa 1: Một quan hệ 2 ngơi R trên một tập hợp X (khácrỗng) được gọi là một quan hệ thứ tưï (hay vắn tắt, là một thứ tự)nếu và chỉ nếu nĩ cĩ 3 tính chất: phản xạ, phản xứng, truyền. Khiđĩ ta cũng nĩi tập hợp X là một tập cĩ thứ tự. Nếu cĩ thêm tínhchất: với mọi x, y  X ta cĩ x
Ry hay y
Rx thì ta nĩi R là một

quan hệ thứ tự tồn phầntrên X.

Bạn đang xem: Cách vẽ biểu đồ hasse

Ghi chú :

 Trong trường hợp trên X cĩ nhiều quan hệ thứ tự thì khi xét đếnthứ tự trên X ta phải nĩi rõ thứ tự nào, và ta thường viết tập hợp
X cĩ thứ tự dưới dạng một cặp (X,R); trong đĩ R là quan hệ thứtự đang xét trên X.

 Với 2 tập hợp cĩ thứ tự X và Y ta cĩ thể định ra một thứ tự trêntích Descartes Xx
Y dựa vào các thứ tự trên X và trên Y. Từ đĩ ta
Xx
Y trở thành một tập hợp thứ tự (xem phần bài tập).

Ví dụ:

1. Quan hệ trên tập hợp các số thựcRlà một quan hệ thứ tựtồn phần.

2. Cho E là một tập hợp. Quan hệtrên

P

(E) là một quan hệthứ tự. Nếu E cĩ nhiều hơn 2 phần tử thì thứ tự nầy khơngphải là thứ tự tồn phần. Việc kiểm chứng điều nầy đượcdành cho người đọc.

3. Trên tập hợp các số nguyên Z, xét qna hệ “chia hết” hay“ước số của”, ký hiệu là, được định nghĩa như sau:

ab  kZ: a = k.b

Dễ dàng kiểm chứng rằng quan hệ  cĩ 3 tính chất: phảnxạ, phản xứng, truyền. Từ đĩ ta cĩ (Z,) là một tập hợp cĩthứ tự.

Ta cĩ 2 số nguyên 2 và 3, khơng cĩ quan hệ với nhau theoquan hệ. Do đĩkhơng phải là thứ tự tồn phần trênZ.

Nhận xét:Nếu (X,R) là một tập hợp cĩ thứ tự và A X thì quan hệthứ R thu hẹp trên tập A, cũng được ký hiệu là R (nếu khơnggây ra nhầm lẫn), là một quan hệ thứ tự trên A. Nĩi một cáchkhác, ta cĩ:

(X,R) thứ tự và AX  (A,R) thứ tự

Đối với một tập hợp cĩ thứ tự thì việc đề cập đến các khái niệm như“phần tử nhỏ nhất”, “phần tử lớn nhất”, ... là điều rất tự nhiên. Dướiđây, chúng ta sẽ giới thiệu một số khái niệm quan trọng khi xét mộttập hợp cĩ thứ tự.

- Định nghĩa 2:Cho (X,) là một tập hợp cĩ thứ tự, và AX. Ta gọi một phần tử a  A là một phần tử nhỏ nhất của tập

hợp A nếu và chỉ nếu với mọi xA ta cĩ : ax.

 Ta gọi một phần tử aA là mộtphần tử lớn nhấtcủa tập hợp
A nếu và chỉ nếu với mọi xA ta cĩ : xa.

 Ta gọi một phần tử a A là mộtphần tử tối tiểucủa tập hợp
A nếu và chỉ nếu khơng tồn tại xA sao cho xa và xa. Ta gọi một phần tử aA là mộtphần tử tối đại của tập hợp

A nếu và chỉ nếu khơng tồn tại xA sao cho xa và ax.

Nhận xét:

(1) Phần tử nhỏ nhất (lớn nhất) của một tập hợp, nếu cĩ, làduy nhất.Ta ký hiệu phần tử nhỏ nhất của một tập hợp Alà min A hay min (A), và ký hiệu phần tử lớn nhất của Alà max A hay max (A).

(2) Phần tử tối tiểu (tối đại) của một tập hợp cĩ thứ tự khơngnhất thiết là duy nhất. Ví dụ: xét tập hợp X = 1,2,3 vớiquan hệ 2 ngơi  được cho bởi  = (1,1), (2,2), (3,3),(1,2), (3,2). Chúng ta cĩ thể kiểm chứng rằng (X, ) làmột tập hợp cĩ thứ tự. Với thứ tựnầy, X cĩ 2 phần tử tốitiểu là 1 và 3.

(3) Phần tử lớn nhất (nhỏ nhất) của một tập hợp, nếu cĩ, làphần tử tối đại (tối tiểu) duy nhất của tập hợp đĩ.

Ví dụ:

1. Trong tập hợp cĩ thứ tự (Z,), tập hợp A = mZm2 2 chận dưới của tập hợp A

nếu và chỉ nếu với mọi a  A ta cĩ : x  a. Chận dưới lớnnhất (nếu cĩ), tức là phần tử lớn nhất trong tập hợp tất cảnhững chận dưới của A được ký hiệu làinf (A).

 Ta gọimộtphần tử xX là mộtchận trêncủa tập hợp A nếuvà chỉ nếu với mọi a  A ta cĩ : a  x. Chận trên nhỏ nhất

(nếu cĩ), tức là phần tử nhỏ nhất trong tập hợp tất cả nhữngchận trên, của A được ký hiệu làsup (A).

Ví du: Trong (R,), A = xRx2thứ tự tốt (hay được sắptốt) nếu và chỉ nếu mọi tập con khác rỗng đều cĩ phần tử nhỏnhất.

Ví du:

1. Tập hợp cĩ thứ tự (N,) là một tập hợp được sắp tốt.

2. Tập hợp cĩ thứ tự (Z, ) khơng phải là một tập hợp đượcsắp tốt vìZkhơng cĩ phần tử nhỏ nhất.

3.2 Biểu đồ Hasse.

Một trong những phương pháp biểu diễn cho một quan hệ là dùng cácđồ thị định hướng (directed graph). Một đồ thị định hướng gồm mộttập hợp các đỉnh cùng với một tập hợp các cặp đỉnh được gọi là cáccạnh (hay các cung). Đồ thị biểu diễn cho một quan hệ 2 ngơi R trênmột tập hợp X cĩ tập hợp các đỉnh chính là X, và tập hợp các cungchính là R. Nếu (a,b)  R thì trên biểu đồ ta vẽ một cung hướng từđỉnh a đến đỉnh b. Đồ thị định hướng tương ứng của một quan hệ haingơi trên một tập hợp sẽ cung cấp cho ta những thơng tin về quan hệmột cách rất trực quan. Do đĩ người ta thường sử dụng các đồ thịđịnh hướng để nghiên cứu các quan hệ và các tính chất của chúng.

Ví dụ: X =a,b,c,d, R =(a,d), (b,b), (b,d), (c,a), (c,b), (d,b). Đồthị định hướng (X,R) cĩ thể được vẽ ra như sau:

Cạnh (b,b) được vẽ trên biểu đồ bởi cung xuất phát từ đỉnh bvà quay trở lại chính đỉnh b. Cạnh nầy được gọi là một“vịng” tại b.

Chúng ta cĩ thể thấy rằng một quan hệ 2 ngơi trên một tập hợp làđối xứng khi và chỉ khi trên đồ thị biểu diễn tương ứng mỗi cặp đỉnhđều cĩ 2 cung nối theo 2 hướng ngược nhau. Như vậy đồ thị của quanhệ trong ví dụ trên ta kết luận quan hệ nầy khơng cĩ tính đối xứng.

Đối với một tập hợp X (hữu hạn) cĩ thứ tự thì trên đồ thị địnhhướng tương ứng cĩ nhiều cạnh khơng nhất thiết phải vẽ ra bởi vìchúng được hiểu ngầm. Nĩi một cách khác, các tính chất của quanhệ thứ tự giúp ta biết được cĩ những cạnh đương nhiên cĩ trên đồ thịcủa quan hệ; và những cạnh đĩ sẽ khơng được vẽ ra trên đồ thị.Trước hết ta thấy rằng tại mỗi đỉnh của đồ thị phải cĩ một vịng dotính phản xạ của quan hệ thứ tự, nên các vịng nầy sẽ khơng được vẽra trên đồ thị. Ngồi ra quan hệ thứ tự cịn cĩ tính truyền, nên ta sẽkhơng cần vẽ ra cạnh (a,c) nếu trên đồ thị cĩ các cạnh (a,b) và (b,c)với b là một đỉnh nào đĩ. Hơn nữa, nếu (a,b), (b,c), và (c,d) là cáccạnh thì ta cũng loại ra cạnh (a,d). Chúng ta cũng khơng ghi mũi tênđịnh hướng trên các cạnh với qui ước rằng : các đỉnh của đồ thị đượcbố trí trên hình vẽ sao cho hướng mũi tên của các cạnh là “hướnglên”.

Như vậy đồ thị định hướng (dạng biểu đồ) tương ứng của tập hợp cĩthứ tự (X,) cĩ thể được rút gọn lại thành một biểu đồ đơn giản hơnnhưng vẫn hàm chứa đầy đủ những thơng tin của thứ tự  trên tậphợp X, bằng cách là ta chỉ vẽ cung nối từ đỉnh x đến đỉnh x" (x" khácx) khi ta cĩ xx", và khơng tồn tại y khác x và x" sao cho xy và y x". Biểu đồ ở dạng rút gọn nầy được gọi làbiểu đồ Hasse của tậphợp cĩ thứ tự (X,). Theo sự trình bày ở trên ta cĩ thể xây dựng mộtthuật tốn để tìm biểu đồ Hasse của một tập hợp (hữu hạn) cĩ thứ tự.

Ví dụ:

1. Xét thứ tự thơng thường trên tập hợp X =1,2,3,4.

Đồ thị đầy đủ của (X, ) cĩ dạng trong hình (a) dưới đây.Hình (b) là dạng rút gọn của đồ thị, tức là biểu đồ Hasse củathứ tự  trên X.

2. Vẽ biểu đồ Hasse biểu diễn thứ tự “chia hết”, được ký hiệu là, trên tập hợp1,2,3,4,6,8,12.

Bắt đầu từ đồ thị định hướng của thứ tự nầy, ta loại bỏ cácvịng tại các đỉnh. Sau đĩ loại bỏ các cạnh cĩ thể được suy rabởi tính chất truyền của thứ tự : (1,4), (1,6), (1,8), (1,12), (2,8),(2,12) và (3,12). Cuối cùng ta được biểu đồ Hasse gồm cáccạnh (1,2), (1,3), (2,4), (2,6), (3,6), (4,8), (4,12), và (6,12) :

3. Vẽ biểu đồ Hasse cho thứ tự trên tập hợp

P

(E), trong đĩ E=a,b,c.

Cũng làm tương tự như trong ví dụ trước ta loại bỏ các cạnhsau đây từ đồ thị biểu diễn cho thứ tự: (,a,b), (,a,c),(,b,c), (,a,b,c), (a,a,b,c), (b,a,b,c), và(c,a,b,c). Từ đĩ ta cĩ biểu đồ Hasse được vẽ như sau :

Ghi chú :

Chúng ta cịn cĩ một cách khác để nêu lên khái niệm biểu đồ
Hasse cho một cấu trúc thứ tự (X,) bằng cách đưa ra một kháiniệm trội trực tiếp: Cho x  X, một phần tử y  X được gọi làmột trội trực tiếp của x nếu và chỉ nếu ta cĩ 2 điều kiện sau đây :

(1) xy (y là một chận trên của x),

(2) Với mọi z, nếu xz và zy thì z = x hay z = y.

Biểu đồ Hasse cho cấu trúc thứ tự (X,) là một đồ thị định hướngcĩ tập hợp đỉnh là X và tập hợp các cạnh là một phần củagồmcác cạnh (a,b) sao cho b là một trội trực tiếp của a.

3.3 Tập hợp hữu hạn cĩ thứ tự.

Trong mục nầy chúng ta sẽ trình bày một số kết quả liên quanđến các tập hợp hữu hạn cĩ thứ tự (hay các cấu trúc thứ tự hữu hạn).Biểu đồ Hasse là một cơng cụ hữu hiệu được dùng trong việc khảosát các thứ tự trên các tập hợp hữu hạn.

Định lý 1.Cho (X,) là một cấu trúc thứ tự hữu hạn. Ta cĩ :1. Trong X cĩ ít nhất một phần tử tối tiểu.

2. Nếu X cĩ một phần tử tối tiểu duy nhất thì phần tử đĩ chínhlà phần tử nhỏ nhất của X.

Chứng minh:

Cho (X,) là một cấu trúc thứ tự hữu hạn (nghĩa là X hữu hạnvàlà một thứ tự trên X). Chọn một phần tử a0 X. Nếu a0khơng phải là một phần tử tối tiểu thì theo định nghĩa củaphần tử tối tiểu ta cĩ một phần tử a1sao cho a1a0và a1a0.

Nếu a1 khơng phải là một phần tử tối tiểu thì ta lại cĩ mộtphần tử a2sao cho a2a1và a2a1. Cứ tiếp tục quá trình nầyđể cho nếu ankhơng tối tiểu thì sẽ cĩ một phần tử an+1sao choan+1anvà an+1an. Do X chỉ cĩ một số hữu hạn phần tử, nênquá trình trên phải dừng đối với một phần tử tối tiểu an. Nhưvậy trong X cĩ ít nhất một phần tử tối tiểu.

Giả sử X cĩ một phần tử tối tiểu duy nhất là m. Cho x là mộtphần tử tùy ý thuộc X. Theo lập luận trên, tồn tại một phần tửtối tiểu ansao cho an x. Vì phần tử tối tiểu là duy nhất nênan = m. Suy ra m  x. Điều nầy chứng tỏ m là phần tử nhỏnhất của X.

Theo dõi chứng minh của định lý trên ta rút ra một thuật tốn để tìmmột phần tử tối tiểu của một cấu trúc hữu hạn.

Thuật tốn 1. Tìm phần tử tối tiểu trong một cấu trúc thứ tựhữu hạn.

Nhập : X là một tập hợp hữu hạn (khác rỗng),là một thứ tự trên X.

Xuất : m là một phần tử tối tiểu trong X.Thuật tốn :1. Chọn một phần tử mX2. for xX doif xm and xm thenmx (gán phần tử x cho biến m), vàtrở lại bước 1.

Nhận xét :

1. Qua chứng minh trên ta thấy rằng với mỗi phần tử x X luơntồn tại một phần tử tối tiểu m sao cho m  x (ở đây là mộtthứ tự trên X).

2. Định lý trên sẽ khơng cịn đúng nếu bỏ đi điều kiện hữu hạncủa tập hợp X. Việc tìm ra một ví dụ cho nhận xét nầy đượcdành cho phần bài tập.

Ví du: Tìm phần tử tối tiểu của tập hợp cĩ thứ tự(2,4,1,5,12,20,).

Aùp dụng thuật tốn trên chúng ta sẽ tìm được phần tử tối tiểucủa cấu trúc thứ tự đã cho là 1.

Tương tự như trên, đối với các phần tử tối đại ta cũng cĩ định lý sauđây:

Định lý 2.

(1) Mọi tập hợp hữ hạn cĩ thứ tự (X,) đều cĩ một phần tử tốiđại. Hơn nữa, với mọi x  X luơn tồn tại một phần tử tốiđại M sao cho xM.

(2) Nếu X cĩ một phần tử tối đại duy nhất thì phần tử đĩ chínhlà phần tử lớn nhất của X.

Việc chứng minh định lý trên và xây đựng thuật tốn để tìm phầntử tối đại được dành cho phần bài tập.

3.4 Sắp xếp topo (topological sorting)

Sắp xếp topo là một vấn đề quan trọng trong việc khảo sát cáccấu trúc thứ tự hữu hạn và phương pháp sắp xếp topo thường được sử

dụng để giải nhiều bài tốn thực tế. Chúng ta thử xem bài tốn đặtra như sau:

Giả sử cĩ một đề tài gồm 20 cơng việc khác nhau. Một số cơng việcchỉ cĩ thể được thực hiện sau khi một số cơng việc khác được thựchiện hồn tất. Chúng ta phải thực hiện các cơng việc theo thứ tự nào?
Để mơ hình cho vấn đề, chúng ta đặt X là tập hợp 20 cơng việc củađề tài; trên X ta xét một thứ tự (hay quan hệ thứ tự) sao cho a bnếu và chỉ nếu a và b là 2 cơng việc trong đĩ cơng việc b chỉ cĩ thểđược bắt đầu khi cơng việc a đã được hồn thành. Muốn cĩ một kếhoạch thực hiện các cơng việc cho đề tài chúng ta phải tìm ra một thứtự cho tất cả 20 cơng việc “tương thích” với thứ tự  nêu trên.

Trước hết chúng ta nêu ra định nghĩa khái niệm “tương thích” nhưsau:

Định nghĩa:Cho (X,) là một tập hợp cĩ thứ tự. Một thứ tự tồnphần trên X được gọi là tương thích với thứ tự nếu và chỉnếu

ab  ab, với mọi a,bX.

Việc xây dựng thứ tự tồn phần tương thích với một thứ tự chotrước được gọi làsắp xếp topo(topological sorting).

Xem thêm: Tổng hợp bản vẽ cửa nhôm xingfa file cad cửa nhôm xingfa chuyên nghiệp

Thuật tốn sắp xếp topo cho một tập hợp hữu hạn cĩ thứ tự dựavào kết quả nêu trong các định lý trên. Để định nghĩa một thứ tự tồnphần trên (X, ), trước hết ta chọn ra một phần tử tối tiểu a1 của X;phần tử nầy tồn tại do định lý 1. Kế đĩ, chú ý rằng Nếu tập hợp X -a1   thì (X -a1,) cũng là một tập hợp hữu hạn (khác rỗng) cĩ

thứ tự. Ta lại chọn ra phần tử tối tiểu a2 trong X -  a1, rồi loại a2khỏi việc xem xét ở bước tiếp theo để chọn phần tử tối tiểu trong X -a1, a2 nếu tập hợp X - a1, a2 khác rỗng. Tiếp tục quá trình nầybằng cách chọn phần tử tối tiểu ak+1trong X -a1, a2, ... , akkhi tậphợp cịn phần tử.

Vì X là một tập hợp hữu hạn nên quá trình chọn trên phải dừng. Cuốicùng ta đã sắp các phần tử của tập hợp X thành một dãy a1, a2, ... , anthỏa điều kiện : với mọi i, j sao cho i GIÁO TRÌNH TOÁN RỜI RẠC PHẦN 2 TS ĐỖ VĂN NHƠN (BIÊN SOẠN) (Trang 47 -61 )


*
*

Bạn đang xem trước 20 trang tài liệu Bài giảng Toán rời rạc - Chương 3: Quan hệ, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
Chương 3QUAN HỆ11. Định nghĩa và tính chất2. Biểu diễn quan hệ
I. Quan hệ23. Quan hệ tương đương. Đồng dư4. Quan hệ thứ tự, biểu đồ Hass1. Định nghĩa3Một quan hệ hai ngôi từ tập A đến tập B là tập con của tích Đề các R ⊆ A x B. Chúng ta sẽ 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 AR = { (a1, b1), (a1, b3), (a3, b3) }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}41. Định nghĩa1. Đị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)}51 2 3 41 2 3 42. 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ảnxạ vì (1,1), (2, 2), (3, 3), (4, 4) ∈ R26 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 > 1Quan hệ“ | ” (“ước số”) trên Z + là phản xạ vì mọi sốnguyên a là ước của chính nó .Chú ý. Quan hệ R trên tập A là phản xạ nếu nó chứa đườngchéo của A × A : 1 2 3 41234∆ = {(a, a); a ∈ A}72. 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ụ. 8 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)(a | b) ∧ (b | a) → (a = b)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ệ“ | ” (“ước số”) trên Z +. không đối xứng
Tuy nhiên nó có tính phản xứng vì92. Các tính chất của Quan hệ1 2 3 412341 2 3 41234***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.2. 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)}10trê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(a ≤ b) ∧ (b ≤ c) → (a ≤ c)(a | b) ∧ (b | c) → (a | c)Tóm lạiR phản xạ : a
RaR đối xứng: a
Rb  b
RaR phản xứng: a
Rb và b
Ra  a=bR bắc cầu: a
Rb và b
Rc  a
Rc11Giới thiệu
Quan hệ tương đương 3. Quan hệ tương đương12Lớp tương đươngĐịnh nghĩa
Ví dụ.Cho S = {sinh viên của lớp}, gọi
R = {(a,b): a có cùng họ với b}Hỏi13Yes
Yes
Yes
Mọi sinh viêncó cùng họ thuộc cùng một nhóm.R phản xạ?
R đối xứng?
R bắc cầu?Đị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 a
Rb3. Quan hệ tương đươngnế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 a
Rb nếu a – b nguyên. Khi đó R là quan hệ tương đương14Ví dụ. Cho m là số nguyên dương và R quan hệ trên Z sao cho a
Rb 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 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 = ka3. Quan hệ tương đươ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à chúng ta viếta ≡ b (mod m) thay vì a
Rb15Lớp tương đươngĐịnh nghĩa. Cho R là quan hệ tương đương trên A và phần tử a ∈ A . Lớp tương đương chứa a được ký hiệu bởi R hoặc là tập16R = {b ∈ A| b R a}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> ={ , – 16, – 8, 0, 8, 16, }17Lớp tương đương8Tương tự <1>8 = {a | a chia 8 dư 1} = { , – 15, – 7, 1, 9, 17, }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 đó18Lớp tương đương(i) a R b nếu R = R(ii) R ≠ R nếu R ∩ 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. Chú ý. Cho {A1, A2, p } 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.19Lớp tương đương
A1 A2 A3A4 A5ab
Ví dụ. Cho m là số nguyên dương, khi đó có m lớp đồng dư modulo m là <0>m , <1>m , , m .Chúng lập thành phân họach của Z thành các tập conrời nhau. Chú ý rằng<0>m = m = <2m>m = p20<1>m = m = <2m +1>m = ppppppppppppppm = <2m – 1>m = <3m – 1>m = p
Mỗi lớp tương đương này được gọi là số nguyên modulo m.Tập hợp các số nguyên modulo m được ký hiệu bởi Zm
Zm = {<0>m , <1>m , p, m}4. Quan hệ thứ tự. Biểu đồ Hasse21Giới thiệu
Biểu đồ Hasse
Phần tử tối tiểu, tối đại
Chặn trên nhỏ nhất, chặn dưới lớn nhấtĐịnh nghĩa
Ví dụ. Cho R là quan hệ trên tập số thực:a R b nếu a ≤ b
Hỏi:R phản xạ không?22Có
CóKhông R phản xứng không?R đối xứng không?R bắc cầu không? CóĐịnh nghĩa. Quan hệ R trên tập A là quan hệ thứ tự (thứ tự) nếu nó có tính chất phản xạ, phản xứng và bắc cầu. p
Cặp (A, ) đựợc gọi là tập sắp thứ tự hay poset
Người ta thường ký hiệu quan hệ thứ tự bởi p23Định nghĩa
Phản xạ: a ap
Phản xứng: (a b) ∧ (b a) → (a = b)ppp
Bắc cầu: (a b) ∧ (b c) → (a c)pp
Ví dụ. Quan hệ ước số “ | ”trên tập số nguyên dương là quan hệ thứ tự, nghĩa là (Z+, | ) là poset
Phản xạ? Có, x | x vì x = 1 ⋅ x24Định nghĩa
Bắc cầu? Có?a | b nghĩa là b = ka, b | c nghĩa là c = jb. Khi đó c = j(ka) = jka: a | c
Phản xứng?a | b nghĩa là b = ka, b | a nghĩa là a = jb. Khi đó a = jkacó?25Suy ra j = k = 1, nghĩa là a = b Ví dụ. (Z, | ) là poset?
Phản xứng?
Không3|-3, và -3|3, nhưng 3 ≠ -3.Không phải(P(S), ⊆ ), ở đây P(S) là tập hợp các con của S, là một poset?
Có, A ⊆A, ∀A∈ P(S)Phản xạ?
Bắc cầu? A ⊆ B, B ⊆ C. Suy ra A ⊆ C?
CóCó, là poset.26Phản xứng? A ⊆ B, B ⊆A. Suy ra A =B?
CóĐịnh nghĩa. Các phần tử a và b của poset (S, ) gọi là so sánh được nếu a b hay b a . pp pp
Cho (S, ), nếu hai phần tử tùy ý của S đều so sánh được với nhau thì ta gọi nó là tập sắp thứ tự toàn phần
Trái lại thì ta nói a và b không so sánh được.27Định nghĩa.Ta cũng nói rằng là thứ tự toàn phần hay thứ tư tuyến tínhtrên Sp
Ví dụ. Quan hệ “≤ ” trên tập số nguyên dương là thứ tự toàn phần. Ví dụ. Quan hệ ước số “ | ”trên tập hợp số nguyên dương không là thứ tự toàn phần, vì các số 5 và 7 là không so sánh được.Ví dụ28Biểu đồ Hasse
Mỗi poset có thể biễu diễn bởi đồ thị đặc biệt ta gọilà biểu đồ Hasse Để định nghĩa biểu đồ Hasse chúng ta cần các khái niệm phần tử trội và trội trực tiếp. Định nghĩa. Phần tử b trong poset (S, ) được gọi là 29Chúng ta cũng nói rằng a là được trội bởi b . Phần tử bđược gọi là trội trực tiếp của a nếu b là trội của a, và không tồn tại trội c sao chophần tử trội của phần tử a trong S nếu a bppbcabca ≠≠,pp
Biểu đồ Hasse Ta định nghĩa Biểu đồ Hasse của poset (S, ) là đồ thị:Mỗi phần tử của S được biễu diễn bởi một điểm trên mặt phẳng .p Nếu b là trội trực tiếp của a thì vẽ một cung đi từ 30abcdecadba ppp ,a đến b .Biểu đồ Hasse
Ví dụ. Biểu đồ Hasse của poset ({1,2,3,4}, ≤) có thể vẽ như sau431Chú ý . Chúng ta không vẽmũi tên với qui ước mỗi cung đều đi từ dưới lên trên321Ví dụ. Biểu đồ Hasse của P({a,b,c}){a,b,c}{a,b} {a,c} {b,c}32{a} {b} {c}∅Phần tử tối đại và phần tử tối tiểu.Xét poset có biểu đồ Hasse như dưới đây: Mỗi đỉnh màu đỏ là tối đại. Không có cung nào xuất phát từ điểm tối đại.  Không có cung nào kết thúc ở điểm tối tiểu. Mỗi đỉnh màu xanh là tối tiểu.33Chú ý. Trong một poset S hữu hạn, phần tử tối đại và phần tử tối tiểu luôn luôn tồn tại. Thật vậy, chúng ta xuất phát từ điêm bất kỳ a0 ∈ S. Phần tử tối đại tìm được bằng phương pháp tương tự.Nếu a0 không tối tiểu, khi đó tồn tại a1 a0, tiếp tục như vậy cho đến khi tìm được phần tử tối tiểu .p34a0a1a2Ví dụ. Tìm phần tử tối đại, tối tiểu của poset ({2, 4, 5, 10, 12, 20, 25}, | ) ?
Giải. Từ biểu đồ Hasse, chúng ta thấy rằng 12, 20, 25 là các phần tử tối đại, còn 2, 5 là các phần tử tối tiểu
Như vậy phần tử tối đại, tối tiểu của poset có thể không duy nhất.352412 2010525Chặn trên, chặn dướiĐịnh nghĩa. Cho (S, ) là poset và A ⊆ S . Phần tử chặn trên của A là phần tử x ∈ S (có thể thuộc A hoặc không) sao cho ∀ a ∈ A, a x.pp
Phần tử chặn dưới của A là phần tử x ∈ S sao cho∀ a ∈ A, x ap36Ví dụ. Phần tử chận trên của {g,j} là a. a bdjfihecg
Tại sao không phải là b?Định nghĩa. Cho (S, ) là poset và A ⊆ S. Chặn trên nhỏ nhất của A là phần tử chặn trên x của A sao cho mọi chặn trên y của A, ta đều có y xpf
Chặn dưới lớn nhất của A là phần tử chặn dưới x37Chặn trên, chặn dướicủa A sao cho mọi chặn dưới y của A, ta cóy xp
Chặn trên nhỏ nhất của : sup
AChặn dưới lớn nhất: inf
Aa bdc
Ví dụ. Chặn dưới chung lớn nhất của {a,b} là gì?
Ví dụ Chặn trên nhỏ nhất của {i,j} là d
Chặn trên, chặn dướijfiheg38a b
Chặn trên nhỏ nhất (nếu có) của A = {a, b} đựơc kýhiệu bởi a ∨ b
Chặn dưới lớn nhất (nếu có) của A = {a, b} đựoc ký hiệu bởi a ∧ b39Chặn trên, chặn dướidjfihecg
Ví dụ. b ∧ c = f
Ví dụ. i ∨ j = d