tailieunhanh - Bài giảng Toán rời rạc và lý thuyết đồ thị - Chương 3: Hàm Bool và mạch tổ hợp

Chương 3 trang bị cho người học những kiến thức về hàm Bool và mạch tổ hợp. Thông qua chương này người học sẽ tìm hiểu về: Đại số Bool cơ bản, hàm Bool và mạch các cổng, tìm công thức đa thức tối tiểu dùng biểu đồ Karnaugh. để nắm bắt các nội dung chi tiết. | Chương 3. Hàm Bool và mạch tổ hợp I. ĐẠI SỐ BOOL CƠ BẢN 1. TAP HỢP BOOL VÀ CÁC PHÉP TÓAN BOOL Tập hợp Bool là tập hợp B 0 1 Trên tập B định nghĩa 3 phép toán Bool như sau Phép bù Bool 0 1 và ĩ ũ Phép cộng Bool 0 0 0 0 1 1 1 0 1 1 1 1 Phép nhân Bool 0 0 . 1 0 1 . 0 0 1 . 1 1 Tập hợp Bool B 0 1 với 3 phép tóan như trên gọi là đại số Bool cơ bản. Ký hiệu B . 0 1 . 2. CÁC TÍNH CHẤT CỦA CÁC PHÉP TÓAN BOOL Tính kết hợp. x y z x y z x . y . z x . y . z Tính giao hoán. x y y x x . y y . x Tính lũy đẳng. x x x x . x x Tính phân phối. x . y z x . y x . z x y . z x y . x z Phần tử trung hòa. x 0 x x . 1 x Tính chất phần tử bù. x x 1 x . x 0 Tính chất hấp thụ. x . x y x x x . y x Tính chất De morgan. II. HÀM BOOL VÀ MẠCH CÁC CỔNG. 1. ĐỊNH NGHĨA HÀM BOOL. Hàm Bool là một khái niệm quan trọng và cũng là công cụ trong việc khảo sát các sơ đồ mạch điện cũng như tính toán thiết kế các mạch logic. Trong phần nầy chúng ta sẽ dùng Đại số Bool cơ bản đã xét ở trên B . 0 1 với B 0 1 Một biến x được gọi là biến Bool nếu x chỉ lấy giá trị thuộc B. Định nghĩa Một hàm Bool bậc n là một biểu thức Bool có n biến Bool tham gia. Ta có thể lập bảng giá trị của hàm Bool giống như lập bảng chân trị của biểu thức logic. Ví dụ Cho hàm bool bậc 3 f x y z xy x z. Ta có thể lập bảng giá trị của f như sau x y z x xy x z f 0 0 0 1 0 0 0 0 0 1 1 0 1 1 0 1 0 1 0 0 0 0 1 1 1 0 1 1 1 0 0 0 0 0 0 1 0 1 0 0 0 0 1 1 0 0 1 0