Toán rời rạc P5

Phần V
Quan hệ RELATIONS
1
1. Định nghĩa và tính chất
2.Biểu diễn quan hệ
3.Quan hệ tương đương. Đồng dư. Phép toán số học trên Zn
4.Quan hệ thứ tự. Hasse Diagram
Relations
2
1. Definitions
Definition. A quan hệ hai ngôi từ tập A đến tập B là tập con của tích Descartess R  A x B.
Chúng ta sẽ viết a R b thay cho (a, b)  R
Quan hệ từ A đến chính nó được gọi là quan hệ trên A
R = { (a1, b1), (a1, b3), (a3, b3) }
3
Example. A = students; B = courses.
R = {(a, b) | student a is enrolled in class b}

1. Definitions
4
1. Definitions
Example. Cho A = {1, 2, 3, 4}, và
R = {(a, b) | a là ước của b}
Khi đó
R = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 4), (3, 3), (4,4)}
5
2. Properties of Relations
Định nghĩa. Quan hệ R trên A được gọi là phản xạ nếu:
(a, a)  R với mọi a  A

Ví dụ. Trên tập A = {1, 2, 3, 4}, quan hệ:
R1 = {(1,1), (1,2), (2,1), (2, 2), (3, 4), (4, 1), (4, 4)} không phản xạ vì(3, 3)  R1
R2 = {(1,1), (1,2), (1,4), (2, 2), (3, 3), (4, 1), (4, 4)} phản xạ vì (1,1), (2, 2), (3, 3), (4, 4)  R2
6
Quan hệ  trên Z phản xạ vì a  a với mọi a Z
Quan hệ > on Z không phản xạ vì 1 > 1
1
2
3
4
4
3
2
1
Quan hệ“ | ” (“ước số”) trên Z + là phản xạ vì mọi số nguyên a là ước của chính nó .
Chú ý. Quan hệ R trên tập A là phản xạ iff nó chứa đường chéo của A × A :
 = {(a, a); a  A}
7
2. Properties of Relations
Định nghĩa. Quan hệ R trên A được gọi là đối xứng nếu:
a  A b  A (a R b)  (b R a)
Quan hệ R được gọi là phản xứng nếu
 a  A b  A (a R b)  (b R a)  (a = b)
Ví dụ.
Quan hệ R1 = {(1,1), (1,2), (2,1)} trên tập
A = {1, 2, 3, 4}là đối xứng
Quan hệ  trên Z không đối xứng.
Tuy nhiên nó phản xứng vì
(a  b)  (b  a)  (a = b)
8
(a | b)  (b | a)  (a = b)
Chú ý. Quan hê R trên A là đối xứng iff nó đối xứng nhau qua đường chéo  của A × A.
Quan hệ“ | ” (“ước số”) trên Z +. không đối xứng
Tuy nhiên nó có tính phản xứng vì
Quan hệ R là phản xứng iff chỉ có các phần tử nằm trên đường chéo là đối xứng qua  của A × A.
9
2. Properties of Relations
Định nghĩa. Quan hệ R trên A có tính bắc cầu( truyền) nếu
a  A b  A c  A (a R b)  (b R c)  (a R c)

