Quan hệ tương đương là khái niệm cơ bản trong toán rời rạc. Trong bài viết này, TTnguyen sẽ cùng bạn tìm hiểu lý thuyết, ví dụ minh họa và bài tập về quan hệ tương đương giúp bạn ôn tập dễ dàng.
Xem thêm:
bài tập toán rời rạc chương 1 có lời giải
I. Lý thuyết về quan hệ tương đương toán rời rạc
1. Quan hệ tương đương là gì?
Một quan hệ hai ngôi R trên tập A được gọi là quan hệ tương đương nếu nó thoả mãn đồng thời ba tính chất sau:
- Tính phản xạ: Với mọi \(x \in A\), ta có \(xRx\)
- Tính đối xứng: Với mọi \(x,y \in A\), ta có \(xRx\) thì \(yRx\)
- Tính bắc cầu: Với mọi \(x,y,z \in A\), ta có \(xRx\) và \(yRx\) thì \(xRz\)
Định lý:
Giả sử R là một quan hệ tương đương trên tập hợp A. Khi đó:
a. ∀x ∈ A, x ∈ [x].
b. ∀x, y ∈ A, xRy <=> [x] = [y].
c. Nếu [x] ∩ [y] ≠ Ø thì [x] = [y].
2. Lớp tương đương là gì?
Cho R là một quan hệ tương đương trên tập hợp A và x ∈ A. Khi đó, lớp tương đương của phần tử x, ký hiệu [x] hay \(\bar{x}\) là một tập hợp con của A và được xác định như sau:
\([x] = \left\{ y\in A | yRx \right\}\)
3. Tập thương trong quan hệ tương đương
Tập thương của tập \(A\) theo quan hệ tương đương \(R\), ký hiệu \(A/R\) là tập hợp các lớp tương đương:
\( A/R = \left\{ [x] | x ∈ A \right\} \)
4. Lớp tương đương và phân hoạch
Giả sử R là một quan hệ tương đương trên tập hợp A. Khi đó, các lớp tương đương của R sẽ lập nên một phân hoạch của A. Ngược lại, với mỗi phân hoạch đã cho {Ai | i ∈ I} của tập hợp A luôn tồn tại một quan hệ tương đương R trên A sao cho các tập con Ai | i ∈ I là các lớp tương đương của nó.
II. Ví dụ về quan hệ tương đương
Ví dụ 1: Cho tập hợp A = {1,2,3}. Hãy cho biết các quan hệ sau, quan hệ nào có tính phản xạ, đối xứng, bắc cầu.
a. R = {(1,1), (1,2), (1,3), (3,3)}
b. S = {(1,1), (1,2), (2,1), (2,2), (3,3)}
c. T = {(1,1), (1,2), (2,2), (2,3)}
Lời giải
a. R = {(1,1), (1,2), (1,3), (3,3)}
Xét ma trận mô tả sau:
| R | 1 | 2 | 3 |
| 1 | 1 | 1 | 1 |
| 2 | 0 | 0 | 0 |
| 3 | 0 | 0 | 1 |
– Do (2,2) ∉ R nên => Quan hệ R không có tính phản xạ.
– Do (1,2) ∈ R nhưng (2,1) ∉ R => Quan hệ R không có tính đối xứng.
– Quan hệ R có tính bắc cầu.
b. S = {(1,1), (1,2), (2,1), (2,2), (3,3)}
| S | 1 | 2 | 3 |
| 1 | 1 | 1 | 0 |
| 2 | 1 | 1 | 0 |
| 3 | 0 | 0 | 1 |
– Do (i,i) ∈ S, ∀i = 1,2,3 nên S có tính phản xạ.
– Do (a,b) ∈ S => (b,a) ∈ S => Quan hệ S có tính đối xứng.
– Quan hệ S có tính bắc cầu.
=> Quan hệ S là quan hệ tương đương.
c. T = {(1,1), (1,2), (2,2), (2,3)}
| T | 1 | 2 | 3 |
| 1 | 1 | 1 | 0 |
| 2 | 0 | 1 | 1 |
| 3 | 0 | 0 | 0 |
– Do (3,3) ∉ T nên T không có tính phản xạ.
– Do (1,2) ∈ T nhưng (2,1) ∉ T nên T không có tính đối xứng.
– Do (1,2) ∈ T , (2,3) ∈ T nhưng (1,3) ∉ T nên T không có tính bắc cầu.
Ví dụ 2: Trong các quan hệ dưới đây, hãy cho biết quan hệ nào là phản xạ, đối xứng, bắc cầu.
a. Quan hệ R trên Z: xRy <=> x+y chẵn.
b. Quan hệ R trên Z: xRy <=> x – y lẻ.
c. Quan hệ R trên Z: xRy <=> |x| =| y|.
d. Quan hệ R trên Z: xRy <=> \(sin^{2}x + cos^{2}y =1\).
Lời giải
a. Quan hệ R trên Z: xRy <=> x+y chẵn.
– Với mọi x ∈ Z ta có: x + x = 2x là số chẵn nên R có tính phản xạ.
– Nếu x, y ∈ Z mà x + y chẵn thì y + x cũng chẵn nên R có đối xứng.
– Nếu x, y, z ∈ Z mà x + y và y + z là các số chẵn thì z, y, z là các số cùng chẵn hoặc cùng lẻ. Do đó, x + z là số chẵn, suy ra R có tính chất bắc cầu.
b. Quan hệ R trên Z: xRy <=> x – y lẻ.
Do 1- 1 = 0 không phải là số lẻ nên R không có tính phản xạ. Nếu x, y ∈ Z mà x – y lẻ thì y – x cũng lẻ nên R có tính đối xứng. Do 5 – 4 = 1 là số lẻ và 4 – 1 = 3 là số lẻ nhưng 5 – 1 =4 không phải số lẻ nên R không có tính bắc cầu.
c. Quan hệ R trên Z: xRy <=> |x| =| y|.
Với mọi x ∈ Z ta luôn có |x|=|x| nên R có tính phản xạ.
Với mọi x,y ∈ Z mà |x| =| y| thì hiển nhiên |y| =|x| nên R có tính đối xứng.
Với mọi x, y, z ∈ Z mà |x| =| y| và |y| =|x| thì |x|=|z| nên R có tính bắc cầu
d. Quan hệ R trên Z: xRy <=> \(sin^{2}x + cos^{2}y =1\).
Với mọi x ∈ Z ta luôn có \(sin^{2}x + cos^{2}y =1\) nên R có tính phản xạ.
Với mọi x, y ∈ Z sao cho \(sin^{2}x + cos^{2}y =1\).
Ta có \(sin^{2}x + cos^{2}y =1\)
<=> \(1 – cos^{2}y + 1 – sin^{2}x =1\)
hay \(sin^{2}x + cos^{2}y =1\) => R có tính đối xứng.
Với mọi x, y, z ∈ Z sao cho \(sin^{2}x + cos^{2}y =1\) và \(sin^{2}y + cos^{2}z =1\)
=> \(sin^{2}x + cos^{2}y + sin^{2}y + cos^{2}z=2\)
<=> \(sin^{2}y + cos^{2}z =1\)
=> R có tính bắc cầu
III. Chứng minh quan hệ tương đương
Bài 1: Cho 4={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15} và một quan hệ trên A x A được xác định bởi (a, b)R(c , d) < a + d = b + c. Chứng minh rằng R là một quan hệ tương đương. Tìm lớp tương đương của phần tử (2,11).
Lời giải
Với mọi (a, b) ∈ A×A ta luôn có a + b = b + a nên (a, b)R(a, b) hay R có tính phản xạ.
Với mọi (a, b),(c, d) ∈ A×A mà (a, b)R(c, d) suy ra a + d=b + c ↔ c + b=d +a nên (c, d)R(a, b). Do đó, R có tính đối xứng.
Với mọi (a, b),(c, d),(e, f)∈ A×A sao cho (a, b)R(c, d) và (c, d)R(e, f) suy ra (a + d=b + c, c+ f = d + e )=>a+ f + c + d = b + e + c + d = a + f = b + e hay (a, b)R(e, f). Vậy R có tính chất bắc cầu. Vậy R là một quan hệ tương đương trên A×A.
Ta có [(2, 11)]={(a, b)∈ A x A | (a, b)R(2, 11)}.
Do (a, b)R(2,11) <=> a + 11 = b + 2 <=> b = a + 9 nên có các trường hợp sau đây xảy ra:
a=1⇒ b = 10,
a=2⇒b=11,
a=3⇒b=12,
a = 4 ⇒ b = 13,
a = 5 ⇒ b = 14,
Vậy [(2,11)] = {(1,10), (2,11), (3,12), (4,13), (5,14), (6,15)}
Bài 2: Cho C là một tập con của E, xét một quan hệ hai ngôi trên P(E) như sau:
ARB <=>A ∩ C=B ∩ C
a. Chứng minh rằng R là một quan hệ tương đương trên P(E).
b. Cho E={1,2,3,4,5} và C={1,2,3}. Tìm [{1,3,5}], có bao nhiêu lớp tương đương khác nhau?
Lời giải
a. Với mọi A ∈ P(E) ta luôn có A ∩ C= A ∩ C nên ARA hay R có tính phản xạ.
Với mọi A,B ∈ P(E) sao cho ARB suy ra A ∩ C=B ∩ C suy ra B ∩ C = A ∩ C nên BRA hay R có tính đối xứng.
Với mọi A, B, D ∈ P(E) sao cho ARB và BRD suy ra:
(A ∩ C = B ∩ C và B ∩ C = D ∩ C ) => A ∩ C = D ∩ C hay ARD suy ra R có tính chất bắc cầu.
Vậy R là một quan hệ tương đương trên P(E).
b. Với mọi A ∈ [{1,3,5}] → A ∩ C={1,3,5} ∩ {1,2,3} = {1,3}.
Vậy {1,3} ⊂ A ⊂{1,3,4,5}
suy ra [{1, 3, 5}] = {{1, 3},{1, 3, 4},{1, 3, 5},{1, 3, 4, 5}}.
Xét các lớp tương đương rời nhau sau:
[Ø] = {A ∈ P(E) | A ∩ C = Ø},
[{1}] = {A ∈ P(E) | A ∩ C = {1}},
[{2}] = {A ∈ P(E)| A ∩ C={2}},
[{3}] = { A ∈ P(E) | A ∩ C={3}},
[{1,2}]={A ∈ P(E)| A ∩ C={1,2}},
[{1,3}] = {A ∈ P(E) | A ∩ C={1,3}},
[{2,3}]={A ∈P(E)| A ∩ C = {2,3}},
[C] = {A ∈ P(E) | A ∩ C=C}.
Với mọi tập A ∈ P (E) thì A ∩ C ∈ P(C) nên
A ∈ [Ø] ∪ [{1}] ∪ [{2}] ∪ [{3}] ∪ [{1,2}] ∪ [{1,3}]∪ [{2,3}] ∪ [C] suy ra
P(E) = [Ø] ∪ [{1}] ∪ [{2}] ∪ [{3}] ∪ [{1,2}] ∪ [{1,3}]∪ [{2,3}] ∪ [C]
Vậy số lớp tương đương là 8
Bài 3: Cho tập S={-5, -4, -3, -2, -1, 0, 1, 2} và một quan hệ hai ngôi trên S được xác định bởi
∀x, y ∈ S, xRy <=> \( x^{2} + 5x = y^{2} +5y \)
Chứng minh rằng R là một quan hệ tương đương và tìm tập thương tương ứng.
Lời giải
Rõ ràng với mọi x ∈ S ta luôn có \( x^{2} + 5x = y^{2} +5y \) nên R có tính phản xạ.
Với mọi x, y ∈ S nếu xRy suy ra \( x^{2} + 5x = y^{2} +5y \) hay_\( x^{2} + 5x = y^{2} +5y \) nên yRx suy ra R có tính đối xứng.
Với mọi x, y, z ∈ S nếu xRy, yRz suy ra \( x^{2} + 5x = y^{2} +5y \) và \( y^{2} + 5y = z^{2} +5z \) nên \( x^{2} + 5x = z^{2} +5z \) suy ra xRz hay R có tính bắc cầu.
Vậy R là một quan hệ tương đương trên S.
Với mọi x ∈ S ta có y ∈ [x] <=> \( x^{2} + 5x = y^{2} +5y \) <=> ( x – y )( x + y + 5) <=>
y = x và y = -x – 5
Vậy |-5] = {-5,0}, [-4] = {-4,-1}, [-3] = {-3, -2}, [1] = {1}, [2]={2}. Do đó, tập thương cần tìm là S/R={[-5], [-4], [-3], [1], [2]}.
IV. Bài tập quan hệ tương đương có lời giải
Bài 4: Có bao nhiêu quan hệ tương đương trên tập hợp A={a,b,c,d,e,f} sao cho:
a. Có đúng hai lớp tương đương với 3 phần tử.
b. Có đúng một lớp tương đương với 3 phần tử.
c. Có đúng một lớp tương đương với 4 phần tử.
Lời giải
Chú ý rằng số phân hoạch của tập hợp 4 là số quan hệ tương đương trên 4 (theo Định lý 2). Do đó,
a. Số cách phân hoạch tập hợp 4 thành hai tập con có số phần tử bằng nhau là:
\( \frac{1}{2}C^{3}_{6} = 10 \). Vậy có 10 quan hệ tương đương thỏa mãn điều kiện bài toán.
b. Trường hợp 1: Số phân hoạch có một lớp có 3 phần tử và ba lớp có 1 phần tử là \( C^{3}_{6} = 10 \).
Trường hợp 2: Số phân hoạch có một lớp có 3 phần tử, một lớp có 2 phần tử và một lớp có 1 phần tử là \( C^{3}_{6} C^{2}_{3}= 60 \).
Vậy số quan hệ tương đương thỏa mãn điều kiện bài toán là: 80.
c. Trường hợp 1: Số phân hoạch có một lớp 4 phần tử và hai lớp có 1 phần tử là: \( C^{4}_{6} = 15 \).
Trường hợp 2: Số phân hoạch có một lớp 4 phần tử và một lớp có 2 phần tử là \( C^{4}_{6} = 15 \).
Vậy số quan hệ tương đương thoả mãn điều kiện bài toán là: 30.
Bài 5: Cho A={1,2,3,4,5,6} và một quan hệ tương đương trên A như sau: R={(1,1),(1,2), (2,1),(2,2), (3,3), (4,4),(4,5),(5,4), (5,5),(6,6)}. Tìm phân hoạch của A thành các lớp tương đương theo quan hệ R như trên.
Lời giải
Ta có:
[1] = {1, 2}
[2] = [1]
[3] = {3}
[4] = {4, 5}
[5] = [4]
[6] = {6}
Vậy A = [1] ∪ [3] ∪ [4] ∪ [6]
Trên đây là lý thuyết và một số dạng bài tập về quan hệ tương đương toán rời rạc. Cảm ơn các bạn đã theo dõi trên ttnguyen.net
Bài viết liên quan:
