Phần thứ nhất

LÝ THUYẾT TỔ HỢP LÝ THUYẾT TỔ HỢP Combinatorial Theory

1

Fall 2008

Toán rời rạc

Fall 2008

Nội dung Nội dung

1. Mở đầu

2. Bài toán đếm tổ hợp (Counting Problem)

3. Bài toán tồn tại tổ hợp (Existence Problem)

4. Bài toán liệt kê tổ hợp (Enumeration Problem)

5. Bài toán tối ưu tổ hợp (Combinatorial

Optimization Problem)

2

Toán rời rạc

0. Mở đầu

NỘI DUNG

0.1. Tổ hợp là gì? 0.1. Tổ hợp là gì?

0.2. Sơ lược về lịch sử phát triển của tổ hợp

0.3. Tập hợp và ánh xạ

3

Toán rời rạc

0.1 Tổ hợp là gì?

 Đối tượng nghiên cứu  Nội dung nghiên cứu

4

Toán rời rạc

Đối tượng nghiên cứu của tổ hợp

ề

 Lý thuy t t

ạ

ạ

ệ ớ ắ  h p g n li n v i vi c nghiên  ầ ử ủ ự ắ ế c a các ph n t  trong các  ầ ủ ố c a  các  ph n  ự ữ s   phân  b   ế ắ ỗ ữ  vào các t p h u h n. M i cách s p x p  ộ c u ấ ư ế ượ ọ ặ c g i là m t

ổ ợ

ế ổ ợ c u ứ s  s p x p  ậ t p  h u  h n  và  ậ ử t ố ho c phân b  nh  th  đ hình t

h p.

ổ ợ

ế ề ắ ắ  T  h p là lý thuy t v

t:

ể  Có th  nói v n t ậ ữ ạ các t p h u h n.

5

Toán rời rạc

Phân loại bài toán

ườ

 Trong các tài li u v  t

h p, th

ặ ng g p các

ệ ướ ạ d ng bài toán d

ề ổ ợ i đây:

ế ế

ổ ợ ổ ợ

1. Bài toán đ m t 1. Bài toán đ m t

h p (Counting Problem)  h p (Counting Problem)

2. Bài toán t n t 2. Bài toán t n t

ồ ạ ổ ợ i t ồ ạ ổ ợ i t

h p (Existence Problem)  h p (Existence Problem)

ổ ợ ổ ợ

t kê t t kê t

h p (Enumeration   h p (Enumeration

ệ 3. Bài toán li ệ 3. Bài toán li Problem)  Problem)

ố ư ổ ợ ố ư ổ ợ

4. Bài toán t 4. Bài toán t

i  u t i  u t

h p (Combinatorial   h p (Combinatorial

optimization Problem) optimization Problem)

6

Toán rời rạc

Bài toán đếm – Counting Problem

ả ờ

i  câu  h i:  “

 Đây  là  các  bài  toán  nh m  tr   l

ấ

ề

ỏ ệ

ế

c?ướ ".  ươ

ộ

ằ Có  ả bao nhiêu c u hình tho  mãn các đi u ki n cho  tr  Ph

ả ế

ụ

ệ

ố ự ườ ng  pháp  đ m  th ng  d a  vào  m t  s   ơ ả ộ ố ế nguyên  lý  c   b n  và  m t  s   k t  qu   đ m  các  ả ấ c u hình đ n gi n.  ượ  Bài  toán  đ m  đ

ơ ế ữ

ả

ấ

ộ ự ệ

ư ứ ạ ủ

ộ c  áp  d ng  m t  cách  có  hi u  ệ qu   vào  nh ng  công  vi c  mang  tính  ch t  đánh  ấ ủ ộ giá  nh   tính  xác  su t  c a  m t  s   ki n,  tính  đ   ậ ộ ph c t p c a m t thu t toán, ...

7

Toán rời rạc

Bài toán tồn tại tổ hợp Bài toán tồn tại tổ hợp (Existence Problem)

án t n t ồ ạ

ế ỏ ả ờ âu  h i:  “T n  t

ớ  Khác v i bài to án đ m, trong bài to ầ úng  ta  c n  tr   l i  c ổ ợ ình t

ồ ạ ổ   i t i  hay  ả ãn các tính ch t đấ ã

h p tho  m

ợ h p  ch chăng c u hấ cho?”

ố ượ

 Rõ  ràng  n u  cế

ượ

ổ ợ  h p tho  m ả i  quy t  đ

ượ ể ế ó  th   đ m  đ ả ãn các tính ch t đó cho th ạ ươ ế i  t

c  s   l ấ ồ án  t n  t

ấ ng  c u  ì ta  ng

c  bài  to

hình t cũng  gi ng!ứ

ư ườ

ể  Có th  coi bài to

ợ ng h p ri

êng

án t n t ượ

ủ c a bài to

ế án đ m đ

ồ ạ c kh

i nh  tr ông?

8

Toán rời rạc

Ví dụ

ố ế ở

ờ

ủ  Bài  toán  ph   bàn  c   qu c  t

b i  các

quân bài domino:

ờ

ị ụ

ướ c 8 ộ

ố ế   “Cho bàn c  qu c t ố ở ủ

ủ

ỏ

ờ

ủ

ở

(cid:0) 8 b  đ c   kích th ệ  hai góc đ i di n và b  bài domino,  đi 2 ô  ỗ m i  quân  bài  ph   kín  2  ô  c a  bàn  c .  H i  ờ ể có  th   ph   kín  bàn  c   đã  cho  b i  31  quân  bài domino?”

9

Toán rời rạc

Bàn cờ quốc tế và quân bài domino

10

Toán rời rạc

Bàn cờ quốc tế và quân bài domino

11

Toán rời rạc

Có thể phủ bàn cờ như vậy bởi 31 quân bài domino?

 Bàn cờ còn 62 ô  31 quân bài có thể phủ kín được 62 ô  Về diện tích là có thể phủ được

12

Toán rời rạc

Không tồn tại cách phủ bàn cờ như vậy bởi 31 quân bài domino!

 Chứng minh

ủ

 M i quân bài ph  kín 1 ô  ộ

ỗ ắ

ắ

 Suy ra s  l

ng ô tr ng

ị ủ ở

tr ng và m t ô đen. ố ượ và ô đen b  ph  b i 31  quân domino là b ng ằ nhau.

ố ượ

ng ô  ầ

ạ ủ

ờ

i c a bàn c  là khác

ồ

 T  đó suy ra không t n

ế ư  Th  nh ng s  l ắ tr ng và ô đen trên ph n  còn l nhau ừ ủ ạ i cách ph !

t

13

Toán rời rạc

Có bao nhiêu cách phủ bàn cờ bởi 32 quân bài domino?

 S  t n t

ủ i cách ph

ự ồ ạ ể

ể ỉ

ễ là hi n nhiên. D   dàng có th  ch  ra vài  cách ph  ủ

ấ

ề  V n đ  “Có bao  nhiêu cách ph ?” ủ ả ễ  Không d  dàng tr

14

Toán rời rạc

l i!ờ

Có bao nhiêu cách phủ bàn cờ bởi 32 quân bài domino?

ấ ỉ  N u ch  phân bi

12 988 816     cách ph .ủ

