Bài giảng Toán rời rạc: Chương 8 - ThS. Trần Quang Khải

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

Thêm vào BST

Báo xấu

19
lượt xem 3
download

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

Bài giảng Toán rời rạc: Chương 8 Đại số Boole, cung cấp cho người học những kiến thức như: Giới thiệu: Boole Algebra; Hàm Boole; Hằng đẳng thức đại số Boole; Các cổng logic; Cực tiểu hóa mạch. . Mời các bạn 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 rời rạc: Chương 8 - ThS. Trần Quang Khải

TOÁN RỜI RẠC Chương 8: Đại số Boole Giảng viên: ThS. Trần Quang Khải
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. Toán rời rạc: 2011-2012 Chương 8: Đại số Boole 2
Chương 8 Giới thiệu Boole Algebra Giảng viên: ThS. Trần Quang Khải Toán rời rạc: 2011-2012 Chương 8: Đại số Boole 3
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ử? Toán rời rạc: 2011-2012 Chương 8: Đại số Boole 4
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. Toán rời rạc: 2011-2012 Chương 8: Đại số Boole 5
Giới thiệu  George Boole (1854) – English mathematician  “The Mathematical Analysis of Logic” (1848).  “The Law of Thought” (1854)  Boole Algebra. Toán rời rạc: 2011-2012 Chương 1: Logic 6
Boole Algebra  Đại số Boole:  Các phép toán trên tập {0, 1}  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. Toán rời rạc: 2011-2012 Chương 8: Đại số Boole 7
Boole Algebra  Phép toán cơ bản:  Phần bù: 0  1 Phép toán NOT Logic? 10  Tổng Boole: 1  1  1; 1  0  1; 0  1  1 OR 00  0  Tích Boole: AND 1.1  1 1.0  0; 0.1  0; 0  0  0 Toán rời rạc: 2011-2012 Chương 8: Đại số Boole 8
Boole Algebra  Example: 1.0  (0  1)  0  1  00 0 (T  F )  ( F  T )  F Toán rời rạc: 2011-2012 Chương 8: Đại số Boole 9
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, x2…xn)|xi {0,1}, 1≤ i ≤n} tới tập {0,1} được gọi là hàm Boole bậc n. Ví dụ: F ( x, y, z )  xy  z Biểu thức Boole Toán rời rạc: 2011-2012 Chương 8: Đại số Boole 10
Hàm Boole  Ví dụ: F ( x, y, z )  xy  z x y z xy z F(x, y, z) 1 1 1 1 0 1 1 1 0 1 1 1 1 0 1 0 0 0 1 0 0 0 1 1 0 1 1 0 0 0 0 1 0 0 1 1 0 0 1 0 0 0 0 0 0 0 1 1 Toán rời rạc: 2011-2012 Chương 8: Đại số Boole 11
Boole Algebra  Phép toán XOR: 11  0 1 0  1 0 1  1 00  0  Example: lập bảng giá trị để chứng minh x  y  ( x  y )( xy )  ( xy )  ( xy ) Toán rời rạc: 2011-2012 Chương 8: Đại số Boole 12
Hằng đẳng thức đại số Boole 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 Luật kết hợp x(yz) = (xy)z x + yz = (x + y) . (x + z) Luật phân phối x . (y + z) = xy + xz ( xy )  x  y Luật De Morgan ( x  y)  x . y Toán rời rạc: 2011-2012 Chương 8: Đại số Boole 13
Chứng minh luật phân phối Toán rời rạc: 2011-2012 Chương 8: Đại số Boole 14
Hàm Boole  Ví dụ: Tìm giá trị của các biến Boole x và y sao cho: xy = x + y Toán rời rạc: 2011-2012 Chương 8: Đại số Boole 15
Hàm Boole  Ví dụ: Lập bảng biểu diễn giá trị các hàm sau: a) F ( x, y , z )  xy  ( xyz ) b) F ( x, y , z )  x ( yz  y z ) c) F ( x, y , z )  x y  yz Toán rời rạc: 2011-2012 Chương 8: Đại số Boole 16
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? Toán rời rạc: 2011-2012 Chương 8: Đại số Boole 17
Tổng của tích x y z F G 1 1 1 0 0 F(x, y, z) = ? 1 1 0 0 1 G(x, y, z) = ? 1 0 1 1 0 1 0 0 0 0 0 1 1 0 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 Toán rời rạc: 2011-2012 Chương 8: Đại số Boole 18
Tổng của tích x y z F G 1 1 1 0 0 1 1 0 0 1 F ( x, y, z )  xyz 1 0 1 1 0 G ( x, y, z )  xy z  x yz 1 0 0 0 0 0 1 1 0 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 Toán rời rạc: 2011-2012 Chương 8: Đại số Boole 19
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). F ( x, y, z )  xyz G ( x, y, z )  xy z  x yz Toán rời rạc: 2011-2012 Chương 8: Đại số Boole 20