Tr−êng §¹i häc Vinh
NguyÔn Trung Hßa
To¸n rêi r¹c
Vinh - 2010
0
Chơng 1. Quan hệ
1.1. Quan hệ hai ngôi v các tính chất
1.1.1. Định nghĩa v các ví dụ
Trongcuộcsốngtathờng gặp rất nhiều hi ện tợng đợc diễn tả bởi
thuật ngữ quan hệ, chẳng hạn quan hệ bạn bè, quan hệ đồng hơng, quan hệ
thầy trò, Hoặc cuối năm học ta thờng quan tâm đến điểm trung bình chung
học tập của các thnh viên trong lớp, khi đó ta có mối quan hệ giữa sinh viên
của lớp v số thực l điểm trung bình chung học tập của các sinh viên. Hay
cuối học kỳ ta phải xếp lịch thi học kỳ, khi đó ta thờng xét quan hệ giữa
lớp trong khoa v môn đợc lớp đó học trong học kỳ, gọi tắt l quan hệ Học,
chẳng hạn 45A Học xác suất; 44B Học toán rời rạc; 44B Học kinh tế, 44A
Học tâm lý học, 44A Học kinh tế Có nghĩa l ta phải ghép cặp (lớp x, môn
y) v hiểu l lớp x học môn y. Nh vậy, tập tất cả các cặp (lớp x, môn y) sao
cho lớp x học môn y đặc trng cho quan hệ Học,v ta có thể coi quan hệ Học
l tập con của tích đề-các của hai tập các lớp v các môn học. Hình thức hoá
các hiện tợngấytacókháiniệmquanhệ,l một khái niệm rất quan trọng
của toán học v đợc ứng dụng trong nhiều lĩnh vực, đặc biệt l trong tin học.
Một quan hệ hai ngôi từ tập A đến tập B l một tập con R của tích đề
các A
ì B.Nếu(a, b) R thì ta nói rằng a có quan hệ R với b v ký hiệu
aRb thay thế cho ký hiệu (a, b).
Ví dụ 1. Quan hệ Họckỳ4= {(a, b) với a l một lớp nođócủakhoá
44, còn b l một môn m lớp a học trong học kỳ 4 (năm học 2004-2005)}.
Rõ rng quan hệ Họckỳ4l một tập con của quan hệ Học đã nói ở trên.
Ví dụ 2. Quan hệ trực thuộc (hnh chính) l tập con I c ủa tích đề-các
của tập H tất cả các huyện của V iệt nam v tập T l tập tất cả các tỉnh của

Giả sử có các quan hệ hai ngôi từ tập X đến tập Y , khi đó chúng đều l
các tập con của tích đề-các X ì Y , nên có thể xét các phép toán tập hợp l
phép hợp, phép giao, phép trừ, phép lấy hiệu đối xứng. Chúng đợc xem l
các phép toán trên các quan hệ v kết quả của chúng đều l cácquanhệhai
ngôi từ X đến Y .
Ta sẽ xây dựng viphéptoánmới.
Phép nghịch đảo: Giả sử R l một quan hệ hai ngôi từ tập X đến tập
Y . Quan hệ ngợc (nghịch đảo) của quan hệ R l quan hệ S từ Y đến X sao
cho S = {(y,x)|(x, y) R}.Quanhệngợc của R đợc ký hiệu bởi R
1
.
Ví dụ 1. Nếu X = {1, 2, 3, 4}, Y = {a, b, c}, R = {(1,b), (2,a), (4,c)}
thì R
1
= {(b, 1), (a, 2), (c, 4)}.
Phép hợp thnh: Giả sử R l một quan hệ hai ngôi từ tập X đến tập Y ,
S l một quan hệ hai ngôi từ tập Y đến tập Z. Hợp thnh của các quan hệ
2
R v S l quan hệ T từ X đến Z với T = {(x, z)|y Y sao cho (x, y)
R v (y, z) S}. Quan hệ hợp thnh T đợc ký hiệu bởi R S hoặc RS.
ChúýrằngRS có thể l tập rỗng mặc dầu R v S đều khác rỗng v phép
hợp thnh có tính chất kết hợp, nghĩa l (R S) V = R (S V ).
Ví dụ 2. Giả sử X = {1, 2, 3, 4}, Y = {a, b, c
}, Z = {, , },
R = {(1,b), (2,a), (3,b), (4,c)}, S = {(a, ), (b, ), (c, )}, khi đó
RS = {(1, ), (2, ), (3, ), (4, )}.
Phép luỹ thừa: Giả sử R l một quan hệ hai ngôi trên tập X. Luỹ thừa
bậc n của quan hệ R ,kýhiệul R
n
,vớin =1, 2, l quan hệ đợc xác