Có 2 cách phủ bàn cờ kích thước 2(cid:0) 2

15

Toán rời rạc

ở ệ ế t hai c u hình b i  ạ ủ ọ ủ d ng hình h c c a cách ph  thì có  ấ ả t c   t

Phân biệt hai bài toán đếm và tồn tại

ể ự ồ ạ ấ i c u hình là hi n nhiên và

 Trong bài toán đ m, s  t n t ầ

ề

ấ ế ấ ự ồ ạ ấ ả i  c u  hình  là  i,  b n  thân  s   t n  t ề ả i quy t v n đ  “có hay không

ế ế ấ v n đ  là c n đ m xem có bao nhiêu. ồ ạ  Trong  bài  toán  t n  t ầ ư ậ ượ ộ ấ ủ ể ẳ ị c m t c u hình là đ  đ  kh ng đ nh

ỏ i  c u  hình  đòi  h i

• Nh ng  đ   ch   ra  s   không  t n  t ồ ạ ấ ỉ ậ ữ ph i đ a ra nh ng l p lu n tin c y

16

Toán rời rạc

ề ấ v n đ  nghi v n. C n gi ấ có” c u hình nh  v y.  • Vi c ch  ra đ ỉ ệ ồ ạ i là t n t ể ư ả ư ự ậ ậ

Bài toán liệt kê tổ hợp (Enumeration Problem)

 Bµi to¸n nµy quan t©m ®Õn viÖc ®­a ra tÊt c¶ cÊu h×nh tho¶ m·n c¸c ®iÒu kiÖn cho tr­íc. • V× thÕ lêi gi¶i cña nã cÇn ®­îc biÓu diÔn d­íi d¹ng thuËt to¸n "vÐt c¹n" tÊt c¶ c¸c cÊu h×nh. Lêi gi¶i trong tõng tr­êng hîp cô thÓ sÏ ®­îc m¸y tÝnh ®iÖn tö gi¶i quyÕt theo thuËt to¸n ®· nªu.

• Bµi to¸n liÖt kª ®­îc lµm "nÒn" cho nhiÒu bµi to¸n kh¸c. HiÖn nay, mét sè bµi to¸n ®Õm, tèi ­u, tån t¹i vÉn ch­a cã c¸ch nµo gi¶i, ngoµi c¸ch gi¶i liÖt kª.

• NÕu tr­íc ®©y, c¸ch gi¶i liÖt kª cßn mang nÆng tÝnh lý thuyÕt, th× b©y giê nã ngµy cµng kh¶ thi nhê sù ph¸t triÓn nhanh chãng cña m¸y tÝnh ®iÖn tö.

17

Toán rời rạc

Bài toán tối ưu tổ hợp (Combinatorial Problem)

ệ ố ư ỉ i  u ch  quan tâm

ố t kê, bài toán t ộ ấ ấ ớ  Khác v i bài bài toán li ộ ấ ế đ n m t c u hình "t t nh t" theo m t nghĩa  nào đ y.

 Trong  các  bài  toán  t

ượ i  u ỗ ấ ố ư ,  m i  c u  hình  đ

ị ố ự ặ

ị ử ụ ặ ữ ấ ố

ướ ệ ề ả ớ

ị ố ỏ c  gán  cho  ộ m t giá tr  s  (là giá tr  s  d ng ho c chi phí xây d ng  ấ c u hình), và bài toán đ t ra là trong s  nh ng c u hình  ấ c hãy tìm c u hình v i  tho  mãn các đi u ki n cho tr ấ ặ ấ ớ giá tr  s  gán cho nó là l n nh t ho c nh  nh t.

ề ứ ụ ễ

 Đây là bài toán có nhi u  ng d ng trong th c ti n và lý   h p đã đóng góp m t ph n đáng k  trong vi c

ự ể ệ ộ

18

Toán rời rạc

ượ ữ ệ ậ ầ ữ ế ổ ợ thuy t t ự xây d ng đ c nh ng thu t toán h u hi u.

0. Mở đầu

NỘI DUNG

0.1. Tổ hợp là gì?

0.2. Sơ lược về lịch sử phát triển của tổ hợp

0.3. Tập hợp và ánh xạ

19

Toán rời rạc

0.2. Sơ lược về lịch sử phát triển

ữ

ộ ể

ấ

ờ

ị

ể ổ ợ  Có  th   nói  là  t   h p  là  m t  trong  nh ng  ử ự lĩnh  v c  có  l ch  s   phát  tri n  lâu  đ i  nh t  ọ ủ c a toán h c

ề ị

ể

ủ ổ ợ ử  Nói  v   l ch  s   phát  tri n  c a  t ủ ể ề ị

h p  cũng  ử chính  là  nói  v   l ch  s   phát  tri n  c a  toán  h cọ

ổ ế

ậ ử ị

ử

ề ẽ ỉ ể  Vì v y, chúng ta s  ch  đi m qua vài nét v   ộ ố ị l ch s , thông qua m t s  bài toán n i ti ng  ể ủ ổ ợ  h p trong l ch s  phát tri n c a t

20

Fall 2008

Toán rời rạc

Hình vuông thần bí - Ma phương Magic Square

9

2

4

5

7

3

1

8

21

Toán rời rạc

6

Hình vuông thần bí - Ma phương Magic Square

49 2

3

5 7 8 1 6

22

Toán rời rạc

Tổng theo mỗi hàng ngang, mỗi hàng dọc cũng như mỗi đường chéo đều bằng 15

23

Toán rời rạc

Ma phương

ế ừ ờ c  bi th i  nhà  Chu  (quãng  2200 t  t

ố  B ng  s   này  đ ướ ượ c công nguyên) ả năm tr

ệ ủ

ấ ặ ượ ọ ố ả t  c a  b ng  s   ươ ng và c g i là ma ph

ờ

ằ ở

gi a bi u hi n Ngũ hành n m

trung tâm vũ

ươ

ể

ẵ

ố

ị

ị  bi u th  cho “d

ng”, các s  ch n bi u th  cho “âm”

trụ • Các s  l ố ẻ ể ố ề

đ u đ i xúng nhau qua trung tâm

ậ

ấ

ượ

ị c giá tr  360 =

• N u tính đ nh th c c a ma tr n c p 3 này ta đ

ứ ủ ị ế ộ ố s  ngày trong m t năm

ứ

ố

ị

ị

• Giá tr  tuy t đ i c a các đ nh th c con cũng là các con s  đáng

ệ ố ủ chú ý: 7, 23, 37, 53.

24

Toán rời rạc

ế ể ấ ạ i sao nó đ ổ ạ i Trung hoa c  đ i tôn th ệ ể ằ ở ữ ữ  Hãy  chú  ý  đ n  nh ng  tính  ch t  đ c  bi ể này đ  có th  th y t ườ ượ c ng đ • Con s  5 n m  ố

Ma phương bậc tuỳ ý

ố ồ n2 s  1, 2, ...,

ả ấ n là b ng g m

ươ ế

ọ

ỗ

ườ

ư

ằ

ọ

 Ma ph n2  ng c p  ượ n hàng ngang và n hàng d c sao  c x p thành  đ ỗ ố ổ cho  t ng  các  s   trên  m i  hàng  ngang  và  m i  ề ng  chéo  đ u  b ng  hàng  d c  cũng  nh   hai  đ nhau

