Toán rời rạc -Đại số bool

Chia sẻ: Lê Tẹt | Ngày: | Loại File: PPT | Số trang:53

Thêm vào BST

Báo xấu

78
lượt xem 13
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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. 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à cầu dao.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Toán rời rạc -Đại số bool

ĐẠI HỌC QUỐC GIA TP HỒ CHÍ MINH ĐẠI HỌC CÔNG NGHỆ THÔNG TIN  GVGD: Ts. Cao Thanh Tình
I. Hàm Bool Ví dụ: Cho mạch điện như hình vẽ. A M N B C Bảng giá trị 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. 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à cầu dao.
I. Hàm Bool
I. Hàm Bool George Boole George Boole (18151864) (18151864)
I. Hàm Bool 2. Hàm Bool:
I. Hàm Bool
I. Hàm Bool
I. Hàm Bool
II. Các dạng biểu diễn hàm Bool
II. Các dạng biểu diễn hàm Bool
II. Các dạng biểu diễn hàm Bool
II. Các dạng biểu diễn hàm Bool
II. Các dạng biểu diễn hàm Bool
III. So sánh các công thức đa thức của hàm Bool 1. So sánh các dạng đa thức của hàm Bool: f ∈ Fn và f có 2 dạng đa thức f = u1 V u2 V… V up (1) f = v1 V v2 V… V vq (2) a. Ta nói (1) và (2) đơn giản ngang nhau nếu p=q deg(uj) = deg(vj) (1 ≤ j ≤ p) b. Ta nói (1) đơn giản hơn (2) hay (2) phức tạp hơn (1) p≤q deg(uj) ≤ deg(uj) (1 ≤ j ≤ p) chú ý:  Có thể hoán vị v1, v2, …,vq trước khi so sánh bậc nếu cần thiết  Có thể có những cặp đa thức không so sánh được 18
III. So sánh các công thức đa thức của hàm Bool 1. So sánh các dạng đa thức của hàm Bool: Ví dụ: a. f ∈ F4 có 3 dạng đa thức f(x,y,z,t) = x ¬y ¬t V ¬xyz V x ¬z ¬ t V xyz (1) = x ¬y ¬t V ¬xyz V xy ¬z V yzt (2) = x ¬y ¬t V ¬xyzt V ¬xyz ¬t V xy ¬z V yzt (3) (1) và (2) đơn giản ngang nhau vì p=q=4 deg(uj) = deg(vj) = 3 (2) đơn giản hơn (3) hay (3) phức tạp hơn (2) vì q = 4 < r = 5 deg(vj) ≤ deg(qj) 19
III. So sánh các công thức đa thức của hàm Bool 1. So sánh các dạng đa thức của hàm Bool: Ví dụ: b. g ∈ F4 có 3 dạng đa thức g(x,y,z,t) = x ¬yz V z ¬t V ¬xyz V ¬xy ¬zt (4) = z ¬t V x ¬yzt V ¬xyzt V ¬xy ¬zt (5) ta thấy: p = q = 4 d(u1) > d(v1); d(u2) < d(v2) nên cần phải hoán vị (5)  x ¬yzt V z ¬t V ¬xyzt V ¬xy ¬zt (5`) (q` = 4) (4) đơn giản hơn 5` vì p = q` = 4 deg(uj) ≤ deg(wj) 20