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 Hàm Bool Ví dụ: Cho mạch điện như hình vẽ. 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. A C M N B Hàm Bool George Boole(1815-1864) Hàm Bool Hàm Bool 2. Hàm Bool: Hàm Bool Hàm Bool 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 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) Ta nói (1) và (2) đơn giản ngang nhau nếu p = q deg(uj) = deg(vj) (1 ≤ j ≤ p) 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 * 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ụ: 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 d(v1); d(u2) Gom 2 ô sẽ loại được 1 biến -> Gom 4 ô sẽ loại được 2 biến. IV. Phương pháp biểu đồ Karnaugh 3. Ví dụ VD: Dùng các bản đồ Karnaugh ba biến để rút gọn các khai triển tổng các tích sau: F= ¬x¬y¬z  ¬xyz  ¬xy¬z  xyz = yz  ¬x¬z IV. Phương pháp biểu đồ Karnaugh 3. Ví dụ VD: Dùng các bản đồ Karnaugh bốn biến để rút gọn các khai triển tổng các tích sau: F = ¬w¬x¬y¬z  ¬w¬x¬yz  ¬wx¬y¬z  ¬wx¬yz  ¬wxyz  wxy¬z  w¬x¬y¬z = ¬w¬y  ¬w¬xz  ¬x¬y¬z  wxy¬z IV. Phương pháp biểu đồ Karnaugh Mở đầu: Như ta đã biết khi số biến lớn hơn bốn thì việc sử dụng bản đồ Karnaugh sẽ rất phức tạp. Vì thế Phương pháp Quine-McCluskey được ra đời để khắc phục nhược điểm đó. Nó có thể được dùng cho các hàm Boole có số biến bất kỳ. HÀM BOOL * V. Phương pháp Quine-McCluskey Về cơ bản, phương pháp Quine-McCluskey có hai phần. Phần đầu là tìm các số hạng là ứng viên để đưa vào khai triển cực tiểu như một tổng các tích Boole mà ta gọi là các nguyên nhân nguyên tố. Phần thứ hai là xác định xem trong số các ứng viên đó, các số hạng nào là thực sự dùng được HÀM BOOL * V. Phương pháp Quine-McCluskey HÀM BOOL * V. Phương pháp Quine-McCluskey Mệnh đề: Hệ các nguyên nhân nguyên tố của hàm F là một hệ đầy đủ. HÀM BOOL * V. Phương pháp Quine-McCluskey Phương pháp Quine-McCluskey tìm dạng tổng chuẩn tắc thu gọn: Bước 1: Viết vào cột thứ nhất các biểu diễn của các nguyên nhân hạng n của hàm Boole F. Các biểu diễn được chia thành từng nhóm, các biểu diễn trong mỗi nhóm có số các ký hiệu 1 bằng nhau và các nhóm xếp theo thứ tự số các ký hiệu 1 tăng dần. HÀM BOOL * V. Phương pháp Quine-McCluskey Bước 2: Lần lượt thực hiện tất cả các phép dán các biểu diễn trong nhóm i với các biểu diễn trong nhóm i+1 (i=1, 2, …). Biểu diễn nào tham gia ít nhất một phép dán sẽ được ghi nhận một dấu * bên cạnh. Kết quả dán được ghi vào cột tiếp theo. Bước 3: Lặp lại Bước 2 cho cột kế tiếp cho đến khi không thu thêm được cột nào mới. Khi đó tất cả các biểu diễn không có dấu * sẽ cho ta tất cả các nguyên nhân nguyên tố của F. HÀM BOOL * V. Phương pháp Quine-McCluskey HÀM BOOL * HÀM BOOL * Phương pháp Quine-McCluskey tìm dạng tổng chuẩn tắc tối thiểu: Bước 1: Phát hiện tất cả các nguyên nhân nguyên tố cốt yếu. Bước 2: Xoá tất cả các cột được phủ bởi các nguyên nhân nguyên tố cốt yếu. Bước 3: Trong bảng còn lại, xoá nốt những dòng không còn dấu + và sau đó nếu có hai cột giống nhau thì xoá bớt một cột. Bước 4: Sau các bước trên, tìm một hệ S các nguyên nhân nguyên tố với số biến ít nhất phủ các cột còn lại. HÀM BOOL * HÀM BOOL * HÀM BOOL * I. Bộ đảo (cổng NOT) Bảng chân trị Các loại cổng cơ bản: Các loại cổng cơ bản: Các loại cổng cơ bản: Chúng ta sẽ dùng đại số bool phân tích các hàm sau đó sẽ thể hiện các biến đầu vào và đầu ra dưới dạng các cổng cơ bản( and, not, or) và thiết kế cách nối chúng lại với nhau để tạo thành các mạch số cần thiết. Thiết kế mạng các cổng tổng hợp hàm Bool Lợi ích của việc thiết kế mạng các cổng tổng hợp hàm Bool: Việc thiết kế mạng cho F dựa vào 1 công thức đa thức nào đó của F. F có nhiều dạng đa thức khác nhau, ta sẽ chọn 1 công thức đa thức tối tiểu của F để thiết kế mạng cho nó. Như vậy ta sẽ tiết kiệm được chi phí mua cổng và dây dẫn. Thiết kế mạng các cổng tổng hợp hàm Bool(tt) Vd: ta có hàm Thiết kế mạng các cổng tổng hợp hàm Bool(tt) Đầu tiên chúng ta sẽ có 3 cổng And như sau Ta dùng cổng or nối 3 cổng and trên lại với nhau ta được kết quả: X Y z Thiết kế mạng các cổng tổng hợp hàm Bool(tt) Nhưng Mạch logic trên vẫn còn phức tạp và chúng ta có thể rút gọn biểu thức F để có mạch logic đơn giản hơn. Thiết kế mạng các cổng tổng hợp hàm Bool(tt) Sau khi rút gọn hàm F ta được: Thiết kế mạng các cổng tổng hợp hàm Bool(tt) Thiết kế mạch Hai mạch lôgic trong hai hình trên thực hiện cùng một hàm Boole, ta nói đó là hai mạch lôgic tương đương, nhưng mạch lôgic thứ hai đơn giản hơn. Vấn đề tìm mạch lôgic đơn giản thực hiện một hàm Boole F cho trước gắn liền với vấn đề tìm biểu thức đơn giản nhất biểu diễn hàm ấy. Như vậy ta sẽ tiết kiệm được chi phí mua cổng và dây dẫn. Thiết kế mạng các cổng tổng hợp hàm Bool(tt)