Chương III: Quan hệ

Chia sẻ: Lê Tẹt | Ngày: | Loại File: PPT | Số trang:18

Thêm vào BST

Báo xấu

152
lượt xem 44
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Đị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ủ đề:

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

Lưu

Nội dung Text: Chương III: Quan hệ

1
Đị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. 2 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 3 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. 4 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. 5 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. 6 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 7 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: 1. Phản xạ: ∀(a,b) ∈ A x B thì ta có (a,b) ≺ vì a = a và b ≤ ’ b. 2. 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 8 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. 9 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,
 Đị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. a e c b d 11 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ó. 2 1 8 5 7 15 30 12 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ứ 13 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. 14 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: 15  Không có cung nàoxuấ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. 2 1 8 5 15 7 16 30 Chương IV: Quan hệ
 Sẽ thêm vào sau. 17
18