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. Hàm Bool và mạch tổ hợp I. ĐẠI SỐ BOOL CƠ BẢN 1. TẬP 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: Phép cộng Bool: 0 + 0 = 0 0 + 1 = 1 1 + 0 = 1 1 + 1 = 1 Phép nhân Bool: 0 . 0 = 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 1 1 1 1 0 1 0 1 Chú í:  Khi cho hàm Bool dưới dạng biểu thức ta lập được bảng giá trị cho nó, giống như lập bảng chân trị của biểu thức logic.  Khi cho hàm Bool dưới dạng bảng giá trị ta có thể chuyển hàm Bool thành biểu thức ở dạng chính tắc tuyển, sẽ trình bày ở dưới. 2. BIỂU DIỄN HÀM BOOL Ở DẠNG CHÍNH TẮC TUYỂN Định nghĩa: Cho n là một số nguyên dương và f là một hàm Bool bậc n theo các biến x1, x2, …, xn. Ta nói (a) mỗi biểu thức Bool (hay hàm Bool) có dạng xi hoặc i là một từ đơn. (b) một biểu thức Bool là một tích cơ bản bậc n nếu nó là tích của n từ đơn. (c) một biểu diễn của hàm f dước dạng tổng của các tích cơ bản bậc n là dạng chính tắc tuyển của f, viết tắc là d.n.f (disjunctive normal form) của f. Ví dụ: Hàm Bool sau chưa ở dạng d.n.f f(x,y,z) = xy + x z. Ví dụ: Hàm Bool sau đã ở dạng d.n.f f(x,y,z) = x y z+ x yz+xy z +xyz 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. Phương pháp đưa hàm Bool về dạng d.n.f:  Lập bảng giá trị của hàm Bool.  Mỗi dòng trên bảng gía trị, mà ở dòng đó hàm bool bằng 1, sẽ chuyển thành một tích cơ bản, bằng cách: biến nào ở dòng đó bằng 1 thì đưa biến vào tích cơ bản, biến nào ở dòng đó bằng 0 thì đưa bù biến vào tích cơ bản,  Tổng của các tích cơ bản này chính là dạng d.n.f của hàm Bool đã cho. Ví dụ: Tìm d.n.f của hàm Bool f: B3  B với 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 1 1 1 1 0 1 0 1 Trên bảng có 4 dòng giá trị của f là 1. Chúng được chuyển thàn 4 tích cơ bản, và từ đó ta có dạng d.n.f của f là: f(x,y,z) = x y z+ x yz+xy z +xyz ... - tailieumienphi.vn