Bài giảng môn Toán rời rạc - Chương 3: Đại số Bool

Nội dung text: Bài giảng môn Toán rời rạc - Chương 3: Đại số Bool

1. LOGO TOÁN RỜI RẠC Chương 3. Đại số Bool GV: Võ Tấn Dũng Trường Cao đẳng CNTT TPHCM 1
2. Nội dung Đại Số Bool Hàm Bool Mạch logic Bản đồ Karnaugh 2
3. Mở đầu 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 3
4. Mở đầu A B C MN 0 0 0 0 0 0 1 0 0 1 0 0 Câu hỏi: Khi mạch điện gồm nhiều 0 1 1 1 cầu dao, làm sao ta có thể kiểm 1 0 0 1 soát được. 1 0 1 1 Giải pháp là đưa ra công thức, với 1 1 0 1 mỗi biến được xem như là một cầu 1 1 1 1 dao
5. 5 I. Đại Số Bool Xét tập hợp B = {0, 1}. Khi đó, B trở thành một đại số Bool
6. 6 II. 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.
7. 7 Bảng chân trị Xét hàm Bool n biến f(x1,x2, ,xn) n Vì mỗi biến xi chỉ nhận hai giá trị 0, 1 nên chỉ có 2 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
8. 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
9. 9 Ví 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 10
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 x hay được gọi là từ đơn. i x i  Đơ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 11
12. là từ tối tiểu 12
13. 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
14. 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
15. Cổng NOT Kí hiệu cổng Bảng chân trị X not X 0 1 1 0 Input Output F() x x 15
16. Cổng AND Bảng chân trị a b a.b 0 0 0 0 1 0 1 0 0 1 1 1 16
17. Cổng OR a b a + b Bảng chân trị: 0 0 0 0 1 1 1 0 1 1 1 1 17
18. Cổng NAND 18
19. Cổng NOR 19
20. Ví dụ f xz  yz  xt  yt  xyz 20
21. Ví dụ 21
22. Cho sơ đồ Viết biểu thức f f(,,)() x y z x  y  z x y z
23. . 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 Tại bảng chân trị, chỉ quan tâm các dòng x y F(x, y) có F(x,y)=1. - Khi x hay y bằng 1, ghi lại x, y 1 1 1 - Khi x hay y bằng không, ghi phủ định x hay phủ định y 1 0 0 Kết quả hàm số dạng dnf là: 0 1 0 0 0 1 23
24. x x y y x x y x y y 24
25. . 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 Giả sử F(x,y,z) =1 khi 1 hoặc 3 x y z F(x,y,z) cái đều bật 1 1 1 1 Chỉ quan tâm các dòng có F(x,y,z)=1. Tại 1 1 0 0 các dòng đó, biến nào bằng 1 thì giữ 1 0 1 0 nguyên, biến nào bằng 0 thì ghi phủ định. 1 0 0 1 Kết quả hàm số dạng dnf là: 0 1 1 0 0 1 0 1 0 0 1 1 0 0 0 0 25
26. x x y z y z x y x y z Mạch y z z x x y z x y z z x x y y z x yz 26
27. 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
28. Bản đồ Karnaugh (xem trong bản viết tay của thầy)  28