[Giáo trình Toán rời rạc] - Chương8 - Đại số Boole

Tài liệu " [Giáo trình Toán rời rạc] - Chương8 - Đại số Boole " mang tính chất tham khảo, giúp ích cho các bạn tự học, ôn thi, với phương pháp học hay, thú vị, rèn luyện kỹ năng giải đề, nâng cao vốn kiến thức cho các bạn trong các kỳ thi sắp tới. Tác giả hy vọng tài liệu này sẽ giúp ích cho các bạn.
Nội dung trích xuất từ tài liệu:
[Giáo trình Toán rời rạc] - Chương8 - Đại số Boole http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p CHƯƠNG VIII ð IS BOOLE Các m ch ñi n trong máy tính và các d ng c ñi n t khác ñ u có các ñ u vào,m i ñ u vào là s 0 ho c s 1, và t o ra các ñ u ra cũng là các s 0 và 1. Các m ch ñi nñó ñ u có th ñư c xây d ng b ng cách dùng b t kỳ m t ph n t cơ b n nào có hai tr ngthái khác nhau. Chúng bao g m các chuy n m ch có th hai v trí m ho c ñóng vàcác d ng c quang h c có th là sáng ho c t i. Năm 1938 Claude Shannon ch ng tr ng có th dùng các quy t c cơ b n c a lôgic do George Boole ñưa ra vào năm 1854trong cu n “Các quy lu t c a tư duy” c a ông ñ thi t k các m ch ñi n. Các quy t cnày ñã t o nên cơ s c a ñ i s Boole. S ho t ñ ng c a m t m ch ñi n ñư c xác ñ nhb i m t hàm Boole ch rõ giá tr c a ñ u ra ñ i v i m i t p ñ u vào. Bư c ñ u tiên trongvi c xây d ng m t m ch ñi n là bi u di n hàm Boole c a nó b ng m t bi u th c ñư cl p b ng cách dùng các phép toán cơ b n c a ñ i s Boole. Bi u th c mà ta s nh nñư c có th ch a nhi u phép toán hơn m c c n thi t ñ bi u di n hàm ñó. cu ichương này, ta s có các phương pháp tìm m t bi u th c v i s t i thi u các phép t ngvà tích ñư c dùng ñ bi u di n m t hàm Boole. Các th t c ñư c mô t là b n ñKarnaugh và phương pháp Quine-McCluskey, chúng ñóng vai trò quan tr ng trong vi cthi t k các m ch ñi n có hi u qu cao.8.1. KHÁI NI M ð I S BOOLE.8.1.1. ð nh nghĩa: T p h p khác r ng 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 im i a, b, c ∈ S.1. Tính giao hoán: a) a.b = b.a, b) a+b = b+a.2. Tính k t h p: a) (a.b).c = a.(b.c), b) (a+b)+c = a+(b+c).3. Tính phân ph i: a) a.(b+c) = (a.b)+(a.c), b) a+(b.c) = (a+b).(a+c).4. T n t i ph n t trung hoà: T n t i hai ph n t khác nhau c a S, ký hi u là 1 và 0sao 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 . và 0 g i là ph n t trung hoà c a phép +.5. T n t i ph n t bù: V i m i a ∈ S, t n t i duy nh t ph n t a’∈ S sao cho: a) a.a’ = a’.a = 0, b) a+a’ = a’+a = 1. 114http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t pa’ g i là ph n t bù c a a.Thí d 1:1) ð 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 toán ∧(h i), ∨ (tuy n), − (ph ñ nh) tương ng v i . , +, ’, các h ng ñ (ñúng), s (sai) tương ng v i các ph n t trung hoà 1, 0.2) ð i s t p h p là m t ñ i s Boole, trong ñó S là t p h p P(X) g m các t p con c at p khác r ng X, các phép toán ∩ (giao), ∪ (h p), − (bù) tương ng v i . , +, ’, các t pX, Ø tương ng v i các ph n t trung hoà 1, 0.3) 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, 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 ngv i ñ (ñúng), s (sai). M i ph n t 0,1 c a B g i là m t bit. Ta thư ng vi t x thay cho x’. n T ng quát, g i B là t p h p các xâu n bit (xâu nh phân ñ dài n). Ta ñ nh nghĩatích, t ng c a hai chu i và bù c a m t chu i theo t ng bit m t như trong B ng 1, mà nthư ng ñư c g i là các phép toán AND-bit, OR-bit, NOT-bit. B v i các phép toán nàyt o thành m t ñ i s Boole.4) Cho M là t p h p các s th c có c n trên p, c n dư i q và tâm ñ i x ng O. Các phéptoán . , +, ’ trên M ñư c ñ nh nghĩa như sau: a.b = min(a, b), a+b = max(a, b), a’ là ñi m ñ i x ng c a a qua O.Khi ñó M là m t ñ i s Boole, trong ñó q, p tương ng v i các ph n t trung hoà 1, 0.8.1.2. 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 m i tiên ñ a), n u ta thay . b i +, thay + b i ., thay1 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 ñư cm t ñ nh lý trong ñ i s Boole thì ta có ngay m t ñ nh lý khác, ñ i ng u c a nó, b ngcá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ý.8.1.3. ð nh lý:6. (Tính nu t) a) a.0 = 0, b) a+1 = 17. (Tính lu ñ ng) a) a.a = a, b) a+a = a. 115http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p8. (H th c De Morgan) a) (a.b)’ = a’+b’, b) (a+b)’ = a’.b’.9. (H th c bù kép) (a’)’ = a.10. a) 1’ = 0, b) 0’ = ...