Chương IV Quan hệ

* Định nghĩa: Một quan hệ hai ngôi R trên tập một tập A (khác rỗng) được gọi là một quan hệ thứ tự nếu và chỉ nếu có ba tính chất: phản xạ, phản xứng và truyền ( bắc cầu ). Ta kí hiệu quan hệ thứ tự là: ≺ Cặp (A, ≺) được gọi là tập sắp thứ tự hay poset. * Chương IV: Quan hệ Vd1: Với 2 số a và b trên tập N* ta nói a b có quan hệ lũy thừa (“^”) nếu tồn tại một số nguyên dương k sao cho a mũ k bằng b. Khi đó (N*, ^ ) là tập sắp thứ tự vì quan hệ “ ^ “ có tính: Phản xạ: aN* ta có, a^a vì a=a1 Phản xứng: a^b nghĩa là  k sao cho ak =b. b^a nghĩa là  j sao cho bj =a (k, j nguyên) Khi đó, ta có ak = b  akj =bj akj = a  k=1 và j=1  a = b Bắc cầu: a^b nghĩa là  k sao cho ak = b b^c nghĩa là  j sao cho bj = c Khi đó, akj = c tức là a^c * Chương IV: Quan hệ Vd2: Với 2 số a và b trên tập R*+ ta nói a và b có quan hệ R nếu phương trình: ax = b có nghiệm. Khi đó, (R*+ , R ) không là tập sắp thứ tự vì quan hệ R không có tính phản xứng. Vì: Phương trình: 2x =3 có nghiệm và phương trình 3x =2 có nghiệm, nhưng 2  3. * Chương IV: Quan hệ Cho (S,≺) là tập sắp thứ tự. Khi đó, với 2 phần tử a và b thuộc S. Nếu a ≺ b hoặc b ≺ a thì a và b được gọi là so sánh được. Ngược lại, ta nói a và b không so sánh được. Cho (S,≺) là 1 tập sắp thứ tự và với mỗi hai phần tử a và b tùy ý thuộc S ta đều có a và b so sánh được thì ta nói đó là tập sắp thứ tự toàn phần. Ta cũng nói rằng ≺ là thứ tự toàn phần hay thứ tự tuyến tính. Ngược lại, nếu tồn tại 2 phần tử a và b thuộc S sao cho a và b không so sánh được thì ta nói (S,≺) là tập sắp thứ tự bán toàn phần và ≺ là quan hệ bán toàn phần. * Chương IV: Quan hệ Vd: Quan hệ (N*,^) là tập sắp thứ tự bán toàn phần vì: Nó là 1 tập sắp thứ tự. Không tồn tại 2^3 hay 3^2. * Chương IV: Quan hệ Vd: Quan hệ “  ” trên tập số nguyên dương là thứ tự toàn phần. Cho (R , ) là tập sắp thứ tự vì quan hệ “ “ có tính: Phản xạ: aR ta có, a  a. Phản xứng: a  b và b  a  a = b. Bắc cầu: a  b và b  c thì a  c. Ta có quan hệ “  ” là một quan hệ thứ tự toàn phần vì  a  b thì ta có b  a (b=a). * Chương IV: Quan hệ Định nghĩa: Cho (A, ) và (B, ’) là hai tập sắp thứ tự toàn phần. Ta định nghĩa thứ tự ≺ trên A x B như sau: (a1,b1) ≺ (a2,b2) nếu a1 < a2 hay (a1 = a2 và b1 ’ b2 ). Ta thấy đây là thứ tự toàn phần trên A x B vì nó có tính: Phản xạ: (a,b)  A x B thì ta có (a,b) ≺ vì a = a và b ’ b. Phản xứng: Nếu (a1,b1) ≺ (a2,b2)(1) và (a2,b2) ≺ (a1,b1)(2) thì ta có: nếu a1  a2 thì (1)  a1 < a2 và (2)  a2 < a1 (Vô lý) Vậy a1 = a2. Tương tự, ta có b1 = b2 Vậy, ta có: (a1,b1) = (a2,b2) * Chương IV: Quan hệ 3. Bắc cầu: Nếu (a1,b1) ≺ (a2,b2)(1) và (a2,b2) ≺ (a3,b3)(2) thì ta có a1  a2 và a2  a3  a1  a3 Nếu a1 < a3 thì ta đã có (a1,b1) ≺ (a3,b3) Nếu a1 = a3 thì chứng minh tương tự ta sẽ có b1 ’ b3 Vây ta luôn có (a1,b1) ≺ (a3,b3) . Quan hệ thứ tự toàn phần ≺ này được gọi là thứ tự tự điển. * Chương IV: Quan hệ Phần tử trội: Phần tử b trong tập sắp thứ tự S được gọi là phần tử trội của phần tử a trong tập S nếu a ≺ b. Chú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 của a sao cho: a ≺ c ≺ b, a  b  c. Vd: Với tập sắp thứ tự (N, <) thì ta có: 5 là phần tử trội của 2 vì 2 < 5. 3 là phần tử trội trực tiếp của 2 vì không tồn tại số c  N sao cho 2 < c < 3 (2  c  3). 4 là phần tử trội nhưng không trội trực tiếp của 2 vì tồn tại phần tử c = 3 mà 2 < c < 4. * Chương IV: Quan hệ Định nghĩa: Biểu đồ Hasse của tập sắp thứ tự (S, ≺) là một đồ thị có hướng mà: Mỗi phần tử của S được biểu diễn bằng một điểm trên mặt phẳng. Nếu b là trội trực tiếp của a thì vẽ một cung đi từ a đến b. Vd: Cho (S, ≺) là một tập sắp thứ tự với S = {a, b, c, d, e} a ≺ b, a ≺ c, b ≺ c, b ≺ d. b d e a c * Chương IV: Quan hệ Vd: Cho tập sắp thứ tự ({1, 2, 5, 7, 8, 15, 30}, “|”). Hãy vẽ biểu đồ Hasse của nó. 1 2 5 7 8 15 30 * Chương IV: Quan hệ Định nghĩa: Trong một tập sắp thứ tự (S, ≺), một phần tử a  S được gọi là: Cực tiểu nếu: x  S ta đều có a ≺ x. Cực đại nếu: x  S ta đều có x ≺ a. Kí hiệu: Phần tử cực tiểu: a = min(S, ≺). Phần tử cực đại: b = max(S, ≺). Nhận xét: Trong một tập sắp thứ tự có thể không có phần tử cực đại và cực tiểu. Nếu tồn tại phần tử cực đại và cực tiểu thì chúng là duy nhất. Nếu tập sắp thứ tự (S, ≺) có |S| hữu hạn và ≺ là quan hệ thứ tự toàn phần thì (S, ≺) luôn có phần tử cực đại và phần tử cực tiểu. * Chương IV: Quan hệ Vd: Cho tập sắp thứ tự (S, “”) với S = [5, 10] (S  R). Khi đó ta có: Min(S, “”) = 5. Max(S, “”) = 10. Tập sắp thứ tự (S, “|”) với S = {3, 4, 5, 6, 7} không có phần tử cực đại và phần tử cực tiểu. Tập sắp thứ tự (S, “^”) với S = {2, 4, 16, 256, 4096} có: Min (S, “^”) = 2. Không có phần tử cực đại. * Chương IV: Quan hệ Định nghĩa: Một phần tử a trong tập sắp thứ tự (S, ≺) được gọi là: Tối tiểu nếu không tồn tại bất kì phần tử a’  S (a’  a) mà a’ ≺ a. Tối đại nếu không tồn tại bất kì phần tử a’  S (a’  a) mà a ≺ a’. Nhận xét: Trong một tập sắp thứ tự thì luôn luôn tồn tại phần tử tối tiểu và tối đại, nhưng chúng có thể không là duy nhất. Trong biểu đồ Hasse: Không có cung nào xuất phát từ phần tử tối đại. Không có cung nào kết thúc tại phần tử tối tiểu. * Chương IV: Quan hệ Vd: Cho tập sắp thứ tự ({1, 2, 5, 7, 8, 15, 30}, “|”}. Hãy tìm các phần tử tối đại và tối tiểu của nó. Phần tử tối đại (màu đỏ) : 7, 8, 30. Phần tử tối tiểu (màu xanh) : 1, 5, 7. 1 2 5 7 8 15 30 * Chương IV: Quan hệ Sẽ thêm vào sau. * *