ởvídụ5(mục1.1.1)l các quan hệ có tính đối xứng.
c. Quan hệ hai ngôi R trên một tập X đợc gọi l có tính chất phản
xứng nếu với mọi a, b X sao cho aRb v bRa thì a = b.
Ví dụ 3. Quan hệ < trên tập Z (ví dụ 5 mục 2.1.1) có tính phản xứng.
d. Quan hệ hai ngôi R trên một tập X đợc gọi l có
tính chất bắc cầu
nếu với mọi a, b, c X sao cho aRb v bRc thì aRc.
Ví dụ 4. Các quan hệ đồng hơng,lớntuổihơnởvídụ4;cácquanhệ
đồng d, < ở ví dụ 5 (mục 1.1.1) có tính chất bắc cầu.
Sau đây ta có định lý về mối liên hệ giữa quan hệ bắc cầu R v các luỹ
thừa của R.
3
Định lý 1. Qu an hệ R trên tập A có tính bắc cầu khi v chỉ khi R
n
R với
mọi n =1, 2, 3,
Chứng minh. Cần: Rõ rng R
1
R, tức l với n =1điều kiện cần đã
đúng.
Giả sử R
n
R ta sẽ chứng minh R
n+1
R. Thật vậy, theo định nghĩa
của luỹ thừa bậc n củaquanhệtacóR
n+1
= R
n
R nghĩa l với mọi (x, z),

+
4. R l quan hệ hm , nghĩa l R = {(a, f(a)) f(a) l ảnh của a qua
ánh xạ f.
5. Liệt kê 16 quan hệ khác nhau trên tập {0, 1}
6. Trongsố16quanhệkhácnhautrêntập{0, 1}, những quan hệ nol
a. Phản xạ
b. Đối xứng.
c. Phản xứng.
d. Bắc cầu.
7. Có bao nhiêu quan hệ trên tập gồm n phần tử l
a. Phản xạ
b. Đối xứng.
c. Phản xứng.
8. Cho R l quan hệ có tính phản xạ trên tập A. Chứng minh rằng R
n
cũng
cótínhphảnxạvớimọisốnguyêndơng n.
4
9. Cho R l quan hệ có tính đối xứng trên tập A. Chứng minh rằng R
n
cũng có tính đối xứng với mọi số nguyên dơng n.
10. Chỉ ra một ví dụ về một quan hệ bắc cầu R sao cho R
2
= R
1.2. Biểu diễn quan hệ
1.2.1. Ma trận logic v các phép toán trên các ma trận logic
Giả sử a, b l các biến (biến boolean) chỉ nhận một trong hai g iá trị 0
hoặc 1 (giá trị logic).
Ta gọi tuyển của a v b l giá trị
c = a b :=

] trong
đó c
i,j
= a
i,j
b
i,j
.
c. Tích boolean của ma trận A cỡ m ì n v ma trận B cỡ n ì p l ma trận
C = A B := [c
i,j
] cỡ m ì p trong đó
c
i,j
=(a
i,1
b
1,j
) ããã (a
i,k
b
k,j
) ããã (a
i,n
b
n,j
)
(các dấu ngoặc có thể đợc bỏ đi). Ta ký hiệu tích boolean của hai ma trận
A v B l A B
Dễ thấy rằng ma trận vuông I

i,j
(a
i,k
b
k,j
).
Vì tích boolean của các ma trận logic có tính chất kết hợp nên ta có thể
định nghĩa luỹ thừa boolean nh sau:
d. Luỹ thừa boole bậc r của một ma trận vuông logic A cấp n,kýhiệu
bởi A
[r]
đợc định nghĩa bằng truy hồi nh sau:
A
[r]
= A A
[r1]
, với r =1, 2, v A
[0]
= I
n
.
hoặc đợc xác định bởi
A
[r]
= A A ãããA


rlần
1.2.2. Biểu diễn quan hệ bằng ma trận
a. Xây dựng biểu diễn

