Toán Rời Rạc_ P3 Chuong03 03 2008 Ppt
--- Bài mới hơn ---
1. Một số khái niệm cơ bản (tt)
1.2. Quan hệ n ngôi:
Một quan hệ n ngôi R trên các tập A1,A2, …,An là một tập con A1 A2… An. Các tập A1, A2,…, An gọi là các miền của R.
Ví dụ 1.7: Cho A1=các chuyến tàu = {S1, S2, S3, LH2}
A2 =Các ga = {NT, DN, TH,BD}
A3= Giờ ={0,1,2,…23}
A4=Phút ={0,1,2,…59}
Xét quan hệ:
LịchTàu={(x,y,z,t)/tàu x có đến (dừng) tại ga y lúc z giờ t phút}
.
Một số khái niệm cơ bản (tt)
LịchTàu là quan hệ 4 ngôi
Nếu tàu S1 đến và dừng tại ga NT lúc 13h30, thì:
(S1, NT,13,30) LịchTàu
Nếu tàu S3 đến và dừng tại ga DN lúc 4h40 thì
(S3,DN,4,40) LịchTàu
Nếu tàu S1 không dừng tại ga TH 18h30 thì
(S1,TH,18,30) LịchTàu
Nếu tàu S1 đến ga Tuy hòa lúc 17h45 thì :
(S1,TH,17,45) LịchTàu
Một số khái niệm cơ bản (tt)
Mỗi dòng là
một bộ của R
Trực quan, có thể xem quan hệ LịchTàu như bảng
Một số khái niệm
Ví dụ 1.8: Trên các tập Sinh_Vien = {sv1, sv2, sv3}, Môn_học = {trr, csdl, mmt}, Điểm = {0, 1, 2, 3, 4, 5, 7, 8, 9, 10}. Xét quan hệ “Kết_quả”:
(s,c,m)Kết_quả sinh viên s có kết quả môn c là m điểm.
Kết_quả là quan hệ 3 ngôi
Một số khái niệm
Tập K={Ai1,Ai2,…,Aim} {A1, A2,…,An} gọi là khoá của quan hệ R nếu với mỗi giá trị (ki1, ki2,.., kim) Ai1Ai2 … Aim chỉ có tối đa một bộ có dạng (… , ki1, …, kim ,….) R
2. Một số phép toán quan hệ
2.1 Phép chọn (selection): Cho C là một điều kiện, phép chọn C(R) là phép lấy ra các bộ từ R thoả điều kiện C
Ví dụ 2.1:
Ket_Qua
2. Một số phép toán quan hệ
Ví dụ 2.2
Lịch_Tàu
2. Một số phép toán quan hệ
2.2.Phép chiếu (Projection):
Cho trước các tập A1, A2, …, An. Ánh xạ chiếu lên các thành phần thứ i1,i2, …, im (mn) được định nghĩa:
Khi đó, với R là một quan hệ trên A1, A2, …, An, thì :
Gọi là quan hệ chiếu
2. Một số phép toán quan hệ
Ví dụ 2.3: Xét quan hệ trong ví dụ 1.7. Nếu chỉ muốn biết thông tin về chuyến tàu và các ga đến (không cần quan tâm đến thời điểm), ta xét quan hệ chiếu:
LichTau
3. Một số tính chất của quan hệ
Một quan hệ R trên A có thể có các tính chất sau đây:
a) Tính phản xạ (reflexivity):
R phản xạ (reflexive relation) aA, aRa
Ví dụ 3.1: Cho A={1,2,3,4,5},và quan hệ R trên A:
R={(1,1),(2,2),(2,3),(3,3),(3,4), (3,5),(4,2) ,(4,4), (5,1), (5,5)}
R có tính phản xạ.
1
2
3
4
5
1
2
3
4
5
3. Một số tính chất của quan hệ (tt)
Ví dụ 3.2: Cho A = {1,2,3,4} và quan hệ R trên A:
R2= {(1,1),(2,1), (3,1), (3,2), (4,4), {3,3)}
Ta thấy 2A như (2,2)R2 nên R2 không có tính phản xạ.
Ví dụ 3.2: Cho A={Người}, xét quan hệ R trên A được định nghĩa: x,yA, xRy “x quen biết với y”
Ta có: “xA, x quen biết với x” (hiển nhiên)
Hay xA, xRx nên R có tính phản xạ.
Ví dụ 3.4: Quan hệ “” trên R có tính phản xạ. Vì:
x R, x x
3. Một số tính chất của quan hệ
b) Tính đối xứng (Symmetry):
R đối xứng (symmetric relation)
a,b A, aRb bRa
Ví dụ 3.5: A={1,2,3}, xét quan hệ trên A
R3 = {(1,1), (3,2), (1,3), (3,1), (2,3)} là quan hệ đối xứng
R4 = {(2,1), (1,2), (3,2), (1,3), (3,1), (3,3)} là quan hệ không đối xứng
3. Một số tính chất của quan hệ
Ví dụ 3.6: Chọ tập A={Con người}, Xét quan hệ R “Quen biết” được định nghĩa như sau:
x,yA, xRy “x quen biết với y”
Quan hệ này có tính phản xạ, và đối xứng
Ví dụ 3.7: Xét quan hệ R:”Láng giềng” trên tập T={các tỉnh-Thành phố} được định nghĩa:
x,yT, xRy “x có phần ranh giới chung với y”
Quan hệ “Láng giềng” cũng có tính đối xứng.
Ví dụ 3.8:Quan hệ “=” trên tập A bất kỳ quan hệ có tính đối xứng
Ví dụ 3.9: Quan hệ “” trên R không có tính đối xứng.
3. Một số tính chất của quan hệ
c) Tính phản xứng (Antisymmetry):
R phản xứng (Antisymmetric relation)
a,bA, (aRb)(bRa) a=b
Ví dụ 3.10: Quan hệ “” trên tập số thực R, có tính phản xứng.
Vì: x,yR, (xy ) (y x) x= y
Ví dụ 3.11: Cho tập A={1,2,3,4} và quan hệ R trên A là:
R1={(1,1),(2,3),(2,2),(4,3),(4,4)}
R1 không có tính phản xạ, nhưng có tính phản xứng.
R2={(1,1),(3,3),(4,4)} : Đối xứng, phản xứng
Tổng quát: Quan hệ (mod n) trên Z có n lớp tương đương.
Zn={,…,
ii) x,y A, xRy
iii) x,y A, ≠
C/m?:
R phản xạ nên xA, xRx x
Lớp tương đương và các phân hoạch
Định nghĩa 4.3: Cho tập hợp S và A1, A2, …, An là các tập con của S thỏa các tính chất:
Ai i{1,2,…,n}
AiAj = i,j {1,2,…,n}, ij
A1A2…An = S
Thì A1, A2, …, An: gọi là một phân hoạch của S
A1
A2
A3
A4
A7
A5
A6
S
Một phân hoạch
Của S thành 7
Tập con
Lớp tương đương và các phân hoạch
Ví dụ 4.8: Cho S={0,1,2,3,4,5,6,7} và A={1,3,5,7}, B={2,4,6}, C={0}.
Ta có: A, B và C
AB=; AC= ; BC=
ABC=S
Vậy A, B, C là một phân hoạch của S
Lớp tương đương và các phân hoạch (tt)
Định lý 4.2: Cho R là một quan hệ tương đương trên A. Khi đó các lớp tương đương của R sẽ tạo nên một phân hoạch của A. Ngược lại, nếu A1, A2, …, An là một phân hoạch của A thì tồn tại quan hệ tương đương R sao cho {Ai} là tập các lớp tương đương của R.
Ví dụ 4.9: Quan hệ “cùng tính chẵn lẻ” trên tập số nguyên Z (xem ví dụ trước) phân hoạch Z thành 2 lớp tương đương:
={…,-4,-2,-0,2,4,6,…}
Tập số lẻ
Tập số chẵn
Z
Lớp tương đương và các phân hoạch (tt)
Ví dụ 4.9: Trên z, tập các lớp tương đương của quan hệ đồng dư modulo 4: z4 ={, } là một phân hoạch của z.
z
Phân hoạch
Ví dụ 4.10: Cho tập A={a1, a2, a3, a4, a5, a6} và các tập con của A: E1={a1, a3}, E2={a2,a4, a5}, E3={ a6}. Hãy tìm một quan hệ tương đương trên A nhận E1, E2, E3 làm các lớp tương đương?
Giải:
Ta có: {E1, E2, E3}là một phân hoạch của A. Theo định lý 4.2, tồn tại quan một hệ tương đương trên A nhận E1, E2, E3 làm các lớp tương đương.
Gọi R là quan hệ tương đương cần tìm.
Do R có tính phản xạ nên R có dạng:
R={(a1, a1), (a2, a2), (a3, a3),(a4, a4),(a5, a5), (a6, a6)}X
E1 là một lớp tương đương của R nên R phải có chứa các cặp: (a1,a3), (a3,a1)
E2 là một lớp tương đương của R, nên R phải có chứa các cặp: (a2,a4), (a4,a2), (a2,a5), (a5,a2), (a4, a5), (a5,a4)
Vậy R cần tìm có thể là: R={(a1, a1), (a2, a2), (a3, a3),(a4, a4),(a5, a5), (a6, a6)}
{(a1,a3), (a3,a1), (a2,a4), (a4,a2), (a2,a5), (a5,a2), (a4, a5), (a5,a4)}
5. Quan hệ thứ tự:
Định nghĩa 5.1: Quan hệ R trên tập A gọi là quan hệ thứ tự khi và chỉ khi R có tính Phản xạ, phản xứng và bắt cầu.
Ghi chú: Thường kí hiệu quan hệ thứ tự bởi < và (A,Ví dụ 5.1: Cho tập A={a1,a2, a3, a4, a5, a6, a7}, Xét các quan hệ:
R1={(a1, a1), (a2,a2), (a3,a3),(a4,a4),(a5,a5),(a6,a6),(a7,a7), (a1,a3), (a3, a5),(a1,a5), (a5,a7), (a3,a7), (a1,a7)}
R2={(a1, a1), (a2,a2), (a3,a3),(a4,a4),(a5,a5),(a6,a6),(a7,a7), (a1,a4), (a4, a6),(a1,a3), (a4,a1), (a3,a7), (a1,a7)}
R1 có phải là một quan hệ thứ tự trên A?
R2 có phải là một quan hệ thứ tự trên A?
Quan hệ thứ tự (tiếp theo)
Ta thấy:
aA, aR1a. nên R1 phản xạ
a,bA, aR1b a=b nên R1 phản xứng
a,b,cA, aR1b bR1c aR1c nên R1 bắt cầu
Vậy R1 là một quan hệ thứ tự trên A
R2 không phải là quan hệ thứ tự vì không phản xứng
--- Bài cũ hơn ---