Ví dụ.
Quan hệ R = {(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.
Quan hệ  và “|”trên Z có tính bắc cầu
(a  b)  (b  c)  (a  c)
(a | b)  (b | c)  (a | c)
10
Introduction
Matrices
Representing Relations

3. Representing Relations
11
ChoR là quan hệ từ A = {1,2,3,4} đến B = {u,v,w}:
R = {(1,u),(1,v),(2,w),(3,w),(4,u)}.
Khi đó R có thể biễu diễn như sau
Đây là matrận cấp 4×3 biễu diễn cho quan hệ R
Định nghĩa
12
Định nghĩa. Cho R là quan hệ từ A = {a1, a2, …, am} đến B = {b1, b2, …, bn}. Matrận biểu diễn của R là matrận cấp m × n MR = [mij] xác định bởi
mij =
0 nếu (ai , bj)  R
1 nếu (ai , bj)  R
Ví dụ. Nếu R là quan hệ từ
A = {1, 2, 3} đến B = {1, 2} sao cho a R b nếu a > b.
Khi đó ma trận biểu diễn của R là
Representing Relations
13
Khi đó R gồm các cặp:
{(a1, b2), (a2, b1), (a2, b3), (a2, b4), (a3, b1), (a3, b3), (a3, b5)}
Ví dụ. Cho R là quan hệ từ A = {a1, a2, a3} đến
B = {b1, b2, b3, b4, b5} được biễu diễn bởi matrận
b1 b2 b3 b4 b5
a1
a2
a3
14
Cho R là quan hệ trên tập A, khi đó MR là matrận vuông.
R là phản xạ iff tất cả các phần tử trên đường chéo của MR đều bằng1: mii = 1 với mọi i
Representing Relations
15
R là đối xứng iff MR is đối xứng
Representing Relations
mij = mji với mọi i, j
16
R is phản xứng iff MR thỏa:
Representing Relations
mij = 0 or mji = 0 if i  j
17
Introduction
Equivalence Relations
Representation of Integers
Equivalence Classes
Linear Congruences.
4.Equivalence Relations
18
Định nghĩa
Ví dụ:
Cho S = {sinh viên của lớp}, gọi
R = {(a,b): a có cùng họ với b}
Hỏi
R phản xạ?
R đối xứng?
R bắc cầu?
19

Quan hệ tương đương
Định nghĩa. Quan hệ R trên tập A được gọi là tương đương nếu nó có tính chất phản xạ, đối xứng và bắc cầu :
Ví dụ. Quan hệ R trên các chuỗi ký tự xác định bởi aRb iff a và b có cùng độ dài. Khi đó R là quan hệ tương đương.

Ví dụ. Cho R là quan hệ trên R sao cho aRb iff a – b nguyên. Khi đó R là quan hệ tương đương
20
Example. Let m be a positive integer and R the relation on Z such that aRb if and only if a – b is divisible by m, then R is an equivalence relation
The relation is clearly reflexive and symmetric.
Let a, b, c be integers such that a – b and b – c are both divisible by m, then a – c = a – b + b – c is also divisible by m. Therefore R is transitive
This relation is called the congruence modulo m and we write
a  b (mod m)
instead of aRb
Recall that if a and b are integers, then a is said to be divisible by b, or a is a multiple of b, or b is a divisor of a if there exists an integer k such that a = kb
21
Lớp tương đương
Định nghĩa. Cho R là quan hệ tương đương trên A và phần tử a  A . Lớp tương đương chứa a được ký hiệu bởi [a]R hoặc [a] là tập
[a]R = {b  A| b R a}
22
Ví dụ. Tìm các lớp tương đương modulo 8 chứa 0 và 1?
Giải. Lớp tương đương modulo 8 chứa 0 gồm tất cả các số nguyên a chia hết cho 8. Do đó
[0]8 ={ …, – 16, – 8, 0, 8, 16, … }
Tương tự
[1]8 = {a | a chia 8 dư 1}
= { …, – 15, – 7, 1, 9, 17, … }
Lớp tương đương
23
Chú ý. Trong ví dụ cuối, các lớp tương đương [0]8 và [1]8 là rời nhau.
Tổng quát, chúng ta có
Theorem. Cho R là quan hệ tương đương trên tập A và a, b  A, Khi đó
(i) a R b iff [a]R = [b]R
(ii) [a]R  [b]R iff [a]R  [b]R = 
Chú ý. Các lóp tương đương theo một quan hệ tương đương trên A tạo nên một phân họach trên A, nghĩa là chúng chia tập A thành các tập con rời nhau.
24
Thật vậy với mỗi a, b  A, ta đặt a R b iff có tập con Ai sao cho a, b  Ai .
Dễ dàng chứng minh rằng R là quan hệ tương đương trên A và [a]R = Ai iff a  Ai
Note. Cho {A1, A2, … } là phân họach A thành các tập con không rỗng, rời nhau . Khi đó có duy nhất quan hệ tương đương trên A sao cho mỗi Ai là một lớp tương đương.
a
b
25
Example. Cho m là số nguyên dương, khi đó có m lớp đồng dư modulo m là [0]m , [1]m , …, [m – 1]m .
Chúng lập thành phân họach của Z thành các tập con
rời nhau.
Chú ý rằng
[0]m = [m]m = [2m]m = …
[1]m = [m + 1]m = [2m +1]m = …
…………………………………
[m – 1]m = [2m – 1]m = [3m – 1]m = …
Mỗi lớp tương đương này được gọi là số nguyên modulo m
.Tập hợp các số nguyên modulo m được ký hiệu bởi Zm
Zm = {[0]m , [1]m , …, [m – 1]m}
26
Example. Cho m là số nguyên dương, ta định nghĩa hai phép tóan “ + ” và “ × “ trên Zm như sau
Theorem. Các phép tóan nói trên được định nghĩa tốt, i.e. Nếu a  c (mod m) và b  d (mod m), thì
a + b  c + d (mod m) và a b  c d (mod m)
5 Linear Congruences
[a ]m + [b]m = [a + b]m
[a ]m [b]m = [a b]m
Example. 7  2 (mod 5) và11  1 (mod 5) .Ta có
7 + 11  2 + 1 = 3 (mod 5)
7 × 11  2 × 1 = 2 (mod 5)
27
Note. Các phép tóan “ + ” và “ × “ trên Zm có các tính chất như các phép tóan trên Z
[a ]m + [b]m = [b]m + [a]m
[a ]m + ([b]m + [c ]m) = ([a]m + [b]m) + [c]m
[a ]m + [0]m = [a]m
[a ]m + [m – a]m = [0]m ,
Ta viết – [a]m = [m – a]m
[a ]m [b]m = [b]m [a ]m
[a ]m ([b]m [c ]m) = ([a]m [b]m) [c]m
[a ]m [1]m = [a]m
[a ]m ([b]m + [c ]m) = [a]m [b]m + [a]m [c]m
28
Example. “ Phương trình bậc nhất” trên Zm
[x]m + [a]m = [b]m
với [a]m và [b]m cho trước, có nghiệm duy nhất:
[x]m = [b ]m – [a]m = [b – a]m
Cho m = 26 ,phương trình [x]26 + [3]26 = [b]26 có nghiệm duy nhất với mọi [b]26 trong Z26 .
Do đó [x]26  [x]26 + [3]26 là song ánh từ Z26 vào chính nó .
Sử dụng song ánh này chúng ta thu được mã hóa Caesar: Mỗi chữ cái tiếng Anh được thay bởi một phần tử
của Z26: A  [0]26 , B  [1]26 , …, Z  [25]26
Ta sẽ viết đơn giản: A  0, B  1, …, Z  25
29
Mỗi chữ cái sẽ được mã hóa bằng cách cộng thêm 3 . Chẳng hạn A được mã hóa bởi chữ cái tương ứng với [0]26 + [3]26 = [3]26, nghĩa là bởi D.
Tương tự B được mã hóa bởi chữ cái tương ứng với [1]26 + [3]26 = [4]26, nghĩa là bởi E, … cuối cùng Z đựơc mã hóa bởi chữ cái tương ứng với [25]26 + [3]26 = [2]26 nghĩa là bởi C.
Bức thư “MEET YOU IN THE PARK” được mã như sau
M E E T Y O U I N T H E P A R K
12 4 4 19 24 14 20 8 13 19 7 4 15 0 17 10
1 17 23 11 16 22 10 7 18 3 20 13
P H H W B R X L Q W K H S D U N
15 7 7 22
30
Để giải mã, ta dùng ánh xạ ngược:
[x]26  [x]26 – [3]26 = [x – 3]26
Mã hóa như trên còn quá đơn giản,dễ dàng bị bẻ khóa. Chúng ta có thể tổng quát mã Caesar bằng cách sử dụng ánh xạ f : [x]26  [ax + b]26 trong đó a và b là các hằng số được chọn sao cho f là song ánh
P H H W tương ứng với
15 7 7 22
12 4 4 19
Lấy ảnh qua ánh xạ ngược:
M E E T
Ta thu đươc chữ đã đươc mã là
31
Trước hết chúng ta chọn a khả nghịch trong Z26 i.e. tồn tại a’ trong Z26 sao cho
Chúng ta viết [a’ ]26 = [a]26–1 nếu tồn tại .
Nghiệm của phương trình
[a]26 [a’ ]26 = [a a’ ]26 = [1]26
[a]26 [x]26 = [c]26
là [x]26 = [a]26–1 [c]26 = [a’c]26
Chúng ta cũng nói nghiệm của phương trình
a x  c (mod 26)
là x  a’c (mod 26)
32
Example. Cho a = 7 và b = 3, khi đó nghịch đảo của [7]26 là [15]26 vì [7]26 [15]26 = [105]26 = [1]26
Bây giờ M được mã hóa như sau
[12]26  [7 12 + 3]26 = [87]26 = [9]26
nghĩa là được mã hóa bởi I. Ngược lại I được giải mã như sau
[9]26  [15  (9 – 3) ]26 = [90]26 = [12]26
nghĩa là tương ứng với M.
Ánh xạ ngược của f xác định bởi
[x]26  [a’(x – b)]26
33
6. Partial Orderings
Introduction
Lexicographic Order
Hasse Diagrams
Maximal and Minimal Elements
Upper Bounds and Lower Bounds
Topological Sorting
34
Định nghĩa
Example. Cho R là quan hệ trên tập số thực:
a R b iff a  b
Hỏi:
Is R reflexive?
Is R symmetric?
Is R transitive?
Is R antisymmetric?
35
Định nghĩa
Definition. Quan hệ R trên tập A là quan hệ thứ tự( thứ tự) nếu nó có tính chất phản xạ, phản xứng và bắc cầu.
36
Định nghĩa
Definition. A relation R on a set A is a partial order if it is reflexive, antisymmetric and transitive.
Example.Quan hệ ước số “ | ”trên tập số nguyên dương là quan hệ thứ tự, i.e. (Z+, | ) là poset
Reflexive?
Transitive?
37
Antisymmetric?
Example. Is (Z, | ) a poset?
Antisymmetric?
38
Ex. Is (2S,  ), where 2S the set of all subsets of S, a poset?
Reflexive?
Transitive?
Antisymmetric?
39
Definition. Các phần tử a và b của poset (S, ) gọi là so sánh được nếu a b or b a .
Trái lại thì ta nói a và b không so sánh được.
Example. Quan hệ “ ” trên tập số nguyên dương là thứ tự toàn phần.
Example. Quan hệ ước số “ | ”trên tập hợp số nguyên dương không là thứ tự tòan phần, vì các số 5 và 7 là không so sánh được.
40
Thứ tự tự điển
Ex. Trên tập các chuỗi bit có độ dài n ta có thể định nghĩa thứ tự như sau:
a1a2…an  b1b2…bn
iff ai  bi,  i.
Với thứ tự này thì các chuỗi 0110 và 1000 là không
so sánh được với nhau .Chúng ta không thể nói chuỗi
nào lớn hơn.
Trong tin học chúng ta thường sử dụng thứ tự tòan phần
trên các chuỗi bit .
Đó là thứ tự tự điển.
41
Thứ tự tự điển
Dễ dàng thấy rằng đây là thứ tự tòan phần trên A  B Ta gọi nó là thứ tự tự điển .
Chú ý rằng nếu A và B được sắp tốt bởi  và  ’ ,tương ứng thì A  B cũng được sắp tốt bởi thứ tự
(a1 , b1) (a2, b2) iff
a1 < a2 or (a1 = a2 and b1  ’ b2)
Chúng ta cũng có thể mở rộng định nghĩa trên cho tích Descartess của hữu hạn tập sắp thứ tự tòan phần.
Cho (A, ) và (B, ’) là hai tập sắp thứ tự tòan phần. Ta định nghĩa thứ tự trên A  B như sau :
42
Thứ tự tự điển
Cho  là một tập hữu hạn (ta gọi là bảng chữ cái).
Tập hợp các chuỗi trên , ký hiệu là * ,xác định bởi
  *, trong đó  là chuỗi rỗng.
Nếu x  , và w  *, thì wx  *, trong đó wx là kết nối w với x.
Example. Chẳng hạn  = {a, b, c}. Thế thì
* = {, a, b, c, aa, ab, ac, ba, bb, bc, ca, cb, cc, aaa, aab,…}
43
Giả sử  là thứ tự tòan phần trên , khi đó ta có thể định
nghĩa thứ tự toàn phần trên * như sau.
Cho s = a1 a2 … am và t = b1 b2 … bn là hai chuỗi trên *
Hoặc ai = bi đối với 1  i  m ,tức là
t = a1 a2 … am bm +1 bm +2 … bn
Hoặc tồn tại k < m sao cho
ai = bi với 1  i  k và
ak+1 < bk+1 , nghĩa là
Thứ tự tự điển
s = a1 a2 … ak ak +1 ak +2 … am
t = a1 a2 … ak bk +1 bk +2 … bn
44
For example
Example. Nếu  là bảng chữ cái tiếng Anh với thứ tự: a < b < … < z,thì thứ tự nói trên là thứ tự thông thường giữa các từ trong Từ điển.
d i s c r e e t
d i s c r e t e
d i s c r e e t
d i s c r e e t n e s s
45
Ta có
Example. Nếu  = {0, 1} với 0 < 1, thì là thứ tự tòan phần trên tập tất cả các chuỗi bit * .
46
Hasse Diagrams
Mỗi poset có thể biễu diễn bởi đồ thị đặc biệt ta gọi
là biểu đồ Hasse
Để định nghĩa biểu đồ Hasse chúng ta cần các khái niệm
phần tử trội và trội trực tiếp.
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 sao cho
47
Hasse Diagrams
Ta định nghĩa Hasse diagram của poset (S, ) là đồ thị:
Mỗi phần tử của S được biễu diễn bởi một điểm trên mặt phẳng .
a
b
c
d
e
Nếu b là trội trực tiếp của a thì vẽ một cung đi từ
a đến b .
48
Hasse Diagrams
Ex. Biểu đồ Hasse của poset ({1,2,3,4}, ) có thể vẽ như sau
49
Example. Biểu đồ Hasse của P({a,b,c})
They look similar !!!
và biểu đồ Hasse của các chuỗi bit độ dài 3 with thứ tự tự điển
50
Phần tử tối đại và phần tử tối tiểu.
Xét poset có biểu đồ Hasse như dưới đây:
Mỗi đỉnh màu đỏ là tối đại.
Không có cung nào xuất phát từ điểm tối đại.
Không có cung nào kết thúc ở điểm tối tiểu.
Mỗi đỉnh màu xanh là tối tiểu.
51
Note. Trong một poset S hữu hạn, phần tử tối đại và phần tử tối tiểu luôn luôn tồn tại.
Thật vậy, chúng ta xuất phát từ điêm bất kỳ a0  S.
a0
a1
a2
Phần tử tối đại tìm được bằng phương pháp tương tự.
Nếu a0 không tối tiểu, khi đó tồn tại a1 a0,
tiếp tục như vậy cho đến khi tìm được phần tử tối tiểu .
52
Example. Tìm phần tử tối đại, tối tiểu của poset ({2, 4, 5, 10, 12, 20, 25}, | ) ?
Solution. Từ biểu đồ Hasse , chúng ta thấy rằng 12, 20, 25 là các phần tử tối đại , còn 2, 5 là các phần tử tối tiểu
Như vậy phần tử tối đại, tối tiểu của poset có thể không duy nhất.
53
Example. Tìm phần tử tối đại, tối tiểu của poset các chuỗi bit độ dài 3?
Solution. Từ biểu đồ Hasse , chúng ta thấy rằng 111 là phần tử tối đại duy nhất và 000 là phần tử tối tiểu duy nhất .
111 là phần tử lớn nhất và
000 là phần tử nhỏ nhất theo nghĩa:
với mọi chuỗi abc
54
Chúng ta có định lý
Theorem. Trong một poset hữu hạn, nếu chỉ có duy nhất một phần tử tối đại thì đó là phần tử lớn nhất .
Tương tự cho phần tử nhỏ nhất.
Proof. Giả sử g là phần tử tối đại duy nhất.
Như vậy g là phần tử lón nhất.
g
l
Chúng minh tương tự cho phần tử nhỏ nhất l
Lấy a là phần tử bất kỳ, khi đó tồn tại
a
m
phần tử tối đại m sao cho
55
Chặn trên , chặn dưới
Definition. Cho (S, ) là poset và A  S . Phần tử chặn trên của A là phần tử x  S (có thể thuộc A hoặc không) sao cho  a  A, a x.
Ex. Phần tử chận trên của {g,j} là a.
Tại sao không phải là b?
56
Ex. Chặn dưới chung LN của{g,j} là gì?

Definition. Cho (S, ) là poset và A  S. Chặn trên nhỏ nhất của A là phần tử chặn trên x của A sao cho mọi chặn trên y của A, ta đều có y x
Ex. Chặn trên nhỏ nhất của {i,j} là d
57
Ex. b  c = f
Chặn trên nhỏ nhất (nếu có ) của A = {a, b} đựơc ký
hiệu bởi a  b
Ex. i  j = d
Chặn dưới lớn nhất (nếu có) của A = {a, b} đựoc ký hiệu bởi a  b
58
Topological Sorting
Consider the problem of getting dressed.
59
Recall that every finite non-empty poset has at least one minimal element a1.
Now the new set after we remove a1 is still a poset.
Topological Sorting
60
Let a2 be a minimal of the new poset.
uwear
Topological Sorting
Now every element of this new poset cannot be a proper lower bound of a1 and a2 in the original poset
61
This process continues until all elements are removed
We obtain a new order of the elements satisfying the given constraints:
a1, a2, …, am
shoes
belt
jacket
swter
jeans
socks
uwear
shirt
jwlry
62
Bài tập
1. Khảo sát các tính chất của các quan hệ R sau. Xét xem quan hệ R nào là quan hệ tương đương. Tìm các lớp tương đương cho các quan hệ tương đương tương ứng.
a) ?x, y ? R, xRy ? x2 + 2x = y2 + 2y;
b) ?x, y ? R, xRy ? x2 + 2x ? y2 + 2y;
c) ?x, y ? R, xRy ?
x3 - x2y - 3x = y3 - xy2 - 3y;
d) ?x, y ? R+, xRy ? x3 - x2y - x = y3 - xy2 - y.
63
Bài tập
2 . Khaûo saùt tính chaát cuûa caùc quan heä R sau. Xeùt xem quan heä R naøo laø quan heä thöù töï vaø khaûo saùt tính toaøn phaàn, tính boä phaän vaø tìm caùc phaàn töû lôùn nhaát, nhoû nhaát, toái ñaïi, toái tieåu (neáu coù) cuûa caùc quan heä thöù töï töông öùng.
a) x, y  Z, xRy  xy;
b) x, y  R, xRy  x = y hay x < y + 1.
c) x, y  R, xRy  x = y hay x < y - 1.
d) (x, y); (z, t)  Z2, (x, y)  (z, t)  x  z hay (x = z vaø y  t);
e) (x, y); (z, t)  Z2, (x, y)  (z, t)  x < z hay (x = z vaø y  t);
64
Bài tập
3 . Xeùt quan heä R treân Z ñònh bôûi:
x, y  Z, xRy  n  Z, x = y2n
Chöùng minh R laø moät quan heä töông ñöông.
Trong soá caùc lôùp töông ñöông
coù bao nhieâu lôùp ñoâi moät phaân bieät?
Caâu hoûi töông töï nhö caâu b) cho caùc lôùp .
65
Bài tập
4 . Xeùt taäp maãu töï A = {a, b, c} vôùi
a < b < c vaø caùc chuoãi kí töï:
s1 = ccbac
s2 = abccaa
theo thöù töï töï ñieån.. Hoûi coù bao nhieâu chuoãi kí töï s goàm 6 kí töï thoûa
s2  s  s1?
66
Bài tập
5. ĐỀ THI NĂM 2006
Xét thứ tự “”trên tập P(S)các tập con của tập S ={1,2,3,4,5}trong đó AB nếu A là tập con của B.
Tìm một thứ tự toàn phần “ ≤ ”trên P(S) sao cho với A, B trong P(S), nếu AB thì A≤ B. Tổng quát hoá cho trường hợp S có n phần tử.
67
Bài tập
6 . Đề 2007.Có bao nhiêu dãy bit có độ dài 15 sao cho 00001  s  011, trong đó “ ” là thứ tự từ điển.
68