, a
m
}, B = {b
1
,b
2
, b
n
}. Matrậnlogicbiểudiễnquanhệ
R l ma trận M
R
=[r
i,j
],trongđó
r
i,j
=

1 nếu (a
i
,b
j
) R
0 nếu (a
i
,b
j
) / R
Để ý rằng thứ tự của các phần tử của A v B honton tuỳ ý, tuy nhiên
phải đợc cho trớc cố định. Nói cách khác ứng với một thứ tự của các phần

e. Ma trận biểu diễn hợp thnh của hai quan hệ.
Định lý. Giả sử A, B, C l các tập hữu hạn có số các phần tử tơng ứng
l m, n, p.GiảsửR, S l các quan hệ hai ngôi từ A đến B v từ B đến C
tơng ứng. Gọi M
R
=[r
i,k
],M
S
=[s
k,j
],M
RS
=[t
i,j
] l cácmatrậnbiểu
diễn R, S, RS tơng ứng. Khi đó ta có
M
RS
= M
R
M
S
7
Chứng minh:
Xét t
i,j
l phầntửbấtkỳ(ởdòngi cột j)củaM
RS
.Tacót

i,n
s
n,j
)=1,
nghĩa l phầntửởdòngi cột j của ma trận tích M
R
M
S
bằng 1. Vậy
M
RS
= M
R
M
S
.

1.2.3. Biểu diễn quan hệ bằng đồ thị có hớng.
a. Định nghĩa đồ thị có hớng
Đồ thị có hớng l một bộ đôi G =(V,E) trong đó V l một tập hợp,
gọi l tập các đỉnh; E V
2
,l tập các cặp sắp thứ tự các phần tử của V ,
đợc gọi l tập các cạnh. Với mỗi cạnh (a, b) E,đỉnha đợc gọi l đỉnh
đầu, b gọi l đỉnh cuối của cạnh. Nếu a trùng b, cạnh (a, a) đợc gọi l một
khuyên. Đồ thị có hớng thờng đợc biểu diễn (minh hoạ) một cách trực
quan nh hình vẽ dới đây: Ví dụ.
b. Đồ thị có hớngbiểudiễnquanhệ
Từ định nghĩa đồ thị có hớng ở trên, nếu R l một quan hệ hai ngôi
trên tập hợp A,tacóthểbiểudiễnR nh l một đồ thị G =(A, R) (với tập

1. Cho tập A = {1, 2, 3, 4}. BiểudiễncácquanhệR, S trên A bằng ma
trận với thứ tự của các phần tử của A đợc liệt kê tăng dần v R, S cho
sau đây:
a. R = {(1, 1), (1, 2), (2, 3), (4, 2)}.
b. S = {(1, 1), (1, 3), (2, 1), (2, 3), (2, 4), (3, 1), 3, 2), (4, 1)}
2. Cho tập A = {a, b, c, d} v các quan hệ P, Q trên tập A đợc biểu diễn
bởi ma trận sau (t
ơng ứng vớ i thứ tự đã đợc liệt kê của phần tử của
A): a. M
P
=



1010
0101
1100
0011



;b.M
Q
=



1001
0110
1010

l ma trận biểu diễn quan hệ R thì M
[k]
R
l
ma trận biểu diễn quan hệ R
k
,vớik =1, 2, 3,
1.3. Các bao đóng của quan hệ.
1.3.1. Định nghĩa bao đóng.
Một quan hệ R trên một tập A có th ể có hoặc k hông có một tính c hất P
no đó (chẳng hạn tính chất đối xứng). Nếu có một quan hệ S trên A có tính
10
chất P , chứa R sao cho mọi quan hệ có tính chất P chứa R đều chứa S thì
S sẽ đợc gọi l bao đóng của R đối với P . Chẳng hạn nếu P l tính chất
phản xạ, (đối xứng, phản xứng, bắc cầu) thì các bao đóng của R đối với P sẽ
đợc gọi l bao đóng phản xạ, (bao đóng đối xứng, bao đóng phản xứng, bao
đóng bắc cầu). Có thể nhận thấy rằng bao đóng S của một quan hệ R đối với
tính chất P l giao của mọi quan hệ chứa R v có tính chất P .
a. Xác định Bao đóng phản xạ
Bao đóng phản xạ của một quan hệ hai ngôi R trên tập A l hợp R
của R v quan hệ bằng nhau = {(a, a)|a A} trên A (Hãy chứng minh?).
b. Xác định Bao đóng đối xứng.
Bao đóng đối xứng của một quan hệ hai ngôi R trên tập A l hợp RR
1
của R v quan hệ ngợc R
1
= {(b, a)|(a, b) R} trên A (Hãy chứng minh?).
Để xác định bao đóng bắc cầu của một quan hệ R ta cần đaramộtsố
khái niệm v kết quả bổ trợ.
1.3.2. Đờng đi trong đồ thị có hớng

