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

Chia sẻ: You You | Ngày: | Loại File: PDF | Số trang:15

Thêm vào BST

Báo xấu

331
lượt xem 28
download

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

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. Mời các bạn cùng tham khảo để nắm bắt các nội dung chi tiết.

Chủ đề:

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

Lưu

Nội dung Text: 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
3.MẠCH CÁC CỔNG A. CÁC CỔNG LOGIC CƠ BẢN. Một sơ đồ mạch điện tử với hai đầu vào a và b, và đầu ra là a.b sẽ được biểu diễn bởi sơ đồ sau đây, được gọi là Cổng "VÀ". Tương tự, đối với các phép toán Bool khác ta cũng có các cổng tương ứng : cổng "HAY", cổng "KHÔNG", cổng "KHÔNG-VÀ", cổng "KHÔNG- HAY". Các cổng nầy lần lượt có ký hiệu sơ đồ là
B. MẠCH CÁC CỔNG. Mỗi biểu thức Boole hay hàm Bool theo n biến tương ứng với một sơ đồ mạch. Sơ đồ mạch nầy có n đầu vào và một đầu ra, và là một hệ thống được lắp ghép từ các cổng logic. Ví dụ: Hàm Bool f(x,y) = có sơ đồ mạch tương ứng như sau: C. CÁC BƯỚC THIẾT KỀ SƠ ĐỒ MẠCH CHO MỘT ỨNG DỤNG.  Bước 1: Từ yêu cầu thực tế, lập ra bảng giá trị cho hàm Bool.  Bước 2: Từ bảng giá trị, rút ra hàm Bool ở dạng chuẩn tắc tuyển.  Bước 3: Rút gọn hàm Bool (Tìm dạng công thức đa thức tối tiểu của hàm Bool).  Bước 4: Vẽ sơ đồ mạch ứng với công thức đa thức tối tiểu đã tìm được. Ví dụ: Thiết kế mạch 1 đèn 2 công tắc.  Bảng giá trị được xây dựng từ yêu cầu thực tế. CT1 CT2 Đèn 0 0 Tối(0) 1 0 Sáng(1) 0 1 Sáng(1)
1 1 Tối(0)  Từ bảng trên ta rút ra hàm Bool ở dạng d.n.f là: f(x,y)= x y+x y hàm Bool này đã ở dạng công thức đa thức tối tiểu. Có hàm Bool này ta sẽ vẽ được mạch tương ứng dễ dàng.
III. TÌM CÔNG THỨC ĐA THỨC TỐI TIỂU DÙNG BIỂU ĐỒ KARNAUGH 1. CÔNG THỨC ĐA THỨC TỐI TIỂU CỦA HÀM BOOL. Mỗi một mạch tương ứng với một hàm Bool. Vấn đề được đặt ra là tìm một công thức đơn giản nhất cho hàm Bool thì mạch tương ứng sẽ đơn giản nhất. Một trong những dạng công thức được quan tâm đối với hàm Bool là dạng tổng của các tích mà ta gọi là công thức đa thức.  Công thức đa thức là công thức có dạng tổng của các đơn thức.  Một đơn thức là tích của các biến (x) hoặc phủ định của biến ( x ). Ví dụ:  x y z là một đơn thức  x y z + xyzt + xy z + x y z t + y z t + x yzt + x y z là một đa thức Đối với các dạng công thức đa thức của một hàm Bool ta thường quan tâm đến các dạng công thức đa thức tối tiểu. Một cách trực quan ta gọi một công thức đa thức (D) của một hàm Bool f là tối tiểu khi không có công thức nào khác của f đơn giản hơn nó theo nghĩa sau đây: 1) Bất kỳ một sự biến đổi nào trên công thức (D) đều dẫn đến một công thức không phải là công thức đa thức, và 2) Nếu f có thể viết đưới một dạng công thức đa thức (D') khác thì số số hạng của (D') lớn hơn hoặc bằng số số hạng của (D) và ta có thể chọn ra các số hạng u' (tức là một đơn thức) trong công thức (D') tương ứng với các số hạng u trong công thức (D) sao cho số "thừa số" trong u' là lớn hơn hoặc bằng số thừa số trong u. Để tìm các công thức đa thức tối tiểu của hàm Bool với số biến nhỏ hơn hoặc bằng 6 ta có thể sử dụng các biểu đồ Karnaugh. (sẽ xét ở phần sau).
2. BIỂU ĐỒ KARNAUGH CỦA HÀM BOOL. Biểu đồ K cua hàm Bool bậc n là một hình chữ nhật chia làm 2n ô, mỗi ô ứng với một tích cơ bản bậc n, sao cho 2 ô có chung một đường biên (kể cả biên đối diện) phải ứng với hai tích cơ bản có (n-1) thừa số giống nhau, 1 thừa số còn lại là bù của nhau. Chẳng hạn với hàm Bool bậc 4 ta vẽ bảng như sau: x x x x y t y t y t y t z z z z Để xác định một ô ứng với tích cơ bản nào, ta chỉ việc chiếu ô đó xuống các cạnh để lấy các biến tương ứng. Tế bào: Để vẽ biểu đồ K của một đơn thức, ta chiếu các biến (hay bù biến) tham gia trong đơn thức, theo các cạnh tương ứng với chúng trên biểu đồ, tìm ra các ô là phần giao, điền 1 vào các ô này. Đây chính là biểu đồ K của nó. Mỗi biểu đồ K của một đơn thức gọi là một tế bào, và chúng luôn là một hình chữ nhật có dạng 2n ô, (tức 1ô, 2ô, 4ô, 8ô, 16ô). Chúng có thể tràn qua biên đối diện). Ví dụ: x x x x
y 1 1 t y 1 1 t y t y t z z z z Đây là tế bào: xy Ngược lại, khi cho một tế bào trên bảng K, để xác nó định ứng với đơn thức nào, ta chiếu nó xuống các cạnh. Nếu chiếu xuống cạnh nào chỉ thuộc biến (hay chỉ thuộc bù biến) thì đưa biến (hay bù biến) vào đơn thức. Nếu chiếu xuống cạnh nào vừa thuộc biến vừa thuộc bù biến thì bỏ qua. Ví dụ: Tế bào trên chiếu xuống cạnh x chỉ thuộc phần x, nên đưa x vào đơn thức. Chiếu xuống cạnh y chỉ thuộc phần y, nên đưa y vào đơn thức. Chiếu xuống cạnh z vừa thuộc z vừa thuộc z , nên bỏ qua. Chiếu xuống cạnh t vừa thuộc t vừa thuộc t , nên bỏ qua. Cách vẽ biểu đồ K của 1 hàm Bool: Viết hàm Bool ở dạng công thức đa thức, sau đó vẽ biểu đồ cho từng số hạng. Ví dụ: x x x x y 1 1 t y 1 1 t y 1 t y 1 t z z z z
Biểu đồ K của hàm Bool f(x,y,z,t)=y z + x y z Tế bào lớn: Tế bào lớn là tế bào không nằm lọt hẳn vào một tế bào nào khác. Ví dụ: Cho bảng Karnaugh của hàm Bool f(x,y,z,t) như sau 1 1 1 1 1 1 1 1 Bảng Karnaugh nầy có các tế bào lớn là: xy, yz, x z 11 1 1 1 1 1 1 1 1 1 1 3. TÌM CÔNG THỨC ĐA THỨC TỐI TIỂU BẰNG BIỂU ĐỒ K. Bước 1: Vẽ biểu đồ K cho hàm Bool f. Bước 2: Tìm và liệt kê ra các tế bào lớn của biểu đồ K. Bước 3: Tìm một tập hợp gồm một số tối tiểu các tế bào lớn của f sao cho các tế bào nầy phủ được f, tức là hợp của các tế bào nầy bằng biểu đồ f. Để tìm ra một phủ tối tiểu gồm các tế bào lớn như thế ta có thể tiến hành một quá trình chọn các tế bào theo trình tự như sau:
Bước 3.1: Các tế bào lớn buộc phải chọn là những tế bào lớn nào, mà có chứa ít nhất một ô 1, không giao nhau với tế bào lớn nào khác. Bước 3.2: Nếu các tế bào lớn đã chọn ở trên phủ kín f thì kết thúc và ta có duy nhất một công thức đa thức tối tiểu là tổng các tế bào lớn này. Ngược lại thì tiếp tục bước 3.3. Bước 3.3: Ta chọn thêm các tế bào lớn khác sao cho chúng phủ kín f. Việc chọn thêm phải đảm bảo là đơn giản nhất, tức số tế bào lớn chọn thêm là ít nhất và mỗi tế bào chọn thêm là lớn nhất. Tổng tất cả các tế bào lớn đã chọn sẽ là công thức đa thức tối tiểu của f. (chú í là trường hợp này có thể có nhiều cách chọn thêm đơn giản như nhau, khi đó f có nhiều công thức đa thức tối tiểu). Ví dụ: Tìm các CTĐTTT của hàm Bool sau f(x,y,z,t)=xyzt+xy t +xy z + x z Bảng Karnaugh của hàm Bool f(x,y,z,t) như sau 11 1 1 1 1 1 1 Bảng Karnaugh nầy có các tế bào lớn là: xy, yz, x z 11 1 1 1 1 1 1 1 1 1 1 Các tế bào lớn phải chọn là: : xy, x z
Các tế bào lớn này đã phủ kín biểu đồ K nên có duy nhất 1 CTĐTTT là: f(x,y,z,t)= xy + x z
BÀI TẬP Bài 1:Tìm các công thức đa thức tối tiểu của các hàm Bool f(x,yz,t) có biểu đồ Karnaugh dưới đây: 111 1 11 1 1 111 11 1 11 11 1 1111 11 1 11 1111 1111 1 1 1 11 11 11 11 1 11 1 1111 1111 11 Bài 2: Tìm các công thức đa thức tối tiểu của các hàm Bool sau, bằng phương pháp biểu đồ Karnaugh. F(x,y,z,t) = x y t + x y z t + xyzt + xy z t + xyz t + x z t + x y z G(x,y,z,t) = x y z + xyzt + xy z + x y z t + y z t + x yzt + x y z H(x,y,z,t) = x y t + xyzt + xy t + xy z t + z t + x y t Bài 3: Thiết kế mạch 1 đèn 3 công tắc.