Bài giảng Nhập môn Tin học - Chương 5: Đại số Boole

Chia sẻ: Blabla Blabla | Ngày: | Loại File: PPTX | Số trang:32

Thêm vào BST

Báo xấu

157
lượt xem 6
download

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

Bài giảng Nhập môn Tin học - Chương 5 trình bày về đại số Boole. Nội dung chính trong chương này gồm có: Đại số boole là gì? Khái niệm cơ bản về đại số Boole, độ ưu tiên của các toán tử, các tiên đề của đại số Boole, nguyên lý đối ngẫu,... 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 Nhập môn Tin học - Chương 5: Đại số Boole

Chương 5: Đại số Boole
Đại số boole là gì? Là phép toán đại số liên quan đến hệ thống số nhị phân Do nhà toán học người Anh đưa ra năm 18151864 nhằm Đơn giản hóa việc trình bày Thao tác với logic mệnh đề 1938 Claude đề xuất sử dụng đại số Boole trong thiết kế mạch Cung cấp cách tiếp cận tiết kiệm và đơn giản Được sử dụng rộng rãi trong thiết kế mạch điện tử trong máy tính
Khái niệm cơ bản về Đại số Boole Các phép toán trong đại số Boole thực hiện trên các biến có 2 giá trị 0 và 1, gồm Cộng logic: ‘+’ hay OR Nhân logic: ‘ . ‘ hay AND Phép bù: ‘’ hay NOT
Khái niệm cơ bản về Đại số Boole Bảng chân trị: A B A AND B A OR B NOT A 0 0 0 0 1 0 1 0 1 1 1 0 0 1 0 1 1 1 1 0
Độ ưu tiên của các toán tử Toán tử có độ ưu tiên cao nhất được định trị đầu tiên. Biểu thức được tính từ trái sang phải Độ ưu tiên Toán tử 1 ( ) Biểu thức trong ngoặc 2 _ (NOT) 3 . (AND) 4 + (OR)
Độ ưu tiên của các toán tử
Các tiên đề của đại số Boole
Các tiên đề của đại số Boole
Nguyên lý đối ngẫu Có sự đối ngẫu giữa toán tử AND, OR và bit 0, 1
Các định lý của đại số Boole
Các định lý của đại số Boole
Hàm Boole Một hàm Boole là một biểu thức được thực hiện với: Các biến nhị phân Các toán tử AND, OR, NOT Các dấu ngoặc và đấu = Giá trị của hàm Boole có thể là 0 hoặc 1 Một hàm Boole có thể được biểu diễn dạng:  Một biểu thức đại số  Một bảng chân trị
Hàm Boole Hàm Boole biểu diễn dưới dạng biểu thức đại số: Hoặc Với: X, Y và Z được gọi là các biến của hàm.
Hàm Boole Hàm Boole biểu diễn dưới X Y Z W dạng bảng chân trị 0 0 0 0 Số hàng của bảng là 2n, n là 0 0 1 1 số các biến nhị phân được sử 0 1 0 0 dụng trong hàm. 0 1 1 0 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 1
Sự dư thừa Khái niệm: Literal: là các biến trong hàm Boole Term của n biến là sự kết hợp của các biến mà mỗi biến chỉ xuất hiện một lần duy nhất. Ví dụ: term của 3 biến A, B, C là A.B.C Một biểu thức là dư thừa nếu nó có chứa Literal lặp: XX hay X+X Biến và bù của biến: XX’ hay X+X’ Hằng: 0 hay 1
Tối thiểu hóa hàm Boole Tối thiểu hàm Boolean: Giảm số phần tử (Term) Giảm số biến (Literal) Phương pháp: Sử dụng phương pháp đại số Áp dụng các định lý, tiên đề, các luật nhiều lần để tối thiểu hàm Boolean tới mức thấp nhất.
Tối thiểu hóa hàm Boole
Phần bù của hàm Boole
Phần bù của hàm Boole Ví dụ: tính phần bù của hàm sau: Bước 1: Chuyển toán tử AND thành OR và ngược lại. Bước 2: tính phần bù của các biến
Dạng chính tắc của hàm Boole Một hàm n biến luôn được biểu diễn dưới 2 dạng: Dạng tổng các tích (sumofproduct SOP): biểu thức được biểu diễn dưới dạng tổng (sum) các toán hạng (term), mỗi toán hạng là tích (product) của các literal Dạng tích các tổng (productofsum POS): biểu thức được biểu diễn dưới dạng tích các toán hạng, mỗi toán hạng là tổng của các literal