đợc gọi l đỉnh khởi đầu v x
n
đợc gọi l
đỉnh kết thúc của đờng đi. Đờng đi có đỉnh khởi đầu v đỉnh kết thúc trùng
nhau thì đợc gọi l một chu trình. Để tránh nhầm lẫn ta quy ớc không có
đờngđiđộdi 0, nghĩa l đờng đi (a, a) l một khuyên v có độ di1.
Chú ý rằng một đờng đi thì tơng ứng với một dãy các đỉnh, tuy nhiên,
một dãy các đỉnh chachắcđãxácđịnhmộtđờng đi.
11
b. Vi dụ. Trongcácdãyđỉnhchodới đây, dãy đỉnh nol một
đờng đi trong đồ thị G chotrênhìnhvẽ? (a, b, d, c, b, a, e); (a, c, d, e, b, a, d);
(a, d, g, b),
c. Đờng đi trong quan hệ R.Địnhlývềđờng đi độ di n v quan hệ
R
n
.
Bởivìmộtđồthịcóhớng G có thể tơng ứng 1-1 với một quan hệ hai
ngôi R trên tập các đỉnh của nó, do đó từ định nghĩa đờng đi ở trên, ta có
thể định nghĩa đờng đi từ a đến b trongquanhệR l một dãy các phần tử
(x
0
,x
1
), (x
1
,x
2
), ,(x
n1
,x

), (x
n1
,b).
Với n 1 phần tử đầu ta xác định một đờng đi trong R có độ di n 1,
do đó theo giả thiết quy nạp ta có (a, x
n1
) R
n1
. Kết hợp biểu thức liên
thuộc ny với phần tử thứ n của đờng đi, ta có (a, b) R R
n1
, nghĩa l
(a, b) R
n
.

1.3.3. Xác định bao đóng bắc cầu
a. Định nghĩa quan hệ liên thông. Cho R l mộtquanhệtrêntậpA.
Quan hệ liên thông R

tơng ứng với R l quan hệ bao gồm các cặp (a, b)
12
sao cho có một đờng đi trong R từ a đến b.
R

