Bài giảng Toán rời rạc và lý thuyết đồ thị - Chương 3: Đại số Bool - Võ Tấn Dũng

LOGO Chương 3. Đại số Bool TOÁN RỜI RẠC 1 GV: Võ Tấn Dũng Trường Cao đẳng CNTT TPHCM Nội dung Đại Số Bool Hàm Bool Mạch logic Bản đồ Karnaugh 2 Xét mạch điện như hình vẽ Tùy theo các trạng thái cầu dao A, B, C mà ta sẽ có dòng điện đi qua MN. Như vậy ta sẽ có bảng giá trị sau Mở đầu 3 Mở đầu A B C MN 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 1 Câu hỏi: Khi mạch điện gồm nhiều cầu dao, làm sao ta có thể kiểm soát được. Giải pháp là đưa ra công thức, với mỗi biến được xem như là một cầu dao 5Xét tập hợp B = {0, 1}. I. Đại Số Bool Khi đó, B trở thành một đại số Bool 6II. Hàm Bool Hàm Bool n biến là ánh xạ f : Bn  B , trong đó B = {0, 1}. Như vậy hàm Bool n biến là một hàm số có dạng : f = f(x1,x2,,xn), trong đó mỗi biến trong x1, x2,, xn chỉ nhận hai giá trị 0, 1 và f nhận giá trị trong B = {0, 1}. Ký hiệu Fn để chỉ tập các hàm Bool n biến. 7Xét hàm Bool n biến f(x1,x2,,xn) Vì mỗi biến xi chỉ nhận hai giá trị 0, 1 nên chỉ có 2 n trường hợp của bộ biến (x1,x2,,xn). Do đó, để mô tả f, ta có thể lập bảng gồm 2n hàng ghi tất cả các giá trị của f tùy theo 2n trường hợp của biến. Ta gọi đây là bảng chân trị của f Bảng chân trị Ví dụ:  Cho hàm bool bậc 3, f(x,y,z) = xy + xz. Ta có thể lập bảng giá trị của f như sau: 8 9Ví dụ Xét kết qủa f trong việc thông qua một quyết định dựa vào 3 phiếu bầu x, y, z Mỗi phiếu chỉ lấy một trong hai giá trị: 1 (tán thành) hoặc 0 (bác bỏ). Kết qủa f là 1 (thông qua quyết định) nếu được đa số phiếu tán thành, là 0 (không thông qua quyết định) nếu đa số phiếu bác bỏ. 10 Hàm Bool Khi đó f là hàm Bool theo 3 biến x, y, z có bảng chân trị như sau: x y z f 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1 11 Dạng chính tắc tuyển (d.n.f) của Hàm Bool Xét tập hợp các hàm Bool của n biến Fn theo n biến x1, x2,,xn Mỗi hàm bool xi hay được gọi là từ đơn.  Đơn thức là tích khác không của một số hữu hạn từ đơn.  Từ tối tiểu là tích khác không của đúng n từ đơn.  Công thức đa thức là công thức biểu diễn hàm Bool thành tổng của các đơn thức.  Dạng chính tắc tuyển là công thức biểu diễn hàm Bool thành tổng của các từ tối tiểu. disjunctive normal form (d.n.f) = chính tắc tuyển ix là từ tối tiểu 12 Ví dụ: Mệnh đề: Mọi hàm Bool f khác 0 đều có thể viết một cách duy nhất (không kể sai khác về thứ tự trước sau của các tích cơ bản) dưới dạng d.n.f. 13 III. Mạch các cổng Ta nói mạch logic trên tổng hợp (hay còn gọi là biểu diễn) hàm Bool f 14 Cổng NOT Kí hiệu cổng ( )F x x X not X 0 1 1 0 Input Output Bảng chân trị 15 Cổng AND a b a.b 0 0 0 0 1 0 1 0 0 1 1 1 Bảng chân trị 16 Cổng OR a b a + b 0 0 0 0 1 1 1 0 1 1 1 1 Bảng chân trị: 17 Cổng NAND 18 Cổng NOR 19 Ví dụ f x z y z x t y t x y z     20 Ví dụ 21 Viết biểu thức f   ( , , ) ( )f x y z x y z x y z Cho sơ đồ . Thiết kế một mạch điều khiển bởi 2 công tắc Mỗi công tắc được xem như là biến x, y : 1 là bật 0 là tắt Cho F(x, y) =1 khi đèn sáng và 0 khi đèn tắt Giả sử F(x, y) =1 khi cả hai công tắc đều cùng bật hoặc đều cùng tắt x y F(x, y) 1 1 1 1 0 0 0 1 0 0 0 1 Tại bảng chân trị, chỉ quan tâm các dòng có F(x,y)=1. - Khi x hay y bằng 1, ghi lại x, y - Khi x hay y bằng không, ghi phủ định x hay phủ định y Kết quả hàm số dạng dnf là: 23 x x x y y x y yxy 24 Giả sử F(x,y,z) =1 khi 1 hoặc 3 cái đều bật x y z F(x,y,z) 1 1 1 1 1 1 0 0 1 0 1 0 1 0 0 1 0 1 1 0 0 1 0 1 0 0 1 1 0 0 0 0 . Thiết kế một mạch điều khiển bởi 3 công tắc Mỗi công tắc xem như là biến x, y,z : 1 là bật 0 là tắt Cho F(x, y) =1 khi đèn sáng và 0 khi đèn tắt Chỉ quan tâm các dòng có F(x,y,z)=1. Tại các dòng đó, biến nào bằng 1 thì giữ nguyên, biến nào bằng 0 thì ghi phủ định. Kết quả hàm số dạng dnf là: 25 xz x y z x y z zyxy z y x y zyxz z x zyx z y x x y Mạch 26 CÁC BƯỚC THIẾT KỀ SƠ ĐỒ MẠCH Bước 1: Từ yêu cầu thực tế, lập ra bảng giá trị cho hàm Bool. Bước 2: Từ bảng giá trị, rút ra hàm Bool ở dạng chuẩn tắc tuyển. Bước 3: Rút gọn hàm Bool (Tìm dạng công thức đa thức tối tiểu của hàm Bool). Bước 4: Vẽ sơ đồ mạch ứng với công thức đa thức tối tiểu đã tìm được. 27 Bản đồ Karnaugh (xem trong bản viết tay của thầy)  https://sites.google.com/site/votandungsg/noi-dung-trr-ltdht 28