Bài giảng Toán rời rạc - Chương 5: Đại số Boole và cấu trúc mạch logic - Bùi Thị Thủy

TOÁN RỜI RẠC (DISCRETE MATHEMATICS) Bùi Thị Thủy Đặng Xuân Thọ Support  TS. Đặng Xuân Thọ  Mobile: 091.2629.383  Email: thodx@hnue.edu.vn  Website: Toán rời rạc - ĐHSPHN 2 NỘI DUNG  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 3 Chương 5. Đại Số Boole & Cấu Trúc Mạch Logic  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 4 Biểu thức Boole và hàm Boole Toán Rời Rạc - ĐHSPHN 5 Biểu thức Boole & hàm Boole  Đị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 6 Biểu thức Boole & hàm Boole  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ù > Phép lấy tích > 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 7 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 (1 )x x y  Ví dụ: Tính giá trị của Ta có: ( .1 . ) ( . ) ( ) . 1 . 1 x x x y x x x y x x x y x y             (1 )x x y  Toán Rời Rạc - ĐHSPHN 9 Biểu thức Boole & hàm Boole  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 10 Biểu thức boole & hàm boole  Hai hàm boole F(x1,x2,,xn) và G(x1,x2,,xn) là hai hàm Boole bằng nhau nếu F(x1, x2, , xn) = G(x1, x2, , xn) cho mọi giá trị của các biến. Toán Rời Rạc - ĐHSPHN 11 Xác định biểu thức Boole của hàm Boole Toán Rời Rạc - ĐHSPHN 12 Xác định biểu thức Boole của hàm Boole  Quy tắc 1: Khai triển các bảng thành các bảng sơ cấp   x1 x2 F(x1,x2) 1 1 1 1 0 0 0 1 0 0 0 1 x1 x2 F1(x1,x2) 1 1 1 1 0 0 0 1 0 0 0 0 x1 x2 F2(x1,x2) 1 1 0 1 0 0 0 1 0 0 0 1 𝐹 𝑥1, 𝑥2 = 𝐹1 𝑥1, 𝑥2 + 𝐹2(𝑥1, 𝑥2) 13 Xác định biểu thức Boole của hàm Boole  Quy tắc 1  Nếu hàm F(x1, x2, , xn) nhận duy nhất giá trị 1 tại (a1,a2, ,an) và 0 tại mọi giá trị khác của (x1,x2, , xn) thì ta có: F(x1, x2, , xn) = y1y2yn quy ước: yi = xi nếu ai = 1 yi = 𝑥𝑖 nếu ai = 0 Toán Rời Rạc - ĐHSPHN 14 Xác định biểu thức Boole của hàm Boole  Quy tắc 1  Ví dụ: x1 x2 F1(x1,x2) 1 1 1 1 0 0 0 1 0 0 0 0 x1 x2 F2(x1,x2) 1 1 0 1 0 0 0 1 0 0 0 1 𝐹 𝑥1, 𝑥2 = 𝑥1𝑥2+𝑥1 𝑥2 𝐹1 𝑥1, 𝑥2 = 𝑥1𝑥2 𝐹2 𝑥1, 𝑥2 = 𝑥1 𝑥2 Toán Rời Rạc - ĐHSPHN 15 Xác định biểu thức Boole của hàm Boole  Quy tắc 2: Khai triển các bảng thành các bảng sơ cấp x1 x2 F(x1,x2) 1 1 1 1 0 0 0 1 0 0 0 1 x1 x2 G1(x1,x2) 1 1 1 1 0 0 0 1 1 0 0 1 x1 x2 G2(x1,x2) 1 1 1 1 0 1 0 1 0 0 0 1 𝐹 𝑥1, 𝑥2 = 𝐺1 𝑥1, 𝑥2 × 𝐺2(𝑥1, 𝑥2) = × 16 Xác định biểu thức Boole của hàm Boole  Quy tắc 2  Nếu hàm F(x1, x2, , xn) nhận duy nhất giá trị 0 tại (a1,a2, ,an) và 1 tại mọi giá trị khác của (x1,x2, , xn) thì ta có: F(x1, x2, , xn) = y1 + y2 + + yn quy ước: yi = 𝑥𝑖 nếu ai = 1 yi = xi nếu ai = 0 Toán Rời Rạc - ĐHSPHN 17 Xác định biểu thức Boole của hàm Boole  Quy tắc 2  Ví dụ: x1 x2 G1(x1,x2) 1 1 1 1 0 0 0 1 1 0 0 1 x1 x2 G2(x1,x2) 1 1 1 1 0 1 0 1 0 0 0 1 𝐹 𝑥1, 𝑥2 = (𝑥1 + 𝑥2)(𝑥1+ 𝑥2 ) 𝐺1 𝑥1, 𝑥2 = 𝑥1 + 𝑥2 𝐺2 𝑥1, 𝑥2 = 𝑥1 + 𝑥2 Toán Rời Rạc - ĐHSPHN 18 Luyện tập  Tìm các hàm chỉ nhận giá trị 1 tại giá trị sau: a) (x, y, z) = (0, 0, 1) b) (x, y, z) = (0, 1, 1) c) (x, y, z) = (0, 1, 0)  Tìm các hàm chỉ nhận giá trị 0 tại giá trị sau: a) (x, y, z) = (0, 0, 1) b) (x, y, z) = (0, 1, 1) c) (x, y, z) = (0, 0, 0) Toán Rời Rạc - ĐHSPHN 19 Sơ đồ mạch logic Toán Rời Rạc - ĐHSPHN 20 Các cổng logic cơ bản  Các mạch chúng ta nghiên cứu ở đây không có khả năng nhớ, nghĩa là giá trị của nó chỉ phụ thuộc vào giá trị đầu vào mà không phụ thuộc vào trạng thái của mạch lúc đó.  Các mạch như vậy gọi là các mạch tổ hợp.  Các phần tử cơ bản của các mạch được gọi là các cổng. Toán Rời Rạc - ĐHSPHN 21 Các cổng logic cơ bản  Cổng NOT  Cổng OR  Cổng AND x x x y x y x y xy Toán Rời Rạc - ĐHSPHN 22 Tổ hợp các cổng và thiết kế mạch  Khi lập tổ hợp các mạch phức hợp, ta sử dụng các cổng cơ bản.  Có thể dùng chung đầu vào cho các cổng.  Ví dụ: 𝑥𝑦 + 𝑥 𝑦 x y xy x y xy xy xy Toán Rời Rạc - ĐHSPHN 23 Luyện tập  Dựng các mạch có đầu ra là các hàm Boole sau: a) 𝑥 + 𝑦 b) 𝑥 𝑦 c) 𝑥 + 𝑥 + 𝑦 d) 𝑥𝑦𝑧 + 𝑥 e) 𝑥 + 𝑦 + 𝑦 + 𝑥 + 𝑧 Toán Rời Rạc - ĐHSPHN 24 THANK YOU!