Bài Giảng Toán Rời Rạc: Chương 2 - Quan Hệ

Trang chủ Tìm kiếm Trang chủ Tìm kiếm Bài giảng Toán rời rạc: Chương 2 - Quan hệ pdf 9 258 KB 6 264 4.7 ( 19 lượt) Xem tài liệu Nhấn vào bên dưới để tải tài liệu Tải về Đang chuẩn bị: 60 Bắt đầu tải xuống Để tải xuống xem đầy đủ hãy nhấn vào bên trên Chủ đề liên quan Toán rời rạc bài giảng toán rời rạc Bài giảng Quan hệ Quan hệ hai ngôi Ma trận biểu diễn quan hệ hai ngôi Tính chất của quan hệ hai ngôi

Nội dung

13/04/2010 1. Định nghĩa và ký hiệu Chương II Cho tập hợp X ≠ ∅. Một quan hệ hai ngôi trên X là một tập hợp con ℜ của X2. Nếu (x,y)∈ℜ, (x y)∈ℜ ta QUAN HỆ Ệ viết xℜy. Nếu (x,y)∉ℜ,ta viết xℜ y . Ví dụ 1: Cho X = {1, {1 2, 2 3, 3 4} và ℜ = {(1,1), {(1 1) (1,3), (1 3) (2, (2 1), 1) (3,1)}. Ta thấy ℜ là một quan hệ trên X và 1ℜ1, 1ℜ3, 2ℜ1, 3ℜ1 nhưng 1ℜ2 , 2ℜ2, 2ℜ3 ... 13/04/2010 1. Định nghĩa và ký hiệu 1. Định nghĩa và ký hiệu Ví dụ 2: Ví dụ 3: Quan hệ có cùng trị tuyệt đối trên tập hợp các số thực R là một quan hệ hai ngôi ℜ trên tập hợp R: ∀x, y ∈ R, xℜy ⇔ |x| = |y| Quan hệ nhỏ hơn hay bằng trên tập các số hữu tỉ Q là một quan hệ hai ngôi trên Q: ∀x, y ∈ Q, x ℜ y ⇔ x ≤ y 13/04/2010 2 3 13/04/2010 4 1 13/04/2010 1. Định nghĩa và ký hiệu 2. Ma trận biểu diễn quan hệ hai ngôi Ví dụ 4: Cho tập hợp hữu hạn X = {x1, x2, ..., xn}. Khi Cho trước một ộ số nguyên g y dươngg n,, ta định ị nghĩa g một ộ quan hệ hai ngôi trên Z như sau: đó mỗi quan hệ hai ngôi ℜ trên X có thể được đó, biểu diễn bởi một ma trận vuông cấp n, ký hiệu ∀x, y ∈ Z, xℜy ⇔ x – y chia hết cho n. Quan hệ này được gọi là quan hệ đồng dư modulo n. Nếu xℜy ta viết: là M(ℜ), trong đó: ⎪⎩ Chẳng hạn, với n = 7 ta có 9 ≡ 2 (mod 7) và 3 ≡ 10 (mod 7) nhưng 3 ≅ 6 (mod 7). 13/04/2010 5 i j i j 13/04/2010 6 Cho ℜ là một quan hệ hai ngôi trên X. Ví dụ: Xét X = {{1,, 2,, 3,, 4}} và qquan hệệ hai ngôi g ℜ như trong Ví dụ 1 ở trên. Ma trận biểu diễn của ℜ là: 13/04/2010 x ℜx x ℜx 3. Tính chất của quan hệ hai ngôi 2. Ma trận biểu diễn quan hệ hai ngôi ⎛1 ⎜ 1 M (ℜ) = ⎜ ⎜1 ⎜ ⎝0 ⎧⎪1 M(ℜ) = rij với r ij = ⎨0 x ≡ y ((mod n)) 3.1. Tính phản xạ: Ta nói quan hệ hai ngôi ℜ có tính phản xạ nếu với mọi x ∈ X, x luôn luôn có quan hệ ℜ với x. Như vậy: ℜ pphản xạ ⇔ ∀x ∈ X, xℜx Suy ra: ℜ không phản xạ ⇔ ∃x ∈ X, x ℜx 0 1 0⎞ ⎟ 0 0 0⎟ 0 0 0⎟ ⎟ 0 0 0⎠ 7 13/04/2010 8 2 13/04/2010 3. Tính chất của quan hệ hai ngôi 3. Tính chất của quan hệ hai ngôi 3.1. Tính phản xạ: • Nếu X hữu hạn thì ℜ phản xạ khi và chỉ khi ma trận biểu ể diễn ễ M(ℜ) có các hệ sốố trên đường chéo đều là 1. 3.1. Tính phản xạ: • Gọi ọ ΔX là đườngg chéo chính của X2: ΔX = {(x, x) | x ∈ X} Khi ấy quan hệ ℜ trên X là phản xạ khi và chỉ khi ℜ ⊃ ΔX. 1 2 3 4 13/04/2010 1 2 3 4 9 3. Tính chất của quan hệ hai ngôi 10 3. Tính chất của quan hệ hai ngôi 3.2. Tính đối xứng: • Quan hệ ℜ trên A là đối xứng khi và chỉ khi nó đối ố xứng nhau qua đường chéo Δ của A × A. Cho ℜ là một quan hệ hai ngôi trên X. 3.2. Tính đối xứng: Ta nói quan hệ hai ngôi ℜ có tính đối xứng khi với mọi x, y ∈ X, nếu x có quan hệ ℜ với y thì y cũng có quan hệ ℜ với x. Như vậy: ℜ đối xứngg ⇔ ((∀x, y ∈ X, xℜyy ⇒ yyℜx). ) Suy ra: ℜ không đối xứng ⇔ (∃x,y∈X, xℜy và yℜx) 13/04/2010 13/04/2010 1 2 3 4 11 13/04/2010 1 2 3 4 12 3 13/04/2010 3. Tính chất của quan hệ hai ngôi 3. Tính chất của quan hệ hai ngôi 3.2. Tính đối xứng: • Nếu X hữu hạn thì ℜ đối xứng khi và chỉ khi ma trận biểu ể diễn ễ M(ℜ) là một ma trận đối ố xứng. Ví dụ Quan hệ ℜ1 = {(1,1), (1,2), (2,1)} trên tập A={1 2 3 4} là đối xứng. A={1,2,3,4} xứng Cho ℜ là một quan hệ hai ngôi trên X. 3.3. Tính phản đối xứng: Ta nói quan hệ hai ngôi ℜ có tính phản đối xứng nếu đối với hai phần tử khác nhau bất kỳ x, y ∈ X không thể xảy ra đồng thời x có quan hệ ℜ với y và y có quan hệ ℜ với x. Như vậy: ℜ phản đối xứng ⇔ (∀x, y ∈ X, x ≠ y và xℜy ⇒ y ℜ x) ⇔ (∀x, y ∈ X, x ℜ y và yℜx ⇒ x = y). Suy ra: R không phản đối xứng ⇔ (∃x, y ∈ X, x ≠ y và xℜy và yℜx). 13/04/2010 13 3. Tính chất của quan hệ hai ngôi 3.3. Tính phản đối xứng: • Với X hữu hạn thì ℜ phản đối xứng khi và chỉ khi ma trận biểu ể diễn ễ M(ℜ) = (rij) thỏa: ∀1 ≤ i ≠ j ≤ n, rji = 1 ⇒ rij = 0. Ví dụ: Quan hệ ≤ trên Z phản xứng vì: (a ≤ b) ∧ (b ≤ a) → (a = b) 1 2 3 13/04/2010 1 2 3 14 3. Tính chất của quan hệ hai ngôi 3.3. Tính phản đối xứng: • Quan hệ ℜ là phản xứng khi và chỉ khi chỉ có các phần ầ tử nằm ằ trên đường chéo là đối ố xứng qua Δ của A × A. 4 13/04/2010 4 15 13/04/2010 16 4 13/04/2010 3. Tính chất của quan hệ hai ngôi 3. Tính chất của quan hệ hai ngôi 3.4. Tính bắc cầu: Ví dụ •Quan hệ ℜ ={(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. Cho ℜ là một quan hệ hai ngôi trên X. 3.4. Tính bắc cầu: Ta nói quan hệ hai ngôi ℜ có tính bắc cầu khi đối với các phần tử bất kỳ x, y, z ∈ X, nếu x có quan hệ ℜ với y và y có quan hệ ℜ với z thì x cũng có quan hệ ℜ với z. Như vậy: R bắc cầu ⇔ (∀x, (∀x y, y z ∈ X, X xℜy và yℜz ⇒ xℜz) Suy ra: R không bắc cầu ⇔ (∃x,y,z ∈ X, xℜy và yℜz và xℜ z). 13/04/2010 • Quan hệ ≤ và “|”trên Z có tính bắc cầu ( ≤ b) ∧ (b ≤ c)) → (a (a ( ≤ c)) (a | b) ∧ (b | c) → (a | c) 17 4. Quan hệ tương đương 18 4. Quan hệ tương đương 4.1. Định nghĩa: 4.2. Định nghĩa: Giả sử ℜ là một quan hệ tương đương trên X và x ∈ X. Khi ấy ấ lớp tương đương chứa x, ký hiệu bởi x hay [x], là tập hợp gồm tất cả các phần tử y của X có quan hệ ℜ với x. Như vậy: x = {y ∈ X | yℜx} Một quan hệ ℜ trên tập hợp X được gọi là một quan hệ tương đương nếu ℜ thỏa các tính chất phản xạ, xạ đối xứng và bắc cầu. cầu Ví dụ: 1) Quan hệ bằng nhau trên một tập hợp X ≠ ∅ bất kỳ là một quan hệ tương đương X. 2) Quan hệ nhỏ hơn hay bằng thông thường trên các tập hợp số không phải là một quan hệ tương đương. 3) Quan hệ “tương đương logic” trên tập hợp các dạng mệnh đềề là một quan hệ tương đương. 4) Quan hệ đồng dư modulo n (n nguyên dương) là một quan hệ tương đương trên Z. 13/04/2010 13/04/2010 19 13/04/2010 20 5 13/04/2010 4. Quan hệ tương đương 5. Quan hệ thứ tự 4.3. Định lý: Giả sử ℜ là một quan hệ tương đương trên X. Khi đó: •∀x ∈ X, x ∈ x . •∀x, y ∈ X, xℜy ⇔ x = y •∀x, y ∈ X, x ∩ y ≠ ∅ ⇔ x = y 13/04/2010 5.1. Định nghĩa: Một quan hệ ℜ trên tập hợp X được gọi là một quan hệ thứ tự nếu ℜ thỏa các tính chất phản xạ, xạ phản xứng và bắc cầu. cầu Khi ấy ta nói X là một tập hợp sắp thứ tự (hay có thứ tự). Ví dụ: 1) Quan hệ nhỏ hơn hay bằng thông thường trên các tập hợp số là một quan hệ thứ tự. 2) Cho tập hợp E ≠ ∅. Trên tập hợp P(E) ta có quan hệ: ∀A, B ∈ P(E), A ℜ B ⇔ A ⊆ B 3) Trên tập N các số tự nhiên ta định nghĩa quan hệ ước số: xℜy ⇔ x|y. Quan hệ thứ tự trên vẫn được ký hiệu bởi x|y. 21 5. Quan hệ thứ tự 5.2. Định nghĩa: Một quan hệ thứ tự ≺ trên X được gọi là toàn phần nếu hai phần tử bất kỳ đều so sánh được với nhau, nhau nghĩa là: ∀x, y ∈ X, x ≺ y hay y≺ x. Trong trường hợp ngược lại, ta nói ≺ là một quan hệ thứ tự bộ phận. Nói cách khác, quan hệ thứ tự ≺ là bộ phận nếu tồn tại hai phần tử không so sánh được với nhau, nghĩa là: ∃x, y ∈ X, x ≺ y và y≺ x. Ví dụ: d 1) N, Z, Q, R với thứ tự ≤ thông thường là những tập hợp sắp thứ tự toàn phần. 2) (P(E), ⊆) là tập được sắp thứ tự bộ phận nếu E có ít nhất 2 phần tử. 13/04/2010 23 13/04/2010 22 5. Quan hệ thứ tự 5.3. Định nghĩa: Xét một ộ tập ập hợp ợp có thứ tự ự ((X,, ≺ ) và x,, y là 2 phần tử bất kỳ của X. Khi đó ta nói: 1) y là trội x hay x được trội bởi y nếu x ≺ y. 2) y là trội trực tiếp của x nếu y ≠ x, x y trội x và không tồn tại một trội z của x sao cho x ≺ z ≺ y. 13/04/2010 24 6 13/04/2010 5. Quan hệ thứ tự 5. Quan hệ thứ tự 5.4. Định nghĩa: Biểu đồ Hasse của một tập hợp hữu hạn có thứ tự (X, ≺ ) bao gồm: ồ 1) Một tập hợp các điểm trong mặt phẳng tương ứng 1 – 1 với X, gọi là các đỉnh. 2) Một tập hợp các cung có hướng nối một số đỉnh: hai đỉnh x, x y được nối lại bởi một cung có hướng từ x tới y nếu y là trội trực tiếp của x. 13/04/2010 5.4. Định nghĩa: Ví dụ: 1) Biểu đồ Hasse của U12 = {x ∈ N | x|n} với quan hệ “ | ” được cho bởi: 25 5. Quan hệ thứ tự 26 5. Quan hệ thứ tự 5.4. Định nghĩa: Ví dụ: 2) Với E = {a, b, c} thì biểu đồ Hasse của (P(E), ⊆) có dạng: 13/04/2010 13/04/2010 5.4. Định nghĩa: Ví dụ: 3) Biểu đồ Hasse của {1, 2, 3, 4, 5} với thứ tự thông thường có dạng của một dây chuyền: 27 13/04/2010 28 7 13/04/2010 5. Quan hệ thứ tự 5. Quan hệ thứ tự 5.5. Định nghĩa: Xét (X, ≺ ) là một tập được sắp và a, b ∈ X. Ta nói: 5.5. Định nghĩa: 1) a là phần tử nhỏ nhất (tương ứng phần tử lớn nhất) X, nếu b là không là trội thực sự của (tương ứng không của X, ký hiệu bởi min X (tương ứng, bởi max X), nếu được trội thực sự bởi) phần tử nào của X. Như vậy: a nhỏ hơn hay bằng (tương ứng, lớn hơn hay bằng) mọi b là phần tử tối tiểu của X ⇔ (∀x ∈ X, x≺ b ⇒ x = b); 2) b là phần tử tối tiểu (tương ứng, phần tử tối đại) của phần tử trong X. Như vậy: b là phần tử tối đại của X ⇔ (∀x ∈ X, b ≺ x ⇒ x = b). a = min X ⇔ ∀x ∈ X, a ≺ x; a = max X ⇔ ∀x ∈ X, x ≺ a. 13/04/2010 29 5. Quan hệ thứ tự 13/04/2010 30 5. Quan hệ thứ tự 5.5. Định nghĩa: 5.6. Định lý: Chú ý: Nếu (X, ≺ ) là một tập được sắp thứ tự toàn phần Trongg một ộ tập ập hợp ợp sắpp thứ tự ự X,, pphần tử nhỏ thì khái niệm tối tiểu trùng với khái niệm nhỏ nhất, và nhất a = min X, nếu tồn tại, là phần tử tối tiểu khái niệm tối đại trùng với khái niệm lớn nhất. duy nhất. Suy ra a cũng là phần tử nhỏ nhất duy nhất. Kết luận tương tự cho phần tử lớn nhất và phần tử tối đại. 13/04/2010 31 13/04/2010 32 8 13/04/2010 5. Quan hệ thứ tự 5. Quan hệ thứ tự 5.7. Định lý: 5.8. Thứ tự tự điển: Cho (A,≺ ) là một tập hữu hạn, khác rỗng, có thứ tự toàn phần, ầ gọi là tập mẫu ẫ tự. Gọi S là tập hợp tất cả các chuỗi kí tự có dạng s = a1a2 ... an với n ∈ N và a1, a2, ..., an ∈ A (với n = 0 ta có chuỗi rỗng ∅ không có ký tự nào). Trong S ta qui ước: với s = a1a2 ... an và t = b1b2 ... bm: s = t ⇔ (n = m và ai = bi, i = 1, n ) Trên S ta định nghĩa quan hệ ≺ như sau: Trongg một ộ tập ập hợp ợp sắpp thứ tự ự hữu hạn ạ ta có: 1) Mọi phần tử trội (tương ứng, được trội bởi) một phần tử tối tiểu (tương ứng, tối đại). 2) Nếu a là phần tử tối tiểu (tương ứng, ứng tối đại) duy nhất của X thì a là phần tử nhỏ nhất (tương ứng, phần tử lớn nhất). 13/04/2010 33 13/04/2010 34 5. Quan hệ thứ tự 5.8. Thứ tự tự điển: 1)) ∀s ∈ S , ∅ ≺ s;; 2) ∀s, t ∈ S , s = a1a2 ... an và t = b1b2 ... bm ⎡ n ≤ m, ai = bi , i = 1, n; s≺t ⇔⎢ ∃ ≤ k min{ n , m}, a1 = b1 ,..., ak −1 = bk −1 , ak < bk ⎣ Khi đó ≺ là quan hệ thứ tự toàn phần trên S. S Ta gọi đây là thứ tự tự điển trên S ứng với tập mẫu tự (A, ≺). 13/04/2010 35 9 This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.

Tìm kiếm

Chủ đề

Hóa học 11 Tài chính hành vi Thực hành Excel Atlat Địa lí Việt Nam Đơn xin việc Mẫu sơ yếu lý lịch Trắc nghiệm Sinh 12 Bài tiểu luận mẫu Đồ án tốt nghiệp Đề thi mẫu TOEIC Lý thuyết Dow Giải phẫu sinh lý adblock ​ Bạn đang sử dụng trình chặn quảng cáo?

Nếu không có thu nhập từ quảng cáo, chúng tôi không thể tiếp tục tài trợ cho việc tạo nội dung cho bạn.

Tôi hiểu và đã tắt chặn quảng cáo cho trang web này