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

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 + xyzt + 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 
 1 1 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 
 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 
 1 1 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: 
1 1 1 1 1 1 1 
 1 1 1 1 1 1 1 
 1 1 1 1 1 1 1 1 1 
 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 
1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 
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.