ậ

ự

ươ

ậ

ả

ớ

ươ

ự

ươ ệ  Hi n  nay  có  thu t  toán  xây  d ng  ma  ph ng  ậ ọ ấ ự ng  b c  m i  c p.  Thu t  toán  xây  d ng  ma  ph ậ ơ ấ ơ ẻ ề   là  đ n  gi n  h n  r t  nhi u  so  v i  thu t  toán  l ẵ ậ ng b c ch n xây d ng ma ph

25

Toán rời rạc

Thuật toán xây dựng ma phương bậc lẻ

ấ

ậ Thu t toán:    ề ầ ượ     Đi n l n l ủ ả ố

ế ề ả ể ề ố ế

n2 vào các v  ị ị ố t các giá tr  s  1, 2, ...,  ứ ắ ầ ừ ở ữ  gi a dòng th  nh t  trí c a b ng, b t đ u t  ô  ể ế đi n  s   1. Ti p  đ n di chuy n lên trên và sang  ph i đ  đi n s  ti p theo.

Chú ý:

ị

ế ố

ề

• Trên dòng 1 là dòng n, bên ph i c t  ả ộ n là c t 1.ộ • N u g p v  trí đã có s  thì s  ti p theo đi n  ề ố ế ố ướ ố ừ i s  v a đi n.

ặ xu ng ngay d

26

Toán rời rạc

ươ

ạ ừ ữ

ng ma ph ượ ở

ố ượ S  l ấ (lo i tr  nh ng c u hình thu đ

ng ả ạ c b i phép quay và ph n x )

n

# Magic Squares

Chú thích

1

1

0

2

1

3

880

Frénicle de Bessy (1693)

4

R. Schroeppel (1973)

5

275 305 224 (1.7745(cid:0) 0.0016)1019

6

Berlekamp et al. (1982)  Approximation by Monte Carlo  Backtracking

(3.79809 ± 0.00050) ∙ 1034

7

Approximation by Monte Carlo  Backtracking

27

Fall 2008

Toán rời rạc

Number of distinct magic squares  (excluding those obtained by rotation and reflection)

8

(5.2225 ± 0.0018) · 1054

0.035 %

9

(7.8448 ± 0.0038) · 1079

0.049 %

10

(2.4149 ± 0.0012) · 10110

0.049 %

To determine the numbers of magic squares  following methods were used:

11

(2.3358 ± 0.0014) · 10146

0.059 %

12

(1.1424 ± 0.0010) · 10188

0.087 %

•    Exhaustive search by Standard Backtracking:  orders 4 and 5

13

(4.0333 ± 0.0054) · 10235

0.14 %

14

(1.5057 ± 0.0024) · 10289

0.16 %

•  Approximation by Monte Carlo Backtracking:  orders 6 to 20

15

(8.052 ± 0.022) · 10348

0.27 %

16

(8.509 ± 0.027) · 10414

0.31 %

17

(2.314 ± 0.009) · 10487

0.39 %

•  Estimation by statistical considerations on magic  series combined with extrapolations of known  approximations: orders greater than 20

18

(2.047 ± 0.008) · 10566

0.40 %

19

(8.110 ± 0.035) · 10651

0.44 %

20

(1.810 ± 0.008) · 10744

0.44 %

28

Fall 2008

Toán rời rạc

Các tính chất đặc biệt của các con số

 36 = 1+2+3+4+5+6+7+8 ố ẻ

ủ

ổ

ố ẵ

ầ

(T ng c a 4 s  l

và 4 s  ch n đ u tiên)

ượ

c ng

ấ i Trung hoa r t tôn sùng =

 36 = 13+23+33 ố  Con s  36 đ ẻ

ố

ườ ị

S  qu  trong Kinh d ch

ấ

 Các nhà tri

ậ ổ ạ t h c Ai c p c  đ i cũng r t tôn  ệ ượ

ng trong t

nhiên

ọ ộ ề ố ắ

ả

ự i thích

ế ọ sùng các con s : “ố M i hi n t ư cũng nh  trong xã h i đ u c  g ng gi ằ b ng các con s

ố”

29

Toán rời rạc

Số hoàn hảo

ị

ể

ả

 Bi u  th   tính  hoàn  h o:

a  đ

ế ố

ả

ố ả Dùng  s   hoàn  h o  ố ọ ượ ố ự (perfect  number).  S   t c  g i  là  s     nhiên  ướ ố ủ ổ ằ c s  c a  hoàn h o, n u s  này b ng t ng các  nó.  Ví d : ụ

• 6 = 1+2+3 • 28 = 1+2+4+7+14

ả

ố ượ

 So sánh: S  l

ố ng s

ố

nguyên t