= {(a, b)|a = x
0
,x
1
, ,x

m1
,x
m
= b l một đờng đi trong R từ a đến
b. Khi đó các đỉnh x
i
với 0 <i<nđợc gọi l các đỉnh trong của đờng đi
đã cho. Chú ý rằng bản thân a hoặc b cũng có thể l các đỉnh trong.
Định lý 3. (về Biểu diễn của bao đóng bắc cầu R

)Giả sử A l một tập có
n phần tử v R l quan hệ hai ngôi trên A đợc biểu diễn bởi ma trận logic
M
R
. Khi đó bao đóng bắc cầu R

của R đợc biểu diễn bởi ma trận logic
M
R

= M
R
M
[2]
R
M
[n]
R
.
Chứng minh. Trớc tiên ta chứng minh nhận xét sau:

đi từ a đến b v có độ di m
1
= m l<m. Cứloạibỏcácchutrình
13
nh trên sau k bớc nođótasẽcómộtđờng đi từ a đến b có độ di
m
k
<m
k1
< <m
1
<mvới các đỉnh trong đôi một khác nhau v khác
với các đỉnh a, b (trừ trờng hợp đặc biệt a = x
0
x
m
= b). Do đó,
-nếua = x
0
x
m
k
= b,đờngđicótốiđan đỉnh phân biệt v có đỉnh
đầutrùngđỉnhcuối,dođóđộdi m
k
< n.
-nếua = b,đờngđicótốiđan-1đỉnhphânbiệt,nêncóđộdi m
k
<n.
Từ nhận xét trên, ta nhận thấy mỗi phần tử (a, b) R

R
.
A := M
R
M
R

:= A;
Với i := 2 đến n
A := A M
R
M
R

:= M
R

A
Thuật toán 2. (Warshall, 1960), (Roy, 1959).
Thuật toán Warshall sẽ xây dựng dãy các ma trận logic W
0
,W
1
, ,W
n
trong đó W
0
= M
R
, W

nh sau:
Giả sử W
k
=[w
(k)
ij
] l ma trận logic trong dãy trên, khi đó
w
(k)
ij
=1khi v chỉ khi có một đờngđitừđỉnha
i
đến đỉnh a
j
m mọi đỉnh trong của nó chỉ thuộc tập {a
1
, ,a
k
} gồm k đỉnh đầu tiên
14
trong danh sách các đỉnh (đã đợc sắp) của tập nền A. Có ba khả năng xảy
ra:
-Hoặctậpcácđỉnhtrongcủađờng đi ny không chứa a
k
,đờng đi ny
chính l đờng đi tơng ứng với w
(k1)
ij
=1.
-Hoặctậpcácđỉnhtrongcủađờng đi nyđiquaa

k
(tức l ta quy về khả năng thứ hai
ởtrên.
Vậy w
(k)
ij
=1khi v chỉ khi w
(k1)
ij
=1hoặc w
(k1)
ik
=1v w
(k1)
kj
=1,
tức l:
w
(k)
ij
= w
(k1)
ij
(w
(k1)
ik
w
(k1)
kj
).

R
I
n
.
15
b. Ma trận biểu diễn bao đóng đối xứng của R l M
R
M
t
R
trong đó
M
t
l ma trận chuyển vị của M.
5. Dùng các thuật toán 1 v 2 để t ìm bao đóng bắc cầu của các quan hệ sau
đây:
a. R = {(1, 0)} trên tập A = {0, 1}
b. R = {(a, b), (a, c)} trên tập A = {a, b, c}.
c. R = {(a, a), (a, b), (b, c), (b, d), (c, a), (d, a), (d, b)} trên tập A =
{a, b, c, d}.
6. Giả sử A l một tập gồm n chữ cái nođó, (n<20). R l một quan hệ
hai ngôi trên A.Viếtmộtchơng trình thực hiện các công việc sau đây:
a. Nhập số phần tử n của tập A v cácphầntửcủaA (l các chữ cái).
b. N hập các cặp thuộc quan hệ R trên A.
c. XácđịnhmatrậnbiểudiễnquanhệR v in ra mnhìnhmatrậnđó.
d. Tìm v in ra mnhìnhmatrậnbiểudiễnquanhệbaođóngbắccầu
của R.
e. In ra mn hình tất cả các cặp phần tử của bao đóng bắc cầu của R.
1.4. Quan hệ tơng đơng v quan hệ thứ tự.
1.4.1. Quan hệ tơng đơng

i
A
j
= với i = j (2)
sao cho hai phần tử a, b cùng thuộc một tập con A
i
khi v chỉ khi aRb.
Thật vậy, với mỗi a A,gọiR
a
l tập tất cả các phần tử của A có quan
hệ với a, khi đó dễ thấy

aA
R
a
= A
mặt khác nếu R
a
R
b
= thì tồn tại c R
a
R
b
v với mọi x R
a
ta có xRa, aRc, cRb suy ra xRb, nghĩa l x R
b
v ngợc lại. Vậy nếu
R

4=6=8.Tậpthơng A/R = {A
1
,A
2
} = {1, 2}.
-Quanhệtơng đơng trong ví dụ 2 xác định phân hoạch của tập A
thnh các tập A
i
m mỗi A
i
l tập tất cả các sinh viên của A thuộc cùng một
huyện. Có thể coi tập thơng l tập các huyện có sinh viên thuộc lớp 48K.
-Quanhệtơng đơng trong ví dụ 3 xác định phân hoạch của tập A
thnh năm tập A
0
= {5k | k Z}, A
1
= {5k +1 | k Z}, A
2
=
{5k +2 | k Z}, A
3
= {5k +3 | k Z}, A
4
= {5k +4 | k Z}.
Tập thơng Z/R = {
0, 1, 2, 3, 4},(chínhl Z
5
quen thuộc).
17

, tức l A
i
sao cho b A
i
,a A
i
, tức l
bRa.
- Tính chất bắc cầu thỏa mãn vì với mọi a, b, c A,nếuaRb v bRc thì
từ aRb suy ra A
i
sao cho a A
i
,b A
i
v từ bRc suy ra A
j
sao cho b
A
j
,c A
j
. Tuy nhiên theo điều kiện (2) ta có i = j,dođóA
i
sao cho a
A
i
,c A
i
,tứcl aRc.

không phải hai phần tử bất kỳ đều có thể so sánh đợc. Các quan hệ thứ tự
nh vậy đợc gọi l quan hệ thứ tự bộ phận.
Từ quan hệ thứ tự <
,nếua<b v a = b thì ta viết a<bv ta nói rằng
<l thứtựchặt.Nh vậy một quan hệ thứ tự chặt chỉ thỏa mãn hai tính
chất phản xứng v bắc cầu.
Giả sử R l quanhệthứtựtrêntậpA. B l một tập con của A.Khiđó
R (B ì B) l một quan hệ thứ tự trên B v ta cũng ký hiệu l R,đợc gọi
l thứ tự trên B cảm sinh bởi thứ tự trên A hoặc l thu hẹp của thứ tự R trên
B.
Giả sử X l một tập hợp sắp thứ tự. Một phần tử a X đợc gọi l
phần tử tối tiểu của X nếu từ x<
a kéo theo x = a.
Chẳng hạn tập Z với quan hệ <
trong ví dụ 6 không có phần tử tối tiểu.
Giả sử X khác rỗng. Tập P(X) \{} với quan hệ (quan hệ bao hm
thu hẹp trên P(X)) chứa ít nhất một phần tử tối tiểu v mọi tập con một phần
tử của X đếu l phần tử tối tiểu.
Giả sử X l một tập hợp sắp thứ tự. Một phần tử a X đợc gọi l
phần tử bé nhất của X nếu từ x X đều có a<
x.
Chẳng hạn tập với quan hệ trong ví dụ 7 l phần tử bé nhất.
Một tập hợp đợc gọi l sắp thứ tự tốt nếu nó l tậpsắpthứtựv mọi
tập con khác rống của nó đều có phần tử bé nhất.
Ví dụ tập hợp các số tự nhiên với quan hệ thứ tự <
thông thờng l tập
sắp thứ tự tốt.
Bitập.
1.Chứngtỏrằngmỗiquanhệtơng đơng đều có thể biểu diễn bởi ma
trận khối dạng

kk




19
trong đó
A
ij
=

ma trận có mọi phần tử bằng 1 nếu i = j
ma trận không (có mọi phần tử bằng 0) nếu i = j
2. Cóthểcóbaonhiêuquanhệtơng đơng trên một tập có n phần tử?
1.5. Quan hệ n ngôi v các ứng dụng của nó.
1.5.1. Quan hệ n ngôi v cơ sở dữ liệu quan hệ
a. Định nghĩa quan hệ n ngôi. Cho n tập hợp A
1
,A
2
, ,A
n
. Một tập
con R củatíchđềcácA
1
ì A
2
ì ì A
n
đợc gọi l một quan hệ n ngôi

gồm 4 thuộc tính: Số thứ tự, Họ v tên, Năm sinh, Quê quán. Thuộc tính số
thứtựđặctrng cho miền A
1
l tập con của tập các số tự nhiên. Thuộc tính
Họ v tên đặc trng cho miền A
2
các xâu ký tự. Thuộc tính Năm sinh đặc
trng cho miền A
3
l tập con của tập các số tự nhiên. Thuộc tính Quê quán
đặc trng cho miền A
4
cácxâukýtựchỉtêncủacáctỉnh.
20
Dễ dng nhận thấy rằng bảng trên l một tập hợp 6 phần tử dữ liệu có
cùng kiểu (bản ghi), mỗi thuộc tính sẽ l một trờng của kiểu bản ghi đó.
Kiểu dữ liệu của từng trờng sẽ xác định cá c tập A
i
l các miền của quan hệ.
Rõ rng từ ví dụ trên, ta bắt đầu thấy đợc một mối liên hệ giữa khái niệm
toán học trừu tợng quan hệ n ngôi v khái niệm ở thực tế cuộc sống v
trong tin học (dữ liệu). Mối liên hệ ấy sẽ đợc xem xét dới tên gọi Mô hình
quan hệ của dữ liệu. Vấn đề l ti ếp tục xây dựng các thao tác (phép toán)
thích hợp trên các quan hệ để tác động vocácdữliệu.
1.5.2. Các phép toán: hợp, giao, tich đề các, kết nối, chiếu, chọn.
Định nghĩa 1. Hai q uan hệ đợc gọi l khả hợp nếu chúng đều l tập
con của tích đề các của n tập đã cho. Nh vậy, hai quan hệ khả hợp phải
cùng bậc v cácphầntửthuộcmỗiquanhệấyđềul cácbộcóthứtựcùng
các thuộc tính tơng ứng.
Từ định nghĩa của tính khả hợp ta có thể định nghĩa hợp, giao, hiệu của

ngôi (m<
n) trên các tập hợp A
i
1
,A
i
2
, ,A
i
m
bao gồm tất cả các phần
tử l các bộ thu đợc từ các bộ của R bằng cách xoá đi n m thnh phần
không thuộc các tập nói trên. Nh vậy phép chiếu thực chất l phép loại bỏ đi
một số thuộc tính v giữ lại một số các thuộc tính của quan hệ đó. Để tránh
nhầmlẫnhoặcmấtmátdữliệu,thôngthờng ta chỉ thực hiện phép chiếu lên
các tập hợp m tập các thuộc tính tơng ứng tạo nên một khoá phức hợp K.
Định nghĩa 4. Phép nối tự nhiên J
p
(R, S)(p< min {m, n} l quan hệ
bậc m + n p bao gồm tất cả các bộ m + n p thnh phần
(a
1
,a
2
, ,a
mp
,c
1
,c
2

p
,b
1
,b
2
, ,b
np
) S
Định nghĩa 5. Phép chọn
F
(R)={r R|F (r) đúng} l một tập con
tất cả các phần tử r của R sao cho hệ thức Boole F no đó đúng đối với
những phần tử ấy của R.Nh vậy, bằng cách chỉ ra các hệ thức F ,nócho
phép ta có thể chọn đợcnhữngphầntửcủaR thoả mãn điều kiện đã cho.
c. Một số ví dụ. (Xem Rosen)
1.5.3. Khoá của một quan hệ R.
Một thuộc tính A
i
đặc trng cho một miền A
i
của quan h ệ n ngôi R
đợc gọi l một khoá cơ bản của quan hệ R nếu với mỗi giá trị bất kỳ a
i
A
i
ta tìm đợc nhiều nhất một phần tử (a
1
,a
2
, ,a

23
Chơng 2. Lý thuyết tổ hợp
2.1. Một số nguyên lý cơ bản
2.1.1. Mở đầu - Sơ lợc về tổ hợp
Trongrấtnhiềubi toán thực tế, cần phải quan tâm đến tập hợp các đối
tợng đợc sắp xếp thep một trật tự nođó,sauđâytasẽgọitắtcụmtừny
bởi thuật ngữ cấu hình v thờng phải trả lời các câu hỏi:
i. Có hay không một cấu hình cho trớc?
ii. Có bao nhiêu cấu hình cho trớc?
iii. Cách thức để liệt kê hay chỉ rõ các cấu hình đó nh thế no?
Câu hỏi thứ nhất liên quan đến một lớp các bitoánm ta sẽ gọi l các
bi toán tồn tại. Câu hỏi thứ hai liên quan đến lớp các bitoánđếmv câu
hỏi thứ ba liên quan đến lớp các bitoánliệtkê.Phơng pháp để giải quyết
các bi toán thuộc các lớp bi toán nói trên cũng mang các đặc thù khác nhau.
Phơng pháp để giải quyết các bi toán tồn tại thờng sử dụng các công cụ
chứng minh diễn dịch (suy diễn) hoặc phản chứng. Đối v ới các bitoánđếm
thờngsửdụngcáccôngcụchứngminhquynạphoặccáccôngcụtínhtoán,
còn đối với các bitoánliệtkêthờng sử dụng các cách thức, các thuật toán
để chỉ ra một cách tờng minh các cấu hình cần tìm.
Để giải quyết các bi toán tổ hợp ta sẽ sử dụng một số các nguyên lý cơ
bản. Các nguyên lý nyl cáccôngcụquantrọngđểgiảicácb
itoánđếm,
các bitoántồntạiv các bitoánliệtkê.
2.1.2. Nguyên lý nhân
Giả sử có một việc đợc tách thnh k côngđoạn. Côngđoạn1cóthể
thực hiện đợc bằng n
1
cách; công đoạn 2 có thể thực hiện đợc bằng n
2
cách; ; công đoạn k cóthểthựchiệnđợc bằng n