Toán học - Tập hợp, ánh xạ

1. Lý thuyết tập hợp 2. Ánh xạ  Tập hợp là khái niệm cơ bản của toán học dùng để biểu diễn 1 lực lượng nào đó  Ví dụ : Tập hợp số thực  Sơ đồ Ven :  Ký hiệu : a  A ;  Tập hợp rỗng không chứa bất kỳ phần tử nào. Ký hiệu : Ø  Liệt kê :  A={1, 2, 3, 4, a, b}  Theo tính chất :  B={ n  N | n là số chính phương}  Hai tập hợp bằng nhau khi chúng có cùng các phần tử  Cho tập hợp: và Hỏi A, B và C có bằng nhau hay không ? }012|{ 2  xxRxB}4,3{ A }2,3{ C  Nếu mọi phần tử của tập A đều là phần tử của tập B thì A là tập hợp con của B. Ký hiệu :  Ta luôn có : ;  Chứng minh hai tập hợp bằng nhau ? BA AA AØ  Cho X là một tập hợp. Khi đó tập tất cả các tập con của X được ký hiệu là P(X)  Ví dụ : Cho tập X = {a, b}  Với tập hợp |X|=k. P(X)=? ( ) { ,{ },{ },{ , }}P X a b a b  {1,2,3}, ( ) ?Y P Y   a. Phép hợp : Cho 2 tập hợp A và B. Ta nói A hợp B. Ký hiệu :  Ví dụ : A = { 1, 2 , 3}; B = { a, b, c } Xác định : ( ) ( )x A B x A x B      A B A B 1. Tính lũy đẳng : 2. Tính giao hoán : 3. Tính kết hợp : 4. Hợp với tập rỗng : A A A  A B B A   ( ) ( )A B C A B C     A A A    b. Phép giao : Giao của 2 tập hợp A và B là tập hợp tạo bởi các phần tử vừa thuộc A vừa thuộc B.  Ký hiệu :  Ví dụ : Xác định giao của hai tập hợp sau : A = { 1, 0 , 2, a, } B = { 2, 0, 1 } ( ) ( )x A B x A x B      A B 1. Tính lũy đẳng : 2. Tính giao hoán : 3. Tính kết hợp : 4. Giao với tập rỗng : Tính phân phối của phép giao và phép hợp : A A A  A B B A   ( ) ( )A B C A B C     A A   1) ( ) ( ) ( ) 2) ( ) ( ) ( ) A B C A B A C A B C A B A C              c. Phép hiệu : Hiệu của hai tập hợp là tập tạo bởi tất cả các phần tử thuộc tập A mà không thuộc tập B  Ký hiệu A\B ( \ ) ( )x A B x A x B      Phần bù : Khi thì B\A gọi là bù của A trong B. Ký hiệu hay A B A BC A  Tích Đề các của tập hợp A với tập hợp B (theo thứ tự lấy) là tập hợp bao gồm tất cả các cặp thứ tự (x,y) với  Ký hiệu AxB hoặc A.B  Chú ý: Tích của 2 tập hợp không có tính chất giao hoán.  Ví dụ : A ={1, 2} B={a, b} A x B = { (1,a), (1,b), (2,a), (2,b)} ,x A y B  ( , ) ( )x y A B x A y B      Chứng minh : và 1) 2) A B A B A B A B       )( BAxBAx  Ax Bx BxAx  BxAx   Các phép toán trên tập hợp có thể mở rộng cho nhiều hơn 2 tập hợp tạo thành 1 phân hoạch : i i i I A {x i I, x A }      i i i I A {x i I, x A }       i i i I i i i I A (x ) i I, x A       Cho hai tập hợp X, Y  . Ánh xạ giữa hai tập X và Y là một qui tắc sao cho mỗi x thuộc X tồn tại duy nhất một y thuộc Y để y = f(x)  Ta viết : : ( ) f X Y x f x  , ! : ( )x X y Y y f x      Cho :  X là miền xác định của ánh xạ.  Y là đích của ánh xạ. YB XA YXf   : f(A) = {f(x)  x  A} = {y  Y  x  A, y = f(x)} Như vậy y  f(A)  x  A, y = f(x); y  f(A)  x  A, y  f(x) f–1(B) = {x  X  f(x)  B} được gọi là ảnh ngược của B f–1(B) x  f –1(B)  f(x)  B  f gọi là đơn ánh nếu f(x1)=f(x2) thì x1=x2, hay hai phần tử khác nhau sẽ có ảnh khác nhau  Ví dụ : là một đơn ánh từ 3)( xxfx  RR  gọi là toán ánh nếu hay đều tồn tại sao cho  Khi đó người ta cũng gọi f là ánh xạ từ X lên Y Yy Xx yxf )( f )()( YfXf   Song ánh là ánh xạ vừa là đơn ánh, vừa là toàn ánh Song ánh Đơn ánh Toàn ánh Cho hai ánh xạ f : X  Y và g : Y'  Z trong đó Y  Y'. Ánh xạ tích h của f và g là ánh xạ từ X vào Z xác định bởi: h : X  Z x h(x) = g(f(x)) Ta viết: h = gof : X  Y  Z Ví dụ : )sin()( )(sin)( )(,sin)( 2 0 2 0 2 xygf xxfg yygxxf    fg0Nếu đơn ánh thì f là đơn ánh Nếu song ánh thì g và f đều là song ánh fg0 Nếu toàn ánh thì g là toàn ánh fg0 1. Định nghĩa và tính chất 2. Biểu diễn quan hệ 3. Quan hệ tương đương. Đồng dư 4. Quan hệ thứ tự. 2 Một quan hệ hai ngôi từ tập A đến tập B là tập con của tích Descartes 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 3 R = { (a1, b1), (a1, b3), (a3, b3) } A = tập sinh viên; B = các lớp học. R = {(a, b) | sinh viên a học lớp b} 4 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 1 2 3 4 1 2 3 4 Đị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 7  Quan hệ  trên Z phản xạ vì a  a với mọi a Z  Quan hệ > trên Z không phản xạ vì 1 > 1 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) 8 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) Định nghĩa. Quan hệ R trên A có tính bắc cầu 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) 9 1. Ma trận 2. Biểu diễn Quan hệ 10 Cho R 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 11 Đây là ma trận cấp 4×3 biễu diễn cho quan hệ R u v w 1 1 1 0 2 0 0 1 3 0 0 1 4 1 0 0 Định nghĩa. Cho R là quan hệ từ A = {a1, a2, , am} đến B = {b1, b2, , bn}. Ma trận biểu diễn của R là ma trận cấp m × n MR = [mij] xác định bởi 12 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à 1 2 1 0 0 2 1 0 3 1 1 Khi đó R gồm các cặp: {(a1, b2), (a2, b1), (a2, b3), (a2, b4), (a3, b1), (a3, b3), (a3, b5)} mij = 1 nếu (ai , bj)  R 0 nếu (ai , bj)  R 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 ma trận 13            10101 01101 00010 RM b1 b2 b3 b4 b5 a1 a2 a3 Biểu diễn Quan hệ  Cho R là quan hệ trên tập A, khi đó MR là ma trận vuông.  R là phản xạ nếu 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 14 u v w u 1 1 0 v 0 1 1 w 0 0 1 R là đối xứng nếu MR là đối xứng 15 u v w u 1 0 1 v 0 0 1 w 1 1 0 mij = mji R là phản xứng nếu MR thỏa: 16 u v w u 1 0 1 v 0 0 0 w 0 1 1 mij = 0 hoặc mji = 0 nếu i  j 1. Giới thiệu 2. Quan hệ tương đương 3. Biểu diễn số nguyên 4. Lớp tương đương 17  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 18 R phản xạ? R đối xứng? R bắc cầu? Đị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 : 19 Ví dụ. Quan hệ R trên các chuỗi ký tự xác định bởi aRb nếu 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 nếu a – b nguyên. Khi đó R là quan hệ tương đương Ví dụ. Cho m là số nguyên dương và R quan hệ trên Z sao cho aRb nếu a – b chia hết m, khi đó R là quan hệ tương đương.  Rõ ràng quan hệ này có tính phản xạ và đối xứng.  Cho a, b, c sao cho a – b và b – c chia hết cho m, khi đó a – c = a – b + b – c cũng chia hết cho m. Suy ra R có tính chất bắc cầu. Quan hệ này được gọi là đồng dư modulo m và chúng ta viết a  b (mod m) thay vì aRb Cho a và b là hai số nguyên. A được gọi là ước của b hay b chia hết cho nếu tồn tại số nguyên k sao a = kb 20 21 Đị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} 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, } 22 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ó 23 Định lý. Cho R là quan hệ tương đương trên tập A và a, b  A, Khi đó (i) a R b nếu [a]R = [b]R (ii) [a]R  [b]R nếu [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. Định nghĩa. 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. Người ta thường ký hiệu quan hệ thứ tự bởi  Cặp (A, ) đựợc gọi là tập sắp thứ tự hay poset  Phản xạ: a a Phản xứng: (a b)  (b a)  (a = b) Bắc cầu: (a b)  (b c)  (a c)        Giả sử A1, A2,,An là n tập hợp. Quan hệ n- ngôi xác định trên các tập A1, A2,An là một tập con của tích Descartes A1xA2xA3x..An. Hay R  A1 x A2 x A3 x..x An.  Ví dụ : A=A1=A2=A3={1, 2, 3, 4} và quan hệ (a, b, c)  R A1x A2x A3 sao cho a<b<c thì  R={(1,2,3), (1,3,4),(2,3,4)} và (3,1,2) Company Logo 1. Mệnh đề 2. Dạng mệnh đề 3. Qui tắc suy diễn 4. Vị từ, lượng từ  Là một khẳng định và có giá trị đúng hoặc sai  Câu hỏi, câu cảm thán, mệnh lệnh không là mệnh đề.  Ví dụ :  Mấy giờ rồi ?  Hôm nay là thứ 3 - Paris là thành phố của Mỹ - n là số tự nhiên - con nhà ai mà xinh thế! - 3 là số nguyên tố. - Bạn có khỏe không? - luôn dương. 2 1x  Ký hiệu: người ta dùng các ký hiệu P, Q, R để chỉ mệnh đề. Chân trị của mệnh đề: Một mệnh đề chỉ có thể đúng hoặc sai, không thể đồng thời vừa đúng vừa sai. Khi mệnh đề P đúng ta nói P có chân trị đúng, ngược lại ta nói P có chân trị sai. Chân trị đúng và chân trị sai sẽ được ký hiệu lần lượt là 1(hay Đ,T) và 0(hay S,F) Ví dụ: - 2 không là số nguyên tố - 2 là số nguyên tố - Nếu 3>4 thì trời mưa - An đang xem phim hay An đang học bài - Hôm nay trời đẹp và 1 +1 =3  Mệnh đề sơ cấp : Là mệnh đề không thể xây dựng từ các mệnh đề khác thông qua liên từ hoặc trạng từ “không”  Mệnh đề phức hợp :là mệnh đề được xây dựng từ các mệnh đề khác nhờ liên kết bằng các liên từ (và, hay, khi và chỉ khi,) hoặc trạng từ “không” - Ví dụ : 2 không là số nguyên tố 2 là số nguyên tố (sơ cấp) 3>4 thì trời mưa 1. Phủ định 2. Hội 3. Giao 4. Kéo theo (suy ra) 5. Tương đương  Phép phủ định : phủ định của mệnh đề P được ký hiệu là P hay (đọc là “không” P hay “phủ định của” P.  Bảng chân trị : P P P 1 0 0 1 Ví dụ : • 2 là số nguyên tố Phủ định: 2 không là số nguyên tố • - 1 >2 Phủ định : -1≤ 2  Phép hội (nối liền , giao): của hai mệnh đề P, Q được kí hiệu bởi P  Q (đọc là “P và Q”), là mệnh đề được định bởi : P  Q đúng khi và chỉ khi P và Q đồng thời đúng. p q pq 0 0 0 0 1 0 1 0 0 1 1 1 Ví dụ: - 3>4 và 5<6 (S) - 2 là số nguyên tố và là số chẵn (Đ) - An đang hát và uống nước (S)  Phép tuyển (nối rời , hợp): của hai mệnh đề P, Q được kí hiệu bởi P  Q (đọc là “P hay Q”), là mệnh đề được định bởi : P  Q sai khi và chỉ khi P và Q đồng thời sai. P Q P  Q 0 0 0 0 1 1 1 0 1 1 1 1 Ví dụ: - p >4 hay p >5 (S) - 2 là số nguyên tố hay là số chẵn (Đ)  Phép kéo theo: Mệnh đề P kéo theo Q của hai mệnh đề P và Q, kí hiệu bởi P  Q (đọc là “P kéo theo Q” hay “Nếu P thì Q” hay “P là điều kiện đủ của Q” hay “Q là điều kiện cần của P”) là mệnh đề được định bởi: P  Q sai khi và chỉ khi P đúng mà Q sai.  Bảng chân trị P Q PQ 0 0 1 0 1 1 1 0 0 1 1 1  Ví dụ: - Nếu 1 = 2 thì 3+5 =6 (Đ)  p >4 kéo theo 5>6 (Đ) Phép kéo theo hai chiều: Mệnh đề P kéo theo Q và ngược lại của hai mệnh đề P và Q, ký hiệu bởi P  Q (đọc là “P nếu và chỉ nếu Q” hay “P khi và chỉ khi Q” hay “P là điều kiện cần và đủ của Q”), là mệnh đề xác định bởi: P  Q đúng khi và chỉ khi P và Q có cùng chân trị Bảng chân trị : P Q PQ 0 0 1 0 1 0 1 0 0 1 1 1  Ví dụ: - 2=4 khi và chỉ khi 2+1=0 - 6 chia hết cho 3 khi và chi khi 6 chia hết cho 2 - London là thành phố nước Anh nếu và chỉ nếu thành phố HCM là thủ đô của VN - p >4 là điều kiện cần và đủ của 5 >6 T T F T  Định nghĩa: là một biểu thức được cấu tạo từ: - Các mệnh đề (các hằng mệnh đề) - Các biến mệnh đề p, q, r, , tức là các biến lấy giá trị là các mệnh đề nào đó - Các phép toán , , , ,  và dấu đóng mở ngoặc (). Ví dụ: E(p,q) = (p q) F(p,q,r) = (p  q)  (q r)  Bảng chân trị của dạng mệnh đề E(p,q,r): là bảng ghi tất cả các trường hợp chân trị có thể xảy ra đối với dạng mệnh đề E theo chân trị của các biến mệnh đề p, q, r. Nếu có n biến, bảng này sẽ có 2n dòng, chưa kể dòng tiêu đề. Ví dụ: E(p,q,r) =(p q) r . Ta có bảng chân trị sau p q r p  q (p q)  r 1 1 1 1 1 1 1 0 1 0 1 0 1 1 1 0 1 1 1 1 0 1 0 1 0 0 0 1 0 1 1 0 0 1 0 0 0 0 0 1 Hai dạng mệnh đề E và F được gọi là tương đương logic nếu chúng có cùng bảng chân trị. Ký hiệu E  F. Ví dụ (p  q)  p   q Dạng mệnh đề được gọi là hằng đúng nếu nó luôn lấy giá trị 1 Dạng mệnh đề gọi là hằng sai (hay mâu thuẫn ) nếu nó luôn lấy giá trị 0. Định lý: Hai dạng mệnh đề E và F tương đương với nhau khi và chỉ khi EF là hằng đúng. Các qui tắc thay thế Qui tắc thay thế 1. Trong dạng mệnh đề E, nếu ta thay thế biểu thức con F bởi một dạng mệnh đề tương đương logic thì dạng mệnh đề thu được vẫn còn tương đương logic với E. Qui tắc thay thế 2 Giả sử dạng mệnh đề E(p,q,r) là một hằng đúng. Nếu ta thay thế những nơi p xuất hiện trong E bởi một F(p’,q’,r’) thì dạng mệnh đề nhận được theo các biến q,r,p’,q’,r’, vẫn còn là một hằng đúng. 1. Phủ định của phủ định   p  p 2. Qui tắc De Morgan  (p  q)   p   q  (p  q)   p   q 3. Luật giao hoán p  q  q  p p  q  q  p 4. Luật kết hợp (p  q)  r  p  (q  r) (p  q)  r  p  (q  r) 5. Luật phân phối p  (q  r)  (p  q)  (p  r) p  (q  r)  (p  q)  (p  r) 6. Luật lũy đẳng p  p  p p  p  p 7. Luật trung hòa p  0  p p  1  p 8. Luật về phần tử bù p   p  0 p   p  1 9. Luật thống trị p  0  0 p  1  1 10. Luật hấp thu p  (p  q)  p p  (p  q)  p 11. Luật về phép kéo theo: p  q  p  q  q   p Qui tắc khẳng định (Modus Ponens) Qui tắc này được thể hiện bằng hằng đúng: p q p q ® \ Hoặc dưới dạng sơ đồ :  Nếu A học tốt thì A thi điểm cao  Mà A học tốt Suy ra : A thi điểm cao Qui tắc tam đoạn luận :  Qui tắc này được thể hiện bằng hằng đúng:  Hoặc dưới dạng sơ đồ :  Nếu trời mưa thì đường ướt  Nếu đường ướt thì đường trơn  Suy ra nếu trời mưa thì đường trơn Phương pháp phủ định  Qui tắc này được thể hiện bằng hằng đúng: Hoặc dưới dạng sơ đồ :  Nếu A học tốt thì A thi đậu môn TT  A không thi đậu  Suy ra : A học không tốt Qui tắc tam đoạn luận rời rạc Qui tắc này được thể hiện bằng hằng đúng: Hoặc dưới dạng sơ đồ : p q q p Ú Ø \ Ý nghĩa của qui tắc: nếu trong hai trường hợp có thể xảy ra, chúng ta biết có một trường hợp sai thì chắc chắn trường hợp còn lại sẽ đúng.  Chủ nhật, An thường lên thư viện hoặc về quê  Chủ nhật này, An không về quê  Suy ra: An lên thư viện ( ) ( )1 2 1 2... ... 0n np p p q p p p qÙ Ù Ù ® Û Ù Ù Ù ÙØ ®é ù é ùë û ë û Qui tắc mâu thuẫn  Ta có tương đương logic  Để chứng minh vế trái g là một hằng đúng ta chứng minh nếu thêm phủ định của q vào các tiền đề thì được một mâu thuẫn. Vị từ là một khẳng định p(x,y,..), trong đó x,y...là các biến thuộc tập hợp A, B,.. Cho trước sao cho: - Bản thân p(x,y,..) không phải là mệnh đề - Nếu thay x,y,.. Thành giá trị cụ thể thì p(x,y,..) là mệnh đề. Ví dụ : - p(n) = “n +1 là số nguyên tố” - q(x,y) = “x2 + y = 1” - r(x,y,z) = “x2 + y 2 >z” Cho trước các vị từ p(x), q(x) theo một biến x  A. Khi ấy - Phủ định của vị từ p(x) kí hiệu là p(x) là vị từ mà khi thay x bởi 1 phần tử cố định của A thì ta được mệnh đề (p(a)) - Phép hội (tương ứng tuyển, kéo theo) của p(x) và q(x) được ký hiệu bởi p(x)q(x) (tương ứng là p(x)q(x), p(x)q(x)) là vị từ theo biến x mà khi thay x bởi phần tử cố định a của A ta được mệnh đề p(a)q(a) (tương ứng là p(a) q(a), p(a)q(a)) Khi xét một mệnh đề p(x) với x  A. Ta có các trường hợp sau : - TH1. Khi thay x bởi 1 phần tử a tùy ý A, ta có p(a) đúng. - TH2. Với một số giá trị a  A, ta có p(a) đúng. - TH3. Khi thay x bởi 1 phần tử a tùy ý A, ta có p(a) sai. Ví dụ. Cho vị từ p(x) với xR - p(x) = “x2 +1 >0” - p(x) = “x2 -2x+1=0” - p(x) = “x2 -2x+3=0”  Định nghĩa : Cho p(x) là một vị từ theo một biến xác định trên A. Ta định nghĩa các mệnh đề lượng từ hóa của p(x) như sau:  - Mệnh đề “Với mọi x thuộc A, p(x) ”, kí hiệu bởi “x  A, p(x)”, là mệnh đề đúng khi và chỉ khi p(a) luôn đúng với mọi giá trị a  A.  - Mệnh đề “Tồn tại (ít nhất )hay có (ít nhất) một x thuộc A, p(x))” kí hiệu bởi : “x  A, p(x)” , là mệnh đề đúng khi và chỉ khi có ít nhất một giá trị x = a0 nào đó sao cho mệnh đề p(a0) đúng. : được gọi là lượng từ phổ dụng  : được gọi là lượng từ tồn tại  Ví dụ. Các mệnh đề sau đúng hay sai - “x  R, x2 + 3x + 1  0” (S) - “x  R, x2 + 3x + 1  0” (Đ) - “x  R, x2 + 1  2x” (Đ) - “x  R, x2 + 1 < 0” (S)  Cho p(x, y) là một vị từ theo hai biến x, y xác định trên AB. Ta định nghĩa các mệnh đề lượng từ hóa của p(x, y) như sau:  “x  A,y  B, p(x, y)” = “x  A, (y  B, p(x, y))”  “x  A, y  B, p(x, y)” = “x  A, (y  B, p(x, y))”  “x  A, y  B, p(x, y)” = “x  A, (y  B, p(x, y))”  “x  A, y  B, p(x, y)” = “x  A, (y  B, p(x, y))” Ví dụ. - Mệnh đề “x  R, y  R, x + 2y < 1” đúng hay sai? Mệnh đề sai vì tồn tại x0 = 0, y0 = 1  R mà x0 + 2y0  1. - Mệnh đề “x  R, y  R, x + 2y < 1” đúng hay sai? Mệnh đề đúng vì với mỗi x = a  R, tồn tại ya  R như ya = –a/2, sao cho a + 2ya < 1.  Mệnh đề “x  R, y  R, x + 2y < 1” đúng hay sai?  Mệnh đề đúng vì với mỗi x = a  R, tồn tại ya  R như  ya = –a/2, sao cho a + 2ya < 1. Mệnh đề “x  R, y  R, x + 2y < 1” đúng hay sai? Mệnh đề đúng vì tồn tại x0 = 0, y0 = 0  R chẳng hạn thỏa x0 + 2y0 < 1. Định lý. Cho p(x, y) là một vị từ theo hai biến x, y xác định trên AB. Khi đó: 1) “x  A, y  B, p(x, y)”  “y  B, x  A, p(x, y)” 2) “x  A, y  B, p(x, y)”  “y  B, x  A, p(x, y)” 3) “x  A, y  B, p(x, y)”  “y  B, x  A, p(x, y)” Phủ định của mệnh đề lượng từ hóa vị từ p(x,y,..) có được bằng các thay  thành , thay  thành  và vị từ p(x,y,..) thành  p(x,y,..) Với vị từ theo 1 biến ta có : (  ( , ,x A p x x A p x     (  ( , ,x A p x x A p x     (  ( , , , , , ,x A y B p x y x A y B p x y         (  ( , , , , , ,x A y B p x y x A y B p x y         (  ( , , , , , ,x A y B p x y x A y B p x y         (  ( , , , , , ,x A y B p x y x A y B p x y         “x  A, 2x + 1  0” “ > 0,  > 0, x  R,  x – a <   f(x) – f(a) < ”. Trả lời : “x  A, 2x + 1 > 0” “ > 0,  > 0, x  R,  x – a <   (f(x) – f(a)  )”. Nếu một mệnh đề đúng có dạng lượng từ hóa trong đó một biến x  A bị buộc bởi lượng từ phổ dụng , khi ấy nếu thay thế x bởi a  A ta sẽ được một mệnh đề đúng Ví dụ: “Mọi người đều chết” “Socrate là người” Vậy “Socrate cũng chết” , ( ) ( ) x A p x a A p a     1. Các nguyên lý 2. Giải tích tổ hợp 3. Hoán vị lặp, tổ hợp lặp 1. Nguyên lý cộng : Giả sử để làm công việc A có 2 phương pháp - Phương pháp 1 có n cách làm - Phương pháp 2 có m cách làm Khi đó số cách làm công việc A là n+m Ví dụ : Danh bạ điện thoại có 3 số ở sim 1. 5 số ở sim 2. Vậy có bao nhiêu cách để gọi một số bất kỳ từ danh bạ trên ? Cho A1, A2,.., An là các tập hữu hạn, không giao nhau từng đôi một. Khi đó : Company Logo            n i i n i AN i N UA 11 )( 2. Nguyên lý nhân Giả sử để làm công việc A cần thực hiện 2 bước - Bước 1 có n cách làm - Bước 2 có m cách làm Khi đó số cách làm công việc A là n.m Ví dụ: A B C Có 3.2 =6 con đường đi từ A đến C Ví dụ: Cho tập X ={1,2,3,4,5,0} Hỏi có bao nhiêu số tự nhiên có 3 chữ số khác nhau mà chia hết cho 2 Giải. Gọi số có 3 chữ số là abc TH1 . c=0. Khi đó c có 1 cách chọn a có 5 cách chọn ( aX\{0} ) b có 4 cách chọn ( bX\{a, 0} ) TH1 có 1.4.5 =20 TH2 . c≠0. Khi đó c có 2 cách chọn a có 4 cách chọn ( aX\{c, 0} ) b có 4 cách chọn ( bX\{a, c} ) TH2 có 2.4.4 =32 Vậy có 20+32 =52  Một hệ thống yêu cầu đăng ký password dạng như sau :  Từ 4 – 8 chữ cái  Phân biệt chữ hoa và thường  Hỏi ?  Có bao nhiêu passwords có thể ?  Sử dụng nguyên lý gì ?  Nếu password có 4 ký tự thì tỷ lệ phần trăm là bao nhiêu ? 87654 PPPPPP  Gọi Pi là tập hợp các password gồm i chữ cái. Và P là tập hợp tất cả các passwords có thể Ta có Pi rời nhau :    8 4 |||| i iPP Với mỗi Pi ta có 52 chữ cái (26 hoa và 26 thường). Ta có : 52 i Tập hợp tất cả passwords có thể : 524 + 525 + 526 + 527 + 528 3. Nguyên lý chuồng bồ câu (Derichlet) Giả sử có n chim bồ câu ở trong k chuồng đặt vào k hộp. Khi đó tồn tại ít nhất một chuồng chứa từ bồ câu trở lên, trong đó là số nguyên nhỏ nhất lớn hơn hay bằng n/k. /n k   /n k    Có 20 chim bồ câu ở trong 7 cái chuồng. Khi đó sẽ có ít nhất 1 chuồng có 3 con bồ câu trở lên  Trong 1 nhóm có 367 người thì ít nhất có 2 người sinh cùng ngày 4. Nguyên lý bù trừ. Cho A và B là hai tập hữu hạn. Khi đó |A  B|= |A|+|B| - |A  B| A  B B A  Định nghĩa : Cho A1, A2,.., An là các tập hữu hạn. Khi đó :   n i i n k nji ji nji ji n i i n i i AN AAANAANANAN 1 1 1111 ()1( ...)()()()(       A  B A  C BC A  B  C A B C |A  B  C|=? Ví dụ. Trong một lớp ngoại ngữ Anh Pháp. Có 24 HS học Tiếng Pháp, 26 học sinh học Tiếng Anh. 15 học sinh học Tiếng Anh và Tiếng Pháp. Hỏi lớp có bao nhiêu người Gọi A là những học sinh học Tiếng Pháp B là những học sinh học Tiếng Anh Khi đó. Số học sinh của lớp là |A  B |. Theo nguyên lý bù trừ ta có |A  B|= |A|+|B| - |A  B|=24+26-15=35 1. Hoán vị : Cho tập hợp A gồm n phần tử. Mỗi cách sắp đặt có thứ tự n phần tử của A được gọi là một hoán vị của n phần tử. Số các hoán vị của n phần tử ký hiệu là Pn Pn = n! = n.(n-1).(n-2)1 Quy ước 0! =1 Phép đếm Ví dụ. Cho A ={a,b,c}. Khi đó A có các hoán vị sau abc, acb, bac, bca, cab, cba Nếu A là tập hợp n phần tử thì số song ánh từ A vào A là n!  Cho X ={1,2,3,4,5}. Hỏi có bao nhiêu số tự nhiên gồm 5 chữ số khác nhau được tạo từ tập X? 2. Chỉnh hợp : Cho A là tập hợp gồm n phần tử. Mỗi bộ gồm k phần tử (1 k n) sắp thứ tự của tập hợp A được gọi là một chỉnh hợp chập k của n phần tử. Số các chỉnh hợp chập k của n ký hiệu là - Công thức   ! ! k n n A n k   k nA Ví dụ : Cho X ={abc}. Khi đó X có các chỉnh hợp chập 2 của 3 là: ab, ba, ac, ca, bc, cb. Ví dụ. Có bao nhiêu số tự nhiên gồm 3 chữ số được tạo thành từ 1,2,3,4,5,6. Kết quả: 3 6A 3.Tổ hợp : Cho tập hợp A gồm n phần tử. Mỗi tập con gồm k phần tử của A được gọi là một tổ hợp chập k của n phần tử. Số tổ hợp chập k của n phần tử được kí hiệu là hay k nC       k n   ! ! ! k n n C k n k   Tính chất : n k k n nC C   1 1 k k k n n nC C C    Ví dụ : Cho X = {1,2,3,4}. Tổ hợp chập 3 của 4 phần tử của X là {1,2,3}, {1,2,4}, {1,3,4} , {2,3,4} Một lớp có 30 học sinh. Hỏi có bao nhiêu cách chọn 10 bạn - Số cách chọn là tổ hợp chập 10 của 30. 10 30C 1. Hoán vị lặp : Cho n đối tượng trong đó có ni đối tượng loại i giống hệt nhau (i =1,2,,k ; n1+ n2,+ nk= n). Mỗi cách sắp xếp có thứ tự n đối tượng đã cho gọi là một hoán vị lặp của n. Số hoán vị của n đối tượng, trong đó có n1 đối tượng giống nhau thuộc loại 1, n2 đối tượng giống nhau thuộc loại 2,, nk đối tượng giống nhau thuộc loại k, là 1 2 ! ! !... !k n n n n Ví dụ : Có bao nhiêu chuỗi kí tự khác nhau bằng cách sắp xếp các chữ cái của từ SUCCESS? Giải : Trong từ SUCCESS có 3 chữ S, 1 chữ U, 2 chữ C và 1 chữ E. Do đó số chuỗi có được là . 7! 420 3!1!2!1!  2. Tổ hợp lặp : Mỗi cách chọn ra k vật từ n loại vật khác nhau (trong đó mỗi loại vật có thể được chọn lại nhiều lần) được gọi là tổ hợp lặp chập k của n Số các tổ hợp lặp chập k của n được ký hiệu là k nK 1 k k n n kK C   Ví dụ. Có 3 loại nón A, B, C. An mua 2 cái nón. Hỏi An có bao nhiêu cách chọn. Ta có mỗi cách chọn là mỗi tổ hợp lặp chập 2 của 3. Cụ thể AA, AB, AC, BB, BC, CC 2 2 2 3 3 2 1 4 6K C C    Nội dung 1. Đại Số Bool 2. Hàm Bool 3. Biểu đồ Karnaugh 4. Mạch logic Xét mạch điện như hình vẽ Tùy theo cách trạng thái cầu dao A, B, C mà ta sẽ có dòng điện đi qua MN. Như vậy ta sẽ có bảng giá trị sau Mở đầu A B C MN 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 1  Một đại số Bool (A,,) là một tập hợp A   với hai phép toán , , với hai ánh xạ: 5  : AA  A (x,y) xy và  : AA  A (x,y)xy thỏa 5 tính chất sau: Tính giao hoán:  x, y A xy = yx; xy = yx; 6 Tính kết hợp:  x, y, z A (xy) z = x(y z); (xy) z = x (y z). Tính phân phối :  x, y, z A x(y z) = (xy) (xz); x (y z) = (xy)  (xz). Có các phần tử trung hòa 1 và 0: x A x  1 = 1  x = x; x  0 = 0  x = x. 7 Mọi phần tử đều có phần tử bù: x A,  A, x  =  x = 0; x  =  x = 1. x x x x x 8 Xét F là tập hợp tất cả các dạng mệnh đề theo n biến p1, p2,,pn với hai phép toán hội , phép toán tuyển , trong đó ta đồng nhất các dạng mệnh đề tương đương E . Khi đó F là một đại số Bool với phần tử 1 là hằng đúng 1, phần tử 0 là hằng sai 0, phần tử bù của dạng mệnh đề E là dạng mệnh đề bù 9 Xét tập hợp B = {0, 1}. Trên B ta định nghĩa hai phép toán , như sau: Khi đó, B trở thành một đại số Bool  0 1 0 0 0 1 0 1  0 1 0 0 1 1 1 1 10 Hàm Bool n biến là ánh xạ f : Bn  B , trong đó B = {0, 1}. Hàm Bool n biến là một hàm số có dạng : f = f(x1,x2,,xn), trong đó mỗi biến trong x1, x2,, xn chỉ nhận hai giá trị 0, 1 và f nhận giá trị trong B = {0, 1}. Ký hiệu Fn để chỉ tập các hàm Bool n biến. Ví dụ. Dạng mệnh đề E = E(p1,p2,,pn) theo n biến p1, p2,, pn là một hàm Bool n biến. 11 Xét hàm Bool n biến f(x1,x2,,xn) Vì mỗi biến xi chỉ nhận hai giá trị 0, 1 nên chỉ có 2 n trường hợp của bộ biến (x1,x2,,xn). Do đó, để mô tả f, ta có thể lập bảng gồm 2n hàng ghi tất cả các giá trị của f tùy theo 2n trường hợp của biến. Ta gọi đây là bảng chân trị của f 12 Xét kết qủa f trong việc thông qua một quyết định dựa vào 3 phiếu bầu x, y, z Mỗi phiếu chỉ lấy một trong hai giá trị: 1 (tán thành) hoặc 0 (bác bỏ). Kết qủa f là 1 (thông qua quyết định) nếu được đa số phiếu tán thành, là 0 (không thông qua quyết định) nếu đa số phiếu bác bỏ. Khi đó f là hàm Bool theo 3 biến x, y, z có bảng chân trị như sau: x y z f 1 1 1 1 1 1 0 1 1 0 1 1 1 0 0 0 0 1 1 1 0 1 0 0 0 0 1 0 0 0 0 0 14 Các phép toán trên Fn được định nghĩa như sau: Phép cộng Bool : Với f, g  Fn ta định nghĩa tổng Bool của f và g: f  g = f + g – fg 15 Phép nhân Bool : Với f, g Fn ta định nghĩa tích Bool của f và g f  g = fg x=(x1,x2,,xn)B n, (f  g)(x) = f(x)g(x) Ta thường viết fg thay cho f  g 16 Phép lấy hàm bù: Với f  Fn ta định nghĩa hàm bù của f như sau: 1f f  Xét tập hợp các hàm Bool của n biến Fn theo n biến x1, x2,,xn  Mỗi hàm bool xi hay được gọi là từ đơn.  Đơn thức là tích khác không của một số hữu hạn từ đơn.  Từ tối tiểu là tích khác không của đúng n từ đơn.  Công thức đa thức là công thức biểu diễn hàm Bool thành tổng của các đơn thức.  Dạng nối rời chính tắc là công thức biểu diễn hàm Bool thành tổng của các từ tối tiểu. ix ttzzyyxx ,,,,,,, tyxtzyx ; tzyx zyzxyf  là các từ đơn là các đơn thức là một đơn thức tối tiểu Đơn giản hơn Cho hai công thức đa thức của một hàm Bool : f = m1 m2 . mk (F) f =M1  M2   Ml (G) Ta nói rằng công thức F đơn giản hơn công thức G nếu tồn tại đơn ánh h: {1,2,..,k} → { 1,2,, l} sao cho với mọi i {1,2,..,k} thì số từ đơn của mi không nhiều hơn số từ đơn của Mh(i) 19 Đơn giản như nhau Nếu F đơn giản hơn G và G đơn giản hơn F thì ta nói F và G đơn giản như nhau Công thức đa thức tối tiểu: Công thức F của hàm Bool f được gọi là tối tiểu nếu với bất kỳ công thức G của f mà đơn giản hơn F thì F và G đơn giản như nhau 20 Phương pháp biểu đồ Karnaugh Xét f là một hàm Bool theo n biến x1,x2,,xn với n = 3 hoặc 4. f là hàm Bool theo 3 biến x, y, z. Khi đó bảng chân trị của f gồm 8 hàng. Thay cho bảng chân trị của f ta vẽ một bảng chữ nhật gồm 8 ô, tương ứng với 8 hàng của bảng chân trị, được đánh dấu như sau: Trường hợp n = 3: Quy ước Các ô tại đó f bằng 1 sẽ được đánh dấu (tô đậm hoặc gạch chéo). Tập các ô được đánh dấu được gọi là biểu đồ Karnaugh của f, ký hiệu là kar(f). Khi một ô nằm trong dãy được đánh dấu bởi x thì tại đó x =1, bởi thì tại đó x =0, tương tự cho y, z. x f là hàm Bool theo 4 biến x, y, z, t. Khi đó bảng chân trị của f gồm 16 hàng. Thay cho bảng chân trị của f ta vẽ một bảng chữ nhật gồm 16 ô, tương ứng với 16 hàng của bảng chân trị, được đánh dấu như sau: Trường hợp n = 4: Với qui ước: Các ô tại đó f bằng 1 sẽ được đánh dấu (tô đậm hoặc gạch chéo). Tập các ô được đánh dấu được gọi là biểu đồ karnaugh của f, ký hiệu là kar(f). Trong cả hai trường hợp, hai ô được gọi là kề nhau (theo nghĩa rộng), nếu chúng là hai ô liền nhau hoặc chúng là ô đầu, ô cuối của cùng một hàng (cột) nào đó. Nhận xét rằng, do cách đánh dấu như trên, hai ô kề nhau chỉ lệch nhau ở một biến duy nhất. Khi một ô nằm trong dãy được đánh dấu bởi x thì tại đó x =1, bởi thì tại đó x =0, và tương tự cho y, z, t. x Định lý Cho f, g là các hàm Bool theo n biến x1,x2,,xn. Khi đó: a) kar(fg) = kar(f)kar(g). b) kar(fg) = kar(f)kar(g). c) kar(f) gồm đúng một ô khi và chỉ khi f là một từ tối tiểu Tế bào là hình chữ nhật (theo nghĩa rộng) gồm 2n-k ô Tế bào Nếu T là một tế bào thì T là biểu đồ karnaugh của một đơn thức duy nhất m, cách xác định m như sau: lần lượt chiếu T lên các cạnh, nếu toàn bộ hình chiếu nằm trọn trong một từ đơn nào thì từ đơn đó mới xuất hiện trong m. Ví dụ : Xét các hàm Bool theo 4 biến x, y, z, t. Ví dụ : Xét các hàm Bool theo 4 biến x, y, z, t. Là biểu đồ Karnaugh của đơn thức nào? Ví dụ Xét các hàm Bool theo 4 biến x, y, z, t. Là biểu đồ Karnaugh của đơn thức nào? Ví dụ : Xét các hàm Bool theo 4 biến x, y, z, t. Là biểu đồ Karnaugh của đơn thức nào? Tế bào sau: Ví dụ: Xét các hàm Bool theo 4 biến x, y, z, t. Tế bào sau: Là biểu đồ Karnaugh của đơn thức nào? Cho hàm Bool f. Ta nói T là một tế bào lớn của kar(f) nếu T thoả hai tính chất sau: Tế bào lớn. a) T là một tế bào và T  kar(f). b) Không tồn tại tế bào T’ nào thỏa T’  T và T  T’  kar(f). Hay tế bào lớn là một tế bào mà không bị phủ bởi bất kỳ một tế bào nào khác Ví dụ : Xét hàm Bool f theo 4 biến x, y, z, t có biểu đồ karnaugh như sau Kar(f) có 6 tế bào lớn như sau: Thuật toán : Biểu đồ Karnaugh 1. Vẽ biểu đồ karnaugh của f. 2. Xác định tất cả các tế bào lớn của kar(f). 3. Xác định các tế bào lớn m nhất thiết phải chọn. Ta nhất thiết phải chọn tế bào lớn T khi tồn tại một ô của kar(f) mà ô này chỉ nằm trong tế bào lớn T và không nằm trong bất kỳ tế bào lớn nào khác. Bước 4: Xác định các phủ tối tiểu gồm các tế bào lớn Nếu các tế bào lớn chọn được ở bước 3 đã phủ được kar(f) thì ta có duy nhất một phủ tối tiểu gồm các tế bào lớn của kar(f). Nếu các tế bào lớn chọn được ở bước 3 chưa phủ được kar(f) thì: Xét một ô chưa bị phủ, sẽ có ít nhất hai tế bào lớn chứa ô này, ta chọn một trong các tế bào lớn này. Cứ tiếp tục như thế ta sẽ tìm được tất cả các phủ gồm các tế bào lớn của kar(f). Loại bỏ các phủ không tối tiểu, ta tìm được tất cả các phủ tối tiểu gồm các tế bào lớn của kar(f). Biểu đồ Karnaugh  Bước 5: Xác định các công thức đa thức tối tiểu của f. Từ các phủ tối tiểu gồm các tế bào lớn của kar(f) tìm được ở bước 4 ta xác định được các công thức đa thức tương ứng của f Loại bỏ các công thức đa thức mà có một công thức đa thức nào đó thực sự đơn giản hơn chúng. Các công thức đa thức còn lại chính là các công thức đa thức tối tiểu của f. Biểu đồ Karnaugh Cho bảng chân trị của hàm Bool. Tìm công thức đa thức tối tiểu xxxx z z y y y y Các tế bào lớn xy yz xz xz yz xy f  Cho hàm Bool  Hãy tìm công thức đa thức tối tiểu zxy.y x yx  zf Tế bào lớn : zx yx zy. Tế bào lớn : zx yx zy. Chỉ cần 2 tế bào và là phủ được hàm Bool zx zy. zxy.y x yx  zf Tìm tất cả các công thức đa thức tối tiểu của hàm Bool: ( , , , ) ( )f x y z t xyzt xy xz yz xy z t      xyzt xy xz yz xyz xyt      ( , , , )f x y z t xy xzx yyzt z xyz xyt      ( , , , ) xf x y z t xyzt xz yz z x ty xy y      ( , , , )f x y z t xyzt xy yz x zz y xytx      ( , , , )f x y z t xyzt x yzy xz xyz xyt      ( , , , )f x y z t xyzt xy xz yz xyz xyt      ( , , , )f x y z t xyzt xy xz yz xyz xyt      Bước 1:Vẽ kar(f): ( , , , )f x y z t xyzt xy xz yz xyz xyt      Bước 2: Kar(f) có các tế bào lớn như sau: x yz ( , , , )f x y z t xyzt xy xz yz xyz xyt      1 2 3 4 5 6 7 8 9 10 1 2 4 5 7 8 9 10 Bước 3: Xác định các tế bào lớn nhất thiết phải chọn: x 2 3 5 6 yz - Ô 1 nằm trong một tế bào lớn duy nhất x. Ta chọn x. - Ô 3 nằm trong một tế bào lớn duy nhất yz. Ta chọn yz. ( , , , )f x y z t xyzt xy xz yz xyz xyt      1 2 3 4 5 6 7 8 9 10 Bước 4: Xác định các phủ tối tiểu gồm các tế bào lớn x yz 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 Ta được duy nhất một phủ tối tiểu gồm các tế bào lớn của kar(f): x ν yz.  Bước 5: Xác định các công thức đa thức tối tiểu của f. Ứng với phủ tối tiểu gồm các tế bào lớn tìm được ở bước 4 ta tìm được duy nhất một công thức đa thức tối tiểu của f: x  yz ( , , , )f x y z t xyzt xy xz yz xyz xyt      1 2 3 4 5 6 7 8 9 B1: Vẽ Kar(f) f yzt yzt yzt xyzt xzt     1 2 3 4 5 6 7 8 9 B2: Xác định tế bào lớn 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 f yzt yzt yzt xyzt xzt     1 2 3 4 5 6 7 8 9 B3: Xác định các tế bào lớn nhất thiết phải chọn 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 f yzt yzt yzt xyzt xzt      Bước 3: Xác định các tế bào lớn nhất thiết phải chọn  Ô 6 nằm trong một tế bào lớn duy nhất . Ta chọn  Ô 1 nằm trong một tế bào lớn duy nhất . Ta chọn  Ô 4 nằm trong một tế bào lớn duy nhất xzt . Ta chọn xzt zt zt xt xt f yzt yzt yzt xyzt xzt     1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 f yzt yzt yzt xyzt xzt     zt xt xzt  B4: Xác định các phủ tối tiểu gồm các tế bào lớn 1 2 3 4 5 6 7 8 9 B4: Xác định các phủ tối tiểu gồm các tế bào lớn 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 Còn lại ô 5 chưa bị phủ Ô 5 nằm trong 2 tế bào lớn: 2 cách chọn f yzt yzt yzt xyzt xzt     zt xt xzt  1 2 3 4 5 6 7 8 9 B4: Xác định các phủ tối tiểu gồm các tế bào lớn 1 2 3 4 5 6 7 8 9 Còn lại ô 5 chưa bị phủ Ô 5 nằm trong 2 tế bào lớn: 2 cách chọn f yzt yzt yzt xyzt xzt     zt xt xzt xyz   1 2 3 4 5 6 7 8 9 B4: Xác định các phủ tối tiểu gồm các tế bào lớn 1 2 3 4 5 6 7 8 9 Còn lại ô 5 chưa bị phủ Ô 5 nằm trong 2 tế bào lớn: 2 cách chọn f yzt yzt yzt xyzt xzt     zt xt xzt yzt    Bước 5: Xác định các công thức đa thức tối tiểu của f f yzt yzt yzt xyzt xzt     zt xt xzt xyz   zt xt xzt yzt    Haõy xaùc ñònh caùc coâng thöùc ña thöùc toái tieåu cuûa haøm Bool: )()( yxytztzxtyzxf   Bieåu ñoà Karnaugh:  Caùc teá baøo lôùn:  Caùc teá baøo lôùn baét buoäc phaûi choïn laø  Coøn laïi oâ (1,4) coù theå naèm trong 2 teá baøo lôùn tyxtzxztzyxz ,,,, tzxztxz ,, tyxzy ,  Do ñoù coù 2 coâng thöùc ña thöùc töông öùng vôùi phuû toái tieåu:  Trong ñoù chæ coù coâng thöùc thöù hai laø toái tieåu zytzxztxzf tyxtzxztxzf   1. Khái niệm cơ bản 2. Đồ thị có hướng & vô hướng 3. Đồ thị đặc biệt 4. Chu trình & Đường đi 5. Các bài toán liên quan 3 Định nghĩa 1: Đồ thị vô hướng G = (V, E) gồm: i) V là tập hợp khác rỗng mà các phần tử của nó gọi là đỉnh (vertex) của G. ii) E là đa tập hợp gồm các cặp không sắp thứ tự của hai đỉnh. Mỗi phần tử của E được gọi là một cạnh (edge) của G. Ký hiệu uv.  Nếu uv là một cung (cạnh) thì ta nói:  Đỉnh u và v kề nhau.  Đỉnh u gọi là đỉnh đầu (gốc), đỉnh v là đỉnh cuối (ngọn) của cung uv. Đỉnh v là đỉnh sau của đỉnh u.  Hai cung có cùng gốc và ngọn gọi là cung song song.  Cung có điểm gốc và ngọn trùng nhau gọi là khuyên. 5 6 b d a k e h g c a b c d b c a d  Định nghĩa 2. Đồ thị vô hướng không có cạnh song song và không có khuyên gọi là đơn đồ thị vô hướng.  Định nghĩa 3. Đồ thị vô hướng cho phép có cạnh song song nhưng không có khuyên gọi là đa đồ thị vô hướng.  Định nghĩa 4. Đồ thị vô hướng cho phép có cạnh song song và có khuyên gọi là giả đồ thị 7 8 Đa đồ thị có hướng G =(V,E) gồm: i) V là tập hợp khác rỗng mà các phần tử của nó gọi là đỉnh của G. ii) E là đa tập hợp gồm các cặp có sắp thứ tự của hai đỉnh. Mỗi phần tử của E được gọi là một cung (cạnh) của G. Ký hiệu uv. Ta nói cung uv đi từ u đến v, cung uv kề với u,v 9 b c a d a b c d Định nghĩa 6. Đa đồ thị có hướng không chứa các cạnh song song gọi là đồ thị có hướng 10  Cho hai đồ thị G1=(V1,E1) và G2=(V2,E2). Ta nói G2 là đồ thị con của G1 nếu V2  V1 và E2  E1.  Trong trường hợp V1=V2 thì G2 gọi là con bao trùm của G1. G1, G2, G3 và G4 là các đồ thị con của G, trong đó G2 và G4 là đồ thị con bao trùm của G, còn G5 không phải là đồ thị con của G.  Đơn đồ thị G’=(V,E’) được gọi là đồ thị bù của đơn đồ thị G=(V,E) nếu G và G’ không có cạnh chung nào (E  E’=) và G  G’là đồ thị đầy đủ.  Cho đồ thị vô hướng G = (V,E). Bậc của đỉnh v, ký hiệu deg(v), là số cạnh kề với v, trong đó một khuyên tại một đỉnh được đếm hai lần cho bậc của đỉnh ấy. 15 Bậc của đỉnh 16 c a b d Bậc đỉnh a: deg(a) = 2 Bậc đỉnh b: deg(b) = 5 Bậc đỉnh c: deg(c) = 3 Bậc đỉnh d: deg(d) = 2 1) deg-(v):= số cung có đỉnh cuối là v, gọi là bậc vào của v. 2) deg +(v):= số cung có đỉnh đầu là v,gọi là bậc ra của v 3) deg(v):= deg- (v) + deg+(v)  Đỉnh bậc 0 gọi là đỉnh cô lập. Đỉnh bậc 1 gọi là đỉnh treo 17 Cho đồ thị có hướng G = (V, E), vV 18 a b d c f e Bậc của các đỉnh? 19 a b d c f e Bậc đỉnh a: Bậc đỉnh b: Bậc đỉnh c: Bậc đỉnh d: Bậc đỉnh e: Bậc đỉnh f: deg-(a)= 1 ; deg+(a)=1 deg-(b)= 1 ; deg+(b)=3 deg-(c)= 1 ; deg+(c)=2 deg-(d)= 0 ; deg+(d)=0 deg-(e)= 1 ; deg+(e)=0 deg-(f)= 2 ; deg+(f)=0 Cho đồ thị G = (V,E), m là số cạnh (cung) 2 deg( ) v V m v   20 Định lí 1) 2) Nếu G có hướng thì: deg ( ) deg ( )m v v v V v V       3) Số đỉnh bậc lẻ của đồ thị là số chẵn Ta sử dụng ma trận kề. Cho G = (V,E) với V={1,2,,n}. Ma trận kề của G là ma trận A = (aij)n xác định như sau: aij = số cạnh (số cung) đi từ đỉnh i đến đỉnh j 21 Biểu diễn ma trận của đồ thị. 22 c a b d             0 1 1 0 1 0 1 1 1 1 0 1 0 1 1 0 b a c d a b c d Tìm ma trận kề 23 a b d c f e                    0 2 1 0 0 0 2 0 1 0 1 1 1 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 1 1 0 0 0 a b c d e f a b c d e f Tìm ma trận kề  Với mỗi đỉnh của đồ thị ta xây dựng một danh sách móc nối chứa các đỉnh kề với đỉnh này: Danh sách này được gọi là danh sách kề.  Một đồ thị được biểu diễn bằng một mảng các danh sách kề a b e d c Cho hai đơn đồ thị G = (V,E) và G’= (V’,E’). Ta nói rằng G đẳng cấu G’, ký hiệu G  G’, nếu tồn tại song ánh f :V→ V’sao cho: uv là cạnh của G  f(u)f(v) là cạnh của G’ 26 Đẳng cấu 27  Nếu G và G’ là các đơn đồ thị vô hướng đẳng cấu qua ánh xạ f thì chúng có:  Cùng số đỉnh  Cùng số cạnh  Cùng số đỉnh với bậc cho sẵn (vd: số đỉnh bậc 2 của G và G’ bằng nhau)  deg v = deg f(v) Đẳng cấu 28 Đẳng cấu a b c d e a b c d e deg(e) = 1 Không có đỉnh bậc 1 Không đẳng cấu 29 Ví dụ a b c d e f 1 2 3 6 5 4 30 Đẳng cấu a b 4 d e 1 2 3 c 5 31 Không đẳng cấu 32 a b c d e  Đồ thị đầy đủ  Đồ thị phẳng  Đồ thị thành phần, đồ thị con  Đồ thị đầy đủ n đỉnh, ký hiệu là Kn, là đơn đồ thị mà hai đỉnh phân biệt bất kỳ của nó luôn liền kề. Kn có cạnh và mỗi đỉnh của Kn có bậc là n1. 2 )1( nn  Đơn đồ thị n đỉnh v1, v2, ..., vn (n3) và n cạnh (v1,v2), (v2,v3), ..., (vn-1,vn), (vn,v1) được gọi là đồ thị vòng, ký hiệu là Cn. Như vậy, mỗi đỉnh của Cn có bậc là 2.  Từ đồ thị vòng Cn, thêm vào đỉnh vn+1 và các cạnh (vn+1,v1), (vn+1,v2), ..., (vn+1,vn), ta nhận được đơn đồ thị gọi là đồ thị bánh xe, ký hiệu là Wn. Như vậy, đồ thị Wn có n+1 đỉnh, 2n cạnh, một đỉnh bậc n và n đỉnh bậc 3.  Đơn đồ thị 2n đỉnh, tương ứng với 2n xâu nhị phân độ dài n và hai đỉnh kề nhau khi và chỉ khi 2 xâu nhị phân tương ứng với hai đỉnh này chỉ khác nhau đúng một bit được gọi là đồ thị lập phương, ký hiệu là Qn.  Mỗi đỉnh của Qn có bậc là n và số cạnh của Qn là n.2 n- 1 (từ công thức 2|E| = ).  Vv v)deg(  Đơn đồ thị G=(V,E) sao cho V=V1V2, V1V2=, V1, V2 và mỗi cạnh của G được nối một đỉnh trong V1 và một đỉnh trong V2 được gọi là đồ thị phân đôi.  Nếu đồ thị phân đôi G=(V1V2,E) sao cho với mọi v1V1, v2V2, (v1,v2)E thì G được gọi là đồ thị phân đôi đầy đủ. Nếu |V1|=m, |V2|=n thì đồ thị phân đôi đầy đủ G ký hiệu là Km,n. Như vậy Km,n có m.n cạnh, các đỉnh của V1 có bậc n và các đỉnh của V2 có bậc m.  Bài toán : 3 nhà có 3 cái giếng  Một đồ thị được gọi là phẳng nếu nó có thể vẽ được trên một mặt phẳng mà không có các cạnh nào cắt nhau  Định lý : Trong một đồ thị phẳng liên thông tuỳ ý, luôn tồn tại ít nhất một đỉnh có bậc không vượt quá 5. Định nghĩa. Cho G = (V,E). Trên V ta định nghĩa quan hệ tương đương như sau: u~v  u = v hay có một đường đi từ u đến v a) Nếu u~v thì ta nói hai đỉnh u và v liên thông với nhau b) Mỗi lớp tương đương được gọi là một thành phần liên thông của G c) Một đồ thị (vô hướng) được gọi là liên thông nếu có đường đi giữa mọi cặp đỉnh phân biệt của đồ thị. 44 45 Liên thông Không liên thông Cho G = (V,E) là đồ thị vô hướng liên thông a) Đỉnh v được gọi là đỉnh khớp nếu G – v không liên thông (G – v là đồ thị con của G có được bằng cách xoá v và các cạnh kề với v) b) Cạnh e được gọi là cầu nếu G- e không liên thông( G-e là đồ thị con của G có được bằng cách xoá cạnh e). 46 Trong đồ thị trên, các đỉnh khớp là v, w, s và các cầu là (x,v), (w,s). Đỉnh khớp là v, w, s và các cầu là (x,v), (w,s).  Mệnh đề 1 : Đơn đồ thị mà bậc của mỗi đỉnh của nó không nhỏ hơn một nửa số đỉnh là đồ thị liên thông.  Mệnh đề 2: Nếu một đồ thị có đúng hai đỉnh bậc lẻ thì hai đỉnh này phải liên thông, tức là có một đường đi nối chúng.  Mệnh đề 3 : Cho G=(V,E) là một đồ thị liên thông. Khi đó một đỉnh của G là điểm khớp khi và chỉ khi trong G tồn tại hai đỉnh u và v sao cho mỗi đường đi nối u và v đều phải đi qua đỉnh này.  Cho G là một đơn đồ thị có n đỉnh, m cạnh và k thành phần liên thông. Khi đó : 2 )1)((   knkn mkn 2 )1)((   knkn mkn  Đồ thị có hướng G được gọi là liên thông mạnh nếu với hai đỉnh phân biệt bất kỳ u và v của G đều có đường đi từ u tới v và đường đi từ v tới u.  Đồ thị có hướng G được gọi là liên thông yếu nếu đồ thị vô hướng nền của nó là liên thông.  Đồ thị có hướng G được gọi là liên thông một chiều nếu với hai đỉnh phân biệt bất kỳ u và v của G đều có đường đi từ u tới v hoặc đường đi từ v tới u. Đồ thị G là liên thông mạnh nhưng đồ thị G’ là liên thông yếu (không có đường đi từ u tới x cũng như từ x tới u). Cho G = (V,E) là đồ thị vô hướng u,vV a) Đường đi (dây chuyền) có chiều dài k nối hai đỉnh u,v là dãy đỉnh và cạnh liên tiếp nhau v0e1v1e2vk-1ekvk sao cho: v 0=u ,v k = v, e i=v i-1v i , i=1,2,,k 52 a) Đường đi không có cạnh nào xuất hiện quá một lần gọi là đường đi đơn b) Đường đi không có đỉnh nào xuất hiện quá một lần gọi là đường đi sơ cấp c) Đường đi được gọi là chu trình nếu nó bắt đầu và kết thúc tại cùng một đỉnh 53 54 • x, y, z, w, v, y là đường đi đơn (không sơ cấp) độ dài 5; • x, w, v, z, y không là đường đi vì (v, z) không là cạnh; • y, z, w, x, v, u, y là chu trình sơ cấp độ dài 6. Bài toán. Thị trấn Königsberg chia thành 4 phần bởi các nhánh của dòng sông Pregel Bốn phần này được nối kết bởi 7 cây cầu 55 Đường đi Euler Câu hỏi. Có thể đi qua bảy cây cầu mà không có cây cầu nào đi quá 1 lần Định nghĩa. 1. Đường đi Euler là đường đi qua tất cả các cạnh mỗi cạnh (cung) đúng một lần. Chu trình Euler là chu trình đi qua tất cả các cạnh của đồ thị mỗi cạnh đúng một lần. 2. Đồ thị được gọi là đồ thị Euler nếu nó có chu trình Euler 57 Điều kiện cần và đủ. Cho G = (V,E) là đồ thị vô hướng liên thông. G là đồ thị Euler  Mọi đỉnh của G đều có bậc chẵn. Nếu G có hai đỉnh bậc lẻ còn mọi đỉnh khác đều có bậc chẵn thì G có đường đi Euler 58 Nhận xét. - Nếu đồ thị G có 2 đỉnh bậc lẻ thì G có 1 đường đi Euler - Nếu đồ thị G có 2k đỉnh bậc chẵn thì ta có thể vẽ đồ thị bằng k nét Chu trình Euler Không có Euler Đường đi Euler Không có Euler Chu trình Euler Đường đi Euler  Ta có thể vạch được một chu trình Euler trong đồ thị liên thông G có bậc của mọi đỉnh là chẵn theo thuật toán Fleury. Xuất phát từ một đỉnh bất kỳ của G và tuân theo hai quy tắc sau:  1. Mỗi khi đi qua một cạnh nào thì xoá nó đi; sau đó xoá đỉnh cô lập (nếu có);  2. Không bao giờ đi qua một cầu, trừ phi không còn cách đi nào khác. 60 •Xuất phát từ u, ta có thể đi theo cạnh (u,v) hoặc (u,x), giả sử là (u,v) (xoá (u,v)). •Từ v có thể đi qua một trong các cạnh (v,w), (v,x), (v,t), giả sử (v,w) (xoá (v,w)). •Tiếp tục, có thể đi theo một trong các cạnh (w,s), (w,y), (w,z), giả sử (w,s) (xoá (w,s)). •Đi theo cạnh (s,y) (xoá (s,y) và s). Vì (y,x) là cầu nên có thể đi theo một trong hai cạnh (y,w), (y,z), giả sử (y,w) (xoá (y,w)). • Đi theo (w,z) (xoá (w,z) và w) và theo (z,y) (xoá (z,y) và z). •Tiếp tục đi theo cạnh (y,x) (xoá (y,x) và y). Vì (x,u) là cầu nên đi theo cạnh (x,v) hoặc (x,t), giả sử (x,v) (xoá (x,v)). • Tiếp tục đi theo cạnh (v,t) (xoá (v,t) và v), theo cạnh (t,x) (xoá cạnh (t,x) và t), cuối cung đi theo cạnh (x,u) (xoá (x,u), x và u).  Nếu G là một đồ thị liên thông có q cạnh thì hành trình ngắn nhất trong G có chiều dài : q + m(G)  Với m(G) là số cạnh mà hành trình đi qua hai lần và được xác định như sau:  Gọi V0(G) là tập hợp các đỉnh bậc lẻ (2k đỉnh) của G. Ta phân 2k phần tử của G thành k cặp, mỗi tập hợp k cặp gọi là một phân hoạch cặp của V0(G).  Ta gọi độ dài đường đi ngắn nhất từ u đến v là khoảng cách d(u,v). Đối với mọi phân hoạch cặp Pi, ta tính khoảng cách giữa hai đỉnh trong từng cặp, rồi tính tổng d(Pi). Số m(G) bằng cực tiểu của các d(Pi):  Tập hợp các đỉnh bậc lẻ VO(G)={B, G, H, K} và tập hợp các phân hoạch cặp là P={P1, P2, P3}, trong đó :  P1 = {(B, G), (H, K)}  d(P1) = d(B, G)+d(H, K) = 4+1 = 5,  P2 = {(B, H), (G, K)}  d(P2) = d(B, H)+d(G, K) = 2+1 = 3,  P3 = {(B, K), (G, H)}  d(P3) = d(B, K)+d(G, H) = 3+2 = 5.  m(G) = min(d(P1), d(P2), d(P3)) = 3.  Do đó GT có được từ G bằng cách thêm vào 3 cạnh: (B, I), (I, H), (G, K) và GT là đồ thị Euler. Vậy hành trình ngắn nhất cần tìm là đi theo chu trình Euler trong GT: A, B, C, D, E, F, K, G, K, E, C, J, K, H, J, I, H, I, B, I, A.  Đường đi Hamilton là một đường đi trong đồ thị vô hướng đi qua tất cả các đỉnh của đồ thị, mỗi đỉnh đúng một lần.  Một Chu trình Hamilton là một đường đi Hamilton sau đi qua tất cả các đỉnh của đồ thị thì trở về đỉnh xuất phát. Chu trình Hamilton Đường đi Hamilton Không Hamilton  Định lý Dirac : Nếu G là một đơn đồ thị có n đỉnh và mọi đỉnh của G đều có bậc không nhỏ hơn n/2 thì G là một đồ thị Hamilton.  Hệ quả : Nếu G là đơn đồ thị có n đỉnh và mọi đỉnh của G đều có bậc không nhỏ hơn (n-1)/2 thì G là đồ thị nửa Hamilton.  Định lý Ore : Nếu G là một đơn đồ thị có n đỉnh và bất kỳ hai đỉnh nào không kề nhau cũng có tổng số bậc không nhỏ hơn n thì G là một đồ thị Hamilton.  Định lý: Nếu G là đồ thị 2 phe(phân đôi) với hai tập đỉnh là V1, V2 có số đỉnh cùng bằng n (n  2) và bậc của mỗi đỉnh lớn hơn n/2 thì G là một đồ thị Hamilton  Đồ thị đầy đủ Kn với n lẻ và n  3 có đúng (n-1)/2 chu trình Hamilton phân biệt.  Đồ thị G này có 8 đỉnh, đỉnh nào cũng có bậc 4, nên G là đồ thị Hamilton  Đồ thị G này có 5 đỉnh bậc 4 và 2 đỉnh bậc 2 kề nhau nên tổng số bậc của hai đỉnh không kề nhau bất kỳ bằng 7 hoặc 8, nên G là đồ thị Hamilton  Đồ thị phân đôi này có bậc của mỗi đỉnh bằng 2 hoặc 3 (> 3/2), nên nó là đồ thị Hamilton.  Đồ thị Hamilton với chu trình Hamilton A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, A  Cây là một đồ thị vô hướng liên thông, không chứa chu trình và có ít nhất hai đỉnh.  Một đồ thị vô hướng không chứa chu trình và có ít nhất hai đỉnh gọi là một rừng. Trong một rừng, mỗi thành phần liên thông là một cây.  Trong đồ thị liên thông G, nếu ta loại bỏ cạnh nằm trên chu trình nào đó thì ta sẽ được đồ thị vẫn là liên thông.  Nếu cứ loại bỏ các cạnh ở các chu trình khác cho đến khi nào đồ thị không còn chu trình (vẫn liên thông) thì ta thu được một cây nối các đỉnh của G. Cây đó gọi là cây khung hay cây bao trùm của đồ thị G.  Trước hết sắp xếp các cạnh của đồ thị G theo thứ tự không giảm của trọng số. : 1. Bắt đầu từ đồ thị rỗng T có n đỉnh.Sắp xếp các cạnh của G theo thứ tự tăng dần về trọng số. 2. Bắt đầu từ cạnh đầu tiên của dãy này, ta cứ thêm dần các cạnh của dãy đã được xếp vào T theo nguyên tắc cạnh thêm vào không được tạo thành chu trình trong T. 3. Lặp lại Bước 3 cho đến khi nào số cạnh trong T bằng n1, ta thu được cây khung nhỏ nhất cần tìm. Sắp xếp các cạnh của đồ thị theo thứ tự trọng số tăng dần : {(v3, v5), (v4, v6), (v4, v5), (v5, v6), (v3, v4), (v1, v3), (v2, v3), (v2, v4), (v1, v2)}.