Bài thuyết trình đại số bool

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

Thêm vào BST

Báo xấu

143
lượt xem 25
download

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

Trong đại số trừu tượng, đại số Boole là một cấu trúc đại số có các tính chất cơ bản của cả các phép toán trên tập hợp và các phép toán logic. Cụ thể, các phép toán trên tập hợp được quan tâm là phép giao, phép hợp, phép bù; và các phép toán logic là Và, Hoặc, Không.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài thuyết trình đại số bool

ĐẠI HỌC QUỐC GIA TP HỒ CHÍ MINH ĐẠI HỌC CÔNG NGHỆ THÔNG TIN 1
Nội dung 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. Các phần tử logic cơ bản 6. Bài tập Đại số bool 2
I ỆU I TH GIỚ Trong đại số trừu tượng, đại số Boole là một cấu trúc đại số có các tính chất cơ bản của cả các phép toán trên tập hợp và các phép toán logic. Cụ thể, các phép toán trên tập hợp được quan tâm là phép giao, phép hợp , phép bù; và các phép toán logic là Và , Hoặc, Không. 3 3
George Boole Full name George Boole Born 2 November 1815 Lincoln, Lincolnshire, England Died 8 December 1864 (aged 49) Ballintemple, County Cork, Ireland Era 19th-century philosophy Region Western Philosophy School Mathematical foundations ofcomputer science Main interests Mathematics, Logic, Philosophy of mathematics Notable ideas Boolean algebra 4
Nội dung 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. Các phần tử logic cơ bản 6. Bài tập Đại số bool 5
2. Đại số Boole Các định nghĩa Biến : đại lượng nào đó, lấy giá trị 0 hoặc 1 Hàm : 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) Đại số bool 6
2. Đại số Boole  Biểu diễn biến và hàm lôgic • Biểu đồ Ven: Mỗi biến lôgic chia không gian thành 2 A B không gian con: 1 không gian con: A hoặc B biến lấy giá trị đúng A và B (=1) Không gian con còn lại: biến lấy giá trị sai (=0) Đại số bool 7
2. Đại số Boole  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 Ví dụ Bảng thật hàm 1 0 1 Hoặc 2 biến 1 1 1 Đại số bool 8
2. Đại số Boole  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 Đại số bool 9
2. Đại số Boole  Biểu diễn biến và hàm lôgic • Biểu đồ thời gian: A Là đồ thị biến thiên 1 theo thời gian của 0 hàm và biến lôgic B t 1 Ví dụ Biểu đồ 0 thời gian của F(A,B) t 1 hàm Hoặc 2 biến 0 t Đại số bool 10
2. Đại số Boole  Các hàm lôgic cơ bản • Hàm Phủ định: Ví dụ Hàm 1 biến A F(A) F( A) = A 0 1 1 0 Đại số bool 11
2. Đại số Boole  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 Đại số bool 12
2. Đại số Boole  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 Đại số bool 13
2. Đại số Boole  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=A A.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 Đại số bool 14
2. Đại số Boole  Định lý De Morgan  Trường hợp 2 biến A + B = A.B 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 Đại số bool 15
Nội dung 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. Các phần tử logic cơ bản 6. Bài tập Đại số bool 16
3. Biểu diễn các hàm lôgic  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 17 Tối thiểu hoá hàm logic
3. Biểu diễn các hàm lôgic  Dạng tuyển chính qui Nhận xét Giá trị hàm = 0 → số hạng tương ứng bị loại Giá trị hàm = 1 → số hạng tương ứng bằng tích các biến 18 Tối thiểu hoá hàm logic
3. Biểu diễn các hàm lôgic A B C F  Dạng tuyển chính qui 0 0 0 0 Ví dụ 0 0 1 1 Cho hàm 3 biến F(A,B,C). 0 1 0 1 Hãy viết biểu thức hàm dưới dạng tuyển chính qui. 0 1 1 1 1 0 0 0 F(A,B, C) = A B C + A B C + 1 0 1 1 A B C + A B C + A B C 1 1 0 0 1 1 1 1 19 Tối thiểu hoá hàm logic
3. Biểu diễn các hàm lôgic  Dạng hội 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ích của 2 tổng lôgic: F( A, B, ..., Z) = [ A + F(1, B, ..., Z)] .[ A + F(0, B, ..., Z)] Ví dụ F( A, B) = [ A + F(1, B)] [ A + F(0, B)] F(0, B) = [ B + F(0, 1)] [ B + F(0, 0)] F(1, B) = [ B + F(1, 1)] [ B + F(1, 0)] F( A, B) = [ A + B + F(1, 1) ] [ A + B + F(1, 0) ] Nhận xét [ A + B + F(0, 1) ] [ A + B + F(0, 0) ] 2 biến → Tích 4 số hạng, 3 biến → Tích 8 số hạng n biến → Tích 2n số hạng 20 Tối thiểu hoá hàm logic