GIÁO TRÌNH TOÁN Ch NG D NG TIN H C ng 1 : C I. Khái ni m m nh S Biên so n : Gv. Ph m Phúc Th nh LOGIC và chân tr 1. Các khái ni m M nh toán h c là các phát bi u di n t m t ý t ng tr n v n và ta có th kh ng nh m t cách khách quan là nó úng ho c sai. Tính ch t c t y u c a m t m nh là nó úng ho c sai, và không th v a úng v a sai. Giá tr úng ho c sai c a m t m nh c g i là chân tr c a m nh . V m t ký hi u, ta th ng dùng các m u t (nh p, q, r, ...) ký hi u cho các m nh , và chúng c ng c dùng ký hi u cho các bi n logic, t c là các bi n l y giá tr úng ho c sai. Chân tr “ úng” th ng c vi t là 1, và chân tr “sai” c vi t là 0. 2. M nh s c p – m nh ph c h p M nh sơ c p là các “nguyên t ” theo ngh a là nó không th c phân tích thành m t hay nhi u (t hai tr lên) m nh thành ph n ơn gi n hơn. M nh ph c h p là m nh c t o thành t m t hay nhi u m nh khác b ng cách s d ng các liên k t logic nh t “không” dùng trong vi c ph nh m t m nh , các t n i: “và”, “hay”, “ho c”, “suy ra”, v.v.... II. Các phép toán m nh 1. B ng chân tr Các phép toán logic c nh ngh a b ng b ng chân tr (truth table). B ng chân tr xác nh chân tr c a m nh ph c h p theo t ng tr ng h p c a các chân tr c a các m nh sơ c p t o thành m nh ph c h p.. Tác d ng c a b ng chân tr • Kê ra s liên h chân tr gi!a m nh ph c h p v"i chân tr c a các m nh sơ c p c u thành nó, • li t kê s liên h chân tr gi!a các m nh v"i các m nh ơn gi n hơn c u thành chúng. 2. Phép ph nh Cho p là m t m nh m nh p. “S ph nh” ng , chúng ta dùng ký hi u ¬p ch# m nh c nh ngh a b i b ng chân tr sau ây: P ¬p 1 0 0 1 Ký hi u ¬ c c là “không” M nh ph nh ¬ p có chân tr là úng (1) khi m nh c l i ¬ p có chân tr sai (0) khi p có chân tr úng (1). ph nh c a p có chân tr sai (0), 3. Phép h i Cho p và q là hai m nh . Ta ký hi u m nh “p hay q” là p Λ q. Phép “và”, ký hi u là Λ , c nh ngh a b i b ng chân tr sau ây: p q pΛq 0 0 0 1 0 0 1 GIÁO TRÌNH TOÁN NG D NG TIN H C Biên so n : Gv. Ph m Phúc Th nh 1 0 0 1 1 1 Nh n xét: B ng cách l$p b ng chân tr , ta có: • Các m nh p và p Λ p luôn có cùng chân tr . • M nh p%Λ¬ Λ¬ p luôn có chân tr b ng 0 (t c là m t m nh luôn sai). 4. Phép tuy n Cho p và q là hai m nh . Ta ký hi u m nh “p hay q” làà p∨q. Phép “hay”, ký hi u là ∨ , c nh ngh a b i b ng chân tr sau ây: p q p∨q 0 0 0 0 1 1 1 0 1 1 1 1 Nh n xét : • Cho p là m t m nh ,ta có m nh p ∨¬ p luôn luônn úng. • Ng i ta còn òn s d ng phép “tuy n lo i” trong vi c liên li k t các m nh . Cho p và q là hai m nh . Ta ký hi u m nh “p tuy tu n lo i q” là p⊕q. Phép “tuy n lo i”, ký hi u là ⊕, c nh ngh a b i b ng chân tr sau ây: p q 0 0 0 0 1 1 1 0 1 1 1 0 p q Chân tr c a m nhh p ⊕q ph thu c vào các chân tr c a 2 m nh p, q : m nh p ⊕q úng khii trong tr 2 m nh p và q có m t m nh úúng, m t m nh sai. 5. Phép kéo theo Phép kéo theo, ký hi h ub i→, c a ra mô hình cho ho lo i phát bi u i u ki n có d ng : “n u . . . th thì . . .”. Cho p và q là 2 m nh , ta s&& vi t p→ q di n t phát bi u “n u p thì q”. Phép Ph toán kéo theo → c nh ngh a b i b ng chân tr sau ây: p q p→q 0 0 1 0 1 1 2 GIÁO TRÌNH TOÁN NG D NG TIN H C Biên so n : Gv. Ph m Phúc Th nh 1 0 0 1 1 1 M nh p → q, c c là “n u p thì q”, còn c phát át bi u d "i các d ng khác sau ây: “q n u p”; “p ch# n u q”; “p là i u ki n cho q”. “q là i u ki n c n cho p”. 6. Phép kéo theo 2 chi u Phép kéo theo 2 chi hi u hay phép t ơng hình cho lo i phát bi u i u ki n hai chi u có d q là 2 m nh , ta vi t p ↔q ↔ di n t phát bi ơng c nh ngh a b i b ng chân tr sau ơng, ký hi u b i↔ ↔, c a ra mô ng : “. . . n u và ch n u . . .”. Cho p và u “p n u và ch## n u q”. Phép toán t ơng ây: p q p↔q 0 0 1 0 1 0 1 0 0 1 1 1 M nh p ↔q, c c là “p n u và ch# n u q”, còn d ng khác sau ây: “p khii và v ch# khi q”; “p la‘ i u ki n c n va‘ c phát bi u d "i các cho c q”. 7. Ð ưu tiên c a các toán án t logic. T ơng t nh i v"i v" các phép toán s h c, tránh ph i dùùng nhi u d u ngo c trong các bi u th c logic,, ta a ra m t th t u tiên trong vi c tính nh toán. ' trên ta có 5 toán t logic:¬ (không) , ∧ (và), ∨ (hay), → (kéo theo), ↔ ( t ơng ơng) ơ ¬ ∧,∨ →↔ trong ó, các toán t lii t kê trên cùng dòng có cùng u tiên. III. D ng m nh vvà các lu t logic Trong phép tính m nh ta c ng có các bi u th c logic c xây d ng t : • Các m nh hay các giá tr h ng. • Các bi n m nh n . • Các phép toá oán logic, và c các d u ngo c “( )” ch# h# rõ th t th c hi n c a các phépp toán. Gi s E, F là 2 bi u th c logic, khi y ¬ E, E ∧ F, E → F, E ↔ F c ng là các bi u th c logic. Ví d : Bi u th c E( E(p,q,r) = (((¬ p) ∨ q)→ (r ∧ s)) là m t bii u th c logic trong ó p, q, r là các bi n m nh . 1. B ng chân tr c a m t bi u th c logic B ng chân tr c a m t bi u th c logic là b ng li t kê chân tr c a bi u th c logic theo các tr ng h p v châ chân tr c a t t c các bi n m nh trongg bi u th c logic hay theo các b giá tr c a b bi n m nh . Ví d 1: B ng chân ân tr c a các bi u th c logic p→ q và ¬ p ∨ q theo các bi n m nh p,q nh sau: 3 GIÁO TRÌNH TOÁN NG D NG TIN H C Biên so n : Gv. Ph m Phúc Th nh P q p→ →q ¬p ¬p∨q 0 0 1 1 1 0 1 1 1 1 1 0 0 0 0 1 1 1 0 1 2. S tư ng ư ng logic Hai bi u th c logic E và F theo các bi n m nh nào ó ư c g i là tương ương logic khi E và F luôn luôn có cùng chân tr trong m i trư ng h p chân tr c a b bi n m nh . Khi ó ta vi t: E ⇔ F c là “E t ơng ơng v"i F”. Nh v$y, theo nh ngh a ta có th ki m tra xem 2 bi u th c logic có t ơng ơng hay không b ng cách l$p b ng chân tr c a các bi u th c logic. 3. Bi u th c h ng úng, bi u th c h ng sai Bi u th c logic E c g i là h ng úng n u chân tr c a E luôn luôn b ng 1 ( úng) trong m i tr ng h p v chân tr c a các bi n m nh trong bi u th c E. Nói m t cách khác, E là m t h ng úng khi ta có: E ⇔1. Bi u th c logic E c g i là h ng sai n u chân tr c a E luôn luôn b ng 0 (sai) trong m i tr ng h p v chân tr c a các bi n m nh trong bi u th c E. Nói m t cách khác, E là m t h ng úng khi ta có: E ⇔ 0. Ta có th ki m tra xem m t bi u th c logic có ph i là h ng úng (h ng sai) hay không b ng cách l$p b ng chân tr c a các bi u th c logic. Lưu ý: Gi s E và F là 2 bi u th c logic. Khi ó, E t ơng ơng logic v"i F (t c là ta có E ⇔ F) khi và ch# khi bi u th c logic E ↔ F là h ng úng (t c là E ↔F ⇔1). N u E ⇔ F và F ⇔ G thì E ⇔ G. 4. Các lu t logic Các lu$t logic là cơ s ta th c hi n các bi n (i trên m t bi u th c logic c m t bi u th c logic m"i t ơng ơng logic v"i bi u th c logic có tr "c. a. Các lu t v phép ph nh • ¬¬ p ⇔ p (lu$t ph nh c a ph • ¬1⇔0 • ¬0⇔1 có nh) b. Lu t giao hoán • p∧q⇔q∧p • p∨q⇔q∨p c. Lu t k t h p • p ∧ (q ∧ r) ⇔ (p ∧ q) ∧ r • p ∨ (q ∨ r) ⇔ (p ∨ q) ∨ r d. Lu t phân b • p ∧ (q ∨ r) ⇔ (p ∨ q) ∧ (p ∨ r) • p ∨ (q ∧ r) ⇔ (p ∧ q) ∨ (p ∧ r) e. Lu t De Morgan 4 GIÁO TRÌNH TOÁN NG D NG TIN H C • ¬ (p ∧ q) ⇔¬ p ∨¬ q • ¬ (p ∨ q) ⇔¬ p ∧¬ q Biên so n : Gv. Ph m Phúc Th nh f. Lu t v ph n t bù • p ∨¬ p ⇔ 1 • p ∧¬ p ⇔ 0 g. Lu t kéo theo • p → q ⇔¬ p ∨ q h. Lu t tương ương • p ↔ q ⇔ (p → q) ∧ (q → p) i. Các lu t ơn gi n c a phép tuy n • p ∨ p ⇔ p (tính l y ng c a phép tuy n) • p ∨ 1 ⇔ 1 (lu$t này còn c g i là lu$t th ng tr ) • p ∨ 0 ⇔ p (lu$t này còn c g i là lu$t trung hòa) • p ∨ (p ∧ q) ⇔ p (lu$t này còn c g i là lu$t h p th ) j. Các lu t ơn gi n c a phép h i • p ∧ p ⇔ p (tính l y ng c a phép h i) • p ∧ 1 ⇔ p (lu$t này còn c g i là lu$t trung hòa) • p ∧ 0 ⇔ 0 (lu$t này còn c g i là lu$t th ng tr ) • p ∧ (p ∨ q) ⇔ p (lu$t này còn c g i là lu$t h p th ) Nh!ng lu$t trên c ch n l a làm cơ s cho chúng ta th c hi n các bi n (i logic, suy lu$n và ch ng minh. 5. Các qui t c thay th D "i ây là các qui t)c tìm ra các bi u th c logic t ơng cho ta có th suy ra nh!ng bi u th c logic m"i hay ơng v"i m t bi u th c logic cho tr "c. a. Qui t c 1 Trong m t bi u th c logic E, n u ta thay th m t bi u th c con b i m t bi u th c logic t ơng ơng v"i bi u th c con ó thì ta s& c m t bi u th c m"i E’ t ơng ơng v"i bi u th c E. b. Qui t c 2 Gi s bi u th c logic E là m t h ng úng. N u ta thay th m t bi n m nh p b i m t bi u th c logic tu* ý thì ta s& c m t bi u th c logic m"i E’ c ng là m t h ng úng. c. Các ví d áp d ng Ví d 1: Ch ng minh r ng (p → q) ⇔ (¬ q →¬ p). Ví d 2: Ch ng minh r ng bi u th c ((p → q) ∧ p) → q là m t h ng úng. Ví d 3: Ch ng minh r ng bi u th cp ∧ q → plà m t h ng úng. Ví d 4: Ch ng minh r ng bi u th cp → p ∨ qlà m t m nh h ng úng. ph c Nh n xét:Các ví d trên cho ta th y m t quan h khác gi a các m nh h p hay các m nh : quan h “suy ra”. Khi m nh p → q là h ng úng, ta ch quan h nói r ng p suy ra q (v m t logic). Chúng ta s dùng ký hi u “suy ra”. Quan h suy ra n y có tính truy n (hay b c c u), nhưng không có tính ch t i x ng. IV.Quy t c suy di n 1. nh ngh a 5 GIÁO TRÌNH TOÁN NG D NG TIN H C Biên so n : Gv. Ph m Phúc Th nh Tuy có nhi u k+ thu$t, nhi u ph ơng pháp ch ng minh khác nhau, nh ng trong ch ng minh trong toán h c ta th ng th y nh!ng lý lu$n d n xu t có d ng: N u p1 và p2 và . . . và pn thì q. D ng lý lu$n n y c xem là h p lý ( c ch p nh$n là úng) khi ta có bi u th c (p1∧ p2∧ . . . ∧ pn) → q là h ng úng. Ta g i d ng lý lu$n trên là m t lu t suy di n Ng i ta c ng th ng vi t lu$t suy di n trên theo các cách sau ây : • Cách 1: Bi u th c h ng úng (p1∧ p2∧ . . . ∧ pn) → q ⇔ 1 • Cách 2: Dòng suy di n (p1∧ p2∧ . . . ∧ pn) q • Cách 3: Mô hình suy di n p1 .... pn ∴q Các bi u th c logic p1, p2, . . ., pn trong lu$t suy di n trên c g i là gi thi t (hay ti n ), và bi u th c q c g i là k t lu$n. Ví d : Gi s p và q là các bi n logic. Xác nh xem mô hình sau ây có ph i là m t lu$t suy di n hay không? p→q p ∴q Gi i: L$p b ng chân tr ta có: ((p→ q) ∧ p)→ q P Q 0 0 1 0 1 0 1 1 1 1 1 0 0 0 1 1 1 1 1 1 p→ q (p→ q)∧ p B ng chân tr cho th y bi u th c ((p→ q) ∧ p)→ q là h ng úng. Do ó, mô hình suy lu$n trên úng là m t lu$t suy di n. 2. Ki m tra m t qui t c suy di n Ð ki m tra m t qui t)c suy di n xem có úng hay không ta có th s d ng m t trong các ph ơng pháp sau ây: a. Phương pháp 1: L p b ng chân tr . Thi t l$p bi u th c logic t ơng ng c a qui t)c suy di n và l p b ng chân tr c a bi u th c ó xem nó có ph i là h ng úng hay không. Trong tr ng h p bi u th c logic là h ng úng thì ta k t lu$n qui t)c suy di n là úng. Ng c l i, ta k t lu$n qui t)c suy di n là sai. Ví d : Ki m tra qui t)c suy di n sau ây(p→ q) ∧ p q b. Phương pháp 2: Ch ng minh b ng cách s d ng các lu t logic. Thi t l$p bi u th c logic t ơng ng c a qui t)c suy di n và ch ng minh bi u th c là h ng úng b ng cách áp d ng các lu$t logic và các qui t)c thay th . 6 GIÁO TRÌNH TOÁN NG D NG TIN H C Biên so n : Gv. Ph m Phúc Th nh Ví d : Ki m tra qui t)c suy di n sau ây: (p→ q) ∧ p q Ghi chú: Ð ki m tra m t qui t c suy di n ta còn có th k t h p 2 phương pháp trên và áp d ng c nh ng lu t suy di n ã bi t trư c. 3. Các qui t c suy di n c b n a. Qui t c Modus Ponens (p→ q) ∧ p →q ho c là vi t d "i d ng mô hình suy di n p→q p −−−−−−−− ∴q b. Qui t c Modus Tollens (p→ q) ∧ q → ¬ p ho c là vi t d "i d ng mô hình suy di n p→q ¬q −−−−−− ∴¬ p c. Tam o n lu n (p→ q) ∧ (q→ r) ∧ (p→ r) ho c là vi t d "i d ng mô hình suy di n p→q q→ r −−−−−−− ∴ p→ r d. Qui t c ch ng minh b ng ph n ch ng p → q (p → ¬q) → 0 Qui t)c n y cho phép ta ch ng minh (p → ¬q) → 0 thay cho p → q. Nói cách khác, n u ta thêm gi thi t ph vào ti n p mà ch ng minh c có s mâu thu n thì ta có th k t lu$n q t ti n p. e. Qui t c ch ng minh theo trư ng h p (p1→ q) ∧ (p2→ q) ∧ . . . ∧ (pn→ q) (p1∨ p2∨ . . . ∨ pn) → q ho c là vi t d "i d ng mô hình suy di n p1 → q p2 → q ... pn→ q −−−−−−−−−−−−−−−−−−−− ∴ ∨ ∨ ∨ → f. Ki m tra m t phép suy lu n c th Ð ki m tra m t suy lu$n c th là úng hay không, ta c,n c vào các qui t)c suy di n (lu$t suy di n). V. Ð nh ngh a v t và l ng t 1. Ð nh ngh a v t : 7 GIÁO TRÌNH TOÁN NG D NG TIN H C Biên so n : Gv. Ph m Phúc Th nh M t v t là m t phát bi u p(x, y, …) ph thu c theo các bi n x, y, … l y giá tr trên các mi n xác nh A, B, … nào ó. Khi thay th các bi n trong v t b i các giá tr c th a, b, … thu c các mi n xác nh thì ta ư c m t m nh p(a, b, …) có chân tr úng ho c sai. G i B là t p h p g!m có hai giá tr : Sai (ký hi u b i 0), và Ðúng (ký hi u b i 1). M t v t p(x, y, …) có th l y 1 trong 2 giá tr c a t p B. Ví d : P(n) ≡ “n là m t s nguyên t ” là m t v t trên t$p h p các s t nhiên (ho c trên t$p h p các s nguyên). Ta có th th y r ng: P(1) = 0, t c là P(1) ≡ “1 là m t s nguyên t ” là m t m nh sai. P(2) = 1, t c là P(2) ≡ “2 là m t s nguyên t ” là m t m nh úng. P(12) = 0, t c là P(12) ≡ “12 là m t s nguyên t ” là m t m nh sai. P(17) = 1, t c là P(17) ≡ “17 là m t s nguyên t ” là m t m nh úng. 2. Các phép toán trên các v t Cho p(x, y, …) là m t v t theo các bi n x, y, … . Ph nh c a p, ký hi u là ¬p, là m t v t mà khi thay các bi n x, y, … b i các ph n t c th a, b, … t ơng ng thì ta c m nh ¬(p(a, b, …)). Nói m t cách khác, v t ¬p c nh ngh a b i:(¬ p) (x, y, …) = ¬(p(x, y, …)) Cho p(x, y, …) và q(x, y, …) là các v t theo các bi n x, y, … . Phép h i c a p và q, ký hi u là p→ q, là m t v t mà khi thay các bi n x, y, … b i các ph n t c th a, b, … t ơng ng thì ta c m nh p(a, b, …) → q(a, b, …). Nói m t cách khác, v t p∧q c nh ngh a b i:(p ∧ q) (x, y, …) = p (x, y, …) ∧ q (x, y, …) M t cách t ơng t , các phép toán tuy n, kéo theo và t ơng ơng c a 2 v t p và q có th c nh ngh a nh sau: (p ∨ q) (x, y, …) = p (x, y, …) ∨ q (x, y, …) (p → q) (x, y, …) = p (x, y, …) → q (x, y, …) (p ↔ q) (x, y, …) = p (x, y, …) ↔ q (x, y, …) VI.Các l ng t và các m nh có l ng t 1. Khái ni m L ng t “v i m i” và “t!n t i” (hay “có ít nh t m t”)là t dùng di n t v t úng i v"i m i giá tr thu c mi n xác nh hay ch# úng v"i m t ph n các giá tr thu c mi n xác nh. Cho P(n) là m t v t theo bi n s t nhiên n. • Phát bi u “v"i m i n ∈N, P(n)” có ngh a là P có giá tr úng trên toàn b mi n xác nh. Ký hi u “ ∀ “ thay th cho l ng t “v i m i”. • Phát bi u “Có (ít nh t) m t n ∈N, P(n)” có ngh a là P có giá tr úng i v"i m t hay m t s giá tr nào ó thu c mi n xác nh. Ký hi u “∃ “ thay th cho l ng t “có ít nh t m t”. L ng t n y còn c cm t cách khác là “t n t i”. Trong nhi u phát bi u ng i ta còn dùng c m t “t n t i duy nh t”, ký hi u b i ∃!, nh là m t s l ng t hóa c bi t. Các Ví d : • Cho v t P(n) ≡ “n là m t s nguyên t ”. M nh “V"i m i s t nhiên n ta có n là nguyên t ” có th c vi t nh sau:∀ n ∈N : P(n)và m nh n y có chân tr là 0 (sai). • M nh “V"i m i s nguyên n ta có 2n-1 là m t s l-” có th c vi t d "i d ng ký hi u nh sau:∀ n ∈Z : 2n-1 l-và m nh n y có chân tr là 1 ( úng). 8 GIÁO TRÌNH TOÁN NG D NG TIN H C 2 Biên so n : Gv. Ph m Phúc Th nh • M nh “Ta có x > 0, v"i m i s th c x khác 0” có th x ∈R - { 0} : x2> 0 và m nh n y có chân tr là 1 ( úng). c vi t là ∀ 2. Qui t c ph nh m nh có lư ng t D a vào cách xác nh chân tr c a các m nh có l ng t , ta có các qui t)c ph nh m nh có l ng t sau ây: • ¬ (∀ x : P(x)) ≡∃ x : ¬ P(x) (1) • ¬ (∃ x : P(x)) ≡∀ x : ¬ P(x) (2) Ghi chú : T các qui t c trên ta có th nói chung v qui t c ph nh m nh có lư ng t như sau: N u trong m t m nh có lư ng t ta thay th lư ng t ∀ b i lư ng t ∃ , lư ng t ∃ b i lư ng t ∀ , và bi u th c v t ư c thay th b i ph nh c a nó thì ta s ư c m nh ph nh c a m nh có lư ng t ban u. Qui t c n y c"ng áp d ng ư c cho các m nh v i nhi u lư ng t . 3. M t s qui t c dùng trong suy lu n a. Thay #i th t$ lư ng t hóa c a 2 bi n Cho m t v t p(x, y) theo 2 bi n x, y. N u l ng t hóa c 2 bi n x, y trong ó ta l ng t hóa bi n y tr "c và l ng t hóa bi n x sau thì s& c 4 m nh sau ây: • x, ∀ y : p(x,y) • x, ∀ y : p(x,y) • x, ∀ y : p(x,y) • x, ∀ y : p(x,y) T ơng t ta c ng có 4 m nh l ng t hóa t v t p(x, y) trong ó ta l ng t hóa bi n x tr "c và l ng t hóa bi n y sau: • y, ∀ x : p(x,y) • y, ∀ x : p(x,y) • y, ∀ x : p(x,y) • y, ∀ x : p(x,y) b. Ð nh lý: Gi s p(x, y) là m t v t theo 2 bi n x, y thì các m nh • (∀ x, ∀ y : p(x,y) ) ↔ (∀ y, ∀ x : p(x,y) ) • (∃ x, ∃ y : p(x,y) ) ↔ (∃ y, ∃ x : p(x,y) ) • (∃ x, ∀ y : p(x,y) ) → (∀ y, ∃ x : p(x,y) ) sau là úng c. Qui t c c bi t hóa ph# d ng Gi s m t m nh có lư ng t trong ó bi n x v i mi n xác nh là A, ư c lư ng t hóa và b bu c b i lư ng t ph# d ng ∀ , và m nh là úng. Khi ó n u thay úng. th x b i a ∈ A thì ta s ư c m t m nh d. Qui t c t#ng quát hóa ph# d ng Qui t c: N u ta thay th bi n x trong v t P(x) b i m t ph n t a c nh nh ng tùy ý th c mi n xác nh c a bi n x mà m nh nh$n c có chân tr là úng, t c là P(a) = 1, thì m nh l ng t hóa∀ x : P(x)là m t m nh úng. T các qui t c trên ta có th ch ng minh ư c m t s tính ch t suy di n ư c phát bi u trong các m nh sau ây: • M nh 1: Cho p(x) và q(x) là các v t theo bi n x l y giá tr trong t$p h p A (mi n xác nh c a bi n x là t$p h p A), và a là m t ph n t c nh tùy ý thu c A. Khi y ta có qui t)c suy di n sau ây: ∀ x : p(x) → q(x) 9 GIÁO TRÌNH TOÁN NG D NG TIN H C Biên so n : Gv. Ph m Phúc Th nh p(a) −−−−−−−−−−−−−−−−− ∴ q(a) • M nh 2: Cho p(x), q(x) và r(x) là các v t theo bi n x l y giá tr trong t$p h p A (mi n xác nh c a bi n x là t$p h p A). Ta có qui t)c suy di n sau ây: ∀ x : p(x) → q(x) ∀ x : q(x) → r(x) −−−−−−−−−−−−−− ∴∀ x : p(x) → r(x) 4. D ch nh ng câu thông thư ng thành bi u th c logic: D ch m t câu c phát bi u b ng ngôn ng! t nhiên (câu h.i thông th ng) thành m t bi u th c logic có vai trò h t s c quan tr ng trong xây d ng các ngôn ng! l$p trình, ch ơng trình d ch và x lý ngôn ng! t nhiên. Quá trình d ch m t câu t ngôn ng! t nhiên thành m t bi u th c s& làm m t i tính t nhiên c a ngôn ng! vì a s các ngôn ng! u không rõ ràng, nh ng m t bi u th c logic l i r t rõ ràng ch t ch& t cú pháp th hi n n ng! ngh a c a câu. /i u này d n n ph i có m t t$p h p các gi thi t h p lý d a trên m t hàm xác nh ng! ngh a cu câu ó. M t khi câu ã c chuy n d ch thành bi u th c logic, chúng ta có th xác nh c giá tr chân lý c a bi u th c logic, thao tác trên bi u th c logic, bi n (i t ơng ơng trên bi u th c logic. Chúng ta s& minh ho vi c d ch m t câu thông th ng thành bi u th c logic thông qua nh!ng sau. a. Ví d 1 D ch câu “B n không c lái xe máy n u b n cao d "i 1.5 mét tr phi b n trên 18 tu(i” thành bi u th c logic. Gi i : Ta g i p là câu : B n ư c lái xe máy. q là câu : B n cao dư i 1.5m. r là câu : B n trên 18 tu#i. Khi ó: Câu h.i trên c d ch là: (q ∧ ¬r) ¬p b. Ví d 2 D ch câu “T t c các sinh viên h c tin h c u h c môn toán h c r i r c” Gi i: G i P(x) là câu “x c n h c môn toán h c r i r c” và x c xác nh trong không gian c a các sinh viên h c tin h c. Khi ó chúng ta có th phát bi u: ∀ x P(x) c. Ví d : D ch câu “Có m t sinh viên l"p này ít nh t ã t t c các phòng c a ít nh t m t nhà trong ký túc xá”. Gi i: G i t$p sinh viên trong l"p là không gian xác nh sinh viên x, t$p các nhà trong ký túc xá là không gian xác nh c,n nhà y, t$p các phòng là không gian xác nh phòng z. Ta g i P(z,y) là “z thu c y”, Q(x,z) là “x ã z”. Khi ó ta có th phát bi u: ∃ x ∃ y ∀ z (P(z,y) Q(x,z)); VII. T p h p - Các phép toán t p h p 1. Khái ni m t p h p 10 GIÁO TRÌNH TOÁN NG D NG TIN H C Biên so n : Gv. Ph m Phúc Th nh T$p h p là m t trong các khái ni m cơ b n c a Toán h c. Khái ni m t$p h p không c nh ngh a mà ch# c mô t qua các ví d : T$p h p các h c sinh c a m t l"p h c, t$p h p các c u th c a m t i bóng, t$p h p các cu n sách trên m t giá sách, t$p h p các s t nhiên,... Các i t ng c u thành m t t$p h p c g i là các ph n t c a t$p h p ó. Ng i ta th ng kí hi u các t$p h p b i các ch! A, B, C, X, Y, Z,... và các ph n t c a t$p h p b i các ch! a, b, c, x, y, z, ... N u a là m t ph n t c a t$p h p A thì ta vi t a ∈ A ( c là a thu c t$p h p A). N u a không ph i là m t ph n t c a t$p h p A thì ta vi t a∉ A ( c là a không thu c t$p h p A). T ph pC 1 2. Bi u di n m t t p h p Có hai cách bi u di n m t t$p h p: 2 • Cách th nh t là li t kê t t c các ph n t c a t$p h p. T$p h p A g0m b n s t nhiên 1, 3, 5, 7 c vi t là: A = {1, 3, 4 8 5, 7}. • Cách th hai là nêu lên m t tính ch t chung c a các ph n t c a t$p h p, nh ó có th nh$n bi t c các ph n t c a t$p h p và các i t ng không ph i là nh!ng ph n t c a nó. Ch ng h n, C = {x / x là "c s c a 8} Ng i ta th ng bi u th t$p h p A b i m t ng cong kín g i là l c 0 Venn. 3. T p h p con, các t p h p b ng nhau a. T p h p con : T$p h p A c g i là m t t$p con c a t$p h p X n u m i ph n t c a A u là nh!ng ph n t c a X. Ký hi u : A X (1) ho c X A(2) ( c là X ch a A) Ký hi u c g i là d u bao hàm. H th c (1) ho c (2) g i là m t bao hàm th c. nh lý : t p h p có n ph n t có c th y 2n t p h p con. b. Các t p h p b ng nhau T$p h p A và t$p h p B c g i là b ng nhau khi và ch# khi A Bvà B A c. V i các t p h p b t kì A, B, C, ta có: • φ A, • N u A B và B C thì A • A A, • N u A ≠B thì A B C, 4. Các phép toán trên t p h p a. Giao c a các t p h p Giao c a hai t$p h p A và B là t$p h p t o nên b i các ph n t chung c a hai t$p h p ó, kí hi u là: A 1 B ( c là A giao B) T nh ngh a c a A 1 B suy ra r ng x ∈ A 1 B ⇔ x ∈ A và x ∈ B T nh ngh a giao c a hai t$p h p, d dàng ch ng minh c các ng th c sau v"i các t$p h p b t kì A, B, C, ta có: • A 1 B = B 1 A, • ∅1A=∅ • (A 1 B) 1 C = A 1 (B 1 C), • A1A=A b. H p c a các t p h p H p c a hai t$p h p A và B là t$p h p t o nên b i các ph n t thu c ít nh t m t trong hai t$p h p ó, kí hi u là A ∪ B ( c là A h p B). T nh ngh a c a A ∪ B suy ra r ng x ∈ A ∪ B x ∈ A ho c x ∈ B. T nh ngh a c a h p các t$p h p d dàng suy ra v"i các t$p h p b t kì A, B, C, • A ∪ B = B ∪ A, • (A ∪ B) ∪ C = A ∪ (B ∪ C), 11 GIÁO TRÌNH TOÁN • ∅∪ A = A, NG D NG TIN H C • A ∪ A = A. Biên so n : Gv. Ph m Phúc Th nh c. Hi u c a hai t p h p Hi u c a hai t$p h p A và B là t$p h p các ph n t thu c A nh ng không thu c B, kí hi u là A \ B ( c là A tr B). T nh ngh a c a A \ B suy ra:x ∈ A \ B ⇔ x ∈ A và x ∉ B V"i các t$p h p b t kì A, B, C, D, ta có: • A\B⊂A • N u C ⊂ D thì A \ D A \ C • N u A ⊂ B và C ⊂ D thì A \ D ⊂ B \ C • A ⊂ B ⇔ A \ B = ∅. d. Ph n bù c a m t t p h p Cho t$p h p X và A là m t t$p con c a X. T$p h p X \ A c g i là ph n bù c a A và c kí hi u là T nh ngh a ph n bù c a m t t$p h p suy ra r ng N u X là m t t$p h p và A ⊂ X thì v"i m i x ∈ X, x ∈ CA ⇔ x ∉ A. V"i các t$p con b t kì A, B c a không gian X, ta có: • X 1 A = A, • C∅ = X, • X ∪ A = X, • CCA = A, • CX = ∅, • A ⊂ B ⇔ CB ⊂ CA. e. Tích Descartes c a các t p h p Cho hai t$p h p X và Y,t$p h p t t c các c p th t (x, y) trong ó x ∈ X, y ∈ Y g i là tích Descartes c a hai t$p h p X, Y và c kí hi u là X x Y. Nh v$y, X x Y = {(x, y) : x ∈ X, y ∈ Y}. Cho m t$p h p X1, X2, ..., Xm. T$p h p các dãy m ph n t (x1, x2, ..., xm),trong ó x1 ∈ X1, x2 ∈ X2, ..., xn ∈ Xm g i là tích /êcác c a m t$p h p X1,X2, ..., Xm và c kí hi u là X1 x X2 x... x Xm. X1 x X2 x... x Xm = {(x1, x2, ..., xm) : x1 ∈ X1, ... xm ∈ Xm}. N u X1 = X2 = ... = Xm thì t$p h p X1 x X2 x... x Xm c kí hi u là Xm. Nh v$y Xm là t$p h p các dãy m ph n t (x1, x2, ..., xm), trong ó x1, ..., xm∈ X. VIII. Khái ni m Ánh x 1. nh ngh a Gi s X và Y là hai t$p h p. m t ánh x f t X vào Y là m t quy t c cho ta v"i m2i ph n t x ∈ X, t0n t i m t ph nt duy nh t y ∈ Y sao cho y=f(x). Ánh x f t t$p h p X vào t$p h p Y c kí hi u là:f : X 3 Y. N u x là m t ph n t c a t$p h p X thì ph n t y c a t$p h p Y sao cho y=f(x) y c g i là nh c a x qua ánh x f. 2. Ánh x b ng nhau Gi s X và Y là hai t$p h p, f và g là hai ánh x t X vào Y. Ta nói r nghai ánh x f và g là b ng nhau, và vi t f = g, n u f (x) = g (x) v"i m i x∈ ∈X. 3. Ánh x h p Cho 2 ánh x f:X→Y g:Y→Z Ánh x h p h c a f và g là ánh x t X vào Z xác h:X→Z x h(x) = g(f(x)) Ta vi t h = g o f. 4. nh b i: nh và nh ngư c Trang 12 GIÁO TRÌNH TOÁN NG D NG TIN H C Biên so n : Gv. Ph m Phúc Th nh a. % nh ngh&a Cho ánh x f t X vào Y và A ⊂ X, B ⊂ Y. Ta nh ngh a: f(A) = {f(x) | x ∈ A} = {y ∈ Y |∃x ∈ A, y = f(x)} ∀y ∈ Y, y ∈ f(A) ⇔∃x ∈ A, y = f(x); ∀y ∈ Y, y ∉ f(A) ⇔∀x ∈ A, y ≠ f(x). f–1(B) = {x ∈ X | f(x) ∈ B} ∀x ∈ X, x ∈ f–1(B) ⇔ f(x) ∈ B; ∀x ∈ X, x ∉ f–1(B) ⇔ f(x) ∉ B. Ta th ng ký hi u f(X) b i Imf và f-1({y}) b i f-1(y). Imf c g i là nh c a ánh x f. b. Tính ch t: f(A1∪ A2) = f(A1) ∪ f(A2); f(A1∩ A2) ⊂ f(A1) ∩ f(A2); f(A1 \ A2) ⊃ f(A1) \ f(A2); f–1(B1∪ B2) = f–1(B1) ∪ f–1(B2); f–1(B1∩ B2) = f–1(B1) ∩ f–1(B2); f–1(B1 \ B2) = f–1(B1) \ f–1(B2). 5. Phân lo i ánh x a. %ơn ánh Ta nói f : X → Y là m t n ánh n u hai ph n t khác nhau b t k* c a X khác nhau, ngh a là: ∀x, x' ∈ X, x ≠ x' f(x) ≠ f(x' ) u có nh b. Toàn ánh Ta nói f : X → Y là m t toàn ánh n u Imf = Y c. Song ánh Ta nói f : X → Y là m t song ánh n u f v a là ơn ánh v a là toàn ánh. IX. L c l ng c a t p h p 1. nh ngh a l c lư ng c a t p h p M2i t$p A ta t t ơng ng v"i m t i t ng |A| g i là l$c lư ng c a t p A ,sao cho |A| = |B| khi và ch# khi t0n t i song ánh t A vào B. L c l ng c a t$p A còn c g i là b n s c a A và ký hi u là cardA. L c l ng c a t$p r2ng là s 0 L c l ng c a t$p {1,2,…,n} là n. 2. nh ngh a t p h p h u h n-vô h n T$p h p A c g i là t$p h!u h n nêu ta có th m c h t các ph n t c a t$p h p này. N u mãi v n còn nh!ng ph n t c a A không c m t"i thì t$p A c g i là t$p vô h n. 3. T p h p m ư c a. % nh ngh&a 1 : L c l ng c a t$p s t nhiên N c g i là l c l b. % nh ngh&a 2 : Hai t$p h p A và B c g i là t ơng gi!a 2 t$p h p này. Ký hi u A ~B c. % nh ngh&a 3 : M t t$p h p t ơng ơng v"i t$p h p N ng m c. ơng nhau n u có th thi t l$p m t song ánh c g i là t$p h p m c Trang 13 GIÁO TRÌNH TOÁN NG D NG TIN H C d. % nh ngh&a 4 : T$p h p không m X. Quy n p toán h c – Biên so n : Gv. Ph m Phúc Th nh c là m t t$p h p vô h n và không là t$p h p nh ngh a m c/ quy 1. Quy n p toán h c a. Khái ni m Quy n p là k t lu$n i t tr ng h p riêng i t"i tr ng h p t(ng quát. Ngh a là, k t lu$n t(ng quát d a trên vi c nghiên c u các tính ch t c a nhi u s ki n, nhi u thí nghi m hay nhi u quan sát riêng l-. N u k t lu$n chung d a vào nghiên c u t t c các s ki n riêng (các i t ng, các hình, các s , vv…) thì quy n p c g i là y hay hoàn ch#nh. N u k t lu$n chung d a vào nghiên c u m t ph n c a tâp h p t t c các s ki n (các i t ng) thì quy n p c g i là không y hay không hoàn ch#nh. b. Cơ s toán c a nguyên lý quy n p N u W là m t tính ch t c xác nh trên t$p h p t t c các s t nhiên sao cho W(1) (1 có tính ch t W), i v"i m t s t nhiên n n u W(n) thì W(n+1) ( n u n có tính ch t W thì n+1 có tính ch t W), thì m i s t nhiên u có tính ch t W. 2. Các nh lý v quy n p a. % nh lý 1. N u W là m t tính ch t c xác nh trong t$p h p c a t t c các s t nhiên sao cho W (1) (1 có tính ch t W) i v"i m i s t nhiên n: n u W(k) (k có tính ch t W) v"i m i s t nhiên k: sao cho thì W(n+1) (n+1 có tính ch t W), thì m i s t nhiên u có tính ch t W. b. % nh lý 2. N u là 4 hàm m nh c a bi n x bi n thiên trên t$p h p t t c các s t nhiên sao cho ϕ(1) (1 tho mãn m nh 4(x)) i v"i m i s t nhiên n : n u ϕ(k) (k tho mãn ϕ(x)) i v"i m i s t nhiên k sao cho , thì 4(n+1) (n+1 th.a mãn 4(x)), thì m i s t nhiên th.a mãn hàm m nh 4(x). 3. Thu t toán quy a. Khái ni m quy M t thu$t toán c g i là quy n u nó gi i bài toán b ng cách rút g n liên ti p bài toán ban u t"i bài toán c ng nh v$y nh ng có d! li u u vào nh. hơn. Ví d : Tìm thu$t toán quy tính UCLN c a hai s nguyên a,b không âm và a > b. procedure UCLN (a,b: các s nguyên không âm, a > b) if b = 0 then UCLN (a,b) := a else UCLN (a,b) := UCLN (a mod b, b) b. % quy và l p: Ví d . Th t c quy sau ây cho ta giá tr c a n! v"i n là s nguyên d ơng. procedure factorial (n: positive integer) if n = 1 then factorial(n) := 1 else factorial(n) := n * factorial(n-1) Trang 14 GIÁO TRÌNH TOÁN NG D NG TIN H C Biên so n : Gv. Ph m Phúc Th nh Thông th ng tính m t dãy các giá tr c nh ngh a b ng quy, n u dùng ph ơng pháp l p thì s các phép tính s& ít hơn là dùng thu$t toán quy (tr khi dùng các máy quy chuyên d ng). Ta s& xem xét bài toán tính s h ng th n c a dãy Fibonacci. procedure fibonacci (n: nguyên không âm) if n = 0 then fibonacci(n) := 0 else if n = 1 then fibonacci(n) := 1 else fibonacci(n) := fibonacci(n - 1) + fibonacci(n - 2) Theo thu$t toán này, tìm fn ta bi u di n fn = fn-1 + fn-2. Sau ó thay th c hai s này b ng t(ng c a hai s Fibonacci b$c th p hơn, c ti p t c nh v$y cho t"i khi f0 và f1 xu t hi n thì c thay b ng các giá tr c a chúng theo nh ngh a. Do ó tính fn c n fn+1-1 phép c ng. Bây gi ta s& tính các phép toán c n dùng tính fn khi s d ng ph ơng pháp l p. Th t c này kh i t o x là f0 = 0 và y là f1 = 1. Khi vòng l p c duy t qua t(ng c a x và y c gán cho bi n ph z. Sau ó x c gán giá tr c a y và y c gán giá tr c a z. V$y sau khi i qua vòng l p l n 1, ta có x = f1 và y = f0 + f1 = f2. Khi qua vòng l p l n n-1 thì x = fn-1. Nh v$y ch# có n – 1 phép c ng c dùng tìm fn khi n > 1. procedure Iterative fibonacci (n: nguyên không âm) if n = 0 then y := 0 else begin x := 0 ; y := 1 for i := 1 to n - 1 begin z := x + y x := y ; y := z end end {y là s Fibonacci th n} Ta ã ch# ra r ng s các phép toán dùng trong thu$t toán quy nhi u hơn khi dùng ph ơng pháp l p. Tuy nhiên ôi khi ng i ta v n thích dùng th t c quy hơn ngay c khi nó t. ra kém hi u qu so v"i th t c l p. / c bi t, có nh!ng bài toán ch# có th gi i b ng th t c quy mà không th gi i b ng th t c l p. Trang 15 GIÁO TRÌNH TOÁN Ch NG D NG TIN H C ng 2 : PHÉP I. Phép Biên so n : Gv. Ph m Phúc Th nh M m 1. nh ngh a: Cho A là m t t$p h p khác r2ng. N u t0n t i m t s nguyên d ơng n và m t song ánh f t A vào { 1, 2, . . ., n} thì ta nói A là m t t$p h p h!u h n và A có n ph n t . Khi ó song ánh f : A →{ 1, 2, . . ., n} c xem là m t phép m t$p h p A. T$p h p r2ng có s ph n t là 0, và c ng c xem là t$p h!u h n. S ph n t c a m t t$p h p h!u h n A c ký hi u là | A |. N u t$p h p A không h!u h n, ta nói A là m t t$p vô h n và vi t| A | = ∞ 2. Tính ch t: Cho A và B là các t$p h p h!u h n. Gi s t0n t i ơn ánh t A vào B. Khi y ta có: | A | ≤ | B |. II. Nguyên lý c ng 1. M nh : Cho A và B là 2 t$p h p h!u h n r i nhau, ngh a là A ∩ B = ∅ . Khi y ta có:| A ∪ B|=|A|+|B| M t cách t(ng quát: N u A1, A2, ..., An là các t$p h p h!u h n r i nhau, ngh a là ph n giao c a hai t$p h p b t k* trong n t$p h p là r2ng, thì s ph n t c a ph n h i c a các t$p h p trên b ng t(ng c a các s l ng ph n t trong m2i t$p h p: | A1∪ A2∪ . . . ∪ An | = | A1 | + | A2 | + . . . + | An | Ghi chú: Trong tr ng h p i v"i hai t$p h p h!u h n A và B tùy ý thì ta có: |A∪B|=|A|+|B|-|A∩B| Tính ch t n y có th m r ng cho tr ng h p i v"i n t$p h p tùy ý A1, A2, ..., An nh sau:| A1∪ A2∪ . . . ∪ An | = Σ1≤ r≤ n | Ar | - Σ1≤ r< s≤ n | Ar ∩ As | + Σ1≤ r< s< t ≤ n | Ar ∩ As ∩ At | - . . . + (-1)n | A1∩ A2∩ . . . ∩ An | 2. Nguyên lý c ng : Gi s ta ph i th c hi n công vi c và th c hi n công vi c n y ta có th ch n m t trong hai bi n pháp khác nhau theo ngh a là cách th c hi n bi n pháp th nh t luôn luôn khác cách th c hi n bi n pháp th hai. Bi n pháp th nh t có n cách th c hi n, và i v"i bi n pháp th hai ta có m cách th c hi n. V$y ta có n+m cách th c hi n công vi c. Ví d : Xác nh giá tr c a k sau khi o n ch ơng trình sau ây c th c hi n xong k := 0 for i1 := 1 to n1 do k := k + 1; for i2 := 1 to n2 do k := k + 1; . . . for im := 1 to nm do k := k + 1; L i gi i. Giá tr c a k ban u là 0. Sau ó là m vòng l p khác nhau. M2i thao tác l p trong m t vòng l p là c ng thêm 1 vào k. Vòng l p th i có ni thao tác, và t t c m vòng l p Trang 16 GIÁO TRÌNH TOÁN NG D NG TIN H C Biên so n : Gv. Ph m Phúc Th nh không th th c hi n 2 vòng l p nào m t cách 0ng th i. Do ó s thao tác th c hi n xong o n ch ơng trình trên là n1 + n2 + ... + nm. /ây c ng chính là giá tr cu i cùng c a k. 3. Nguyên lý nhân : M nh : Cho A và B là 2 t$p h p h!u h n r i nhau. Khi y ta có: |AxB|=|A|.|B| M t cách t(ng quát: N u A1, A2, ..., An là các t$p h p h!u h n thì s ph n t c a tích Descartes c a các t$p h p trên b ng tích c a các s l ng ph n t c a các t$p h p trên: | A1 x A2 x . . . x An | = | A1 | . | A2 | . . . . . | An | Gi s ta ph i th c hi n m t th t c bao g0m hai công vi c k ti p nhau. / th c hi n công vi c th nh t ta có n1 cách, và ng v"i m2i cách ch n th c hi n công vi c th nh t ta có n2 cách th c hi n công vi c th hai. V$y ta có s cách th c hi n th t c là n1 x n2 . Nguyên lý nhân trên có th c m r ng và có d ng t(ng quát nh sau: Gi s m t th t c bao g0m m công vi c k ti p nhau T1, T2, . . ., Tm. N u công vi c T1 có th c th c hi n theo n1 cách, và sau khi ch n cách th c hi n cho T1 ta có n2 cách th c hi n T2, v.v… cho n cu i cùng, sau khi ch n cách th c hi n các công vi c T1, T2, . . ., Tm-1 ta có nm cách th c hi n Tm. V$y ta có n1.n2. ... .nm cách th c hi n th t c. Nguyên lý nhân d ng t(ng quát n y có th c ch ng minh b ng qui n p t qui t)c nhân cho tr ng h p th t c g0m 2 công vi c. Ví d : Theo qui t)c nhân ta th y r ng sau khi th c hi n o n ch ơng trình d "i ây thì giá tr c a bi n k s& là n1.n2. ... .nm. k := 0 for i1 = 1 to n1 do for i1 = 1 to n2 do . . . for i1 = 1 to nm do k := k + 1 III. Nguyên lý Dirichlet t ng quát: 1. M nh : N u có N ! v t ư c t vào trong k h p thì s t!n t i m t h p ch a ít nh t ]N/k[ ! v t. 2. Các ví d : • Có n'm lo i h c b#ng khác nhau. H(i r ng ph i có ít nh t bao nhiêu sinh viên ch c ch n r ng có ít ra là 6 ngư i cùng nh n h c b#ng như nhau. G i N là s sinh viên, khi ó ]N/5[ = 6 khi và ch# khi 5 < N/5 ≤ 6 hay 25 < N ≤ 30. V$y s N c n tìm là 26. • S mã vùng c n thi t nh( nh t ph i là bao nhiêu m b o 25 tri u máy i n tho i trong nư c có s i n tho i khác nhau, m)i s có 9 ch s (gi s s i n tho i có d ng 0XX - 8XXXXX v i X nh n các giá tr t 0 n 9). Có 107 = 10.000.000 s i n tho i khác nhau có d ng 0XX - 8XXXXX. Vì v$y theo nguyên lý Dirichlet t(ng quát, trong s 25 tri u máy i n tho i ít nh t có ]25.000.000/10.000.000[ = 3 có cùng m t s . / m b o m2i máy có m t s c n có ít nh t 3 mã vùng. 3. M t s ng d ng c a nguyên lý Dirichlet. Trang 17 GIÁO TRÌNH TOÁN NG D NG TIN H C Biên so n : Gv. Ph m Phúc Th nh • Trong m t phòng h p có n ngư i, bao gi c"ng tìm ư c 2 ngư i có s ngư i quen trong s nh ng ngư i d$ h p là như nhau. S ng i quen c a m2i ng i trong phòng h p nh$n các giá tr t 0 n n − 1. Rõ ràng trong phòng không th 0ng th i có ng i có s ng i quen là 0 (t c là không quen ai) và có ng i có s ng i quen là n − 1 (t c là quen t t c ). Vì v$y theo s l ng ng i quen, ta ch# có th phân n ng i ra thành n −1 nhóm. V$y theo nguyên lý Dirichlet t0n tai m t nhóm có ít nh t 2 ng i, t c là luôn tìm c ít nh t 2 ng i có s ng i quen là nh nhau. • Trong m t tháng g!m 30 ngày, m t i bóng chuy n thi u m)i ngày ít nh t 1 tr n nhưng chơi không quá 45 tr n. Ch ng minh r ng tìm ư c m t giai o n g!m m t s ngày liên t c nào ó trong tháng sao cho trong giai o n ó i chơi úng 14 tr n. G i aj là s tr$n mà i ã chơi t ngày u tháng n h t ngày j. Khi ó 1 ≤ a1 < a2< ... < a30< 45 15 ≤ a1+14< a2+14 < ... < a30+14 < 59. Sáu m ơi s nguyên a1, a2, ..., a30, a1+ 14, a2 + 14, ..., a30+14 n m gi!a 1 và 59. Do ó theo nguyên lý Dirichlet có ít nh t 2 trong 60 s này b ng nhau. Vì v$y t0n t i i và j sao cho ai= aj+ 14 (j < i). /i u này có ngh a là t ngày j + 1 n h t ngày i i ã chơi úng 14 tr$n. • Ch ng t( r ng trong n + 1 s nguyên dương không vư t quá 2n, t!n t i ít nh t m t s chia h t cho s khác. k Ta vi t m2i s nguyên a1, a2,..., an+1 d "i d ng aj = 2 j qj trong ó kj là s nguyên không âm còn qj là s d ơng l- nh. hơn 2n. Vì ch# có n s nguyên d ơng l- nh. hơn 2n nên theo nguyên lý Dirichlet t0n t i i và j sao cho qi = qj = q. Khi ó ai= 2 ki k q và aj = 2 j q. Vì v$y, n u ki ≤ kj thì aj chia h t cho ai còn trong tr ng h p ng c l i ta có ai chia h t cho aj. • Gi s trong m t nhóm 6 ngư i m)i c p hai ho c là b n ho c là thù. Ch ng t( r ng trong nhóm có ba ngư i là b n l*n nhau ho c có ba ngư i là k+ thù l*n nhau. G i A là m t trong 6 ng i. Trong s 5 ng i c a nhóm ho c là có ít nh t ba ng i là b n c a A ho c có ít nh t ba ng i là k- thù c a A, i u này suy ra t nguyên lý Dirichlet t(ng quát, vì ]5/2[ = 3. Trong tr ng h p u ta g i B, C, D là b n c a A. n u trong ba ng i này có hai ng i là b n thì h cùng v"i A l$p thành m t b ba ng i b n l n nhau, ng c l i, t c là n u trong ba ng i B, C, D không có ai là b n ai c thì ch ng t. h là b ba ng i thù l n nhau. T ơng t có th ch ng minh trong tr ng h p có ít nh t ba ng i là k- thù c a A. IV.CH NH H P 1. Ð nh ngh a Cho X là m t t$p h p g0m n ph n t , và r là m t s nguyên d ơng nh. hơn ho c b ng n. M2i phép ch n r ph n t phân bi t c a X theo m t th t nào ó s& cho ta m t ch nh h p n ch n r. Nói cách khác, ta có th xem m t ch#nh h p nh là m t dãy hay m t b g0m r ph n t phân bi t c ch n t n ph n t cho tr "c. Ví d . Cho t$p h p S = { 1, 2, 3} . Dãy g0m 2 ph n t 3, 2 là m t ch#nh h p 3 ch n 2. S s)p x p các ph n t thành dãy 3, 1, 2 cho ta m t ch#nh h p 3 ch n 3. Ch#nh h p 3 ch n 3 n y còn c g i là m t hoán v c a 3 ph n t . M t ch#nh h p n ch n n c g i là m t hoán v c a n ph n t . Nói cách khác, m t hoán v n ph n t là m t cách s)p x p n ph n t theo m t th t nào ó. M2i hoán v n ph n t c a t$p X c ng có th c xem nh m t song ánh t X vào X. 2. Công th c ch nh h p Trang 18 GIÁO TRÌNH TOÁN NG D NG TIN H C Biên so n : Gv. Ph m Phúc Th nh Ð nh lý I.1. S cácc ch#nh h p n ch n r là Ghi chú: 0! = 1 n! = (n-1)! n (n l"n "n hơn h 0) V. T H P 1. Ð nh ngh a Cho X là m t t$p $ h p g0m n ph n t , và r là m t s nguyên không k âm nh. hơn ho c b ng n. M2i phép ch n r ph n t phân bi t c a X mà không phân bbi t th t tr "c sau s& cho ta m t t# h p n ch n r. N Nói cách khác, ta có th xem m t t( h p n ch n r nh là m t t$p h p con g0m r ph n t c a m t t$p h p có n ph n t . Ví d : Cho t$p h p S = { 1, 2, 3, 4} . Ta có t$p S’ = { 1, 3, 4} là l m t t( h p 4 ch n 3. S các t( h p n ch n r c ký hi u là C(n,r). Ví d : C(4,2) = 6 vìì tta có th li t kê ra t t c các t$p h p con on 2 ph n t c a m t t$p h p có 4 ph n t và th y có t t c là 6 t$p con. 2. Công th c t! h p Ð nh lý. S các t( h p n ch n r , v"i n và r là các s nguyên th.a 0 5 r 5 n, là Ví d : S danh sách kkhông k th t tr "c sau g0m 5 ng ng i là C(10,5) = 10! 0! / (5!5!) = 252. i c a m t l"p h c g0m 10 VI.CÔNG TH!C NH"" TH!C TH NEWTON: 1. Ð nh lý. Cho x và y là 2 bi n th c, n là m t s nguyên không m tùyy ý. Ta có: (x+y)n= 2. H qu 1. Cho n là m t s nguyên ên không âm tùy ý. Ta có: 3. H qu 2. Cho n là m t s nguyên ên không âm. Ta có: VII. H CH%T KHÁC C&A T M#T S$ TÍNH H P a. V i m i s t$ nhi hiên n ta có: C(n, 0) = 1 C(n, n) = 1 b. Cho n và r là 2 s nguyên không âm và r ≤ n. Ta có: C(n,r) = C(n, n,n-r) c. Cho n và k là 2 s nguyên sao cho 0 < k < n. Khi ó ta có: ó: C(n, k) = C(n (n-1, k) + C(n-1, k-1). Trang 19 GIÁO TRÌNH TOÁN NG D NG TIN H C Biên so n : Gv. Ph m Phúc Th nh d. Công th c Vande dermonde: Cho m, n, và r là các s nguyên không âm v"i r nh. hơn ơ ho c b ng m và n. Ta có: VIII. 'P VÀ T HOÁN V" L'P H P L'P 1. Hoán v l"p a. % nh ngh&a 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), M22i 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. b. Ð nh lý 1: $t hay h i t ng trong ó có n1 i t ng thu hu c lo i 1 (gi ng nhau), Gi s có n v$t n2 i t ng thu c lo i 2, . . ., và nr i t ng thu c lo i th r, v"i "i n = n1 + n2 + . . . + nr. Khi y s cách s)p x p n i t ng trên thành dãy có th t , hay ha s hoán v c a n i t ng, là : n! / (n1! n2! . . . nr!) Ví d :Gi s n và k là 2 s nguyên d ơng sao cho n = 2k. Ch ng minh m r ng n!/ 2k là m t s nguyên. Gi i: Xét n ký hi u x1, x1, x2, x2, . . ., xk, xk. Theo nh lý trên ta có s hoán v c a n ký hi u n y làn! / (2! 2! . . . 2!) = n!/ 2kSuy ra r ng n!/ 2k là m t s nguyên. c. Ð nh lý 2: (x1 + x2 + . . . + xm)n = Σ {C(n, r1, …, rm) : 0 5 ri 5 n, r1 + r2 + . . . + rm = n} trong ó các h s c(n (n, r1, …, rm) c tính theo công th cC(n, n, r1, …, rm) = n! / (r1! r2! . . . rm!) Ví d : Tìm h s c a x3y2z2 trong khai tri n c a (x + 2y - 3z)7. Gi i: Áp d ng nh lý taa ccó: trong khai tri n c a (x + 2y - 3z)7 , s h ng ch a x3y2z2 có d ng C(7, 3, 2, 2) x3(2y) (2 2(-3z)2 Suy ra h s c a x3y2z2 là C(7, 3, 2, 2) 22(-3)2 = 36 x 7! / (3! 2!! 2!) 2 = 7560 IX. T h p l(p 1. Ð nh ngh a: M2i cách ch n ra k v$t t n lo i v$t khác nhau(trong ó m2i m2 lo i v$t có th ch n l i nhi ul n) c g i là t( h p l p ch$p k c a n.S cáct( h p l p ch$p k c a n ký hi u là l" 2. Công th c tính t! h p l"p: S các t( h p l p ch$p $ kc an c c c tính theo công th c 3. Các h qu : a. H qu 1 : S nghi m nguyên ên không âm (x1,x2,…,xn) (m2i xi ph ơng trình x1+ x2+…+ xn = k là u nguyên n không âm) c a b. H qu 2 : S cách chia k v$t $t 00ng ch t nhau vào n h p phân bi t c nng chính b ng s t( h p l p ch$p k c a n là Trang 20 GIÁO TRÌNH TOÁN NG D NG TIN H C Biên so n : Gv. Ph m Phúc Th nh Ví d : Tìm s cách x p 30 viên bi gi ng nhau vào 5 h p khác nhau sao cho h p 1 có ít nh t 5 bi, bi t r ng h p 2 và 3 ch a không quá 6 bi. • Tr "c h t ta tìm s cách x p 30 viên bi gi ng nhau vào 5 h p khác nhau sao cho h p 1 có ít nh t 5 bi. • Nh$n xét r ng ta c n l y 5 bi x p tr "c vào h p 1, do ó s bi còn l i ch# là 25. Suy ra s cách x p trong tr ng h p này b ng s cách x p 25 bi vào 5 h p mà không có i u ki n gì thêm. S ó là =23751 • T ơng t ta có S cách x p 30 viên bi gi ng nhau vào 5 h p khác nhau sao cho h p 1 ch a ít nh t 5 bi, h p 2 ch a ít nh t 7 bi là: • T ơng t ta có S cách x p 30 viên bi gi ng nhau vào 5 h p khác nhau sao cho h p 1 ch a ít nh t 5 bi, h p 3 ch a ít nh t 7 bi là: • S cách x p 30 viên bi gi ng nhau vào 5 h p khác nhau sao cho h p 1 ch a ít nh t 5 bi, m2i h p 2 và 3 ch a ít nh t 7 bi là: • S d ng công th c ∪ ta suy ra s cách x p 30 viên bi gi ng nhau vào 5 h p khác nhau sao cho h p 1 ch a ít nh t 5 bi, 0ng th i h p 2 hay h p 3 ch a ít nh t 7 bi là Trang 21 GIÁO TRÌNH TOÁN Ch NG D NG TIN H C Biên so n : Gv. Ph m Phúc Th nh ng 3 : QUAN H) I. Quan h hai ngôi 1. nh ngh a Cho m t t$p h p X khác r2ng. M t quan h 2 ngôi trên X là m t t$p h p con R c a 2 X . Cho 2 ph n t x và y c a X, ta nói x có quan h R v"i y khi và ch# khi (x,y) ∈ R, và vi t là x R y. Nh v$y:x R y ⇔ (x,y) ∈ R; Khi x không có quan h R v"i y, ta vi t: x y. Ví d : Trên t$p h p X = { 1,2,3,4} , xét quan h 2 ngôi R c nh ngh a b i:R = { (1,1), (1,3), (2,2), (2,4), (3,1), (3,3), (4,2), (4,4)}V"i quan h n y ta có: 2 R 4, nh ng 2 3. Trên t$p h p các s nguyên Z ta nh ngh a m t quan h 2 ngôi R nh sau:x R y n u và ch# n u x-y là s ch n.hay nói cách khác:R = { (x,y) ∈ Z2 x-y = 2k v"i k ∈ Z } Quan h R n y chính là quan h 0ng d modulo 2. Ghi chú : Ng i ta còn nh ngh a m t quan h (2 ngôi) gi!a m t t$p h p A và m t t$p h p B là m t t$p h p con c a AxB. Ví d : A = { 1, 2, 3, 4, 5} , B = { 0, 1} . Ta có R = { (1,1), (2,0), (3,1), (4,0), (5,0)} là m t quan h gi!a A và B. T(ng quát hơn, ta có th nh ngh a m t quan h gi!a các t$p h p A1, A2, . . ., An là m t t$p h p con c a A1 x A2 x . . . x An (tích Descartes c a các t$p h p A1, A2, . . ., An). Nh v$y, khi R là m t quan h gi!a các t$p A1, A2, . . ., An thì m2i ph n t c a R là m t b n (a1, a2, . . ., an) v"i ai∈ Ai (i=1, …, n). 2. Cách xác nh m t quan h : D a vào các ph ơng pháp xác các ph ơng pháp sau ây: nh m t t$p h p, ta có th xác nh m t quan h b ng a. Li t kê: Li t kê t t c các c p hay b ph n t có quan h R (t c là thu c R). b. Nêu tính ch t c trưng cho quan h R : Nêu tính ch t hay tiêu chu6n xác nh các ph n t thu c R hay không. c. Các tính ch t c a quan h 2 ngôi Gi s R là m t quan h 2 ngôi trên m t t$p h p X • Tính ph n x Quan h R có tính ph n x n u và ch# n u x R x v"i m i x ∈ X. • Tính i x ng Quan h R có tính i x ng n u và ch# n u x R y y R x v"i m i x,y ∈ X. • Tính ph n x ng Quan h R có tính ph n x ng n u và ch# n u (x R y và y R x) x = y v"i m i x,y ∈ X. • Tính b c c u Quan h R có tính truy n hay b c c u n u và ch# n u (x R y và y R z) x R z v"i m i x,y,z ∈ X. 3. Bi u di n quan h 2 ngôi dư#i d ng ma tr n Gi s R là m t quan h 2 ngôi gi!a m t t$p h p h!u h n A = { a1, a2, ... , am} và m t t$p h!u h n B = { b1, b2, ... , bm} . Quan h R có th c bi u di n b i ma tr$n MR = Trang 22 GIÁO TRÌNH TOÁN NG D NG TIN H C Biên so n : Gv. Ph m Phúc Th nh [mij] g0m m dòng và n c t (t c là ma tr$n c p mxn), trong ó mij = 1 n u (ai, bj) ∈ Rmij = 0 n u (ai, bj) ∉ RTa g i ma tr$n MR là ma tr n bi u di n c a quan h R. Ví d : V"i A = { 1,2,3} và B = { a, b, c} , thì các quan h sau ây: R = { (1,a), (1,b), (1,c)} S = { (1,a), (1,b), (1,c), (2,b), (2,c), (3,c)} có các ma tr$n bi u di n là ! ! ! ! ! ! MR = " " "# MS = ! ! "# " " ! " " " Trong tr ng h p R là m t quan h 2 ngôi trên m t t$p X h!u h n và có n ph n t thì ma tr$n bi u di n c a R là m t ma tr$n có n dòng và n c t (t c là ma tr$n vuông c p n). Ghi chú: Ngoài cách bi u di n quan h d "i d ng ma tr$n ta còn bi u 0 (d ng 0 th ) bi u di n quan h . Cách bi u di n n y s& c xét n trong ph n sau, khi nói v bi u 0 Hasse c a m t c u trúc th t . II. Quan h t ng ng 1. Khái ni m M t quan h 2 ngôi R trên m t t$p h p X c g i là m t quan h tương ương n u và ch# n u nó th.a 3 tính ch t: ph n x , i x ng, truy n. Ví d : Quan h 0ng d modulo n trên Z. Ta ã bi t quan h n y có 3 tính ch t ph n x , i x ng, truy n. Quan h ≤ trên Z không ph i là m t quan h t ơng ơng vì nó không có tính ch t i x ng. 2. L#p tư ng ư ng và t p h p thư ng V"i m2i ph n t x∈ X, ta nh ngh a l p tương ương ch a x, ký hi u$% , là t$p h p t t c nh!ng ph n t (thu c X) có quan h R v"i x:$%= { y ∈ X : y R x } Nh v$y m2i l"p t ơng ơng là m t t$p h p con c a X. T$p h p các l"p t ơng ơng c a quan h t ơng ơng R trên X t o thành m t "phân ho ch" c a t$p h p X, t c là t$p các l"p t ơng ơng khác nhau cho ta m t h các t$p con c a X r i nhau ôi m t và có ph n h i b ng X. T$p h p các l"p t ơng ơng c a quan h t ơng ơng R trên Xn y (là m t t$p con c a P(X)) c g i là t p h p thương (c a quan h t ơng ơng R trên X). Ví d Quan h 0ng d modulo n trên Z có t$p h p th ơng t ơng ng, c ký hi u là % % % % %%%%%%% * trong ó +(k∈Z) là t$p h p t t c nh!ng s Zn, g0m n ph n t :Zn = { & & ' ( ( & ) nguyên 0ng d v"i k modulo n. 3. ng dư a. % nh ngh&a Cho n là m t s nguyên d ơng. Ta nói 2 s nguyên a và b 0ng d modulo n n u các s d trong phép chia a cho n và chia b cho n b ng nhau. Trong tr ng h p n y ta c ng nói là a 0ng d v"i b modulo n, và vi t:a ≡ b (mod n). Nh v$y, theo nh ngh a ta có:a ≡ b (mod n) ⇔ a mod n = b mod n. b. Các nh lý • nh lý 1: Cho n là m t s nguyên d ơng, a và b là 2 s nguyên tùy ý. Ta có các phát bi u sau ây là t ơng ơng: a ≡ b (mod n) Trang 23 GIÁO TRÌNH TOÁN NG D NG TIN H C Biên so n : Gv. Ph m Phúc Th nh n (a-b) (n chia h t hi u a và b) t0n t i m t s nguyên k sao cho a = b + k.n • nh lý 2. Cho n là m t s nguyên d ơng. Gi s a ≡ b (mod n) và c ≡ d (mod n). Khi ó ta có : a ± c ≡ b ± d (mod n) a.c ≡ b.d (mod n) • H qu* : N u a ≡ b (mod n) thì k.a ≡ k.b (mod n) v"i m i s nguyên k. N u a ≡ b (mod n) thì ak ≡ bk (mod n) v"i m i s nguyên d ơng k. • nh lý 3. (Fermat) Cho p là m t s nguyên t và a là m t s nguyên không ph i là b i s c a p. Khi ó ta có h th c sau:ap-1≡ 1 (mod p) III. Phép toán s+ h c trên Zn 1. T p h p s t nhiên, t p h p s nguyên Ta dùng ký hi u N ch# t$p h p các s t nhiên, t c là t$p h p các s nguyên không âm. T$p h p các s nguyên s& c ký hi u là Z. Chúng ta bi t r ng trên các t$p h p N và Z có hai phép toán cơ s : phép c ng (+) và phép nhân (.) th.a m t s tính ch t thông th ng: • a+b=b+a • a.b = b.a • (a+b)+c = a+(b+c) • (a.b).c = a.(b.c) • a+0 = a • a.1 = a • v"i m i s nguyên a, có duy nh t m t s nguyên • a.(b+c) = a.b + a.c c ký hi u là -a th.a:a + (-a) = 0 Trong các tính ch t trên các ký hi u a, b, c là các s t nhiên hay các s nguyên tùy ý. T tính ch t (4), trong t$p h p các s nguyên Z ta có m t phép toán tr c nh ngh a nh sau : a - b = a + (-b). Ngoài các tính ch t nêu trên các t$p h p N và Z còn là nh!ng t$p h p có th t và m c. Quan h th t trên N và Z c ký hi u b i ≤ ( c là: "nh. hơn ho c b ng"). Ngoài ra chúng ta còn dùng m t s ký hi u so sánh khác r t quen thu c nh : "≥ ", "<", ">", "=", "≠ ". Th t "≤ " trên t$p s t nhiên N có m t tính ch t r t quan tr ng c phát bi u trong nh lý d "i ây: nh lý. M i t p h p con khác r)ng c a t p h p các s t$ nhiên N u có duy nh t m t t nh( nh t. 2. Phép chia s nguyên a. % nh lý.(Thu t chia Euclide) Cho a là m t s nguyên b t k* và b là m t s nguyên khác 0. Khi ó, có duy nh t 2 s nguyên q, r th.a mãn các i u ki n: (1) a = b.q + r (2) 0 ≤ r < | b |. S q trong nh lý trên c g i là thương s c a phép chia a cho b; và r c g i là dư s (hay s d ). Th ơng s trong phép chia a cho b th ng c vi t d "i d ng: a div b, và ký hi u "div" c dùng ch# phép toán chia l y th ơng s . D s trong phép chia a cho b c vi t là: a mod b. b. Các nh ngh&a v s$ “chia h t”, “chia h t cho”, “ư c s ", "b i s ", "ư c s chung l n nh t". Trang 24 GIÁO TRÌNH TOÁN NG D NG TIN H C Biên so n : Gv. Ph m Phúc Th nh • Ta nói m t s nguyên n a chia h t cho m t s nguyên b (b ≠ 0) khi và ch# khi s d trong phé hép chia a cho b b ng 0. Nói m t cách khá hác, s nguyên a chia h t cho s nguy uyên b (b ≠ 0) khi và ch# khi có m t s ng nguyên q sao cho a = q.b. Trong tr ng n h p n y ta vi t: ( c là: "a chia h t cho b"). Khi a chia h t cho c b, ta c ng có th nói r ng "b chia h t a" a và vi t: b  a ( c là: "b chia h t a"). • Ta nói m t s nnguyên a làb i s c a m t s nguyên b khi kh và ch# khi có m t s nguyên q th..a i u ki n: a = q.b. ' ây ta v n dùng ng cách vi t " " ch# r ng “a là b i s c a b". Trong tr ng h p n y ta c ng n nói r ng "b là ư c s c a a", và s d ng cách vi t "b  a". c. Các m nh v s$ “chia h t”, “chia h t cho”, “ư c s ",, ""b i s ", "ư c s chung l n nh t". ". • M nh 1: S chia h t có các tính ch t sau ây: a a v"i m i s nguyên a. N u a b và b a thì | a | = | b |. Nh v$y trong tr ng h p a và b là các s t nhiên, thì t i u ki n a b và b a ta có th k t lu$n a = b. N u a b và b c thì th a c. • M nh 2: Chho a, b, c, d là các s nguyên tùy ý. Ta cóó các c tính ch t sau: a 0 1 a N u a b và c d thì (a.c) (b.d) N u a b và a c thì a (b ± c). • H qu*. T các ác tính ch t c phát bi u trong m nh ttrên chúng ta d dàng suy ra các ác h qu sau ây: N u a b thì th a (b.c) N u a b thì th an bn, v"i m i s nguyên d ơng n. 3. $#c S Chung L#n Nh h t và B i S Chung Nh% Nh t a. nh ngh a: (ư c s chung l n nh t dương) Cho a và b là 2 s nguyên n không 0ng th i b ng 0. M t "c s chung d c a a và b (t c là s nguyên v a là "c s c a a v a là "c s c a b) c g i là ư c s chung l n nh t c a a và b n u "c s cchung d n y l"n hơn m i "c s chung khác kh c a a và b. Nh v$y, "c s ch chung l"n nh t d c a a và b c c tr ng b i 2 i u ki n sau ây: • d a và d b • N u d’ a,, d’ d b, và d’≠ d thì d’ < d. b. Nh n xét : Ta có s 1 là m t "c s chung c a a và b; và m i "c s chung u nh. hơn ho c b ng | a |. Do ó t$p $ h p U g0m các "c s chung c a a và b là m t t$p h p khác r2ng các s nguyên. Suy ra U có duy nh t m t ph n t l"n nh t. /i u n y ch ng t. r ng "c s chung l"n nh t c a 2 s nguyên a và b (a, b không 00ng th t i b ng 0) t0n t i, d ơng, và duy nh t. Ta ký hhi u "c s chung l"n nh t c a a và b là:: (a,b). ( N u m ≠ 0 thì (m,0) ,0) = |m|. c. Ghi chú : Trong i s , ng i ta nh ngh a "c s chung l"n nh t c a 2 s nguyên a và b là m t s nguyên d th.a mãn ãn 2 i u ki n: Trang 25 GIÁO TRÌNH TOÁN NG D NG TIN H C Biên so n : Gv. Ph m Phúc Th nh • d a và d b, và • N u d’ a và d’ b thì d’ d. Theo nh ngh&a n y thì ư c s chung l n nh t c a 2 s nguyên không nh t thi t là m t s dương, và ư c s chung l n nh t không duy nh t. Ch,ng h n, 12 và 8 có hai ư c s chung l n nh t là 4 và -4. Tuy nhiên ư c s chung l n nh t dương c a 2 s nguyên không !ng th i b ng 0 theo nh ngh&a n y trùng v i ư c s chung l n nh t trong nh ngh&a trên. d. % nh lý: Gi s d là "c s chung l"n nh t c a 2 s nguyên a và b. Khi ó ta có 2 s nguyên u và v sao cho : d = u.a + v.b e. H qu : Cho a và b là 2 s nguyên, ta có:(a,b) = 1 khi và ch# khi có m,n ∈Z sao cho m.a + n.b = 1. f. % nh ngh&a : Khi (a,b) = 1, ta nói a và b nguyên t+ cùng nhau. g. nh ngh a: (b i s chung nh( nh t dương) Cho a và b là 2 s nguyên không 0ng th i b ng 0. M t b i s chung M c a a và b (t c là s nguyên v a là b i s c a a v a là b i s c a b) c g i là b i s chung nh( nh t c a a và b n u M nh. hơn m i b i s chung khác c a a và b. h. % nh lý: Cho a và b là 2 s t nhiên. Gi s d là USCLN c a a và b, và M là BSCNN c a a và b. Khi y ta có:a.b = d.M 4. S nguyên t và nh lý c&n b n c a s h c nh ngh a: (s nguyên t dương) M t s nguyên d ơng p c g i là s nguyên t n u 2 i u ki n sau ây c th.a mãn: • p≠1 • p ch# có 2 "c s d ơng là 1 và p. Trong tr ng h p s nguyên tùy ý, Ng i ta nh ngh a s nguyên t nh sau: a. b. nh ngh a: (s nguyên t ) M t s nguyên p c g i là s nguyên t n u 2 i u ki n sau ây c th.a mãn: • p ≠± 1 • v"i m i s nguyên a và b, n u p (a.b) thì p a hay p b. Nh n xét : N u p là m t s nguyên t và p (a1.a2...an) thì t0n t i m t i sao cho p ai. c. % nh lý c'n b n c a s h c: M i s nguyên l"n hơn 1 u có th vi t d "i d ng tích c a các s nguyên t (d ơng). Hơn n!a, cách vi t trên là duy nh t (không k sai khác th t vi t các s nguyên t ). Ví d : 128 = 27 ; 45 = 32.5 IV.Quan h th, t 1. nh ngh a quan h th t M t quan h 2 ngôi R trên m t t$p h p X (khác r2ng) c g i là m t quan h th t$ n u và ch# n u nó có 3 tính ch t: ph n x , ph n x ng, truy n. Khi ó ta c ng nói Trang 26 GIÁO TRÌNH TOÁN NG D NG TIN H C Biên so n : Gv. Ph m Phúc Th nh t$p h p X là m t t$p có th t . N u có thêm tính ch t: v"i m i x, y ∈ X ta có xRy hay yRx thì ta nói R là m t quan h th t$ toàn ph n trên X. Chú ý Trong tr ng h p trên X có nhi u quan h th t thì khi xét n th t trên X ta ph i nói rõ th t nào, và ta th ng vi t t$p h p X có th t d "i d ng m t c p (X,R); trong ó R là quan h th t ang xét trên X. V"i 2 t$p h p có th t X và Y ta có th nh ra m t th t trên tích Descartes XxY d a vào các th t trên X và trên Y. T ó ta XxY tr thành m t t$p h p th t . N u (X,R) là m t t$p h p có th t và A ⊂ X thì quan h th t R thu h p trên t$p A, c ng c ký hi u là R (n u không gây ra nh m l n), là m t quan h th t trên A. Nói m t cách khác, ta có:(X,R) th t và A ⊂ X (A,R) th t 2. nh ngh a ph'n t nh% nh t, l#n nh t, t i ti u, t i i. Cho (X, ≤ ) là m t t$p h p có th t , và A ⊂ X. • Ta g i m t ph n t a ∈ A là m t ph n t nh( nh t c a t$p h p A n u và ch# n u v"i m i x ∈ A ta có : a ≤ x. • Ta g i m t ph n t a ∈ A là m t ph n t l n nh t c a t$p h p A n u và ch# n u v"i m i x ∈ A ta có : x ≤ a. • Ta g i m t ph n t a ∈ A là m t ph n t t i ti u c a t$p h p A n u và ch# n u không t0n t i x ∈ A sao cho x ≠ a và x ≤ a. • Ta g i m t ph n t a ∈ A là m t ph n t t i i c a t$p h p A n u và ch# n u không t0n t i x ∈ A sao cho x ≠ a và a ≤ x. Chú ý • Ph n t nh. nh t (l"n nh t) c a m t t$p h p, n u có, là duy nh t.Ta ký hi u ph n t nh. nh t c a m t t$p h p A là min A hay min (A), và ký hi u ph n t l"n nh t c a A là max A hay max (A). • Ph n t t i ti u (t i i) c a m t t$p h p có th t không nh t thi t là duy nh t. • Ph n t l"n nh t (nh. nh t) c a m t t$p h p, n u có, là ph n t t i i (t i ti u) duy nh t c a t$p h p ó. 3. nh ngh a ch n trên, ch n dư#i c a m t t p h p: Cho (X, ≤ ) là m t t$p h p có th t , và A ⊂ X. • Ta g i m t ph n t x ∈ X là m t ch n dư i c a t$p h p A n u và ch# n u v"i m i a ∈ A ta có : x ≤ a. Ch n dư i l n nh t (n u có), t c là ph n t l"n nh t trong t$p h p t t c nh!ng ch$n d "i c a A c ký hi u là inf (A). • Ta g i m t ph n t x ∈ X là m t ch n trên c a t$p h p A n u và ch# n u v"i m i a ∈ A ta có : a ≤ x. Ch n trên nh( nh t (n u có), t c là ph n t nh. nh t trong t$p h p t t c nh!ng ch$n trên, c a A c ký hi u là sup (A). Nh n xét : N u trong m t t$p h p A t0n t i ph n t max(A) thì ó c ng chính là sup(A). T ơng t , n u trong m t t$p h p A t0n t i ph n t min(A) thì ó c ng chính là inf(A). 4. nh ngh a t p có th t t t: M t t$p h p có th t c g i là có th t$ t t (hay m i t$p con khác r2ng u có ph n t nh. nh t. V. Bi-u 1. #nh c s)p t t) n u và ch# n u Hasse th nh hư#ng (directed graph). M t ! th nh hư ng g0m m t t$p h p các #nh cùng v"i m t t$p h p các c p c g i là các c nh (hay các cung). Trang 27 GIÁO TRÌNH TOÁN NG D NG TIN H C Biên so n : Gv. Ph m Phúc Th nh /0 th bi u di n cho ch m t quan h 2 ngôi R trên m t t$p $ h p X có t$p h p các #nh chính là X, và t$p h p các cung chính là R. N u (a,b) ∈ R thì tr trên bi u 0 ta v& m t cung h "ng t #nh a n ##nh b. /0 th nh h " "ngg t ơng ng c a m t quan h hai ngôi trênn m t t$p h p s& cung c p cho ta nh!ng thông tinn v quan h m t cách r t tr c quan. Do ó ng i ta th ng s d ng các 0 th nh h " "ngg nghiên c u các quan h và các tính ch t c a chúng. Ví d : X = { a,b,c,d} , R = { (a,d), (b,b), (b,d), (c,a), (c,b), (d,b)}} . /0 th nh h "ng (X,R) có th c v& ra nh sau: C nh (b,b) c v& trêên bi u 0 b i cung xu t phát t #nh b vàà quay tr l i chính #nh b. C nh n y c g i là m t "vòng" t i b. Chúng ta có th th y r ng m t quan h 2 ngôi trên m t t$p $ h p là i x ng khi và ch# khi trên 0 th bi u dii n t ơng ng m2i c p #nh u có 2 cun ung n i theo 2 h "ng ng c nhau. Nh v$y 0 th c a quan h trong ví d trên ta k t lu$n $n quan h n y không có tính i x ng. irected graph). th nh hư#ng (dire / i v"i m t t$p h p X (h!u h n) có th t ρ thì trên 0 th nh h "ng t ơng ng có nhi u c nh không nnh t thi t ph i v& ra b i vì chúng c hi h u ng m. Nói m t cách khác, các tính ch t c a quan h th t giúp ta bi t c có nh!n !ng c nh ơng nhiên có trên 0 th c a quan h ; và v nh!ng c nh ó s& không c v& ra trên ên 0 th . Tr "c h t ta th y r ng t i m2i #nh c a 0 th ph i có m t vòng v do tính ph n x c a quan h th t , nên các ác vòng n y s& không c v& ra trên 0 th . Ngoài ra quan h th t còn có tính truy n, nêên ta s& không c n v& ra c nh (a,c) n u trêên 0 th có các c nh (a,b) và (b,c) v"i b là m t #nh # nào ó. Hơn n!a, n u (a,b), (b,c), vàà (c,d) là các c nh thì ta c ng lo i ra c nh (a,d). Ch Chúng ta c ng không ghi m i tên nh h "ng " trên các c nh v"i qui "c r ng : các nh c a ! th ư c b trí trên hình v sao cho hư ư ng m"i tên c a các c nh là "hư ng lên". "ngg ((d ng bi u 0) t ơng ng c a t$p h p cóó th t (X, ρ ) có th /0 th nh h " c rút g n l i thành m t bi u 0 ơn gi n hơn nh ng v n hàm m ch a y nh!ng thông tin c a th t ρ trênn t$p t h p X, b ng cách là ta ch# v& cung n i t #nh x n #nh x' (x' khác x) khi ta có x ρ x', x và không t0n t i y khác x và x' sao choo x ρ y và y ρ x'. Bi u ( d ng rút g n n'y ư c g i là bi u Hasse c a t p h p có th h t (X, ρ ). Ví d : Xét th t ≤ thông th ng trên t$p h p X = { 1,2,3,4} . /0 th y c a (X, ≤ ) có d ng trong hình (a) d "i ây. Hìnhh (b) là d ng rút g n c a 0 th , t c là bi u 0 Hasse c a th t ≤ trên X. 2. Trang 28 GIÁO TRÌNH TOÁN NG D NG TIN H C Biên so n : Gv. Ph m Phúc Th nh • V& bi u 0 Hass sse bi u di n th t “chia h t”, c ký hi u là  , trên t$p h p { 1,2,3,4,6,8,12} . B)t u t 0 th nh h "ng c a th t n y, ta lo i b. cácc vòng v t i các #nh. Sau ó lo i b. các c nh có th c suy ra b i tính ch t truy n c a th t : (1,4), (1,6), (1,8), (1,12), (2,8 ,8), (2,12) và (3,12). Cu i cùng ta c bi u 0 Hasse g0m các c nh (1,2), (1,3), (2,4), 4), (2,6), (3,6), (4,8), (4,12), và (6,12) : • V& bi u 0 Hasse sse cho th t ⊂ trên t$p h p P(E), trong ó E = { a,b,c} . C ng làm t ơ ơngg t nh trong ví d tr "c ta lo i b. các c nhh sau ây t 0 th bi u di n cho th t : ((∅ ,{ a,b} ), (∅ ,{ a,c} ), (∅ ,{ b,c} ), (∅ ,{ a,b,c} a ), ({ a} ,{ a,b,c} ), ({ b} ,{ a,b,c} ), và ({ c} ,{ a,b,c} ). T ó ta có bi u 0 Has asse c v& nh sau : Chú ý Chúng ta còn có m t cách khác nêu lên khái ni m bi u 0 Hasse Ha cho m t c u trúc th t (X,ρ ) b ng cách a ra m t khái ni m tr i tr$c ti p: Cho x ∈ X, m t ph n t y ∈ X c g i là m t tr i tr c ti p c a x n u và ch# n u ta có 2 i u ki n sau ây : (1) x ρ y (y là m t ch$n $n ttrên c a x), (2) V"i m i z, n u x ρ z và z ρ y thì z = x hay z = y. Bi u 0 Hasse cho c u trúc th t (X,ρ ) là m t 0 th nh h " "ngg có t$p h p #nh là X và t$p h p các c nh là m t phh n c a ρ g0m các c nh (a,b) sao cho b là m t tr i tr c ti p c a a. Trang 29 GIÁO TRÌNH TOÁN Ch NG D NG TIN H C ng 4 : Biên so n : Gv. Ph m Phúc Th nh .I S$ BOOLE I. Phép toán 1. nh ngh a phép toán2 ngôi Cho X là m t t$p h p khác r2ng. M t phép toán hai ngôi trên t$p h p X là m t ánh x T i t XxX vào X. Ký hi u c a ánh x c g i là ký hi u c a phép toán hay là m t toán t . 7nh c a c p (a,b) qua ánh x T c g i là k t qu th c hi n phép toán T trên 2 ph n t a và b, và th ng c vi t là a T b. Nh v$y, n u T là m t phép toán 2 ngôi trên X thì ta có ánh x : T : XxX → X (a,b)| T(a,b) = a T b. 2. nh ngh a phép toán 1 ngôi Cho X là m t t$p h p khác r2ng. M t phép toán 1 ngôi trên t$p h p X là m t ánh x T i t X vào X. Ký hi u c a ánh x c g i là ký hi u c a phép toán hay là m t toán t . 7nh c a a qua ánh x T c g i là k t qu th c hi n phép toán T trên ph n t a. Ví d Cho E là m t t$p h p. t X = P(E) (t$p các t$p con c a E). Trên X có các phép toán t$p h p thông th ng : Phép giao hai t$p h p, c ký hi u là ∩ . Phép h i hai t$p h p, c ký hi u là ∪ . Phép l y bù c a m t t$p h p, c ký hi u là , . Phép toán ∩ và ∪ là các phép toán 2 ngôi, phép toán -. / là phép toán 1 ngôi. 3. Các chú ý M t cách t(ng quát, ta có th nh ngh a phép toán n-ngôi trên m t t$p h p X là n m t ánh x i t X vào X. 8ng v"i m2i b n ph n t (a1, ... , an) phép toán s& cho ta m t ph n t k t qu thu c X. Trong tr ng h p t$p h p X là h!u h n thì ng i ta có th nh ngh a hay xác nh phép toán b ng cách li t kê k t qu th c hi n phép toán cho m i tr ng h p có th có. Ví d X = { a1, ... , an } g0m n ph n t . Gi s * là m t phép toán 2 ngôi trên X. Khi ó, phép toán * có th c xác nh b i b ng sau ây: aj * a1 … … an a1 : : : … … : an B ng trên c g i là b ng Cayley c a phép toán 2 ngôi. Nh v$y ng v"i m2i phép toán 2 ngôi trên X ta có m t ma tr$n có c p n v"i ph n t dòng i c t j b ng ai* aj. V sau, nhi u tính ch t c a phép toán s& c xem xét thông qua ma tr$n n y. Chúng ta ã t ng th y nh!ng phép toán 2 ngôi c nh ngh a b ng b ng nh th ; ó là các phép toán logic ∨ (hay), ∧ (và), → (kéo theo). 4. Các tính ch t i s c a phép toán 2 ngôi a. % nh ngh&a 1. Trang 30 GIÁO TRÌNH TOÁN NG D NG TIN H C Biên so n : Gv. Ph m Phúc Th nh Ta nói m t phép toán 2 ngôi T trên m t t$p h p X có tính giao hoán n u ∀ x,y ∈ X : x T y = y T x Ta nói m t phép toán 2 ngôi T trên m t t$p h p X có tính k t h p n u ∀ x,y,z ∈ X : x T (y T z) = (x T y) T z b. % nh ngh&a 2. Cho X là m t t$p h p khác r2ng, * là m t phép toán 2 ngôi trên X. • Phép toán * c g i là l y ng khi và ch# khi x * x = x , v"i m i x∈ X • M t ph n t e∈ X c g i là ph n t trung hòa c a phép toán * trên X khi và ch# khix * e = e * x = x , v"i m i x∈ X • Gi s phép toán * có ph n t trung hòa là e. Ta nói m t ph n t x∈ X là kh ngh ch (hay có ngh ch o) khi và ch# khi∃ x’∈ X : x * x’ = e = x’ * x Nh n xét : • N u phép toán có tính k t h p thì ph n t trung hòa (n u có) là duy nh t, và trong tr ng h p t(ng quát ng i ta còn g i là “ph n t ơn v ”. • Khi phép toán có tính k t h p và có ph n t trung hòa, v"i m2i ph n t x kh ngh ch, ph n t x’ trong nh ngh a trên là duy nh t. Ta g i x’ là ph n t ngh ch o c a x, và ký hi u là x-1. Ghi chú : • Trong tr ng h p phép toán c ký hi u là ‘.’ (d u nhân) thì ph n t trung hòa c a phép toán th ng c ký hi u 1, và c g i là “ ơn v ”. • Khi phép toán c ký hi u là ‘+’ (d u c ng) thì ph n t trung hòa c a phép toán th ng c ký hi u 0, và c g i là “zero”. Trong tr ng h p n y, m2i ph n t x th.a i u ki n kh ngh ch s& c g i là “có i”, và ph n t x’ trong nh ngh a c g i là ph n t i c a x. Ta ký hi u ph n t i c a x là -x. Các Ví d : • Trên t$p B = { 0,1} (g0m 2 giá tr Boole), có các phép toán ∨ và ∧ . Phép toán V có các tính ch t : giao hoán, k t h p, có trung hòa là 0, l y ng. Ph n t 1 không kh ngh ch i v"i phép ∨ vì 1 ∨ x = 1 ≠ 0 v"i m i x∈ B. Phép toán ∧ có các tính ch t : giao hoán, k t h p, có trung hòa là 1, l y ng. Ph n t 0 không kh ngh ch i v"i phép ∧ vì 0 ∧ x = 0 ≠ 1 v"i m i x∈ B. • Phép toán + (c ng) trên các t$p h p s N, Z, Q, R, C có các tính ch t : giao hoán, k t h p, có trung hòa (hay ph n t zero) là 0. Trong các t$p h p Z, Q, R, C m i s u có i. Phép toán * (nhân) trên các t$p h p s N, Z, Q, R, C có các tính ch t : giao hoán, k t h p, có trung hòa (hay ph n t ơn v ) là 1. Trong các t$p h p Q, R, C m i s khác 0 u kh ngh ch c. % nh lý 1. Cho * là m t phép toán 2 ngôi giao hoán, k t h p và l y ng trên m t t$p h p X. Khi ó, n u R là quan h 2 ngôi trên X c nh ngh a b i (a R b) ⇔ (a * b = b) thì ta có : R là m t quan h th t . ∀ a,b ∈ X : sup(a,b) = a * b. 5. nh ngh a phân b bên trái, ph i c a phép toán 2 ngôi. • Cho T và * là hai phép toán 2 ngôi trên m t t$p h p X. Ta nói phép toán * phân b bên trái trên phép toán T khi và ch# khia * (b T c) = (a * b) T (a * c)v"i m i a, b, c ∈ X. • T ơng t , ta nói * phân b bên ph i trên T khi và ch# khi (b T c) * a = (b * a) T (c * a)v"i m i a, b, c ∈ X. • Khi * phân b bên trái và bên ph i trên T thì ta nói chung là * phân b trên T. Trang 31 GIÁO TRÌNH TOÁN NG D NG TIN H C Biên so n : Gv. Ph m Phúc Th nh Ví d : • Trên t$p h p các s th c R, phép toán * (nhân) là phân b trên phép toán +. Nh ng phép + không phân b trên phép *. • Cho E là m t t$p h p. Trên P(E) ta bi t có 2 phép toán c ký hi u là ∪ và ∩ . Theo các tính ch t c a các phép toán t$p h p, ta có phép toán ∩ phân b trên ∪ , t c là A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)v"i m i A, B, C ∈ P(E). Ng c l i, phép toán ∪ c ng phân b trên phép toán ∩ . 6. nh ngh a C u trúc i s . M t i s (hay m t c u trúc i s ) là m t t$p h p khác r2ng X trên ó có m t hay nhi u phép toán th.a mãn các tính ch t nào ó. Gi s các phép toán tên X là *, T, .... Ta s& ký hi u i s là (X, *, T, ...). II. 1. i s+ boole nh ngh a i s Boole T$p h p khác r2ng S cùng v"i các phép toán ký hi u nhân (.), c ng (+), l y bù (’) c g i là m t i s Boole n u các tiên sau ây c tho mãn v"i m i a, b, c∈S. a. Tính giao hoán: a) a.b = b.a, b) a+b = b+a. b. Tính k t h p: a) (a.b).c = a.(b.c), b) (a+b)+c = a+(b+c). c. Tính phân ph i: a) a.(b+c) = (a.b)+(a.c), b) a+(b.c) = (a+b).(a+c). d. T!n t i ph n t trung hoà: T0n t i hai ph n t khác nhau c a S, ký hi u là 1 và 0 sao cho: a) a.1 = 1.a = a, b) a+0 = 0+a = a. 1 g i là ph n t trung hoà c a phép . 0 g i là ph n t trung hoà c a phép +. e. T!n t i ph n t bù: V"i m i a ∈ S, t0n t i duy nh t ph n t a’∈ S sao cho: a) a.a’ = a’.a = 0, b) a+a’ = a’+a = 1. a’ g i là ph n t bù c a a. f. Các thí d • / i s lôgic là m t i s Boole, trong ó S là t$p h p các m nh , các phép nh) t ơng ng v"i . , +, ’, các h ng toán ∧ (h i), ∨ (tuy n), − (ph ( úng), s (sai) t ơng ng v"i các ph n t trung hoà 1, 0. • / i s t$p h p là m t i s Boole, trong ó S là t$p h p P(X) g0m các t$p con c a t$p khác r2ng X, các phép toán ∩ (giao), ∪ (h p), − (bù) t ơng ng v"i . , +, ’, các t$p X, Ø t ơng ng v"i các ph n t trung hoà 1, 0. • Cho B= {0,1}, các phép toán . , +, ’ trên B c nh ngh a nh sau: 1.1 = 1, 1+1 = 1, 1’ = 0, 1.0 = 0, 1+0 = 1, 0’ = 1. (1) 0.1 = 0, 0+1 = 1, Trang 32 GIÁO TRÌNH TOÁN NG D NG TIN H C Biên so n : Gv. Ph m Phúc Th nh 0.0 = 0, 0+0 = 0, Khi ó B là m t i s Boole. /ây c ng chính là i s lôgic, trong ó 1, 0 t ơng ng v"i ( úng), s (sai). M2i ph n t 0,1 c a B g i là m t bit. Ta th ng vi t x thay cho x’. Chú ý: • Tr "c h t c n l u ý i u quan tr ng sau ây: các tiên c a i s Boole c x p theo t ng c p a) và b). T m2i tiên a), n u ta thay . b i +, thay + b i ., thay 1 b i 0 và thay 0 b i 1 thì ta c tiên b) t ơng ng. • Ta g i c p tiên a), b) là i ng u c a nhau. Do ó n u ta ch ng minh c m t nh lý trong i s Boole thì ta có ngay m t nh lý khác, i ng u c a nó, b ng cách thay . và 1 t ơng ng b i + và 0 (và ng c l i). Ta có: Quy t c i ng)u: % i ng*u c a m t nh lý là m t nh lý. nh lý: Tính nu t Tính lu- ,ng H th c De Morgan a) a.0 = 0, a) a.a = a, a) (a.b)’ = a’+b’, b) a+1 = 1 b) a+a = a. b) (a+b)’ = a’.b’. Ph n bù H th c bù kép Tính hút a) 1’ = 0, (a’)’ = a. a) a.(a+b) = a, b) 0’ = 1. b) a+(a.b) = a. III. Hàm boole 1. nh ngh a hàm Boole Cho 2 t$p h p B = {0, 1} và Bn = {(x1, x2, …, xn) | xi∈ B, 15 i 5 n}, ây B và n B là các i s Boole. Bi n x c g i là m t bi n Boole n u nó nh$n các giá tr ch# t B. M t hàm Bool theo n bi n là m t ánh x f: Bn → B (x1, x2, …, xn) f(x1, x2, …, xn) T nh ngh a trên ta th y m t hàm Bool có th c xác nh b ng cách li t kê d "i d ng b ng, g i là b ng giá tr c a hàm Bool, hay b ng cách cho m t bi u th c Bool. Ví d : Cho f và g : B3→ B là các hàm Bool (theo 3 bi n x, y, z) xác nh b i x y z f(x,y,z) 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1 và g(x,y,z) = xy + z. 2. Các phép toán hàm Boole: T các phép toán c ng, nhân và bù trên B ta nh ngh a các phép toán c ng, nhân và bù trên các hàm Bool theo n bi n nh sau: 1 1, x2, …, xn) = 1 - f(x1, x2, …, xn) = bù c a f(x1, x2, …, xn) • 0(x • (f+g) (x1, x2, …, xn) = f(x1, x2, …, xn) + g(x1, x2, …, xn) Trang 33 GIÁO TRÌNH TOÁN NG D NG TIN H C Biên so n : Gv. Ph m Phúc Th nh • (f.g) (x1, x2, …, xn)) = f(x1, x2, …, xn) . g(x1, x2, …, xn) • T ơng t nh các phép ph toán trên B, các phép toán trên các hà hàm Bool n y c ng có các tính ch t nh : Lu$t L ph nh c a ph nh; Lu$t l y ng; Lu$t v ph n t trung hòa; Lu$t v ph p n t trung bù; Lu$t giao hoán; Lu$t $ k t h p; Lu$t phân b ; Lu$t De Morgan; Lu$t Lu th ng tr . Ví d : D "i ây là m t s ví d áp d ng các lu$t trong vi c bi n (i ( các bi u th c Bool. x + xy = x1 + xy = x(1+y) = x 1 = x wx + +y+ = wx + ( + = wx + (x + )+y+ )+y+ = (wx + x) + y + + =x+y+ IV.Bi-u di n hàm Boole: 1. nói nh ngh a: guyên d ơng và f là m t hàm Bool theo n bi b n x1, x2, …, xn. Ta Cho n là m t s ngu • M2i bi u th c Bool B (hay hàm Bool) có d ng xi ho c là m t t ơn. • M t bi u th c Bool B là m t tích cơ b n n u nó có d ng y1y2…yn v"i yi = xi ho c v"i m i i = 1, 2, …, n. • M t bi u di n c a f d "i d ng t(ng c a các tích cơ b n làà d ng chính t)c tuy n c a f, vi t t)c là d.n.f (disjunctive normal form) c a f. 2. M nh : M i hàm Bool f khá hác 0 u có th vi t m t cách duy nh t (kh không k sai khác v th t tr "c sau c a các tích ch cơ b n d "i d ng d.n.f). Ví d : Tìm d.n.f c a hààm Bool f: B3→ B v"i f(x,y,z) = xy + Ta có th l$p b ng giá tr c a f nh sau: x y Z xy f 0 0 0 0 0 0 0 0 1 0 1 1 0 1 0 0 0 0 0 1 1 0 1 1 1 0 0 0 0 0 1 0 1 0 0 0 1 1 0 1 0 1 1 1 1 1 0 1 C t giá tr c a f có 4 giá iá tr ( ng v"i 4 tr ng h p v giá tr c a xx, y, z) là 1. Chúng ch# ra 4 tích cơ b n trong ng d.n.f c a f, và t ó ta có:f(x,y,z) = M t cách khác gi i quy q t bài toán n y là s d ng các tính ch t c a các phép toán Bool, ta có : xy + =xy(z+ =x + (y+ )z = V. M ng các c ng 1. C!ng Logic x Trang 34 GIÁO TRÌNH TOÁN NG D NG TIN H C Biên so n : Gv. Ph m Phúc Th nh Xét m t thi t b nh hình trên, có m t s ng vào (d n tín hi u vào) và ch# có m t ng ra (phát tín hi u ra). Gi s các tín hi u vào x1, x2, …,, xn (ta g i là u vào hay input) c ng nh tín hi u ra F ( u ra hay output) u ch# có haii tr t ng thái khác nhau, t c là mang m t bit thông tin tin, mà ta ký hi u là 0 và 1. Ta g i m t thi t b v"i các u vào và u ra mang giá trr 0, 1 nh v$y là m t m ch lôgic. / u ra c a m t m ch c lôgic là m t hàm Boole F c a các u vào v x1, x2, …, xn. Ta nói m ch lôgic trong hình trên tr th c hi n hàm F. Các m ch lôgic c t o thành t m t s m ch cơ s , g i làà c(ng c lôgic. 2. M t s c!ng logic thư ng g"p a. C#ng NOT: p nh. C(ng ch# có m t C(ng NOT th c hi n hàm ph / u ra F(x) là ph nh c a u vào x. F ( x) = x = u vào. 0 khi x = 1, 1 khi x = 0. Ch ng h n, xâu bit 1001 0101011 qua c(ng NOT cho xâu bit 011010 10100. b. C#ng AND: C(ng AND th c hi n hàm h i. / u ra F(x,y) là h i (tích) c a các F ( x, y ) = xy = u vào. 1 khi x = y = 1, 0 trongg ccác truong hop khác Ch ng h n, hai xâu bitt 101001101 1 và 111010110 qua c(ng AND D cho 101000100. c. C#ng OR: C(ng OR th c hi n hàm tuy n (t(ng). / u ra F(x,y) là tuy n (t(ng)) c a các 1 khi x = 1 hay y = 1, F ( x, y ) = x + y = 0 khi hi x = y = 0. u vào. Ch ng h n, hai xâu bit 101001101 1 và 111010100 qua c(ng OR ch cho 111011101. 3. M ch logic g: a. T# h p các c#ng: Các c(ng lôgic cóó th l)p ghép c nh!ng m ch lôgic ic th c hi n các hàm Boole ph c t p hơn. Nh ta ã bi t r ng m t hàm Boole b t k* có th bi u di n b ng m t bi u th c ch# ch a các phép ép −, ., +. T ó suy ra r ng có th l)p ghép ép thích h p các c(ng NOT, AND, OR c m t m ch lôgic th c hi n m t hàm Boole b t k*. Trang 35 GIÁO TRÌNH TOÁN NG D NG TIN H C Biên so n : Gv. Ph m Phúc Th nh Thí d : Xây d ng m t m ch lôgic th c hi n hàm Boole cho b i b ng sau. x y z F(x,y,z) 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 1 1 1 1 1 Theo b ng này, hàm F có d ng t(ng (tuy n) chu6n t)c hoàn toàn là: F ( x, y , z ) = xyz + xy z + x yz . Hình d "i ây v& m ch lôgic th c hi n hàm F ã cho. Bi u th c c a F(x, y, z) có th rút g n: xyz + xy z + x y z = xy ( z + z ) + x y z = xy + x y z . Hình d "i ây cho ta m ch lôgic th c hi n hàm xy + x yz . Hai m ch lôgic trong hai hình trên th c hi n cùng m t hàm Boole, ta nói ó là hai m ch lôgic t ơng ơng, nh ng m ch lôgic th hai ơn gi n hơn. VI.Công th,c a th,c t+i ti-u / i v"i các d ng công th c a th c c a m t hàm Bool ta th ng quan tâm n các d ng công th c a th c t i ti u. M t cách tr c quan ta g i m t công th c a th c (D) c a m t hàm Bool f là t i ti u khi không có công th c nào khác c a f ơn gi n hơn nó theo ngh a sau ây: • B t k* m t s bi n (i nào trên công th c (D) u d n n m t công th c không ph i là công th c a th c, và • N u f có th vi t "i m t d ng công th c a th c (D') khác thì s s h ng c a (D') l"n hơn ho c b ng s s h ng c a (D) và ta có th ch n ra các s h ng u' (t c là m t ơn th c) trong công th c (D') t ơng ng v"i các s h ng u trong công th c (D) sao cho s "th a s " trong u' là l"n hơn ho c b ng s th a s trong u. Trang 36 GIÁO TRÌNH TOÁN NG D NG TIN H C Biên so n : Gv. Ph m Phúc Th nh / tìm các công th c a th c t i ti u c a hàm Bool v"i s bi n nh. hơn ho c b ng 6 ta có th s d ng các bi u 0 Karnaugh. VII. Bi-u Karnaugh 1. Khái ni m Cho hàm Boole f theo n bi n. Bi u 0 Karnaugh c a hàm f là m t hình ch! nh$t n g0m 2 ô sao cho: • M2i ô s& t ơng ng v"i m t dòng trong b ng c a f. • M t ô s& c ánh d u n u và ch# n u t i dòng t ơng ng v"i nó trong b ng chân tr , giá tr c a f b ng 1. • Các ô c cho t ơng ng v"i các dòng sao cho hai dòng t ơng ng v"ihai ô c nh nhau luôn sai khác nhau v giá tr c a ch# m t bi n duy nh t. hình v& sau ây là cách t( ch c bi u 0 Karnaugh cho m t hàm Boole theo 3 bi n. Các ô c xác nh t ơng ng v"i các dòng d a vào cách ánh a ch# c a các bi n nh trong hình v&. Ch ng h n nh ô (1) có a ch# là x, y, z , do ó, nó s& t ơng ng v"i dòng {x=0,y=0,z=0} trong b ng chân tr . Ho c, ô (2) có a ch# là x, y, z và nó t ơng ng v"i dòng {x=0,y=1,z=0}. Rõ ràng ô (1) và (2) là hai ô c nh nhau và nó c ng t ơng ng v"i hai dòng trong b ng chân tr ch# sai khác nhau giá tr c a bi n y. 2. Chú ý: • Có nhi u cách b trí v trí c a các bi n khác nhau, mi n sao ph i m b o c nh!ng yêu c u c a m t bi u 0 Karnaugh. • Hai ô n m biên v n c coi là hai ô c nh nhau (t ng t ng r ng bi u 0 Karnaugh c cu n l i). 3. nh ngh a. Cho bi u 0 Karnaugh c a m t hàm Boole f theo n bi n. Ta nh ngh a: • M t t bào là m t hình ch! nh$t g0m 2k ( 0 ≤k ≤n ) ô c ánh d u li n nhau. • M t t bào l"n là m t t bào mà không b ph b i b t c t bào nào khác. Ví d : Hàm Boole có 3 bi n f(x;y;z) có b ng chân tr nh sau : bi u 0 Karnaugh c a hàm Boole f này nh hình 2, ta có Các tê bào x. y.z , xyz , x. y.z , xyz (t bào 1 ô); xy, yz, xz (t bào 2 ô) Các t bào l"n xy, yz, xz (t bào 2 ô) 4. Phư ng pháp Karnaugh tìm công th c a th c t i ti u c a hàm Boole. Cho hàm Boole f (d "i d ng công th c ho c b ng chân tr ), tìm công th c a th c t i ti u c a f , ta th c hi n theo các b "c sau: Trang 37 GIÁO TRÌNH TOÁN NG D NG TIN H C Biên so n : Gv. Ph m Phúc Th nh • B c 1. Xây d ng bi u 0 Karnaugh c a f • B c 2. Xác nh t t c các t bào l"n trong bi u 0 Karnaugh v a xây d ng • B c 3. Tìm m t s l ng ít nh t các t bào l"n ph kín các ô ã ánh d u trong bi u 0 Karnaugh, ghép chúng l i v"i nhau b ng phép +, ta s& c công th c a th c t(i ti u c n tìm. 5. Các ví d . a. Ví d 1 : Cho hàm Boole f có b ng chân tr d "i ây. Hãy tìm công th c a th c t i ti u c a f. B c 1. Xây d ng bi u 0 Karnaugh c a hàm f: B B c 2. Xác nh t t c các t bào l"n: xy, yz, xz c 3. Tìm m t s l ng ít nh t các t bào l"n ph các ô ã c ánh d u. T ng t ng r ng chúng ta có th tách riêng các t bào l"n, khi ó hình nh v các t bào l"n nh sau: Nh v$y th c ch t vi c ch n các t bào l"n ph kín các ô c ánh d u trong bi u 0 Karnaugh chính là vi c ch n các t bào l"n r0i x p ch0ng chúng lên nhau sao cho hình thu c gi ng bi u 0 Karnaugh ban u. Trong ví d trên, rõ ràng là trong tr ng h p này, ta ph i ch n c 3 t bào l"n. Nh v$y, công th c a th c t i ti u c a hàm f này s& là:f =xy +yz +xz b. Ví d 2 : Cho hàm Boole f (x,y,z)= x. y.z + x. y + x. y.z . Hãy tìm công th c a th c t i ti u c a f. B c 1. Xây d ng bi u 0 Karnaugh c a hàm f: Trang 38 GIÁO TRÌNH TOÁN B B NG D NG TIN H C Biên so n : Gv. Ph m Phúc Th nh c 2. Xác nh t t c các t bào l"n: x.z; x. y; y.z c 3. Tìm m t s l ng ít nh t các t bào l"n ph các ô ã c ánh d u. M c dù có 3 t bào l"n, nh ng trong tr ng h p này, ph kín các ô ã ánh d u trong b n 0 Karnaugh, ta ch# c n ch n 2 t bào l"n: x.z; y.z Nh v$y, công th c a th c t i ti u c a hàm f này s& là: x.z + y.z c. Áp d ng cho hàm boole 4 bi n / i v"i hàm Boole theo 4 bi n, bi u 0 Karnaugh s& bao g0m 16 ô x pnh d "i ây: c s)p Chú ý: / i v"i bi u 0 Karnaugh c a hàm Boole 4 bi n, hai ô trên cùng và d "i cùng (c a cùng m t c t) v n c coi là c nh nhau, 4 ô 4 góc v n c coi là c nh nhau. /i u này là b i vì bi u 0 Karnaugh có th c g p l i theo c 2 chi u ngang và d c. Ví d : Hãy tìm công th c a th c t i ti u c a f sau ây B f(x,y,,z,t)= x. y.z.t + x. y.z.t + x. y.z.t + x. y.z.t + x. y.z.t + x. y.z.t + x. y.z.t c 1. Xây d ng bi u 0 Karnaugh c a hàm f: x x t z t z t y y y Trang 39 GIÁO TRÌNH TOÁN B NG D NG TIN H C c 2. Xác Biên so n : Gv. Ph m Phúc Th nh nh t t c các t bào l"n: B c 3. Tìm m t s l ng ít nh t các t bào l"n ph các ô ã ' ây, d th y là ta không th b. t bào l"n nào. Nh v$y, công th c ath c t i ti u c a hàm Boole ban u là: c ánh d u. f(x,y,,z,t)= x.z + y.z + x. y.t d. Khi áp d ng phương pháp bi u ! Karnaugh, c n lưu ý các i m sau: • V& bi u 0 Karnaugh ph i tuy t i chính xác. Ch# nh m l n vi c ánh d u 1 ô s& d n t"i k t qu hoàn toàn sai l ch trong nh!ng b "c ti p theo. • Vi c xác nh các t bào l"n ph i th$n tr ng, n u xác nh không chính xác các t bào l"n thì công th c thu c cu i cùng có th không ph i là công th c d ng ơn gi n nh t. (Do các t bào l"n có nhi u ô hơn, nh ng s bi n bi u di n l i ít hơn). • Khi ch n các t bào l"n ph các ô c ánh d u c n u tiên ch n nh!ng t bào l"n b)t bu c (không th không ch n) tr "c. V"i nh!ng ô c ánh d u ch# thu c m t t bào l"n duy nh t thì t bào l"n này b)t bu c ph i c ch n. Bên c nh ó khi có hai t bào l"n cùng ph qua m t ô thì ta u tiên ch n t bào l"n có nhi u ô hơn ph . Trang 40 GIÁO TRÌNH TOÁN NG D NG TIN H C Biên so n : Gv. Ph m Phúc Th nh BÀI T/P CHƯ NG 1 1. N u Q có chân tr là T, hãy xác th c m nh sau c ng là úng nh chân tr c a các bi n m nh (Q 3 ((¬P R) ¬S)) P, R, S n u bi u (¬S 3 (¬R Q)) 2. Cho o n ch ơng trình sau • if n>5 then n:=n+2 ; • if ((n+2 = 8) or (n-3=6)) then n:= 2*n + 1 ; • if ((n-3=16) and (n div 5=1)) then n:= n + 3 ; • if ((n<>21) and (n-7=15)) then n:= n - 4 ; • if ((n div 5 = 2) or (n+1=20)) then n:=n+1 ; Ban u bi n nguyên n c gán tr là 7. Hãy xác nh giá tr n trong các tr ng h p sau : a. Sau m2i câu l nh ( ngh a là khi qua câu l nh m"i thì gán l i n = 7) b. Sau t t c các l nh ( s d ng k t qu c a câu l nh tr "c tính toán cho câu sau) 3. Cho o n ch ơng trình sau : • if n-m = 5 then n:= n-2 ; • if ((2*m=n) and (n div 4 =1) then n:= 4*m - 3 ; • if ((n<8) or (m div 2=2)) then n:= 2*m else m:= 2*n ; • if ((n<20) and (n div 6 =1) then m:= m-n-5 ; • if ((n= 2*m) or (n div 2= 5)) then m:= m+2 ; • if ((n div 3 = 3) and (m div 3 <>1)) then m:= n ; • if m*n <> 35 then n:= 3*m+7 ; Ban u bi n nguyên n = 8 và m = 3. Hãy xác nh giá tr c a m, n trong các tr ng h p sau : a. Sau m2i câu l nh ( ngh a là khi qua câu l nh m"i thì gán l i n = 7) b. Sau t t c các l nh ( s d ng k t qu c a câu l nh tr "c tính toán cho câu sau) 4. Vòng l p Repeat ... Until trong m t o n ch ơng trình Pascal nh sau : Repeat ..... Until ((x<>0) and (y>0)) or ( not ((w>0) and (t=3)) ; V"i m2i cách gán giá tr bi n nh sau, hãy xác nh trong tr l p k t thúc. a. x= 7, y= 2, w= 5, t= 3 b. x= 0, y= 2, w= -3, t= 3 c. x= 0, y= -1, w= 1, t= 3 d. x= 1, y= -1, w= 1, t= 3 5. Cho a và b là hai s nguyên d ơng. Bi t r ng, trong 4 m nh úng và 1 m nh sai. Hãy tìm m i c p s (a, b) có th có. a. a+1 chia h t cho b b. a = 2b + 5 c. a+b chia h t cho 3 d. a+7b là s nguyên t 6. Không l$p b ng chân tr , s d ng các công th c t ơng ng h p nào thì vòng sau ây có 3 m nh ơng logic, ch ng minh Trang 41 GIÁO TRÌNH TOÁN NG D NG TIN H C Biên so n : Gv. Ph m Phúc Th nh r ng các bi u th c m nh sau là h ng úng a. (P Q)3P b. P3(¬ P 3 P) c. P3((Q3 (P Q)) d. ¬ (P ¬Q)3¬ P e. ((P3Q) (Q3R)) 3 (P3R) 7. Không l$p b ng chân tr , s d ng các công th c t ơng th c m nh G có là h qu c a F không ? a. F = P (Q R) G = (P Q) R b. F = (P3Q) (Q3R) G = P3 (Q 3R) c. F = P Q G = (¬P3Q) (P3 ¬Q) 8. Không l$p b ng chân tr , ch ng minh các t ơng ơng logic sau ây: a. (P Q) ¬ (¬P Q) ⇔ P b. ¬(¬((P Q) R) ¬Q) ⇔ Q R c. ((P Q) (P ¬Q)) Q ⇔ P Q d. ¬(P Q) ((¬P Q) ¬Q) ⇔ ¬(Q P) e. (P3Q) (¬Q (R ¬Q)) ⇔ ¬ (Q P) f. P (P (P Q) ⇔ P g. P Q (¬P ¬Q R) ⇔ P Q R h/ ((¬P ¬Q) 3 (P Q R ) ⇔ P Q h. P ((¬Q 3 (R R)) ¬ (Q (R S) (R ¬S))) ⇔ P i. (P Q R) (P S ¬Q) (P ¬S R) ⇔ P (R (S ¬Q) 9. Cho P(x,y) là câu “x là thành ph c a y”. Hãy xác sau: a) P(Viên Ch,n, Lào) b) P(Hà N i, Vi t Nam) 10. ơng logic, xét xem bi u nh giá tr chân lý c a các m nh c) P(Hà N i, Trung Qu c) d) P(B)c Kinh, Trung Qu c) Cho P(x, y) là m nh ch a bi n: “x ã h c h c ph n y”. V"i x ∈ X: t$p h p các sinh viên trong l"p, y ∈ Y: t$p các h c ph n ph i h c trong k* này. Hãy di n t các m nh sau: a) ∃x ∃y P(x,y) d) ∃x ∀y P(x,y) g) ∃x∀yP ( x, y ) b) ∀x ∃y P(x,y) e) ∀x∃y P ( x, y ) h) ∀y ∃x P(x,y) c) ∃x∀y P ( x, y ) f) ∀x ∀y P(x,y) i) ∃y ∀x P(x,y) 11. Cho F(x,y) là m nh ch a bi n “x có th l a g t y” trên t$p X là t$p con ng th gian này. Hãy di n t các câu sau dùng l ng t : a. M i ng i ai c ng có th l a g t tôi. b. Tôi không th l a g t t t c m i ng i. c. Không ai có th l a g t t t c m i ng i. d. Tôi không th l a g t dù có m t ng i. e. Không ai có th l a g t c chính mình. 12. Dùng l ng t di n t các câu nói sau, ph nh chúng r0i d ch các ph l i câu thông th ng: a. M i ng i ai c ng thích môn toán r i r c. b. Có m t ng i ch a bao gi nhìn th y chi c máy tính. c. Có m t ng i ã h c t t c các môn toán. i trên nh này tr Trang 42 GIÁO TRÌNH TOÁN NG D NG TIN H C Biên so n : Gv. Ph m Phúc Th nh d. Ch a có ai ã nhìn th y chi c máy tính l ng t . e. Có m t l"p h c mà m i ng i trong ó u gi.i môn toán. f. Trong m i l"p h c u có m t h c sinh không h c gi.i môn toán. 13. Cho A, B, C là các t$p h p. Ch ng minh r ng: (A - B) - C = (A - C) - (B - C) 14. Cho A, B, C là các t$p h p. Ch ng minh r ng: (B - A) ∪ (C - A)= (B ∪ A) - A 15. Ch ng minh r ng n u A, B là các t$p h p thì: (A ∩ B) ∪ (A ∩ % ) = A (ký hi u % ch# ph n bù c a B t c là {x/ x ∉ B} 16. Cho A, B, C là các t$p h p. Ch ng minh r ng %%%%%%%%%%%%% a. (2 3 4) = 2 3 4 b. (A – C) ∩ (C – B) = ∅ c. (A - B) – C ⊆ A - C 17. Cho t$p h p B = {a1, a2, a3, a4}. G i P(B) là t$p h p t t c các t$p h p con c a t$p h pA a. Hãy li t kê t t c các ph n t c a P(B). b. P(B) có bao nhiêu ph n t ? 18. B ng ph ơng pháp quy n p, hãy ch ng minh r ng n u t$p h p A có n ph n t thì nó có c th y 2n t$p con. 19. B ng ph ơng pháp quy n p ch ng minh r ng 111...111 (3n ch! s 1) chia h t cho 3n v"i m i s t nhiên n. 20. B ng ph ơng pháp quy n p ch ng minh công th c sau úng v"i m i s t nhiên n. a. 12 + 12 + ....+ (2n-1)2 = 22. 8 n(2n-1)(2n+1) ;< 9: Trong m t l"p h c ngo i ng!, t$p h p A các h c viên n! có 4 ph n t , t$p h p B các h c viên t 20 tu(i tr lên có 5 ph n t . Có 3 h c viên n! t 20 tu(i tr lên. Tìm s ph n t c a t$p h p A ∪ B. b. 21. 67 89: 5 Trên m t bãi xe, có 42 xe g0m taxi và xe buýt. Có 14 xe màu vàng và 37 xe buýt ho c xe không có màu vàng. H.i trên bãi xe có bao nhiêu xe buýt vàng? 23. M t l"p h c có 40 h c sinh, trong ó có 15 em h c khá môn Toán, 16 em h c khá môn V,n và 17 em h c khá môn Ti ng Anh. Có 5 em h c khá c hai môn V,n và Toán, 8 em h c khá c hai môn Toán và Anh, 6 em h c khá c hai môn V,n và Anh, và 2 em h c khá c ba môn. H.i có bao nhiêu h c sinh a. Ch# h c khá môn Toán b. Ch# h c khá môn V,n? c. Ch# h c khá môn Anh? d. Không h c khá môn nào? 24. Trên m t ph ng k- n ng th ng sao cho không có ba ng nà 0ng qui và không có hai ng nào song song. H.i m t ph ng c chia làm m y ph n ? 25. Hãy ngh ra thu$t toán quy tìm s h ng th n c a dãy a0=1, a1 = 2 và an = an-1 + an-2 v"i n = 2, 3, 4, ... c xác nh nh sau: BÀI T/P CHƯ NG 2 Trang 43 GIÁO TRÌNH TOÁN NG D NG TIN H C Biên so n : Gv. Ph m Phúc Th nh 1. M t t$p th g0m 14 ng i g0m 6 nam và 8 n! trong ó có An và Bình , ng i ta mu n ch n 1 t( công tác g0m 6 ng i. Tìm s cách ch n t( sao ccho có 1 t( tr ng , 5 t( viên trong ó An vàà Bình B không 0ng th i có m t. 2. Cho A là m t t$p h p t$ t$p có ph n t a. Có bao nhiêu t$p $p h p con c a A b. Có bao nhiêu t$p $p h p con khác r2ng c a A mà có s ph n t là s ch9n 3. M t nhóm g0m 10 h c sinh, trong ó 7 nam và 3 n!. H.i có bao ao nhiêu cách s)p x p 10 h c sinh trên thành 1 hàng d c sao cho 7 h c sinh nam ph i ng li n nhau. 4. Cho t$p E={0,1,2,3,4,5, ,5,6,7,8,9}, có bao nhiêu s t nhiên g0m 0m 5 ch! s khác nhau t E mà chia h t cho 5? 5. Có bao nhiêu chu2i bit it ccó 6. Xem o n ch ơng trình nh PASCAL d "i ây, trong ó i, j, k là các ác bi n nguyên. dài nh. hơn ho c b ng 6 For i := 1 to 12 do For j := 5 to 10 do For k := 15 downto to 8 do Writeln ( (i-j)*k ); L nh Writeln 7. c thh c hi n bao nhiêu l n? Gi s n là m t h ng s cho tr "c. Xác nh giá tr c a bi n ngu guyên counter sau khi th c hi n o n ch ơ ơngg trình t PASCAL d "i ây. (' ây i, j và k là l các bi n nguyên) Counter := 0; For i := 1 to N do For j := i to N do For k := 1 to N do Counter := Counte ter + 1 8. T các ch! s 1, 2, 3,, 44, 5, 6 l$p các s t nhiên g0m các s cóó 6 ch! s khác nhau. H.i nhiêu s ? a. Có t t c bao nh b. Có bao nhiêu s ch9n, bao nhiêu s l- ? c. Có bao nhiêu s bé hơn 432000? 9. N,m h c sinh nam và 3 h c sinh n! c s)p x p vào 8 ch2 ng0i 0i. Có bao nhiêu cách s)p x p ch2 ng0i sao ch cho không có hai h c sinh n! ng0i vào c nh nhau ? 10. Hãy tính s các t khác ác nhau (có th vô ngh a) thu cái c a t TOANHOCT TUOITRE. c b ng cách c hoán v các ch! 11. Hãy tính s các t khác ác nhau (có th vô ngh a) thu c b ng cách c hoán v các ch! cái c a t TOANHOCT TUOITRE mà trong ó không có ba ch! ! T ng c nh nhau. 12. Ch ng minh các ng th c sau: a. C n0 + C n1 + ... + C nn−1 + C nn = 2 n b. C n0 − C n1 + ... + ( −1) n−1 C nn−1 + ( −1) n C nn = 0 13. Ch ng minh r ng C nm C mk = C nk C nm−−kk = C nm − k C nk− m + k 14. Có bao nhiêu cách x p k bit 0 và m bit 1 (k ≤ m)trên vòng tròn c ánh s t 1 n Trang 44 GIÁO TRÌNH TOÁN NG D NG TIN H C Biên so n : Gv. Ph m Phúc Th nh m+k (v trí m+k k v"i v trí 1) sao cho không có 2 bit 0 k nhau. 15. Trong 45 h c sinh làm bài ki m tra không có ai b i m d "i 2, ch# có 2 h c sinh c i m 10. Ch ng minh r ng ít nh t c ng tìm c 6 h c sinh có i m ki m tra b ng nhau ( i m ki m tra là m t s t nhiên t 0 n 10). 16. 8 i tham gia gi i vô d ch bóng á trong ó hai i b t kì ph i g p nhau úng 1 l n bi t n cu i gi i khôngcó tr$n nào hòa . Ch ng minh trong 8 i trên luôn tìm c 4 i ABCD th.a mãn A th)ng B,C,D ; B th)ng C,D ; C th)ng D. 17. Có 6 i bóng thi u v"i nhau (m2i i ph i u 1 tr$n v"i 5 i khác). CMR vào b t c lúc nào c ng có 3 i trong ó t ng c p ã u v"i nhau ho c ch a u v"i nhau tr$n nào. 18. Cho 5 s nguyên phân bi t a1, a2, a3, a4, a5. Xét tích : P=(a1-a2)(a1-a3)(a1-a4)(a1-a5)(a2-a3)(a2-a4)(a2-a5)(a3-a4)(a3-a5)(a4-a5). Ch ng minh r ng P chia h t cho 288. 19. Bên trong tam giác u ABC c nh 1 kho ng cách nh. hơn 0,5 20. Ng i a th tên là Phong c phân công a th m t làng nh. mang tên M i nhà. Làng này, ch# có 1 ng ph và có 10 nhà, ánh s t 1 n 10. Trong m t tu n n , Phong không a th t i hai ngôi nhà c a làng; t i các nhà khác anh y a th úng ba l n. M2i m t ngày làm vi c anh y a th t i úng 4 nhà. T(ng c a s các ngôi nhà mà Phong a th là: • Th hai : 18 • Th ba : 12 • Th t : 23 • Th n,m : 19 • Th sáu : 32 • Th b y : 25 Ch nh$t: Phong không làm vi c. H.i Hai nhà nào không nh$n c th trong tu n này? 21. cho X ={0,1,...,10} .Ch ng t. r ng n u S là 1 t$p con g0m 7 ph n t c a X thì có 2 ph n t c a S có t(ng b ng 10 . t 5 i m. Ch ng minh r ng t0n t i 2 i m có BÀI T/P CHƯ NG 3 1. Trong các quan x ng, b)c c u: a. Quan h b. Quan h c. Quan h h sau, hãy cho bi t quan h nào có tính ph n x , R trên Z : xRy R trên Z : xRy R trên Z : xRy i x ng, ph n x + y ch9n. x - y l-. x2 + y2 ch9n. 2. Các quan h nào d "i ây trên t$p m i ng a. {(a, b)|a, b cùng tu(i} b. {(a, b)|a, b có cùng b m } c. {(a, b)|a, b nói cùng 1 th ti ng} i là t ơng ơng ? 3. A = {1, 2, 3, 4, 5, 6} và R = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 3), (4, 4), (4, 5), (5, 4), (5, 5), (6, 6)} a. Ki m tra R là m t quan h t ơng ơng. b. Tìm các l"p t ơng ơng % , % , % . Trang 45 GIÁO TRÌNH TOÁN NG D NG TIN H C Biên so n : Gv. Ph m Phúc Th nh 4. Xét m t t$p h p A = {1, 2, 3, 4, 6, 9}, nh ngh a m t quan h R trên A nh sau R = {(x, y)|x − y là b i s c a 3} a. Li t kê các ph n t c a R b. Ch ng minh R là quan h t ơng ơng trên A c. Các l"p t ơng ơng c a R là gì ? 5. G i R là quan h hai ngôi “có cùng s d v"i... trong phép chia cho 4” trên t$p h p N. a. Ch ng minh r ng R là m t quan h t ơng ơng trên t$p h p N. b. Quan h t ơng ơng R trên N chia t$p h p N thành m y l"p t ơng ơng? Hãy v& sơ 0 Ven bi u di n các l"p t ơng ơng c a quan h R. 6. Cho t$p h p X = {1, 2, 3, 4, 5} và P = P(X) là t$p h p các t$p con c a X. G i R là quan h hai ngôi trên P xác nh b i: A R B khi và ch# khi N (A) = N (B) trong ó N X. (C) là s ph n t c a t p h p C a. Ch ng minh r ng R là m t quan h t ơng ơng trên P. b. Tìm l"p t ơng ơng c a quan h ~ trên P, có i di n là ph n t {1, 3} c a P. 7. Ký hi u C* ch# t$p h p các s ph c có ph n th c khác 0. G i R là quan h hai ngôi trên C* xác nh b i (a + bi) R (c + di) khi và ch# khi ac > 0. Ch ng minh r ng R là m t quan h t ơng ơng trên C*. 8. Cho t$p X = {0, 1, 2, 3, 4, 5, 6, 7} và quan h hai ngôi R xác nh trên X nh sau: x,y∈X, xRy (x+y)÷2 (ký hi u ÷ di n t ý “chia h t cho”). a. T$p R có nh!ng ph n t nào? b. Quan h hai ngôi R có nh!ng tính ch t gì? c. R có ph i là quan h t ơng ơng trên X? N u ph i thì hãy tìm l"p t ơng ơng c a các ph n t 1, 2. T$p th ơng X/R có nh!ng ph n t nào? 9. X = { 1,2,3,4,5} x { 1,2,3,4,5} . Xét quan h 2 ngôi R trên X sau: (a,b) R (c,d) a+b = c+d a. Ch ng minh r ng R là m t quan h t ơng ơng trên X. b. Tìm các l"p t ơng ơng. c nh ngh a nh 10. Cho t$p h p X = {1, 3, 9, 18, 36}. G i ≤ là quan h “chia h t” trên X. a. Ch ng minh ≤ là m t quan h th t trên X. b. Quan h• th t ≤ trên X có ph•i là quan h th t toàn ph•n không? 11. Cho R là quan h hai ngôi trên t$p h p C các s ph c xác nh nh sau: V"i m i a + bi, c + di ∈ C, (a + bi) R (c + di) khi và ch# khi a ≤ c và b ≤ d. a. Ch ng minh r ng R là m t quan h th t trên C. b. R có ph i là quan h th t toàn ph n không? 12. Tìm các ph n t t i i, t i ti u, l"n nh t, nh. nh t c a t$p A= {2,3,4,5,6,12,30,60} i v"i quan h chia h t trên N* 13. Cho t$p h p s)p th t (X, ≤) v"i X = {35, 36, 37, 38, 39} và ≤ là quan h “chia h t cho” trên X (a ≤ b a chia h t cho b). Tìm giá tr l"n nh t và giá tr nh. nh t c a X. 14. Gi s A = P(E) v"i E = {1, 2, 3}. Trong t$p h p A v"i th t bao hàm, hãy tìm sup và inf c a t$p h p con B A d "i ây: a. B = {{1}, {2}} b. B = {{1}, {2}, {3}, {1, 2}} c. B = { ∅, {1}, {2}, {1, 2}} Trang 46 GIÁO TRÌNH TOÁN NG D NG TIN H C Biên so n : Gv. Ph m Phúc Th nh 15. Cho t$p h p X = {2, 5, 8, 10, 20, 40} và R là quan h “chia h t” trên X nh sau : a R b a chia h t b. a. Ch ng t. R là quan h th t . b. Tìm các ph n t t i i và t i ti u c a X. c. Tìm ph n t l"n nh t và nh. nh t (n u có) c a X. nh ngh a 16. Tìm các ph n t ch n trên và ch n d "i (n u có) c a m2i t$p con A = {7, 11} và B = {2, 4, 6, ..., 2n, ...} trong t$p h p s)p th t {N*, ≤}, trong ó ≤ là quan h “chia h t” trên t$p h p N* 17. Gi s {R, ≤} là t$p h p s)p th t , trong ó ≤ là quan h “nh. hơn ho c b ng” (thông th ng) trên t$p h p các s th c R. Tìm các ph n t ch n trên và các ph n t ch n d "i c a t$p h p A = [−7, 3) = {x ∈ R : −7 ≤ x < 3} trong R. 18. Cho t$p X={a,b,c,d}. a. Hãy li t kê các ph n t c a t$p t t c các t$p h p con c a X ( kí hi u là P(X)) b. Ch ng minh quan h bao hàm là quan h th t trên P(X). c. Tìm các ph n t l"n nh t, nh. nh t, t i i, t i ti u c a t$p Y={{a}; {a,b}; {a,b,c}; {a,b,d}} d. T ơng t câu h.i c) i v"i t$p P(X); P(X)\X 19. Cho A = {1,2,3,4,5} . Cho R và S là hai quan h (2 ngôi) trên A có ma tr$n bi u di n l n l t là 1 0 0 0 0 1 0 1 1 0 1 1 0 1 0 0 1 1 1 0 MR = 1 1 1 1 1 0 0 0 1 0 MS = 0 0 1 1 0 0 0 0 1 0 0 0 0 0 1 1 1 1 1 1 a. Ch ng minh r ng R và S là nh!ng quan h th t trên A. b. V& các bi u 0 Hasse cho (A,R) và (A,S). 20. Cho (A, ≤) là t$p h p s)p th t , trong ó A= {2, 4, 5, 10, 12, 20, 25} là quan h “chia h t” a. V& bi u 0 Hasse cho (A, ≤) b. D a vào bi u 0 Hasse tìm ph n t c c i, c c ti u c a (A, ≤) 21. Cho (A, ≤) là t$p h p s)p th t , trong ó A là t$p các chu2i nh phân có 3, ≤ là quan h “nh. hơn ho c b ng” thông th ng a. V& bi u 0 Hasse cho (A, ≤) b. D a vào bi u 0 Hasse tìm ph n t c c i, c c ti u c a (A, ≤) c. D a vào bi u 0 Hasse tìm ph n t t i i, t i ti u c a (A, ≤) dài b ng BÀI T/P CHƯ NG 4 1. Ki m tra tính giao hoán và tính k t h p c a các phép toán sau ây : a. Phép toán * trên N cho b i : a * b = a+b+2, ∀ a,b ∈ N. b. Phép toán * trên X = { x ∈ R | x > 0} nh b i : a* b = ab/(a+b). c. Phép toán * trên R nh b i : a* b = a+b+ab. 2. Ch ng minh r ng a. (a+b).(a+b’)=a Trang 47 GIÁO TRÌNH TOÁN NG D NG TIN H C Biên so n : Gv. Ph m Phúc Th nh b. (a.b)+(a’.c)=(a+c).(a’+b) 3. Cho S là t$p h p các "c nguyên d ơng c a 70, v"i các phép toán •, + và ’ c ngh a trên S nh sau: a • b = UCLN(a, b), a + b = BCNN(a, b), a’ = 70/a. Ch ng t. r ng S cùng v"i các phép toán •, + và ’ l$p thành m t i s Boole. 4. Cho các hàm Boole F1, F2, F3 xác nh b i b ng sau: F2 X y z F1 0 0 0 1 1 0 0 1 1 0 0 1 0 0 1 0 1 1 1 1 1 0 0 1 0 1 0 1 0 0 1 1 0 0 1 1 1 1 1 1 V& m ch các c(ng logic th c hi n các hàm Boole này. 5. nh F3 0 1 1 0 1 1 1 1 Dùng các b n 0 Karnaugh, tìm d ng a th c t i ti u c a các hàm Boole ba bi n sau: a. F = x yz + x y z . b. F = xyz + xy z + + x yz + x y z . c. F = xy z + + x y z + x y z + x yz + x y z . d. F = xyz + x y z + x y z + x yz + x y z + x y z . 6. Dùng các b n 0 Karnaugh, tìm d ng a th c t i ti u c a các hàm Boole ba bi n sau: a. F = wxyz + wx yz + wx y z + w x y z + w x y z . b. F = wxy z + wx y z + w x yz + wx y z + w x y z + w x y z . c. F = wxyz + wxy z + wx y z + w x y z + w x y z + wx y z + w x y z + w x yz . d. F = wxyz + wxy z + wx y z + w x yz + w x y z + wxyz + w x yz + w x y z + w x y z . 7. Cho hàm Boole f(x,y)= x. y + x. y + x. y a. Tìm a th c t i ti u c a f(x,y). b. V& m ch logic bi u di n hàm f(x,y) và a th c t i ti u c a f(x,y) Trang 48 GIÁO TRÌNH TOÁN NG D NG TIN H C Biên so n : Gv. Ph m Phúc Th nh M1C L1C CHƯ NG 1 : I. C S LOGIC ....................................................................................................... 1 Khái ni m m nh và chân tr ................................................................................................. 1 1. Các khái ni m........................................................................................................................... 1 2. M nh sơ c p – m nh ph c h p....................................................................................... 1 II. Các phép toán m nh ............................................................................................................. 1 1. B ng chân tr ............................................................................................................................ 1 2. Phép ph nh........................................................................................................................... 1 3. Phép h i.................................................................................................................................... 1 4. Phép tuy n ................................................................................................................................ 2 5. Phép kéo theo ........................................................................................................................... 2 6. Phép kéo theo 2 chi u .............................................................................................................. 3 7. Ð u tiên c a các toán t logic............................................................................................... 3 III. D ng m nh và các lu t logic ................................................................................................. 3 1. B ng chân tr c a m t bi u th c logic ..................................................................................... 3 2. S t ơng ơng logic............................................................................................................... 4 4. Các lu$t logic ........................................................................................................................... 4 5. Các qui t)c thay th .................................................................................................................. 5 IV. Quy t c suy di n ......................................................................................................................... 5 1. / nh ngh a ................................................................................................................................ 5 2. Ki m tra m t qui t)c suy di n .................................................................................................. 6 3. Các qui t)c suy di n cơ b n...................................................................................................... 7 V. Ð nh ngh a v t và l ng t ..................................................................................................... 7 1. Ð nh ngh a v t : ...................................................................................................................... 7 2. Các phép toán trên các v t ..................................................................................................... 8 VI. Các l ng t và các m nh có l ng t ................................................................................ 8 1. Khái ni m ................................................................................................................................. 8 2. Qui t)c ph nh m nh có l ng t ..................................................................................... 9 3. M t s qui t)c dùng trong suy lu$n .......................................................................................... 9 4. D ch nh!ng câu thông th ng thành bi u th c logic: ............................................................ 10 VII. 1. 2. 3. 4. T p h p - Các phép toán t p h p ....................................................................................... 10 Khái ni m t$p h p .................................................................................................................. 10 Bi u di n m t t$p h p ............................................................................................................ 11 T$p h p con, các t$p h p b ng nhau ...................................................................................... 11 Các phép toán trên t$p h p..................................................................................................... 11 VIII. 1. 2. 3. 4. 5. Khái ni m Ánh x ................................................................................................................ 12 / nh ngh a .............................................................................................................................. 12 Ánh x b ng nhau .................................................................................................................. 12 Ánh x h p ............................................................................................................................. 12 7nh và nh ng c .................................................................................................................. 12 Phân lo i ánh x ..................................................................................................................... 13 IX. L c l ng c a t p h p............................................................................................................. 13 1. / nh ngh a l c l ng c a t$p h p .......................................................................................... 13 2. / nh ngh a t$p h p h!u h n-vô h n ....................................................................................... 13 Trang 49 GIÁO TRÌNH TOÁN 3. X. 1. 2. 3. T$p h p 1. 2. Biên so n : Gv. Ph m Phúc Th nh c ................................................................................................................. 13 Quy n p toán h c – nh ngh a quy .................................................................................. 14 Quy n p toán h c ................................................................................................................... 14 Các nh lý v quy n p ........................................................................................................... 14 Thu$t toán quy................................................................................................................... 14 CHƯ NG 2 : I. NG D NG TIN H C m PHÉP M........................................................................................................... 16 Phép m .................................................................................................................................. 16 / nh ngh a: ............................................................................................................................. 16 Tính ch t: ............................................................................................................................... 16 II. Nguyên lý c ng ......................................................................................................................... 16 1. M nh : ................................................................................................................................ 16 2. Nguyên lý c ng : .................................................................................................................... 16 3. Nguyên lý nhân : .................................................................................................................... 17 III. Nguyên lý Dirichlet t ng quát:................................................................................................ 17 1. M nh : ................................................................................................................................ 17 2. Các ví d : .............................................................................................................................. 17 3. M t s ng d ng c a nguyên lý Dirichlet.............................................................................. 17 IV. CH NH H P ............................................................................................................................ 18 1. Ð nh ngh a .............................................................................................................................. 18 2. Công th c ch#nh h p .............................................................................................................. 18 V. T 1. 2. H P .................................................................................................................................... 19 Ð nh ngh a .............................................................................................................................. 19 Công th c t( h p .................................................................................................................... 19 VI. CÔNG TH!C NH" TH!C NEWTON: ................................................................................. 19 1. Ð nh lý.................................................................................................................................... 19 2. H qu 1. ................................................................................................................................ 19 3. H qu 2. ................................................................................................................................ 19 VII. M#T S$ TÍNH CH%T KHÁC C&A T H P ................................................................. 19 VIII. HOÁN V" L'P VÀ T H P L'P ..................................................................................... 20 1. Hoán v l p ............................................................................................................................. 20 IX. T 1. 2. 3. h p l(p ................................................................................................................................. 20 Ð nh ngh a: ............................................................................................................................. 20 Công th c tính t( h p l p: ..................................................................................................... 20 Các h qu : ............................................................................................................................. 20 CHƯ NG 3 : I. QUAN H) ............................................................................................................. 22 Quan h hai ngôi ...................................................................................................................... 22 1. / nh ngh a .............................................................................................................................. 22 2. Cách xác nh m t quan h : ................................................................................................... 22 3. Bi u di n quan h 2 ngôi d "i d ng ma tr$n ......................................................................... 22 II. Quan h t ng ng .............................................................................................................. 23 1. Khái ni m ............................................................................................................................... 23 Trang 50 GIÁO TRÌNH TOÁN 2. 3. NG D NG TIN H C Biên so n : Gv. Ph m Phúc Th nh L"p t ơng ơng và t$p h p th ơng ..................................................................................... 23 /0ng d .................................................................................................................................. 23 III. Phép toán s+ h c trên Zn ......................................................................................................... 24 1. T$p h p s t nhiên, t$p h p s nguyên ................................................................................ 24 2. Phép chia s nguyên ............................................................................................................... 24 3. Ư"c S Chung L"n Nh t và B i S Chung Nh. Nh t .......................................................... 25 4. S nguyên t và nh lý c,n b n c a s h c .......................................................................... 26 IV. Quan h th, t ......................................................................................................................... 26 1. / nh ngh a quan h th t ...................................................................................................... 26 2. / nh ngh a ph n t nh. nh t, l"n nh t, t i ti u, t i i. ........................................................ 27 3. / nh ngh a ch$n trên, ch$n d "i c a m t t$p h p: ................................................................ 27 4. / nh ngh a t$p có th t t t: .................................................................................................. 27 V. 1. 2. Bi-u Hasse............................................................................................................................ 27 /0 th nh h "ng (directed graph). ...................................................................................... 27 /0 th nh h "ng (directed graph). ...................................................................................... 28 CHƯ NG 4 : I. .I S$ BOOLE ................................................................................................... 30 Phép toán .................................................................................................................................. 30 1. / nh ngh a phép toán2 ngôi ................................................................................................... 30 2. / nh ngh a phép toán 1 ngôi .................................................................................................. 30 3. Các chú ý................................................................................................................................ 30 4. Các tính ch t i s c a phép toán 2 ngôi .............................................................................. 30 5. / nh ngh a phân b bên trái, ph i c a phép toán 2 ngôi. ....................................................... 31 6. / nh ngh a C u trúc i s . .................................................................................................... 32 II. 1. i s+ boole ............................................................................................................................... 32 / nh ngh a i s Boole ......................................................................................................... 32 III. Hàm boole ................................................................................................................................. 33 1. / nh ngh a hàm Boole ........................................................................................................... 33 2. Các phép toán hàm Boole: ..................................................................................................... 33 IV. Bi-u di n hàm Boole: ............................................................................................................... 34 1. / nh ngh a: ............................................................................................................................. 34 2. M nh : ................................................................................................................................ 34 V. 1. 2. 3. M ng các c ng .......................................................................................................................... 34 C(ng Logic ............................................................................................................................. 34 M t s c(ng logic th ng g p ............................................................................................... 35 M ch logic.............................................................................................................................. 35 VI. Công th,c a th,c t+i ti-u ....................................................................................................... 36 VII. 1. 2. 3. 4. 5. Bi-u Karnaugh ................................................................................................................ 37 Khái ni m ............................................................................................................................... 37 Chú ý: ..................................................................................................................................... 37 / nh ngh a. ............................................................................................................................. 37 Ph ơng pháp Karnaugh tìm công th c a th c t i ti u c a hàm Boole. ............................... 37 Các ví d . ............................................................................................................................... 38 Trang 51