ố ố ượ ng s  hoàn h o và S  l ạ a, b]   trên đo n [

30

Toán rời rạc

Cặp số hữu nghị

ị

ể

ữ

 Bi u th  tình h u ngh :

ọ

ị  Dùng c p s  h u  ặ ố ữ ố ự ngh  ị (pair of friendship numbers). Hai s  t   ị ế ặ ố ữ ượ nhiên a, b đ c g i là c p s  h u ngh  n u  ướ ố ủ ố ổ ố s  này b ng t ng các  c s  c a s  kia và  ng

ằ ượ ạ i c l

ụ

 Ví d : (220, 284), (1184, 1210),

(2620,2924), (5020, 5564), (6232, 6368)

31

Fall 2008

Toán rời rạc

Trò chơi với con súc sắc

ắ

ộ

 Ng

ơ ẽ ượ

ệ ủ

ộ ả

ấ

i  ch i  s   gieo  m t  (m t  vài)  con  súc  s c  c vào kh  năng xu t hi n c a các

ườ ặ và đ t cá c m t.ặ

ệ

ủ

ể

ệ

ổ

ầ ướ  H u t c de Mere phát hi n khi gieo các con súc  ấ ả ắ ố s c s  kh  năng có th  xu t hi n c a các t ng  ể đi m là khác nhau:

ụ

 Ví d : Gieo hai con súc s c,

ể

ắ • T ng đi m 7 có 6 kh  năng: (1, 6), (2, 5), (3,  ả

ổ 4)

ể

32

Toán rời rạc

• T ng đi m 6 có ? kh  năng: (1, 5), (2, 4), (3,  ả

ổ 3)

Các khả năng xuất hiện tổng điểm khi gieo hai con súc sắc

33

Toán rời rạc

Tôn Tẫn đấu ngựa

ộ

ườ

ề

ườ i th ng cu c là  ấ

ắ ơ

ấ  Có 3 vòng đ u 1, 2, 3. Ng ở ắ i th ng

ng

nhi u vòng đ u h n

ự

ạ

ạ

 Vua: Có 3 con ng a A (lo i 1), B (lo i 2) và

C (lo i 3)ạ

ự

ạ

ạ  Tôn T n: Có 3 con ng a a (lo i 1), b (lo i

ẫ 2) và c (lo i 3)ạ

34

Toán rời rạc

Lịch thi đấu của Tôn Tẫn

Vòng đấu Vua Điểm Tôn Tẫn Điểm

Vòng 1 A 1 c 0

Vòng 2 B 0 a 1

Vòng 3 C 0 b 1

35

Toán rời rạc

Tổng điểm 1 2

Bài toán tối ưu tổ hợp

ố ấ ả ạ

ể

ề

 Trong s  t cách đem l

ấ ổ ứ t c  các cách t  ch c thi đ u hãy tìm  ấ i nhi u đi m nh t

ấ ả

ổ ứ

ấ

 Có t

t c  bao nhiêu cách t

ch c thi đ u ?

ạ ượ

ượ

=>  D   dàng  tìm  đ

ể ắ

ề ế

ễ c  nhi u  đi m  c  cách  đ t  đ ẫ ấ nh t và may thay đó cũng là cách d n đ n th ng  i!ợ l

ố ượ

ấ

ơ

ễ

ề ng  vòng  đ u  nhi u  h n,  cách  tính  nh m ẩ ra

ề

ấ

ế  N u  s   l ể đi m  ph c  t p  h n  thì  không  d   dàng  ượ đ

ơ ể ạ i nhi u đi m nh t!

ứ ạ c cách đem l

36

Toán rời rạc

0. Mở đầu

NỘI DUNG

0.1. Tổ hợp là gì?

0.2. Sơ lược về lịch sử phát triển của tổ hợp

0.3. Tập hợp và ánh xạ 0.3. Tập hợp và ánh xạ

37

Fall 2008

Toán rời rạc

TẬP HỢP

ệ

ơ ả  Các khái ni m c  b n

ậ

ợ  Các phép toán t p h p

ơ ồ

 S  đ  Venn

ứ ẳ  Các đ ng th c

38

Toán rời rạc

Tập hợp

ầ ử t p c a các ph n t .

ầ ử a­z ự ụ ậ ủ ầ ử ủ  c a nó. ở A­Z, các ph n t

ấ ả ụ U  mà  t t  c   ể ượ ậ U  có  th   đ c

ầ ị c ng m đ nh.

ỉ ị

: ư ậ ợ  Ta hi u: ể T p h p nh  là s  t • Ta nói t p h p ch a các ph n t ứ ợ ậ • Các t p h p đ ệ ợ ượ ậ c ký hi u b i  • Thông  th ộ ậ ả ườ ng  ph i  có  m t  t p  vũ  tr   ầ ử ượ   đ các  ph n  t c  xét  trong  nó.  T p  ặ ượ ch  rõ ho c đ ậ ợ  Xác đ nh t p h p: • Danh sách các ph n t ầ ử

ặ ạ ầ ử ẫ i m t ph n t không d n

39

Toán rời rạc

ệ ớ S = (cid:0)  a, b, c, d (cid:0)  = (cid:0)  b, c, a, d, d (cid:0) ộ ệ (Chú ý: Vi c li t kê l p l ứ ự ệ ế ậ đ n t p m i. Th  t  li t kê là không có vai trò.)

Tập hợp

ợ

• Xác đ nh t p h p (ti p): ậ ậ

ế ự

ị • Mô t ề ệ m nh đ  lôgic:

ả ệ ử ụ ằ ợ  cách xây d ng t p h p b ng vi c s  d ng

ầ ử

t c  các ph n t

S là t p t

x sao cho x là

S = (cid:0)  x | P(x) } ầ ử ứ ệ S ch a các ph n t tho  mãn m nh đ

ầ ử ề P. ả • Ví d , ụ S = { x (cid:0)  x là sinh viên ĐHBK HN}  ậ ấ ả ọ đ c là “ sinh viên ĐHBK HN.”  t kê các ph n t :

• Li ệ     S = (cid:0)  (cid:0)

40

Toán rời rạc

ậ ố , ­3, ­2, ­1 (cid:0)  ­ t p các s  nguyên âm .

Tập hợp

ậ

ụ ườ

ng dùng

nhiên =

(cid:0)  0,1, 2, 3, (cid:0)

(cid:0)

ố

, ­3, ­2, ­1, 0, 1, 2, 3,

 Các t p vũ tr  th • R = t p s  th c ậ ố ự • N = t p s  t ậ ố ự • Z = t p các s  nguyên =  ậ

(cid:0) (cid:0)

(cid:0)

ậ

ố

• Z+ t p các s  nguyên không âm

41

Toán rời rạc

(cid:0)

Tập hợp

ầ ử ủ ậ ợ ậ  Nh n bi t các ph n t c a t p h p

ầ ử ủ S hay còn nói x thu c ộ S: x (cid:0)

S

S

ế • Ký hi u:ệ

• x là ph n t  c a  ầ ử ủ S: x (cid:0) • x không là ph n t  c a  • Ví d :ụ  G i ọ S là t p các s  nguyên t ừ ậ

ế ố 1 đ n 12. Khi

đó

5 (cid:0)

(cid:0)

S ế

S  có thu c m t t p cho

 Chú ý: Vi c bi

ư nh ng   15  ầ ử ộ t m t ph n t ề ấ

ệ ộ ậ

ộ ả c hay không là v n đ  không ph i lúc nào cũng là

ướ tr ễ d  dàng:

42

Toán rời rạc

ậ ố ỏ . H i

ố       Ví d :ụ  G i ọ P là t p các s  nguyên t       x=12121212121212121212111111111111111111111        có thu c ộ P?

Tập con

ỗ ầ ử

ậ t p con   c a

(cid:0) x [x(cid:0) A (cid:0)

• Ký hi u:ệ

ặ

A (cid:0)

B    ho c

B (cid:0)

A

• Ví d :ụ

, 11, 12 (cid:0)  và T = (cid:0)  1, 2, 3, 6 (cid:0)

• N u ế S = (cid:0)  1, 2, 3, (cid:0) T (cid:0)

ế    Th  thì

S.

43

Toán rời rạc

ế ủ ậ B n u m i ph n t ọ ượ  T p ậ A đ c a t p  c g i là  ầ ử ủ B, nghĩa là  ề c a ủ A đ u là ph n t  x(cid:0) B]

Tập con

 M t s  đ nh nghĩa:

ủ

ỉ

ầ ử ủ ậ

ứ

ộ ố ị • M t t p luôn là t p con c a chính nó. ộ ậ ậ • Hai t p là b ng nhau khi và ch  khi m i ph n t ậ ỗ ứ   c a  t p  th   hai  và  ng

ầ ử ủ ậ  c a t p  ượ ạ i,  c  l

ằ ấ ề th   nh t  đ u  là  ph n  t nghĩa là

A (cid:0)

B và B (cid:0)

A ậ

ự

• N u ế A (cid:0)

A = B   khi và ch  khi     A (cid:0)  B, nh ng ư A (cid:0) s   ự c a ủ B. Ký hi u:  ệ

ỉ  B khi đó ta nói A là t p con th c   B.

ả ử A = { 1, 2, 3 }, B = { 2, 3, 1 }, C = { 3 }

• Ví d :ụ • Gi  s   • Khi đó                     B = A, C (cid:0)  A, C (cid:0)  B.

44

Toán rời rạc

Tập con

 M t s  đ nh nghĩa:

ầ ử

nào

ậ ậ ỗ (tr ngố ) là t p không có ph n t

ộ ố ị • T p r ng

.

c .ả • Ký hi u:  ệ

(cid:0)

ủ

ậ

