intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE

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

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ủ đề:
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

  1. TOÁN RỜI RẠC Chương 8: Đại số Boole Giảng viên: ThS. Trần Quang Khải
  2. 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
  3. 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
  4. 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
  5. 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
  6. 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
  7. 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
  8. 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
  9. 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
  10. 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
  11. 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
  12. 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
  13. 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
  14. Chứng minh luật phân phối Toán rời rạc: 2011-2012 Chương 8: Đại số Boole 14
  15. 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
  16. 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
  17. 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
  18. 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
  19. 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
  20. 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
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

 

Đồng bộ tài khoản
2=>2