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

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.
Nội dung trích xuất từ tài liệu:
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 Cac­nô  B  0  1 bằng số dòng bảng thật A Ví dụ Bìa Cac­nô 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 ...