ọ ậ  là t p con c a m i t p

(cid:0) (cid:0)

ậ

ủ ậ A

t c  các t p con

(Power set) c a t p

• T p t

A (đôi khi dùng ký hi u: ệ P(A))

ụ ế A = {1} thì  2A = {(cid:0)

,{1}}

ầ ử

ậ

ồ n ph n t

có 2

n t p con.

ậ ấ ả • Ký hi u:  2 ệ • Ví d , n u  • T p g m  ậ

45

Toán rời rạc

Tập con

ố

ầ ử

 L c l

ng

ự ượ (cardinality) c a t p

ủ ậ A là s  ph n t

ệ ệ A| (đôi khi còn ký hi u là # A, N(A)).

ộ ậ

ạ

ở

nhiên) là vô h n, b i vì |

N| không là

trong A. • Ký hi u:  | • N u l c l ế ự ượ ọ ượ đ c  g i  là  h nạ . • Ví d :ụ  N (t p các s  t ố ự ậ  nhiên.

ố ự s  t

• Chú ý: N u |ế A| = n thì  |P(A)| = 2n.

46

Toán rời rạc

ợ ế ạ ,  n u  trái  l i  nó  là ố ự ủ ng c a m t t p h p là s  t ạ ậ ữ t p  h u  h n nhiên thì nó  ậ t p  vô

Tập con

• Ví d : ụ

• N u ế A = (cid:0)  a, b (cid:0)  thì

ậ

ủ A:

• T p các t p con c a  ậ

2A = (cid:0)

, (cid:0) a(cid:0) , (cid:0) b(cid:0) , (cid:0) a, b(cid:0)

ự ượ

ng c a

ủ A:

• L c l

|A| = |(cid:0) a, b(cid:0) | = 2

|2A| = 4

• A và 2A là các t p h u h n. ậ ữ ạ

47

Toán rời rạc

(cid:0) (cid:0)

Lý thuyết tập hợp là không hoàn chỉnh

Nghịch lý Russell (Russell’s paradox):

ứ

ư

nh  là ph n t

ợ  Xét S là t p các t p h p không ch a chính nó   c a nó:

ậ ậ ầ ử ủ                           S = {x | x(cid:0) x }.

ỏ

 Câu h i:  Có ph i

ả S (cid:0)

S?

Bertrand Russell 1872­1970

48

Toán rời rạc

Nghịch lý Russell

ố ượ

x (cid:0)

ng

ả x tho  mãn

x.

ộ ố ượ

x (cid:0)

ng

ả x tho  mãn

x.

 Cho S = {x | x(cid:0) x }.  H i ỏ S(cid:0) S? • N u ế S(cid:0) S, thì S không là đ i t      Suy ra, S(cid:0) S ?! • N u ế S(cid:0) S, thì S là m t đ i t      Suy ra, S(cid:0) S ?!

ể ế

ậ

Vì v y ta không th  k t lu n đ

ậ ượ S(cid:0) S và cũng

c

ể ế không th  k t lu n đ

ậ ượ S(cid:0) S ?! c

 Paradox!

49

Toán rời rạc

Các phép toán tập hợp

ủ

ậ A và B:

ầ ử ừ

ừ

ộ

 Giao (intersection) c a 2 t p  ộ  v a thu c vào

A v a thu c

• là t p các ph n t

A (cid:0)

B

ậ vào B.  • Ký hi u:  ệ A (cid:0)

ế

B = (cid:0)  x (cid:0)  x(cid:0) A (cid:0)  x(cid:0) B (cid:0) ậ ỗ

ượ ọ

A và B đ

c g i là

• N u giao là t p r ng, thì

không giao nhau.

50

Toán rời rạc

Các phép toán tập hợp

ủ

 H p ợ (union) c a 2 t p  ầ ử ặ

ậ A và B:  ho c thu c

• là t p t vào B.  A (cid:0) • Ký hi u:  ệ A (cid:0)

ậ ấ ả ộ t c  các ph n t ặ ộ A ho c thu c

ự ượ

ủ ợ ủ

 L c l

ng c a h p c a hai t p

ậ A và B:

?

ệ Có quan h  so sánh nào                 |A(cid:0) B|  ?   |A|  ?   |B|  ?    |A(cid:0) B|

51

Toán rời rạc

B  B = (cid:0)  x (cid:0)  x(cid:0) A (cid:0)  x(cid:0) B (cid:0)

Các phép toán tập hợp

 Hi u ệ (difference) c a ủ A và B:

ộ

ầ ử ủ A không thu c vào

B.

• là t p h p các ph n t ợ ậ • Ký hi u:  ệ

c a  A – B ho c ặ A \ B A – B = (cid:0)  x (cid:0)  x(cid:0) A (cid:0)  x(cid:0) B (cid:0)

 Hi u đ i x ng

ệ ố ứ (symmetric difference)

và B:

(B – A)

B

c a Aủ • là t p (ậ A – B) (cid:0) A (cid:0) • Ký hi u:  ệ

52

Toán rời rạc

Các phép toán tập hợp

ủ ậ A:

ầ  Ph n bù

ậ

(complement) c a t p  • là t p ậ  U – A, trong đó U  là t p vũ tr . ụ • ph n bù c a  (cid:0) A • Ký hi u:  ệ

ầ ộ ụ ủ A là ph  thu c vào U !

(cid:0) A = (cid:0)  x (cid:0)  (cid:0) (x(cid:0) A) (cid:0)

• Cách ký hi u khác:

53

Toán rời rạc

ệ Ac.

Các phép toán tập hợp

 Ví dụ:

• U = (cid:0) 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 (cid:0) • A= (cid:0) 1, 2, 3, 4, 5 (cid:0) , B = (cid:0) 4, 5, 6, 7, 8 (cid:0) . • Khi đó

=

� �

A B

=

� �

A B

=

A

=

(cid:0)

B

(cid:0)

= =

(cid:0)

=

A­B     B­A � �

A B

54

Toán rời rạc

(cid:0)

René Descartes  (1596­1650)

Tích Đề các

ặ t c  các c p có th  t

ứ ự a, b), trong đó a

