Toán rời rạc-Chương 6: Đạ số Boole và mạch tổ hợp

Chia sẻ: Bùi Ngọc Thành | Ngày: | Loại File: PDF | Số trang:0

Thêm vào BST

Báo xấu

131
lượt xem 8
download

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

Tham khảo sách 'toán rời rạc-chương 6: đạ số boole và mạch tổ hợp', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả

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-Chương 6: Đạ số Boole và mạch tổ hợp

TOÁN RỜI RẠC CHƯƠNG 6 ĐẠI SỐ BOOLE VÀ MẠCH TỔ HỢP Lecturer: PhD. Ngo Huu Phuc Tel: 0438 326 077 Mob: 098 5696 580 Email: ngohuuphuc76@gmail.com 1 @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University
NỘI DUNG 6.1. Giới thiệu chung. 6.2. Hàm Boole. 6.3. Biểu diễn các hàm Boole. 6.4. Các cổng logic. 6.5. Một số ứng dụng. 2 @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University
6.1. Giới thiệu chung  Giới thiệu một số khái niệm cơ bản của mạch tổ hợp và đại số Boole.  Mối liên hệ giữa các hàm Boole và các mạch tổ hợp.  Dùng các hàm Boole để phân tích và thiết kế các mạch trong thực tế.  Phương pháp tối ưu hoá biểu thức Boole - phương pháp Quine-McClusky. 3 @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University
6.2. Hàm Boole (1/10) 6.2.1. Giới thiệu (1/2):  Đại số Boole đưa ra quy tắc, phép toán làm việc với tập B = {0,1}  Sử dụng đại số Boole trong:  Các chuyển mạch điện tử,  Quang học có thể nghiên cứu.  3 phép toán cơ bản được dùng nhiều nhất: 1. Phép lấy tổng Boole; 2. Phép lấy tích Boole; 3. Phép lấy phần bù. 4 @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University
6.2. Hàm Boole (2/10) 6.2.1. Giới thiệu (2/2):  Phép lấy tổng Boole:  Ký hiệu + hoặc ˅,  Được định nghĩa : 1 + 1 = 1; 1 + 0 = 1; 0 + 1 = 1; 0 + 0 = 0  Phép lấy tích Boole:  Ký hiệu . hoặc ˄,  Được định nghĩa: 1 . 1 = 1; 1 . 0 = 0; 0 . 1 = 0; 0 . 0 =0  Phép lấy phần bù:  Ký hiệu ,  Được định nghĩa: ; 5 @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University
6.2. Hàm Boole (3/10) 6.2.2. Biểu thức Boole và hàm Boole (1/4):  Cho B = {0, 1}, khi đó:  Biến x được gọi là biến Boole nếu nó nhận giá trị ∈ .  Một ánh xạ f: → – được gọi là hàm Boole bậc n.  Biểu thức Boole, với các biến Boole, được định nghĩa một cách đệ quy như sau:  Các ký hiệu 0,1 và các biến Boole , ,…, là các biểu thức Boole.  Nếu , là các biểu thức Boole nào đó, thì , . , cũng là các biểu thức Boole. 6 @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University
6.2. Hàm Boole (4/10) 6.2.2. Biểu thức Boole và hàm Boole (2/4):  Ví dụ: Tìm các giá trị của hàm Boole của hàm Boole được biểu diễn: , , . ̅.  Giải: các giá trị được cho dạng bảng: x y z x.y , , . 1 1 1 1 0 1 1 1 0 1 1 1 1 0 1 0 0 0 1 0 0 0 1 1 0 1 1 0 0 0 0 1 0 0 1 1 0 0 1 0 0 0 0 0 0 0 1 1 7 @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University
6.2. Hàm Boole (5/10) 6.2.2. Biểu thức Boole và hàm Boole (3/4):  Cho hàm Boole F, G với n biến, khi đó:  F và G được gọi là bằng nhau nếu: , ,…, , ,…, với ∀ , ,…, ∈ B={0,1}  Hai biểu thức Boole khác nhau biểu diễn cùng một hàm được gọi là tương đương.  Phần bù của hàm Boole F, ký hiệu , được định nghĩa: , ,…, , ,…, .  Tổng Boole của F và G được định nghĩa: , ,…, , ,…, + , ,…,  Tích Boole của F và G được định nghĩa: . , ,…, , ,…, . , ,…, 8 @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University
6.2. Hàm Boole (6/10) 6.2.2. Biểu thức Boole và hàm Boole (4/4):  Ví dụ: Có bao nhiêu hàm Boole khác nhau bậc n?  Giải: Có 2n bộ n phần tử khác nhau gồm các số 0 và 1. Vì hàm Boole là sự gán 0 hoặc 1 cho mỗi bộ trong số 2n bộ n phần tử. Theo quy tắc nhân, số hàm Boole bậc n sẽ có: hàm Boole. 9 @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University
6.2. Hàm Boole (7/10) 6.2.3. Các hằng đẳng thức của đại số Boole: CÁC HẰNG ĐẲNG THỨC BOOLE Hằng đẳng thức Tên gọi x x Luật phần bù kép x x x x . x x Luật lũy đẳng x 0 x Luật đồng nhất x . 1 x x 1 1 Luật nuốt x . 0 0 x y y x Luật giao hoán x . y y. x x y z x y z Luật kết hợp x . y. z x. y . z x y. z x y . x z Luật phân phối x . y z x. y x. z x. y x y Luật De Morgan x y x. y 10 @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University
6.2. Hàm Boole (8/10) Ví dụ: Chứng minh bằng các phương pháp sau:  Sử dụng bảng giá trị.  Sử dụng hằng đẳng thức của đại số Boole. 11 @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University
6.2. Hàm Boole (9/10) a. Chứng minh bằng bảng giá trị (học viên tự làm). b. Chứng minh bằng hằng đẳng thức Boole: Ta có: – luật đồng nhất đối với tổng Boole. – luật phân phối của tổng Boole đối với tích Boole. – luật giao hoán của tích Boole. – luật nuốt đối với tích Boole. – luật nuốt đối với tổng Boole. . 12 @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University
6.2. Hàm Boole (10/10) 6.2.4. Định nghĩa đại số Boole:  Đại số Boole là một tập B có hai phần tử 0 và 1 với hai phép toán hai ngôi ∨ và ∧, và một phép toán 1 ngôi sao cho các tính chất sau đây đúng với mọi x,y,z ∈ B:  x∨0 x ; x ∧ 1 x – luật đồng nhất.  x∨x 1 ; x ∧ x 0 – luật nuốt. ∨ ∨ ∨ ∨  – luật kết hợp. ∧ ∧ ∧ ∧  x ∨ y y ∨ x ; x ∧ y y ∧ x – luật giao hoán. ∧ ∨ ∧ ∨ ∧  – luật phân phối. ∨ ∧ ∨ ∧ ∨ 13 @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University
6.3. Biểu diễn các hàm Boole (1/7) 6.3.1. Đặt vấn đề:  Có hai bài toán quan trọng của đại số Boole được nghiên cứu:  Bài toán thứ nhất:  Cho các giá trị của một hàm Boole, làm thế nào tìm được biểu thức Boole biểu diễn hàm đó.  Bài toán này được giải bằng cách chứng minh mọi hàm Boole đều có thể được biểu diễn bởi tổng và tích Boole của các biến và phần bù của chúng.  Bài toán thứ 2:  Liệu có thể dùng một tập nhỏ hơn các toán tử để biểu diễn các hàm Boole không?  Bài toán này có thể giải bằng cách chứng minh mọi hàm Boole đều có thể được biểu diễn bằng cách dùng chỉ 1 toán tử. 14 @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University
6.3. Biểu diễn các hàm Boole (2/7) 6.3.2. Khai triển tổng các tích (1/6):  Định nghĩa 6.3.2:  Một biến Boole hoặc phần bù của nó được gọi là một tục biến.  Tích Boole . … trong đó hoặc với x1, x2,...,xn là các biến Boole được gọi là một tiểu hạng (minterm). (tiểu hạng là tích của n tục biến).  Chú ý:  Một tiểu hạng có giá trị 1 đối với một và chỉ một tổ hợp giá trị của các biến của nó.  Hay, tiểu hạng . … bằng 1 khi và chỉ khi mọi yi=1 và điều này chỉ xảy ra khi và chỉ khi xi=1 nếu và xi=0 khi . 15 @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University
6.3. Biểu diễn các hàm Boole (3/7) 6.3.2. Khai triển tổng các tích (2/6):  Có thể lập được biểu thức Boole bằng cách lấy tổng Boole của các tiểu hạng phân biệt với tập các giá trị đã được cho trước.  Tổng Boole các tiểu hạng biểu diễn hàm được gọi là khai triển tổng các tích Boole hay dạng tuyển chuẩn tắc.  Tích Boole của các tổng Boole đối với một hàm Boole được gọi là khai triển tích các tổng Boole hay dạng hội chuẩn tắc. 16 @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University
6.3. Biểu diễn các hàm Boole (4/7) 6.3.2. Khai triển tổng các tích (3/6): Ví dụ 3.1: Tìm các biểu thức Boole biểu diễn các hàm , , và , , được cho bởi bảng sau: x y z F G 1 1 1 0 0 1 1 0 0 1 1 0 1 1 0 1 0 0 0 0 0 1 1 0 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 17 @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University
6.3. Biểu diễn các hàm Boole (5/7) 6.3.2. Khai triển tổng các tích (4/6): Lời giải:  Đối với hàm F: F = 1 khi x=z=1 và y=0 và có F = 0 khi ngược lại. Có thể lập được bằng tích Boole của các biến x, y, z, ta có: , , ∧ ∧  Đối với hàm G: G = 1 khi x=y=1 và z=0 hoặc khi x=z=0 và y=1. Ta có 2 biểu thức: x ∧ y ∧ z hoặc x ∧ y ∧ z Tổng Boole của 2 tích là biểu diễn của hàm G: , , ∧ ∧ ∨ ∧ ∧ 18 @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University
6.3. Biểu diễn các hàm Boole (6/7) 6.3.2. Khai triển tổng các tích (5/6): Ví dụ 3.2: Tìm khai triển tổng các tích của hàm 19 @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University
6.3. Biểu diễn các hàm Boole (7/7) 6.3.2. Khai triển tổng các tích (6/6): Lời giải:  Lập bảng giá trị của F, ta có: x y z ∨ ∨ ∧ 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 0 0 1 0 0 1 1 1 0 1 1 1 0 0 0 1 0 1 1 1 0 0 1 0 0 0 0 0 0 0 1 0 , , ∧ ∧ ∨ ∧ ∧ ∨ ∧ ∧ 20 @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University