Bài giảng Toán ứng dụng tin học: Chương 1

Chia sẻ: Minh Minh | Ngày: | Loại File: PDF | Số trang:9

Thêm vào BST

Báo xấu

144
lượt xem 9
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng Toán ứng dụng tin học nhằm trang bị cho sinh viên những kiến thức cơ bản về Logic, lý thuyết tập hợp, các nguyên lý đếm, quan hệ và hàm Bool. Chương 1 của bài giảng trình bày về cơ sỏ logic, mời bạn đọc cùng tham khảo.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Toán ứng dụng tin học: Chương 1

3/5/2009 PH N M U Ph m Phúc Th nh Các ki n th c s h c Các ki n th c s h c 1. Cơ S Logic 2. Phép m a) M nh & chân tr a) nh nghĩa – tính ch t cơ b n. b) Các phép toán m nh b) Nguy n lý c ng - nguyên lý nhân c) D ng m nh & Lu t logic c) Nguyên lý Chu ng b câu d) Quy t c suy di n d) Ch nh h p – T h p. Công th c nh th c e) V t & lư ng t e) T h p có l p f) T p h p – Các phép toán t p h p 3. Quan h g) Quy n p toán h c – nh nghĩa quy a) Quan h & Các tính ch t b) Bi u di n quan h c) Quan h tương ương – ng dư. d) Quan h th t Các ki n th c s h c Th i gian h c t p 4. i s Bool T ng s ti t : 45 (Bao g m lý thuy t + bài t p a) Hàm Bool. D ng n i r i chính t c a) Lý thuy t : 30 ti t b) Bài t p : 14 ti t b) Công th c a th c t i ti u c) Ki m tra : 1 ti t c) Phương pháp bi u Karnaugh M c tiêu c a h c ph n: d) M ng các c ng Nh m trang b cho sinh viên nh ng ki n th c cơ b n v Logic, Lý thuy t t p h p, Các nguyên lý m, Quan h , và Hàm Bool. Tài li u tham kh o: -Các giáo trình toán r i r c c a b c h c Cao ng (Có th tìm th y trong thư vi n ho c trên m ng Internet) -- Bài gi ng c a giáo viên quan trang blog : Chuottau.blogtiengviet.net 1
3/5/2009 CHƯƠNG 1 PH N 1 Khái ni m m nh và chân tr Khái ni m m nh và chân tr Các i tư ng cơ b n mà chúng ta kh o sát Tính ch t cơ b n c a m t m nh là nó úng ây là các phát bi u hay các m nh .Tuy ho c sai, và không th v a úng v a sai. Giá tr nhiên, ta ch xét n các m nh toán h c, và úng ho c sai c a m t m nh ư c g i là chúng ta nói v n t t các m nh toán h c là chân tr c a m nh . các m nh . V m t ký hi u, ta dùng các m u t (như p, q, r, ...) ký hi u cho các m nh , và chúng cũng M nh toán h c là nh ng phát bi u di n ư c dùng ký hi u cho các bi n logic, t c là t m t ý tư ng tr n v n và ta có th kh ng các bi n l y giá tr úng ho c sai. nh m t cách khách quan là nó ú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. Các ví d v m nh Các ví d v m nh 1. 6 là m t s nguyên t . Các phát bi u sau ây không ph i là các m nh (toán h c) vì tính úng sai c a chúng không 2. 5 là m t s nguyên t . xác nh. 3. -3 < 2 1. Ai ang c sách? (m t câu h i) 4. Tam giác cân có hai góc b ng nhau. 2. Hãy óng c a l i i! 5. H2O là m t axít. 3. Anh ta r t thông minh. Các m nh 2, 3, và 4 trong ví d trên là nh ng 4. Cho x là m t s nguyên dương. m nh úng. 5. a là m t s chính phương. Các m nh 1, 5 là nh ng m nh sai. 6. x + y = z. 2
3/5/2009 M nh sơ c p – M nh ph c h p Ví d v phân lo i m nh Phân lo i m nh : m nh sơ c p 1. p = “15 chia h t cho 3”. (elementary), m nh ph c h p (compound). 2. q = “2 là m t s nguyên t và là m t s l ”. M nh sơ c p là các m nh không th phân tích ư c thành m t hay nhi u (t hai tr lên) Ta có p là m t m nh sơ c p. Nhưng q là m t m nh thành ph n ơn gi n hơn. m nh ph c h p, vì m nh q ư c t o thành t hai m nh “2 là m t s nguyên t ” và M nh ph c h p là m nh ư c t o thành “2 là m t s l ” nh vào liên k t logic “và”. 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.... B ng chân tr c a m t m nh V n : làm th nào tính toán chân tr c a PH N 2 các m nh ph c h p theo các m nh sơ c p c u thành m nh ph c h p ó nh vào các phép toán logic. Các phép toán logic là các ký hi u ư c dùng thay cho các t liên k t logic như “không”, “và”, “hay”, “ho c”, “suy ra” hay “n u ... thì ...”, “n u và ch n u”. B ng chân tr c a m t m nh Phép Ph nh Các phép toán logic ư c nh nghĩa b ng b ng Cho p là m t m nh , ký hi u “¬p” ch m nh chân tr (truth table). B ng chân tr cho ta chân ph nh c a m nh p. “S ph nh” ư c tr c a m nh ph c h p theo t ng trư ng h p nh nghĩa b i b ng chân tr sau ây: c a các chân tr c a các m nh sơ c p t o p ¬p M nh ph nh ¬p có thành m nh ph c h p. chân tr là úng (1) khi B ng chân tr ư c dùng v i m c ích : li t kê 1 0 m nh p có chân tr sai s liên h chân tr gi a các m nh v i các m nh (0), ngư c l i ¬p có chân tr ơn gi n hơn c u thành chúng. sai (0) khi p có chân tr 0 1 úng (1). 3
3/5/2009 Phép Ph nh Phép Ph nh Ví d 1 : Ví d 2 : Ch ra r ng ¬(¬p) và p luôn có cùng chân tr . N u ta ký hi u p là m nh “5 < 3” thì ¬p là ký Gi i. L p b ng chân tr c a m nh hi u cho m nh “5 ≥ 3”. Trong trư ng h p n y p p ¬ p ¬ (¬ p) ¬(¬ p): sai, ¬ p úng. Ta có th vi t p = 0, ¬ p = 1. Trên m i dòng giá tr trong b ng chân tr 0 1 0 ta có chân tr c a p và ¬(¬p) u b ng nhau (so sánh c t 1 và c t 3 trong 1 0 1 b ng). V y ¬(¬p) và p có cùng chân tr . Ta cũng nói r ng ¬(¬p) tương ương logic v i p. M nh ¬(¬p) thư ng ư c vi t là ¬¬p. Phép H i Phép H i Cho p và q là hai m nh . Ta ký hi u m nh “p Qua nh nghĩa trên ta nh n th y r ng các m nh pΛq hay q” là p Λ q. Phép “và”, ký hi u là Λ ư c nh và q Λ p luôn luôn có cùng chân tr , hay tương ương logic. nghĩa b i b ng chân tr sau ây: Tuy nhiên, trong ngôn ng thông thư ng các m nh “p và q” và “q và p” ôi khi có ý nghĩa khác nhau theo ng c nh. p q pΛq Ví d : Cho các m nh 0 0 0 p = “5 > -7”, 0 1 0 q = “2721 là m t s nguyên t ”, r = “m t tam giác u cũng là m t tam giác cân”. 1 0 0 Khi ó ta có : p Λ q = 0 (p Λ q sai, t c là có chân tr b ng 0, vì p = 1 và q = 0), 1 1 1 p Λ r = 1 (p Λ r úng, t c là có chân tr b ng 1, vì p = 1 và r = 1). Phép H i Phép Tuy n Nh n xét: B ng cách l p b ng chân tr , ta có: 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 1. Các m nh p và p Λ p luôn có cùng chân tr . nghĩa b i b ng chân tr sau ây: 2. M nh p Λ¬ p luôn có chân tr b ng 0 (t c là m t m nh luôn sai). p q p∨q 3. M t m nh ph c h p luôn luôn có chân tr là sai 0 0 0 trong m i trư ng h p chân tr c a các m nh sơ 0 1 1 c p t o thành nó s ư c g i là m t s mâu thu n. 1 0 1 1 1 1 4
3/5/2009 Phép Tuy n Phép Tuy n Chân tr c a m nh p ∨ q ph thu c vào các chân Ví d : Cho các m nh tr c a 2 m nh p, q. Trong 4 trư ng h p ch có • p = “5 > 7”, m t trư ng h p m nh p ∨ q sai, ó là trư ng • q = “2721 là m t s nguyên t ”, h p p sai và q sai. • r = “m t tam giác u cũng là m t tam giác cân”. Qua nh nghĩa trên ta nh n th y r ng các m nh p ∨ q và q ∨ p luôn luôn có cùng chân tr , hay tương Khi ó ta có : ương logic. p V q = 0, p V r = 1. Phép Tuy n Phép Kéo theo Nh n xét : Phép kéo theo, ký hi u b i → , ư c ưa ra mô 1. Cho p là m t hình cho lo i phát bi u i u ki n có d ng : “n u . . . p ¬p p∨¬ p m nh . L p thì . . .”. Cho p và q là 2 m nh , ta s vi t p→ q b ng chân tr di n t phát bi u “n u p thì q”. Phép toán kéo theo c a m nh p 0 1 1 → ư c nh nghĩa b i b ng chân tr sau ây: ∨¬ p ta có m nh 1 0 1 p q p q p q p q p ∨¬ p luôn luôn úng. 0 0 1 1 0 0 0 1 1 1 1 1 Phép Kéo theo Phép Kéo theo 2 chi u M nh p → q, ư c c là “n u p thì q”, còn ư c Phép kéo theo 2 chi u hay phép tương ương, ký hi u phát bi u dư i các d ng khác sau ây: b i ↔, ư c ưa ra mô hình cho lo i phát bi u i u ”q n u p”. ki n hai chi u có d ng : “. . . n u và ch n u . . .”. Cho p và q là 2 m nh , ta vi t p↔q di n t phát bi u “p ”p ch n u q”. n u và ch n u q”. Phép toán tương ương ư c nh ”p là i u ki n cho q”. nghĩa b i b ng chân tr sau ây ”q là i u ki n c n cho p”. p q p ↔q p q p ↔q 0 0 1 1 0 0 0 1 0 1 1 1 5
3/5/2009 Phép Kéo theo 2 chi u ưu tiên c a các toán t Logic M nh p↔ q, ư c c là “p n u và ch n u q”, Tương t như i v i các phép toán s h c, tránh còn ư c phát bi u dư i các d ng khác sau ây: ph i dùng nhi u d u ngo c trong các bi u th c logic, ta ”p khi và ch khi q”. ưa ra m t th t ưu tiên trong vi c tính toán. ”p là i u ki n c n và cho q”. trên ta có 5 toán t logic:¬ (không) , ∧ (và), ∨ (hay), → ¬ M nh p↔q có chân tr úng (=1) trong các trư ng (kéo theo), ↔ ( tương ương) Th t ưu tiên : h p p và q có cùng chân tr . ¬ ∧,∨ →↔ trong ó, các toán t li t kê trên cùng dòng có cùng ưu tiên. ưu tiên c a các toán t Logic Ví d : 1. ¬ p∨q có nghĩa là ((¬ p) ∨ q). PH N 2 2. ¬ p∨ q→ r ∧ s có nghĩa là (((¬ p) ∨ q)→ (r ∧ s)). 3. ¬ p∨ q∧ r là không rõ ràng, trong trư ng h p này c n ph i dùng các d u ngo c ch rõ nghĩa. nh nghĩa bi u th c Logic B ng chân tr c a bi u th c Logic Bi u th c logic là bi u th c ư c xây d ng t : B ng chân tr c a m t bi u th c logic là b ng li t kê 1. Các m nh hay các giá tr h ng. chân tr c a bi u th c logic theo các trư ng h p v 2. Các bi n m nh . chân tr c a t t c các bi n m nh trong bi u th c 3. Các phép toán logic, và c các d u ngo c “( )” logic hay theo các b giá tr c a b bi n m nh . ch rõ th t th c hi n c a các phép toán. V i m t bi n m nh , ta có 2 trư ng h p là 0 (sai) ho c 1 ( úng). V i 2 bi n m nh p, q ta 4 trư ng Gi s E, F là 2 bi u th c logic, khi y ¬ E, E ∧ F, E → F, h p chân tr c a b bi n (p,q) là các b giá tr (0,0), E ↔ F cũng là các bi u th c logic. (0,1), (1,0), và (1,1). Ví d : Bi u th c Trong trư ng h p t ng quát, v i n bi n m nh thì ta E(p,q,r) = (((¬ p) ∨ q)→ (r ∧ s)) là m t bi u th c logic có 2n trư ng h p chân tr cho b n bi n ó. trong ó p, q, r là các bi n m nh . 6
3/5/2009 B ng chân tr c a bi u th c Logic B ng chân tr c a bi u th c Logic Ví d 2: B ng chân tr c a các bi u th c logic p ∨ ( q ∧ r) theo các bi n Ví d 1: m nh p, q, r như sau: B ng chân tr c a các bi u th c logic p→ q và ¬ p ∨ q p q r q∧r p ∨ ( q ∧ r) theo các bi n m nh p,q như sau: 0 0 0 0 0 p q p→ q → ¬p ¬p∨q 0 0 1 0 0 0 0 1 1 1 0 1 0 0 0 0 1 1 1 1 0 1 1 1 1 1 0 0 0 1 1 0 0 0 0 1 0 1 0 1 1 1 0 0 1 1 1 1 0 1 1 1 1 1 1 S tương ương Logic Bi u th c h ng úng, h ng sai Hai bi u th c logic E và F theo các bi n m nh nào Bi u th c logic E ư c g i là h ng úng n u chân tr ó ư c g i là tương ương logic khi E và F luôn luôn c a E luôn luôn b ng 1 ( úng) trong m i trư ng h p có cùng chân tr trong m i trư ng h p chân tr c a b v chân tr c a các bi n m nh trong bi u th c E. bi n m nh . Nói m t cách khác, E là m t h ng úng khi ta có: E Khi ó ta vi t: E ⇔ F c là “E tương ương v i F”. ⇔1. Như v y, theo nh nghĩa ta có th ki m tra xem 2 Bi u th c logic E ư c g i là h ng sai n u chân tr bi u th c logic có tương ương hay không b ng cách c a E luôn luôn b ng 0 (sai) trong m i trư ng h p v l p b ng chân tr c a các bi u th c logic. chân tr c a các bi n m nh trong bi u th c E. Nói Ví d : t b ng chân tr c a các bi u th c logic p → q m t cách khác, E là m t h ng úng khi ta có: E ⇔ 0. và ¬ p∨q theo các bi n m nh p, q ta có: Như v y, ta có th ki m tra xem m t bi u th c logic có p → q ⇔ ¬ p∨q 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. Bi u th c h ng úng, h ng sai Ví d : Bi u th c p ∧ ¬ p là h ng sai. PH N 3 Bi u th c là p → q ↔ ¬ p∨ q là h ng úng. Lu ý: 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). 7
3/5/2009 Lu t Logic là gì ? Các Lu t Logic Các lu t logic là cơ s ta th c hi n các bi n i Lu t v phép ph nh trên m t bi u th c logic nh m có ư c m t bi u th c ¬ ¬ p ⇔ p (lu t ph nh c a ph nh) logic m i tương ương logic v i bi u th c logic có ¬1⇔0 trư c. ¬0⇔1 Các lu t n y có th ư c suy ra tr c ti p t các b ng Lu t giao hoán chân tr c a các bi u th c logic. p∧q⇔q∧p p∨q⇔q∨p Lu t k t h p p ∧ (q ∧ r) ⇔ (p ∧ q) ∧ r p ∨ (q ∨ r) ⇔ (p ∨ q) ∨ r Các Lu t Logic Các Lu t Logic Lu t phân b Lu t kéo theo p ∧ (q ∨ r) ⇔ (p ∨ q) ∧ (p ∨ r) p ∧ (q ∨ r) ⇔ (p ∨ q) ∧ (p ∨ r) p ∨ (q ∧ r) ⇔ (p ∧ q) ∨ (p ∧ r) p ∨ (q ∧ r) ⇔ (p ∧ q) ∨ (p ∧ r) Lu t De Morgan Lu t tương ương ¬ (p ∧ q) ⇔ ¬ p ∨ ¬ q ¬ (p ∧ q) ⇔ ¬ p ∨ ¬ q ¬ (p ∨ q) ⇔ ¬ p ∧ ¬ q ¬ (p ∨ q) ⇔ ¬ p ∧ ¬ q Lu t v ph n t bù p∨¬p⇔1 p∧¬p⇔0 Các Lu t c a phép H i Các Lu t c a phép H i p ∨ p ⇔ p (tính lũy ng) p ∧ p ⇔ p (tính lũy ng) p ∨ 1 ⇔ 1 (Lu t th ng tr ) p ∧ 1 ⇔ p (Lu t trung hòa) p ∨ 0 ⇔ p (Lu t trung hòa) p ∨ 0 ⇔ 0 (Lu t th ng tr ) p ∨ (p ∧ q) ⇔ p (Lu t h p th ) p ∧ (p ∨ q) ⇔ p (Lu t h p th ) 8
3/5/2009 Các quy t c thay th Qui t c 1 Trong m t bi u th c logic E, n u ta thay th m t bi u PH N 4 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. Ví d : Cho bi u th c logic E = q ∨¬ p. Thay th q trong bi u th c E b i bi u th c ¬ ¬ q (tương ương v i q) ta ư c m t bi u th c m i E' = ¬ ¬ q ∨¬ p. Theo qui t c thay th 1 ta có: q∨¬p⇔¬¬q∨¬ p Các quy t c thay th Các ví d quy t c thay th Qui t c 2 Ví d 1: Ch ng minh r ng (p → q) ⇔ (¬ q → ¬ p) 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 Gi i : tuỳ ý thì ta s ư c m t bi u th c logic m i E’ cũng là Ta có (p → q) ⇔ (¬ p ∨ q) (lu t kéo theo) m t h ng úng. ⇔ (q ∨ ¬ p) (lu t giao hoán) ⇔ (¬ ¬ q ∨ ¬ p) (lu t ph nh) Ví d : ⇔ (¬ q ¬ p) (lu t kéo theo) Ta có bi u th c E(p,q) = (p → q) ↔ ( ¬ p ∨ q) là m t h ng úng. Thay th bi n q trong bi u th c E b i bi u Bài t p nh : hãy ch ng minh th c q ∧ r ta ư c bi u th c logic m i: a) ((p → q) ∧ p) → q là m t h ng úng. E’(p,q,r) = (p → (q ∧ r)) ↔ ( ¬ p ∨ (q ∧ r)) b) p ∧ q → p là m t h ng úng. Theo qui t c thay th 2 ta có bi u th c E’(p,q,r) cũng c) p → p ∨ q là m t h ng úng là m t h ng úng. 9