Đang chuẩn bị liên kết để tải về tài liệu:
Bài giảng Toán rời rạc: Chương 5 - TS. Đặng Xuân Thọ

Bài giảng Toán rời rạc: Chương 5 Đại số Boole và cấu trúc mạch logic cung cấp cho người học những kiến thức như: Giúp tính toán các biểu thứ logic trên bảng giá trị chân lý 0 và 1 cho ra đời một ngành toán học mới là đại số Boole; Biểu thức Boole và hàm Boole; Xác định biểu thức Boole của hàm Boole; Sơ đồ mạch logic. | TOÁN RỜI RẠC DISCRETE MATHEMATICS Bùi Thị Thủy Đặng Xuân Thọ Support 2 TS. Đặng Xuân Thọ Mobile 091.2629.383 Email thodx@hnue.edu.vn Website http fit.hnue.edu.vn thodx Toán rời rạc - ĐHSPHN NỘI DUNG 3 Chương 1. Logic mệnh đề Chương 2. Lý thuyết tập hợp Chương 3. Một số công thức tổ hợp Chương 4. Suy luận và kiểm chứng chương trình Chương 5. Đại số Boole và cấu trúc mạch logic Chương 6. Thuật toán Chương 7. Lý thuyết đồ thị Toán Rời Rạc - ĐHSPHN Chương 5. Đại Số Boole amp Cấu Trúc Mạch Logic 4 Giúp tính toán các biểu thứ logic trên bảng giá trị chân lý 0 và 1 cho ra đời một ngành toán học mới là đại số Boole. Biểu thức Boole và hàm Boole Xác định biểu thức Boole của hàm Boole Sơ đồ mạch logic Toán Rời Rạc - ĐHSPHN 5 Biểu thức Boole và hàm Boole Toán Rời Rạc - ĐHSPHN Biểu thức Boole amp hàm Boole 6 Định nghĩa. Đại số Boole là một tập hợp B với 3 phép toán phép lấy phần bù - phép lấy tổng Boole và phép nhân . Tập hợp B có 2 phần tử đặc biệt là 0 và 1 sao cho các đẳng thức sau thỏa mãn b.1 b 0 b b B luật đồng nhất b 1 b. 0 b B luật bù x y z x y z x.y .z x. y.z kết hợp x y y x x.y y.x giao hoán x. y z x.y x.z x.y z x z . y z phân phối Toán Rời Rạc - ĐHSPHN Biểu thức Boole amp hàm Boole 7 Thứ tự thực hiện của các phép tính của đại số Boole như sau Lấy phần bù gt Phép lấy tích gt Phép lấy tổng Khi có các dấu ngoặc thực hiện theo thứ tự thông thường là ngoặc trong cùng được thực hiện trước. Phép lấy phần bù phép nhân và phép tổng của đại số Boole tương ứng với các toán tử logic phần bù và . Toán Rời Rạc - ĐHSPHN Các hằng đẳng thức của đại số Boole 8 0 1 Các hằng đẳng thức của đại số Boole 9 Ví dụ Tính giá trị của x x 1 y Ta có x x 1 y x x.1 x. y x x x. y x x x. y 1 x. y 1 Toán Rời Rạc - ĐHSPHN Biểu thức Boole amp hàm Boole 10 Một hàm số Boole F với n biến x1 x2 xn được kí hiệu F x1 x2 xn là một ánh xạ f 0 1 n 0 1 Hàm Boole có thể được mô tả bằng lời hoặc dùng bảng tương tự bảng logic toán. Ví dụ hàm F x y sau x y F x y 1 1 1 1 0 0 0 1 0 0 0 0 Toán Rời Rạc - ĐHSPHN Biểu .