Bài giảng học Đại số Boole

Chia sẻ: Lê Tẹt | Ngày: | Loại File: PPT | Số trang:37

Thêm vào BST

Báo xấu

49
lượt xem 6
download

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

Mạch logic (mạch số) hoạt động dựa trên chế độ nhị phân: Điện thế ở đầu vào, đầu vào hoặc bằng 0, hoặc bằng 1 Với 0 hay 1 tượng trưng cho các khoảng điện thế được định nghĩa sẵn

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 học Đại số Boole

ĐẠI HỌC QUỐC GIA TP HỒ CHÍ MINH ĐẠI HỌC CÔNG NGHỆ THÔNG TIN 1
 1. Giới thiệu. 2. Đại số Boole. 3. Biểu diễn các hàm logic dưới dạng chính quy. 4. Tối thiểu hóa các hàm logic. 5. Bài tập. 2
1.GIỚI THIỆU George Boole Full name George Boole Born 2 November 1815 Lincoln, Lincolnshire, England A Died 8 December 1864 (aged 49) AB Ballintemple, County Cork, Ireland B Era 19th-century philosophy A A Region Western Philosophy School Mathematical foundations of computer science A AB Main interests Mathematics, Logic, Philosophy of mathematics B 3 Notable ideas Boolean algebra
 Mạch logic (mạch số) hoạt động dựa trên chế độ nhị phân:  Điện thế ở đầu vào, đầu vào hoặc bằng 0, hoặc bằng 1  Với 0 hay 1 tượng trưng cho các khoảng điện thế được định nghĩa sẵn  VD: 0 → 0.8V :0 Cho phép2.5 ta→sử5V dụng Đ: ạ 1i số Boole như 4 là một công cụ để phân tích và thiết kế các hệ thống số.
 Đại số Boole:  Do George Boole sáng lập vào thế kỷ 19  Các hằng, biến và hàm chỉ nhận 1 trong 2 giá trị: 0 và 1.  Là công cụ toán học khá đơn giản cho phép mô tả mối liên hệ giữa các đầu ra của mạch logic với các đầu vào 5 của nó dưới dạng biểu thức logic.  Là cơ sở lý thuyết, là công cụ cho phép nghiên cứu, mô tả, phân tích, thiết kế và xây dựng các hệ thống số, hệ thống logic, mạch số ngày nay.
oCác phần tử logic cơ bản: o Còn gọi là các cổng logic, mạch logic cơ bản o Là các khối cơ bản cấu thành nên các mạch logic và hệ thống số khác 6
 1. Giới thiệu.  2. Đại số Boole. 3. Biểu diễn các hàm logic dưới dạng chính quy. 4. Tối thiểu hóa các hàm logic. 5. Bài tập. 7
Các định nghĩa • Biến lôgic: đại lượng biểu diễn bằng ký hiệu nào đó, lấy giá trị 0 hoặc 1. • Hàm lôgic: nhóm các biến lôgic liên hệ với nhau qua các phép toán lôgic, lấy giá trị 0 hoặc 1. • Phép toán lôgic cơ bản: VÀ (AND), HOẶC (OR), PHỦ ĐỊNH (NOT). 8
 Biểu diễn biến và hàm lôgic • Biểu đồ Ven: Mỗi biến lôgic chia A hoặc B không gian thành 2 không gian con: -Một không gian con: A B biến lấy giá trị đúng (=1) A và B -Không gian con còn lại: biến lấy giá trị sai (=0) 9
 Biểu diễn biến và hàm lôgic • Bảng thật: A B F(A,B) Hàm n biến sẽ có: n+1 cột (n biến và giá trị 0 0 0 hàm). 0 1 1 2n hàng : 2n tổ hợp biến. 1 0 1 Ví dụ : Bảng thật hàm Hoặc 1 1 1 2 biến. 10
 Biểu diễn biến và hàm lôgic • Bìa Cac-nô: Số ô trên bìa Cacnô B 0 1 bằng số dòng bảng thật A Ví dụ Bìa Cacnô hàm 0 0 1 Hoặc 2 biến 1 1 1 11
 Biểu diễn biến và hàm lôgic • Biểu đồ thời gian: A 1 Là đồ thị biến thiên 0 theo thời gian của hàm B t và biến lôgic. 1 0 Ví dụ : Biểu đồ F(A,B) t thời gian của 1 hàm Hoặc 2 biến. 0 t 12
 Các hàm lôgic cơ bản. • Hàm Phủ định: A F(A) Ví dụ: Hàm 1 biến F( A) = A 0 1 1 0 13
 Các hàm lôgic cơ bản • Hàm Và : A B F(A,B) Ví dụ : Hàm 2 biến 0 0 0 F( A, B) = AB 0 1 0 1 0 0 1 1 1 14
 Các hàm lôgic cơ bản A B C F • Hàm Hoặc : 0 0 0 0 0 0 1 1 0 1 0 1 Ví dụ: Hàm 3 biến 0 1 1 1 F( A, B, C) = A + B + C 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 1 15
 Tính chất các hàm lôgic cơ bản  Tồn tại phần tử trung tính duy nhất cho phép toán Hoặc và phép toán Và: A + 0 = AA.1 = A Giao hoán: A + B = B + A A.B = B.A  Kết hợp: A + (B+C) = (A+B) + C = A + B + C A . (B.C) = (A.B) . C = A . B . C  Phân phối: A(B+C) = AB + AC A + (BC) = (A+B)(A+C)  Không có số mũ, không có hệ số: A + A + ... + A = A A.A....A = A  Phép bù: A = A A + A = 1 A.A = 0 16
 Định lý Đờ Mooc-gan A + B = A.B  Trường hợp 2 biến : A.B = A + B  Tổng quát : F( Xi , +, .) = F( Xi , ., +)  Tính chất đối ngẫu : + �� 0 1 A + B = B + A � A.B = B.A A + 1 = 1 � A.0 = 0 17
 1. Giới thiệu.  2. Đại số Boole.  3. Biểu diễn các hàm logic dưới dạng chính quy. 4. Tối thiểu hóa các hàm logic. 5. Bài tập. 18
 Dạng tuyển và dạng hội : - Dạng tuyển (tổng các tích) : F( x, y, z) = xyz + x y + x z - Dạng hội (tích các tổng):F( x, y, z) = ( x + y + z) ( x + y) ( x + y + z)  Dạng chính qui : • Tuyển chính qui : F( x, y, z) = xyz + x yz + xyz • Hội chính qui : F( x, y, z) = ( x + y + z) ( x + y + z) ( x + y + z) Không phải dạng chính qui tức là dạng đơn giản hóa. 19
 Dạng tuyển chính qui:  Định lý Shannon: Tất cả các hàm lôgic có thể triển khai theo một trong các biến dưới dạng tổng của 2 tích lôgic: F( A, B, ..., Z) = A.F(0, B, ..., Z) + A.F(1, B, ..., Z) Ví dụ: F( A, B) = A.F(0, B) + A.F(1, B) F(0, B) = B.F(0, 0) + B.F(0, 1) F(1, B) = B.F(1, 0) + B.F(1, 1) F( A, B) = AB.F(0, 0) + AB.F(0, 1) + AB.F(1, 0) + AB.F(1, 1)  Nhận xét: • 2 biến → Tổng 4 số hạng • 3 biến → Tổng 8 số hạng • n biến → Tổng 2n số hạng 20