zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Khoa Học Tự Nhiên

Bài giảng Toán rời rạc: Chương 2 - Quan hệ

Chia sẻ: Lavie Lavie | Ngày: | Loại File: PDF | Số trang:9

Báo xấu

152
lượt xem 8
download

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

Bài giảng Toán rời rạc: Chương 2 - Quan hệ được biên soạn nhằm trang bị cho các bạn những kiến thức về định nghĩa và ký hiệu; ma trận biểu diễn quan hệ hai ngôi; tính chất của quan hệ hai ngôi; quan hệ tương đương; quan hệ thứ tự.

Chủ đề:

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

Lưu

Nội dung Text: Bài giảng Toán rời rạc: Chương 2 - Quan hệ

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, 3 4} và ℜ = {(1,1), 2 3, {(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 2 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ố Quan hệ nhỏ hơn hay bằng trên tập các số hữu tỉ thực R là một quan hệ hai ngôi ℜ trên tập hợp Q là một quan hệ hai ngôi trên Q: R: ∀x, y ∈ Q, x ℜ y ⇔ x ≤ y ∀x, y ∈ R, xℜy ⇔ |x| = |y| 13/04/2010 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 ộ đó mỗi quan hệ hai ngôi ℜ trên X có thể được đó, quan hệ hai ngôi trên Z như sau: ∀x, y ∈ Z, xℜy ⇔ x – y chia hết cho n. biểu diễn bởi một ma trận vuông cấp n, ký hiệu Quan hệ này được gọi là quan hệ đồng dư modulo n. là M(ℜ), trong đó: Nếu xℜy ta viết: ⎧⎪1 x ℜx i j x ≡ y ((mod n)) M(ℜ) = rij với r ij = ⎨0 Chẳng hạn, với n = 7 ta có 9 ≡ 2 (mod 7) và 3 ≡ 10 ⎪⎩ x ℜx i j (mod 7) nhưng 3 ≅ 6 (mod 7). 13/04/2010 5 13/04/2010 6 2. Ma trận biểu diễn quan hệ hai ngôi 3. Tính chất của quan hệ hai ngôi Ví dụ: Cho ℜ là một quan hệ hai ngôi trên X. g ℜ như Xét X = {{1,, 2,, 3,, 4}} và qquan hệệ hai ngôi 3.1. Tính phản xạ: trong Ví dụ 1 ở trên. Ma trận biểu diễn của ℜ là: Ta nói quan hệ hai ngôi ℜ có tính phản xạ nếu ⎛1 0 1 0⎞ với mọi x ∈ X, x luôn luôn có quan hệ ℜ với x. ⎜ 1 ⎟ 0 0 0⎟ Như vậy: M (ℜ) = ⎜ ⎜1 0 0 0⎟ ℜ pphản xạ ⇔ ∀x ∈ X, xℜx ⎜ ⎟ ⎝0 0 0 0⎠ Suy ra: ℜ không phản xạ ⇔ ∃x ∈ X, x ℜx 13/04/2010 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ạ: 3.1. Tính phản xạ: ọ ΔX là đườngg chéo chính của X2: • Gọi • 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 ΔX = {(x, x) | x ∈ X} đường chéo đều là 1. Khi ấy quan hệ ℜ trên X là phản xạ khi và chỉ khi ℜ ⊃ ΔX. 1 2 3 4 1 2 3 4 13/04/2010 9 13/04/2010 10 3. Tính chất của quan hệ hai ngôi 3. Tính chất của quan hệ hai ngôi Cho ℜ là một quan hệ hai ngôi trên X. 3.2. Tính đối xứng: • Quan hệ ℜ trên A là đối xứng khi và chỉ khi 3.2. Tính đối xứng: ố xứng nhau qua đường chéo Δ của A × nó đối Ta nói quan hệ hai ngôi ℜ có tính đối xứng khi A. 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: 1 2 ℜ đối xứngg ⇔ ((∀x, y ∈ X, xℜyy ⇒ yyℜx). ) 3 Suy ra: 4 ℜ không đối xứng ⇔ (∃x,y∈X, xℜy và yℜx) 1 2 3 4 13/04/2010 11 13/04/2010 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: Cho ℜ là một quan hệ hai ngôi trên X. • Nếu X hữu hạn thì ℜ đối xứng khi và chỉ khi 3.3. Tính phản đối xứng: ma trận biểu ể diễn ễ M(ℜ) là một ma trận đốiố Ta nói quan hệ hai ngôi ℜ có tính phản đối xứng nếu xứng. đối với hai phần tử khác nhau bất kỳ x, y ∈ X không Ví dụ thể xảy ra đồng thời x có quan hệ ℜ với y và y có quan Quan hệ ℜ1 = {(1,1), (1,2), (2,1)} trên tập hệ ℜ với x. Như vậy: A={1 2 3 4} là đối xứng. A={1,2,3,4} xứng ℜ 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 13/04/2010 14 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.3. Tính phản đối xứng: 3.3. Tính phản đối xứng: • Quan hệ ℜ là phản xứng khi và chỉ khi chỉ có • Với X hữu hạn thì ℜ phản đối xứng khi và chỉ các phần ầ tử nằm ằ trên đường chéo là đối ố xứng khi ma trận biểu ể diễn ễ M(ℜ) = (rij) thỏa: qua Δ của A × A. ∀1 ≤ i ≠ j ≤ n, rji = 1 ⇒ rij = 0. 1 Ví dụ: 2 Quan hệ ≤ trên Z phản xứng vì: 3 (a ≤ b) ∧ (b ≤ a) → (a = b) 4 1 2 3 4 13/04/2010 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 Cho ℜ là một quan hệ hai ngôi trên X. 3.4. Tính bắc cầu: Ví dụ 3.4. Tính bắc cầu: •Quan hệ ℜ ={(1,1),(1,2),(2,1),(2,2),(1,3),(2,3)} Ta nói quan hệ hai ngôi ℜ có tính bắc cầu khi đối với trên tập A = {1, 2, 3, 4} có tính bắc cầu. 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: • Quan hệ ≤ và “|”trên Z có tính bắc cầu R bắc cầu ⇔ (∀x, (∀x y,y z ∈ X, X xℜy và yℜz ⇒ xℜz) ( ≤ b) ∧ (b ≤ c)) → (a (a ( ≤ c)) Suy ra: (a | b) ∧ (b | c) → (a | c) R không bắc cầu ⇔ (∃x,y,z ∈ X, xℜy và yℜz và xℜ z). 13/04/2010 17 13/04/2010 18 4. Quan hệ tương đương 4. Quan hệ tương đương 4.1. Định nghĩa: 4.2. Định nghĩa: Một quan hệ ℜ trên tập hợp X được gọi là một quan hệ tương Giả sử ℜ là một quan hệ tương đương trên X và đươ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ụ: x ∈ X. Khi ấyấ lớp tương đương chứa x, ký hiệu 1) Quan hệ bằng nhau trên một tập hợp X ≠ ∅ bất kỳ là một bởi x hay [x], là tập hợp gồm tất cả các phần tử y quan hệ tương đương X. của X có quan hệ ℜ với x. Như vậy: 2) Quan hệ nhỏ hơn hay bằng thông thường trên các tập hợp số x = {y ∈ X | yℜx} 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 19 13/04/2010 20 5
13/04/2010 4. Quan hệ tương đương 5. Quan hệ thứ tự 4.3. Định lý: 5.1. Định nghĩa: Giả sử ℜ là một quan hệ tương đương trên X. 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 đó: Khi ấy ta nói X là một tập hợp sắp thứ tự (hay có thứ tự). •∀x ∈ X, x ∈ x . Ví dụ: •∀x, y ∈ X, xℜy ⇔ x = y 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ự. •∀x, y ∈ X, x ∩ y ≠ ∅ ⇔ x = y 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. 13/04/2010 21 13/04/2010 22 5. Quan hệ thứ tự 5. Quan hệ thứ tự 5.2. Định nghĩa: 5.3. Đị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ét một ộ tập ập hợp ự ((X,, ≺ ) và x,, y là 2 ợp có thứ tự ∀x, y ∈ X, x ≺ y hay y≺ x. phần tử bất kỳ của X. Khi đó ta nói: 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 1) y là trội x hay x được trội bởi y nếu x ≺ y. và y≺ x. Ví dụ: d 2) y là trội trực tiếp của x nếu y ≠ x, x y trội x và 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. không tồn tại một trội z của x sao cho x ≺ z ≺ y. 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 24 6
13/04/2010 5. Quan hệ thứ tự 5. Quan hệ thứ tự 5.4. Định nghĩa: 5.4. Định nghĩa: Biểu đồ Hasse của một tập hợp hữu hạn có thứ Ví dụ: tự (X, ≺ ) bao gồm: ồ 1) Biểu đồ Hasse của U12 = {x ∈ N | x|n} với 1) Một tập hợp các điểm trong mặt phẳng tương quan hệ “ | ” được cho bởi: ứ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 25 13/04/2010 26 5. Quan hệ thứ tự 5. Quan hệ thứ tự 5.4. Định nghĩa: 5.4. Định nghĩa: Ví dụ: Ví dụ: 2) Với E = {a, b, c} thì biểu đồ Hasse của (P(E), 3) Biểu đồ Hasse của {1, 2, 3, 4, 5} với thứ tự ⊆) có dạng: thông thường có dạng của một dây chuyền: 13/04/2010 27 13/04/2010 28 7
13/04/2010 5. Quan hệ thứ tự 5. Quan hệ thứ tự 5.5. Định nghĩa: 5.5. Định nghĩa: Xét (X, ≺ ) là một tập được sắp và a, b ∈ X. Ta nói: 2) b là phần tử tối tiểu (tương ứng, phần tử tối đại) củ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); 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 13/04/2010 30 5. Quan hệ thứ tự 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: Trongg một ộ tập ập hợp ợp sắpp thứ tự ự hữu hạn ạ ta có: 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 1) Mọi phần tử trội (tương ứng, được trội bởi) 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 một phần tử tối tiểu (tương ứng, tối đại). rỗng ∅ không có ký tự nào). Trong S ta qui ước: 2) Nếu a là phần tử tối tiểu (tương ứng, ứng tối đại) với s = a1a2 ... an và t = b1b2 ... bm: s = t ⇔ (n = m và ai = bi, i = 1, n ) duy nhất của X thì a là phần tử nhỏ nhất (tương Trên S ta định nghĩa quan hệ ≺ như sau: ứ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

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.