(

(Cartesian product) c a ủ A v i ớ B: ề  Tích Đ ­các  • Là t p bao g m t ồ ậ

ấ ả thu c ộ A và b thu c ộ B.

• Ký hi u: ệ A (cid:0) A (cid:0)

ị  B. Theo đ nh nghĩa  B = (cid:0)  (a, b)(cid:0) a(cid:0) A (cid:0)  b(cid:0) B (cid:0)

• Ví d :ụ

• Cho A = (cid:0)  1, 2, 3 (cid:0)  và B = (cid:0)  3, 4 (cid:0) . Khi đó

A (cid:0)

B = (cid:0)  (1,3), (1,4), (2,3), (2,4), (3,3), (3,4) (cid:0)  A = (cid:0)  (3,1), (3,2), (3,3), (4,1), (4,2), (4,3) (cid:0) ng

B (cid:0)

B (cid:0)

A

ườ  B| = ?

A (cid:0) B (cid:0) • Thông th • |A (cid:0)

55

Toán rời rạc

Tích Đề các

 Ví d : ụ

ắ ườ

ỗ ơ

• A = { Th ng, M nh, Hùng, C ng }; ạ • B = { Mai, M , M n, Me, Mu m } ậ • A(cid:0) B = { (T, Mai), ..., (T, Mu m}, ...,(C, Mu m) } ở ộ

ề ậ

ề

c m  r ng cho nhi u t p:

 Tích Đ  các đ

ỗ ỗ

ượ • Cho A1, A2, ..., Am là các t p h p ợ • A1 (cid:0)

56

Toán rời rạc

... (cid:0) Ai, i = 1, 2,..., m} ậ  Am = {(a1, a2, ..., am): ai (cid:0) A2 (cid:0)

Tích Đề các

 Ví d : ụ

ắ

ườ

ỗ

• A = { Th ng, M nh, Hùng, C ng }; ạ • B = { Mai, M , M n, Me, Mu m } ậ ơ • C = { P30 ­ B4, P55­B3, P17­A1 } • A(cid:0) B(cid:0) C = {(Th ng, Mai, P30­B4), ... } ắ

 Ký hi uệ

n

...

= X X

X X 1 44 2 4 43 l�n n

57

Toán rời rạc

(cid:0) (cid:0) (cid:0)

SƠ ĐỒ VENN (John Venn 1834-1923)

 Venn diagrams:

ố

ỉ

• Là cách bi u di n r t tr c quan giúp ch  ra m i liên h   ệ

ễ ấ ự ợ ậ

ữ ậ

ễ

ở

ể

ậ

c bi u di n b i hình ch  nh t.

ụ U đ

ủ

ể

ễ

ộ

ở

ượ

ầ c bi u di n b i ph n trong c a m t

ủ U đ

ể ặ ữ gi a 2 ho c 3 t p h p. • T p vũ tr   ượ • M i t p con c a  ỗ ậ vòng kín.

 Ví d :ụ

Cho 3 tập

Cho 2 tập

58

Toán rời rạc

Ví dụ: Nhiều tập sẽ rất rối mắt!

59

Toán rời rạc

SƠ ĐỒ VENN

ẽ ơ ồ

ủ

ấ

ộ

 Ví d : ụ V  s  đ  Venn cho th y tác đ ng c a

ậ

ợ

các phép toán t p h p.

• Các mi n t ủ ộ

ề ươ ứ ớ ế ể ỉ ả ẽ ng  ng v i k t qu  s  tô đen đ  ch  ra

60

Toán rời rạc

ậ ợ tác đ ng c a phép toán t p h p.

Sơ đồ Venn

61

Toán rời rạc

Sơ đồ Venn

62

Toán rời rạc

Sơ đồ Venn

 Câu h i:ỏ

ủ A (cid:0)

B

ư

đ

c s  d ng trong logic nh  là phép

• Hãy v  s  đ  Venn c a  ẽ ơ ồ • Phép (cid:0)

ượ ử ụ toán Exclusive OR?

63

Toán rời rạc

Các đẳng thức tập hợp

ứ ậ

ợ ươ

ự ư

ẳ

 Các đ ng th c t p h p t

ng t

nh  các đ ng

ứ

ọ

ẳ th c logic. ẳ

ứ  Các đ ng th c quan tr ng:

Tên g iọ

ồ

ấ Đ ng nh t (Identity laws)

Tr iộ (Domination laws)

ồ

ứ ẳ Đ ng th c  (cid:0) A (cid:0)  = A A (cid:0)  U = A A (cid:0) A (cid:0) A (cid:0) A (cid:0)

ấ Đ ng nh t Idempotent laws

Bù (Complementation laws)

U = U  = (cid:0)  (cid:0)  A = A  A = A A=

)A

(

64

Toán rời rạc

Các đẳng thức tập hợp

 Tiếp theo:

Tên g iọ

Giao hoán Commutative laws

ế ợ K t h p Associative laws

A  A  C) = (A (cid:0)  C) = (A (cid:0)  C) = (A (cid:0)  C) = (A (cid:0)

B) (cid:0)  B) (cid:0)  B) (cid:0)  B) (cid:0)

C  C  (A (cid:0)  (A (cid:0)

C)  C)

Phân ph iố Distributive laws

ậ

(cid:0) (cid:0) (cid:0)

ứ ẳ Đ ng th c  B = B (cid:0) A (cid:0)  B = B (cid:0) A (cid:0)  (B (cid:0) A (cid:0)  (B (cid:0) A (cid:0)  (B (cid:0) A (cid:0) A (cid:0)  (B (cid:0) BABA

Lu t De Morgan De Morgan’s laws

BABA

65

Toán rời rạc

(cid:0) (cid:0) (cid:0)

Chứng minh các đẳng thức tập hợp

ứ ậ

ợ

ể ứ

 Đ  ch ng minh đ ng th c t p h p

ẳ                      A = B,

ể ử ụ

ậ

ỹ

ườ

có th  s  d ng các k  thu t th

ng dùng

sau:

ứ

1. Ch ng minh

A (cid:0)

B và B (cid:0)

A.

ươ

ủ ng c a

ị 2. S  d ng đ nh nghĩa và s  t ề

ự ươ ậ ị

ử ụ ệ

ng đ ợ

các m nh đ  logic xác đ nh t p h p.

ử ụ

ệ

ả

3. S  d ng b ng quan h  thành viên.

66

Toán rời rạc

Ví dụ 1.

ẳ

ứ A(cid:0)

CM đ ng th c:

(A(cid:0) C).

x(cid:0)

(A(cid:0) C).

ặ

 Ph n 1:ầ • Gi • Ta bi

(A(cid:0) C). (A(cid:0) C).

(B(cid:0) C)=(A(cid:0) B)(cid:0)  CM A(cid:0) (A(cid:0) B)(cid:0) (B(cid:0) C)(cid:0) ả ử x(cid:0) A(cid:0) (B(cid:0) C), c n ch  ra  ầ ỉ  s   x(cid:0) B ho c là  t ế x(cid:0) A, và ho c là  ặ • TH 1: x(cid:0) B.  Khi đó x(cid:0) A(cid:0) B, vì th  ế x(cid:0) • TH 2: x(cid:0) C. Khi đó x(cid:0) A(cid:0) C , do đó x(cid:0)

(A(cid:0) B)(cid:0)

(A(cid:0) C).

(A(cid:0) B)(cid:0)

(A(cid:0) C). (A(cid:0) B)(cid:0) x(cid:0) C. (A(cid:0) B)(cid:0) (A(cid:0) B)(cid:0)

(B(cid:0) C)(cid:0) CM (A(cid:0) B)(cid:0)

(A(cid:0) C).  A(cid:0)

ươ (A(cid:0) C) (cid:0) (B(cid:0) C). (t ự ng t )

• Suy ra, x(cid:0) • V y ậ A(cid:0) ầ  Ph n 2:

67

Toán rời rạc

Ví dụ 2

ứ

• Ch ng minh r ng

ằ =�

�

A B A B

• CM:

=�

theo ��nh ngh�a ph�n b�

A B

x

A B

(

} ))

theo ��nh ngh�a

theo ��nh ngh�a

x

} )

giao

theo lu�t DeMorgan

��� x x A x B

=

theo ��nh ngh�a ph�n b�

x A x B } ) } )

