Đ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 4: Đại Số Bool (Phạm Thế Bảo)

Bài giảng Toán rời rạc - Chương 4: Đại Số Bool (Phạm Thế Bảo) có nội dung trình bày các kiến thức về đại dố Bool, hàm Bool - các phép toán trên hàm Bool, dạng nối rời chính tắc của Hàm Bool, biểu đồ karnaugh, mạch logic, . Mời các bạn cùng tham khảo chi tiết nội dung bài giảng! | LOGO4 Chương TOÁN RỜI RẠC Phạm Thế Bảo email ptbao@hcmus.edu.vn www.math.hcmus.edu.vn ptbao TRR Chương 4 Chương IV. Đại số Bool Đại Số Bool Hàm Bool Biểu đồ karnaugh Mạch logic Mở đầu Xét mạch điện như hình vẽ Tùy theo cách 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 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 1 1 0 1 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 1 1 1 1 dao 5 I. Đại Số Bool Một đại số Bool A là một tập hợp A với hai phép toán tức là hai ánh xạ A A A x y x y và A A A x y x y thỏa 5 tính chất sau 6 I. Đại Số Bool - Tính giao hoán x y A x y y x x y y x - Tính kết hợp x y z A x y z x y z x y z x y z . - Tính phân phối x y z A x y z x y x z x y z x y x z . 7 I. Đại Số Bool - Có các phần tử trung hòa 1 và 0 x A x 1 1 x x x 0 0 x x. - Mọi phần tử đều có phần tử bù x A x A x x x x 0 x x x x 1. 8 I. Đại Số Bool Ví dụ. Xét F là tập hợp tất cả các dạng mệnh đề theo n biến p1 ôip2 pn với hai phép toán hội phép toán tuyển trong đó ta đồng nhất các dạng mệnh đề tương đương. Khi đó F là một đại số Bool với phần tử 1 là hằng đúng 1 phần tử 0 là hằng sai 0 phần tử bù của dạng mệnh đề E là dạng mệnh đề bù E 9 I. Đại Số Bool Xét tập hợp B 0 1 . Trên B ta định nghĩa hai phép toán như sau Khi đó B trở thành một đại số Bool 10 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 biến. Ví dụ. Dạng mệnh đề E E p1 p2 pn theo n biến p1 p2 pn là một hàm Bool n biến. 11 Bảng chân trị Xé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ó 2n 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à .