Bài giảng Toán rời rạc - Chương 8: Đại số Boole

Giảng viên: ThS. Trần Quang Khải TOÁN RỜI RẠC Chương 8: Đại số Boole Toán rời rạc: 2011-2012 Nội dung 1. Giới thiệu:  Boole Algebra. Hàm Boole. Hằng đẳng thức đại số Boole. 2. Các cổng logic. 3. Cực tiểu hóa mạch:  Bản đồ Karnaugh. Chương 8: Đại số Boole 2 Toán rời rạc: 2011-2012 Giảng viên: ThS. Trần Quang Khải Giới thiệu Boole Algebra Chương 8: Đại số Boole 3 Chương 8 Toán rời rạc: 2011-2012 Giới thiệu Nhắc lại phần mệnh đề: TRUE & FALSE. Các mạch điện tử trong máy tính: 1 & 0.  Thiết kế các mạch điện tử? Chương 8: Đại số Boole 4 Toán rời rạc: 2011-2012 Giới thiệu Mạch điện tử:  Trạng thái chuyển mạch: Mở & Đóng. Dụng cụ quang học: Sáng & Tối. Sử dụng các quy tắc của Logic:  Claude Shannon: 1938.  “The Law of Thought” (1854).  Boole Algebra. Chương 8: Đại số Boole 5 Toán rời rạc: 2011-2012 Giới thiệu George Boole (1854) – English mathematician  “The Mathematical Analysis of Logic” (1848).  “The Law of Thought” (1854)  Boole Algebra. Chương 1: Logic 6 Toán rời rạc: 2011-2012 Boole Algebra Đại số Boole:  Các phép toán  Các quy tắc Ứng dụng chủ yếu:  Chuyển mạch điện tử.  Chuyển mạch quang học. Chương 8: Đại số Boole 7 trên tập {0, 1} Toán rời rạc: 2011-2012 Boole Algebra Phép toán cơ bản:  Phần bù: NOT  Tổng Boole: OR  Tích Boole: AND Chương 8: Đại số Boole 8 01 10   000 110 ;101 ;111   000 ;01.0 ;00.1 11.1   Phép toán Logic? Toán rời rạc: 2011-2012 Boole Algebra Example: Chương 8: Đại số Boole 9 )10(0.1  0 00 10    FTFFT  )()( Toán rời rạc: 2011-2012 Hàm Boole Biến Boole (Boolean variable): Biến x được gọi là biến Boole nếu nó chỉ nhận các giá trị trong tập {0, 1}. Hàm Boole (Boolean function): Một hàm từ tập {(x1, x2xn)|xi {0,1}, 1≤ i ≤n} tới tập {0,1} được gọi là hàm Boole bậc n. Ví dụ: Chương 8: Đại số Boole 10 zxyzyxF ),,( Biểu thức Boole Toán rời rạc: 2011-2012 Hàm Boole Ví dụ: Chương 8: Đại số Boole 11 zxyzyxF ),,( x y z xy F(x, y, z) 1 1 1 1 0 0 0 0 1 1 0 0 1 1 0 0 1 0 1 0 1 0 1 0 1 1 0 0 0 0 0 0 0 1 0 1 0 1 0 1 1 1 0 1 0 1 0 1 z Toán rời rạc: 2011-2012 Boole Algebra Phép toán XOR: Example: lập bảng giá trị để chứng minh Chương 8: Đại số Boole 12 000 110 101 011     )()()()( yxyxxyyxyx  Toán rời rạc: 2011-2012 Hằng đẳng thức đại số Boole Chương 8: Đại số Boole 13 Hằng đẳng thức Tên gọi x = x Luật phần bù kép x + x = x; x . x = x Luật lũy đẳng x + 0 = x; x . 1 = x Luật đồng nhất x + 1 = 1; x . 0 = 0 Luật nuốt x + y = y + x; xy = yx Luật giao hoán x + (y + z) = (x + y) + z x(yz) = (xy)z Luật kết hợp x + yz = (x + y) . (x + z) x . (y + z) = xy + xz Luật phân phối Luật De Morgan y . )( )( xyx yxxy   Toán rời rạc: 2011-2012 Chứng minh luật phân phối Chương 8: Đại số Boole 14 Toán rời rạc: 2011-2012 Hàm Boole Ví dụ: Tìm giá trị của các biến Boole x và y sao cho: xy = x + y Chương 8: Đại số Boole 15 Toán rời rạc: 2011-2012 Hàm Boole Ví dụ: Lập bảng biểu diễn giá trị các hàm sau: Chương 8: Đại số Boole 16 zyyxzyxF zyyzxzyxF xyzyxzyxF    ),,( )(),,( )(),,( c) b) a) Toán rời rạc: 2011-2012 Biểu diễn các hàm Boole Hai vấn đề trong đại số Boole: 1. Cho các giá trị của hàm Boole, làm thế nào để tìm biểu thức Boole biểu diễn hàm đó? 2. Có biểu thức nào đơn giản hơn để biểu diễn cùng một hàm Boole hay không?  Rút gọn biểu thức Boole? Chương 8: Đại số Boole 17 Toán rời rạc: 2011-2012 Tổng của tích Chương 8: Đại số Boole 18 x y z F G 1 1 1 1 0 0 0 0 1 1 0 0 1 1 0 0 1 0 1 0 1 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 F(x, y, z) = ? G(x, y, z) = ? Toán rời rạc: 2011-2012 Tổng của tích Chương 8: Đại số Boole 19 x y z F G 1 1 1 1 0 0 0 0 1 1 0 0 1 1 0 0 1 0 1 0 1 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 zyxzxyzyx zyxzyx   ),,( ),,( G F Toán rời rạc: 2011-2012 Khái niệm Literal (Đơn tử): là một biến Boole hoặc phần bù của nó. Minterm (Tiểu hạng): là một tích các literal (gồm chính xác n literals). Chương 8: Đại số Boole 20 zyxzxyzyx zyxzyx   ),,( ),,( G F Toán rời rạc: 2011-2012 Khai triển tổng của tích Chương 8: Đại số Boole 21 Sum-of-products là một biểu thức viết dưới dạng tổng của các minterm. Sum-of-products Expansion viết lại biểu thức dưới dạng tổng của tích (còn gọi là “dạng chuẩn tuyển” – disjunctive normal form). Toán rời rạc: 2011-2012 Khai triển tích của tổng Chương 8: Đại số Boole 22 Product-of-sums là một biểu thức viết dưới dạng tích của các tổng (mỗi tổng chứa chính xác n literals). Product-of-sums Expansion viết lại biểu thức dưới dạng tổng của tích (còn gọi là “dạng chuẩn hội” – conjunctive normal form). Toán rời rạc: 2011-2012 Tính “đầy đủ hàm” Functional completeness: Mọi hàm Boole đều có thể được biểu diễn với chỉ các toán tử NOT, OR và AND. gọi là “tập đầy đủ hàm” (functionally complete) Example: có thể loại bớt phép tổng hoặc tích bằng cách sau: Chương 8: Đại số Boole 23 },{., yxxy yxyx   Toán rời rạc: 2011-2012 Giảng viên: ThS. Trần Quang Khải Các cổng Logic Chương 8: Đại số Boole 24 Chương 8 Toán rời rạc: 2011-2012 Các cổng logic Chương 8: Đại số Boole 25 Toán rời rạc: 2011-2012 Các cổng logic Chương 8: Đại số Boole 26 Toán rời rạc: 2011-2012 Các cổng logic Mạch tổ hợp:  Kết hợp các cổng logic cơ bản.  Cho output phụ thuộc vào trạng thái input. Mạch không nhớ (output không phụ thuộc trạng thái hiện tại của mạch). Chương 8: Đại số Boole 27 Toán rời rạc: 2011-2012 Các cổng logic Ví dụ: Xây dựng mạch thể hiện các biểu thức sau: Chương 8: Đại số Boole 28 ) )(( ) ( )( zyxzyx zyx xyx    c) b) a) Toán rời rạc: 2011-2012 Các cổng logic – Ví dụ Chương 8: Đại số Boole 29 Toán rời rạc: 2011-2012 Các cổng logic – Ví dụ Chương 8: Đại số Boole 30 Toán rời rạc: 2011-2012 Các cổng logic Example:  Tìm hàm thể hiện output?  Lập bảng giá trị tương ứng. Chương 8: Đại số Boole 31 Toán rời rạc: 2011-2012 Các cổng logic – Ví dụ Example: Một căn phòng có 3 cửa ra vào, mỗi cửa có 1 công tắc đèn, chuyển trạng thái bất cứ công tắc nào sẽ chuyển trạng thái đèn từ ON  OFF (nếu đang là ON) và ngược lại. Thiết kế mạch điện theo yêu cầu trên, với giả thiết sau: Nếu 3 công tắc đều bật thì đèn là ON. Nếu 3 công tắc đều tắt thì đèn là OFF. Chương 8: Đại số Boole 32 Toán rời rạc: 2011-2012 Các cổng logic – Ví dụ Chương 8: Đại số Boole 33 x y z Đèn minterm 1 1 1 1 0 0 0 0 1 1 0 0 1 1 0 0 1 0 1 0 1 0 1 0 1 0 0 1 0 1 1 0 xyz zyx zyx zyx zyxzyxzyxxyz zyxF  ),,( Chương 8: Đại số Boole 34 zyxzyxzyxxyz zyxF  ),,( Toán rời rạc: 2011-2012 Mạch tổ hợp – Bài tập Dựng các mạch tổ hợp để tạo các output sau: ) )(( )( zyxxyz zyzx xyx    c) b) a) Toán rời rạc: 2011-2012 Giảng viên: ThS. Trần Quang Khải Cực tiểu hóa mạch tổ hợp Chương 8: Đại số Boole 36 Chương 8 Toán rời rạc: 2011-2012 Cực tiểu hóa các mạch Hiệu suất của mạch tổ hợp phụ thuộc vào:  Số các cổng.  Sự bố trí các cổng đó. Các bước thiết kế mạch:  Bước 1: lập bảng giá trị input/output.  Bước 2: tìm khai triển tổng các tích.  Bước 3: đơn giản hóa biểu thức tìm được. Toán rời rạc: 2011-2012 Cực tiểu hóa các mạch Lợi ích:  Tăng độ tin cậy của mạch.  Tăng tốc độ hoạt động của mạch. Giảm giá thành. Giảm tiêu thụ điện. Giảm tỏa nhiệt. Giảm kích thước mạch. Toán rời rạc: 2011-2012 Đơn giản hóa biểu thức Example: Chương 8: Đại số Boole 39 xz yyxz zyxxyzzyxF    )( ),,( Toán rời rạc: 2011-2012 Cực tiểu hóa mạch Phương pháp “Bản đồ Karnaugh”: K-maps Mauric Karnaugh (1953).  Trực quan.  Không thích hợp để thực hiện bằng máy tính. Chương 8: Đại số Boole 40 Maurice Karnaugh (October 4, 1924 in New York City) Toán rời rạc: 2011-2012 K-maps Mô tả:  Sử dụng bảng (hoặc hình vuông, hình chữ nhật) gồm các ô vuông kề nhau. Mỗi ô vuông tượng trưng cho 1 minterm. Hai ô gọi là kề nhau nếu chúng tượng trưng cho 2 minterms chỉ khác nhau đúng 1 literal. Khai triển tổng-của-tích: Nếu minterm nào xuất hiện trong khai triển, điền số 1 vào ô tương ứng. Chương 8: Đại số Boole 41 Toán rời rạc: 2011-2012 K-maps Chương 8: Đại số Boole 42 x x y y xy yx yx yx x x yz zy zyzy y y xyz zxy zyxzyx yzx zyx zyxzyx 2 biến 3 biến z Toán rời rạc: 2011-2012 K-maps: 3 biến Chương 8: Đại số Boole 43 xyz zyx zxy zyx zyx zyx zyxyzx Toán rời rạc: 2011-2012 K-maps: 4 biến Chương 8: Đại số Boole 44 wx xw yz zy zyzy y y wxyz zwxy zywxzywx yzxw zyxw zyxwzyxw w w x xw xw yzxw zyxw zyxwzyxw xyzw zxyw zyxwzyxw z Toán rời rạc: 2011-2012 K-maps: 4 biến Chương 8: Đại số Boole 45 Toán rời rạc: 2011-2012 K-maps: 2 biến Ví dụ: Rút gọn Chương 8: Đại số Boole 46 yxyxGb yxxyFa   )( )( 1 1 x x y y yF  1 1 x x y y yxyxG  Toán rời rạc: 2011-2012 K-maps: 2 biến Ví dụ: Rút gọn Chương 8: Đại số Boole 47 yxyxyxHc )( 1 1 1 x x y y yxH  Toán rời rạc: 2011-2012 K-maps: 3 biến Chương 8: Đại số Boole 48 1 1 x x yz zy zyzy zyzyxzyx  1 1 x x yz zy zyzy zxzyxzyx  Toán rời rạc: 2011-2012 K-maps: 3 biến Chương 8: Đại số Boole 49 1 1 1 1 x x yz zy zyzy zzyxzyxzyxzxy  1 1 1 1 1 1 x x yz zy zyzy xzyxzyxzyxzyx  Toán rời rạc: 2011-2012 K-maps: 3 biến Ví dụ: Chương 8: Đại số Boole 50 1 1 1 1 1 1 x x yz zy zyzy 1 1 1 1 1 1 x x yz zy zyzy 1 1 1 1 1 1 x x yz zy zyzy Toán rời rạc: 2011-2012 K-maps: 3 biến Ví dụ: Chương 8: Đại số Boole 51 1 1 1 1 1 x x yz zy zyzy zyxzyxzyxzyxzyxF  zxyF  Toán rời rạc: 2011-2012 K-maps: 3 biến Example: Chương 8: Đại số Boole 52 zyxzyxzyxzxyH zyxzyxzyxzyxzyxzxyxyzG   Toán rời rạc: 2011-2012 K-maps: 4 biến Ví dụ: Chương 8: Đại số Boole 53 zyxwzyxwzyxwzyxw zyxwzyxwzywxzyxwzyxwF   1 1 1 1 1 1 1 1 1 wx xw yz zy zyzy xw xw  wyzF zwx yxw yxw zyxw Toán rời rạc: 2011-2012 K-maps: 4 biến Chương 8: Đại số Boole 54 zyxwzyxwzyxw zyxwzyxwzyxwzywxG   zyxwzyxwzyxwzyxwzyxw zyxwzyxwzyxwzyxwzywxzywxH   ):Answer( zxyxwzy  ):Answer( yxwxwz 