=

} { � � x x A B { = ���� x ( { = ���� ( { = { {

theo ��nh ngh�a h�p

�� x x A B

��� x x A x B } )

68

Toán rời rạc

• Q.E.D.

Bảng quan hệ thành viên

ả

ự  Xây d ng b ng:

ớ ộ ứ ứ ậ ể ợ

ệ ể ề   h p  có  th   v   quan  h

• Các c t  ng v i các bi u th c t p h p. • Các  dòng  ng  v i  m i  t ớ ứ thành viên trong các t p đang xét.

ề

ả

 Đi n vào b ng:

ọ ổ ợ ậ

• S  d ng “1” đ  ghi nh n là thành viên, “0” đ  ch  ra

ử ụ ể ể ậ ỉ

ượ

ứ

ứ

ứ ở

ể

ớ

ng  ng v i hai bi u th c

ế ế  hai v  là

ộ c  ch ng  minh  n u  hai  c t  gi ng ố

.

không là thành viên.

ẳ  Đ ng  th c  là  đ ứ ươ t ệ h t nhau

69

Toán rời rạc

Ví dụ 3

Chứng minh: (A(cid:0) B)(cid:0) B = A(cid:0) B.

AA BB AA(cid:0) 0 0 0 1 1 0 1 1

(cid:0) BB ((AA(cid:0) 0 1 1 1

(cid:0) BB))(cid:0) 0 0 1 0

(cid:0) BB (cid:0) BB AA(cid:0) 0 0 1 0

70

Toán rời rạc

Ví dụ 4

 Sử dụng bảng quan hệ thành viên, chứng

minh rằng

A (cid:0)

(B (cid:0)

C) = (A (cid:0)

B) (cid:0)

(A (cid:0)

C)

A B C B(cid:0) C A(cid:0)

(B(cid:0) C) A(cid:0) B A(cid:0) C (A(cid:0) B)(cid:0)

(A(cid:0) C)

1 1 1 1 1 0 1 0 1 1 0 0 0 1 1 0 1 0 0 0 1 0 0 0

1 1 1 0 1 1 1 0

71

Toán rời rạc

Các đẳng thức tập hợp

 Ví dụ 5:

• Cho A, B, và C là các tập hợp. Chứng minh rằng ( BC

CB

A

A

(

)

)

• CM:

=

)

)

theo lu�t De Morgan

A

( � � B C

A

( � � B C

= ��

)

theo lu�t De Morgan

( B C

A

theo lu�t giao ho�n

(

= �� ) B C

A

��i v�i ph�p giao

theo lu�t giao ho�n ��i ph�p h�p

= �� ) ( C B

A

72

Toán rời rạc

(cid:0) (cid:0) (cid:0) (cid:0) (cid:0)

Hợp của nhiều tập

ợ ủ

ậ A(cid:0) B

 H p c a hai t p:

(cid:0) …)(cid:0)

A2)

((…((A1 ứ ự

ọ

ợ ủ n t p:ậ  H p c a  (cid:0) …(cid:0) An  (cid:0) (cid:0) A2 A1 (ghép nhóm và th  t

An)  là không quan tr ng)

 Ký hi u:ệ

n

iA

(cid:0)

i

1(cid:0)

73

Toán rời rạc

Giao của nhiều tập

ậ A(cid:0) B

ủ  Giao c a hai t p:

(cid:0) A2

((…((A1 ứ ự

 Giao c a ủ n t p:ậ (cid:0) …(cid:0) An  A1 (ghép nhóm và th  t

(cid:0) A2)(cid:0) …)(cid:0) An) ọ  là không quan tr ng)

 Ký hi u:ệ

n

(cid:0)

 iA

i

1(cid:0)

74

Toán rời rạc

Biểu diễn tập hợp bởi xâu nhị phân

 Đ i v i t p vũ tr

ồ

ể ề ầ ử ụ U = { x1, x2, …, xn } g m không quá  ễ ậ S(cid:0) U .  Ta  có  th   s   d ng  bi u  di n  t p

ị ố ớ ậ nhi u  ph n  t ở b i xâu nh  phân

(cid:0) S.

• S = {2,3,5,7,11} (cid:0) • T = {1,2,4,11}    (cid:0)

S, T (cid:0) U. ể ử ụ b1b2…bn trong đó                       bi=1 (cid:0)  xi  Ví d . ụ U = {1,...,11}. Xét các t p con

ậ ợ (cid:0)  Trong cách bi u di n này các phép toán t p h p , (cid:0)

ể ệ ậ  01101010001.  11010000001. ễ ờ ,(cid:0)   ớ c th c hi n nh  phép toán logic OR, AND, NOT v i

75

Toán rời rạc

ự ượ đ ừ t ng bít!  Ví d :ụ  S (cid:0)  T =     01101010001                                    (cid:0)  11010000001                               =     11111010001

Phân hoạch

ậ

 Gi

s

ủ X. Ta nói

ả ử X1, X2, ..., Xm là các t p con c a  ạ

ạ

ộ

ủ X

ượ

ạ

X1,  X2,  ...,  Xm  t o  thành  m t  phân  ho ch  c a  (ho c ặ X  đ

c  phân  ho ch  thành  các  t p

ậ X1,

... (cid:0)

Xm ;

, i(cid:0) (cid:0)

j.

X2   Xj = (cid:0)

X2, ..., Xm ) n u:ế •    X = X1  •    Xi  (cid:0)

76

Toán rời rạc

(cid:0) (cid:0)

ÁNH XẠ

ị

 Đ nh nghĩa

ị

ạ

 Cách xác đ nh ánh x

ơ

 Đ n ánh, toàn ánh, song ánh

77

Fall 2008

Toán rời rạc

Ánh xạ

ế

t p

ộ

ạ ừ ậ X vào t p ậ Y n u nó đ t  ặ ầ ử x(cid:0) X v i m t ph n  ầ ớ

ng  ng m i m t ph n t

t t

ả

ọ

ọ ố y g i là  nh.

ả

ỗ ố ự

i  tích  chúng  ta  đã  làm  quen  ặ ươ ng  ng  m i  s   th c

ớ

 Ta nói f là ánh x  t ộ ỗ ứ ươ  ử y(cid:0) Y nào đó. • Ký hi u: ệ  f: X (cid:0) Y ho c ặ y = f(x) • x g i là g c,   Trong  giáo  trình  gi ố ự f  đ t  t ớ v i  hàm  s   th c  x(cid:0) R v i m t giá tr  th c  ộ

ứ ị ự y = f(x).

78

Toán rời rạc

Xác định ánh xạ

 Cho hai t p h u h n

ậ ữ ạ X và Y.

ị

ộ

ể

ừ X vào Y (f: X(cid:0) Y)

ạ f  t

ả

 Đ  xác đ nh m t ánh x    ộ ể ử ụ ta có th  s  d ng m t trong các cách sau: • B ng giá tr  đ y đ ị ầ ủ • S  đ  ánh x ạ ơ ồ • Ma tr n ánh x ạ ậ

79

Toán rời rạc

Xác định ánh xạ: Bảng giá trị đầy đủ

 Gi

sả ử

ể

ị

ạ f t

ừ X vào Y (f: X(cid:0) Y) có th  xác đ nh  ị ầ ủ

• X = {x1, x2,..., xm},  Y = {y1, y2,..., yn},  ộ  M t ánh x   ở ả b i b ng giá tr  đ y đ  sau đây

x

...

y=f(x)

...

xm f(xm)

x1 f(x1)

x2 f(x2)

ư ậ ầ ử X vào t p ậ n ph n ầ

ạ ừ ậ m ph n t  t p  ở ộ ả ị ỗ Nh  v y m i ánh x  t  ử Y hoàn toàn xác đ nh b i b   nh  t

80

Toán rời rạc

(f(x1), f(x2), ..., f(xm))

Sơ đồ ánh xạ

 Ánh xạ có thể xác định bởi sơ đồ như sau:

f

f

y • x • y Y • • •

• X • • • • •

81

Toán rời rạc

X S  đơ ồ Y x ồ ị ố Đ  th  hàm s

Ma trận ánh xạ

 Gi

sả ử

• X = {x1, x2,..., xm}, • Y = {y1, y2,..., yn},  ộ

ị

 M t ánh x

ừ X vào Y (f: X(cid:0) Y) có th  xác đ nh b i  ể ở c ướ m(cid:0) n v i các ph n t ầ ử ớ

ạ f t ma tr n ậ Af = {aij} kích th ắ ượ đ l� ph�n t� t��ng �ng v�i x

ị c xác đ nh theo qui t c sau đây: 1, n�u y

qua �nh xﾹ f

i

= (cid:0)

a ij

(cid:0)

j 0, n�u tr�i l�i

82

Toán rời rạc

(cid:0)

Ví dụ

• X = { Thắng, Mạnh, Hùng, Cường }; • Y = { Mai, Mơ, Mận, Me, Muỗm }

 Xét ánh xạ f từ X vào Y xác định bởi bảng giá trị đầy đủ sau:

x

Thắng

Mạnh

Hùng

Cường

y=f(x)

Mai

Mai

Mận

Muỗm

 Ánh xạ nói trên có thể cho bởi sơ đồ và ma trận như sau:

Mai M� M�n Me Mu�m

Mai

Thắng

Thắng

Mơ

Mạnh

Mạnh

=

Mận

fA

Hùng

Hùng

Me

Cường

1 0 0 0 0 � � 1 0 0 0 0 � � 0 0 0 1 0 � 0 0 0 0 1 �

� � � � � �

Cường

Muỗm

83

Toán rời rạc

Một số loại ánh xạ hay dùng

ạ

 Xét 3 lo i ánh x  hay dùng

ậ

ạ • Đ n ánh ơ • Toàn ánh • Song ánh  s

ượ

ọ c g i là

ả ử X, Y là các t p h p.  Gi ơ  Đ n ánh:

đ n ánh    khác

ợ  Ánh x  ạ f : X (cid:0) ặ ươ ế (injection) n u nó đ t t ầ ử ớ nhau c a ủ X v i hai ph n t                   x1, x2 (cid:0)  x2

X, x1 (cid:0)

ơ  Y đ ầ ử ứ ng  ng hai ph n t ủ Y.  khác nhau c a   f(x1) (cid:0)

f(x2)(cid:0)

84

Toán rời rạc

(cid:0) (cid:0)

Một số loại ánh xạ hay dùng

 Toàn ánh: Ánh x  ạ f t

ỗ ầ ử

ế ộ

ủ

ấ nh c a ít nh t m t ph n t

ọ ượ toàn  c g i là  ề ầ ử ủ Y  đ u  là    c a  ủ X qua ánh   nào đó c a

ừ X vào Y đ ánh  (surjection)  n u  m i  ph n  t ả x  ạ f.

(cid:0)

(cid:0) y(cid:0) Y, (cid:0)

x(cid:0) X: y = f(x)(cid:0)

.

ượ

ừ X vào Y đ

 Song ánh: Ánh x  ạ f t

ừ

ọ song  c g i là  ươ ọ ánh  (bijection,  one  to  one)  hay  còn  g i  là    t ng  ế ứ one­to­one correspondence), sánh, n u nó  ng 1­1( ơ ừ v a là đ n ánh v a là toàn ánh.

85

Toán rời rạc

Ví dụ

 Sơ đồ của một số ánh xạ:

• • •

• • • • • • • • • • •

•

• • • • • • • • • • •

86

Toán rời rạc

ơ Toàn ánh Đ n ánh Song ánh

Ứng dụng

 Xét  bài  toán:  Đ m  s   ph n  t

ả ử Y  là    s   ả ử  s  ta

ể ầ ử ủ ậ X.  Gi   c a  t p  ế (cid:0) ny = |Y|. Gi t:   ừ X vào Y. Khi đó

ny

(cid:0)

ế

ố  Trong tình hu ng th  ba ta gi ự ứ ượ

ậ X) vào t p các c u hình t ặ c bài toán đ m đ t  ổ ấ ừ ậ    t p các c u hình t ổ ợ ấ  h p mà ta

87

Toán rời rạc

ố ế ầ ử ủ ố ậ t p mà s  ph n t  c a nó là đã bi ạ f t ự ượ có th  xây d ng đ c ánh x   X| (cid:0) • N u ế f là đ n ánh, thì ta có | ơ • N u ế f là toàn ánh, thì ta có |X| (cid:0)  ny • N u ế f là song ánh, thì ta có |X| = ny ả ượ i đ c song ánh t ậ  (t p ờ ra, nh  xây d ng đ ầ ế ợ h p c n đ m (t p  ế ướ ố t tr đã bi ầ ử ậ Y). c s  ph n t

Ví dụ

ữ ố ứ

ỗ

ố ữ ố ứ

ữ ố  H i có bao nhiêu s  có 5 ch  s  mà m i ch  s  đ ng sau  ướ c?

ỏ ạ ớ ơ l i l n h n ch  s  đ ng tr

ươ

ộ

ọ

Gi

ữ ố ừ

ấ ầ

ứ ế ộ ố ầ ữ ố ộ  9 ch  s  1, 2, ..., 9, và ng ứ ự ắ  1, 2, ..., 9 sau khi s p x p theo th  t ố ầ ậ ộ ố ầ

ế

ng  ng v i m t cách ch n ra 5  ỗ i m i m t cách l y   tăng d n  ế ng s   c n  đ m  là

ỗ i:ả  M i m t s  c n đ m t ớ ữ ố ừ ượ ạ ch  s  t c l ế ra 5 ch  s  t ố ượ cho  ta  đúng  m t  s   c n  đ m.  V y  s   l C(9, 5).

ố ượ

ố ầ

ế

 L p  lu n  t

ta  cũng  có  s   l ữ ố ừ

ự ạ ỏ

ậ

ng  s   c n  đ m  chính  ố   dãy  1  2  3  ...  9.  V y  s

ậ ươ ố ố ầ

ậ ng  t ằ b ng  s   cách  lo i  b   4  ch   s   t ượ l

ế ng s  c n đ m là C(9, 4)

ậ ổ ợ

ứ

ậ

ượ

ằ  Nh  v y b ng l p lu n t

h p ta đã ch ng minh đ

c C(9,5)

ư ậ = C(9,4).

88

Fall 2008

Toán rời rạc

Ask questions!

89

Toán rời rạc

90

Toán rời rạc

91

Toán rời rạc