ĐẠI HỌC QUỐC GIA TP. HỒ CHÍ MINH
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
KHOA KHOA HỌC MÁY TÍNH
TIỂU LUẬN MÔN HỌC TOÁN HỌC CHO KHMT
ĐẠI SỐ BOOL VÀ ỨNG DỤNG
TRONG THIẾT KẾ MẠCH SỐ
Giảng viên hướng dẫn: PGS. TS. NGUYỄN PHI KHỨ
Học viên thực hiện: NGUYỄN NGỌC HOÀNG
Mã số học viên: CH1301026
TP. Hồ Chí Minh, tháng 12 năm 2013
LỜI MỞ ĐẦU
Hiện nay, máy tính là một công cụ hữu hiệu phục vụ cho các hoạt động lao
động sáng tạo cũng như giải trí. Máy tính với bộ phận chính là bộ vi xử lý được cấu
thành từ hành triệu mạch số khác nhau. Để có thể chế tạo được các mạch số hoạt
động hiệu quả thì cần một cơ sở nền tảng có hệ thống để chứng minh tính hiệu quả
của mạch số từ đó có thể sản xuất ra các bộ vi xử lý hiệu quả hơn và tăng năng lực
tính toán cho máy tính.
Sau một quá dài nghiên cứu dựa trên logic mệnh đề, các nhà nhiên cứu đã phát
triển nên đại số Bool. Đại số Bool với cơ sở lý luận toán học vững vàng đã làm nền
tảng để thiết kế cũng như tối ưu các mạch số.
LỜI CẢM ƠN
Toán học là nền tảng của ngành Khoa Học Máy Tính. Trong đó phần logic
chính là kim chỉ nam cho việc suy diễn, định hướng suy nghĩ cho mọi nghiên cứu
sau này. Với các chuyên đề được giảng dạy trong môn Toán học cho Khoa Học Máy
Tính như cơ sở toán học, phương pháp phân tích và thiết kế thuật toán, logic mệnh
đề - logic vị từ, PGS.TS Nguyễn Phi Khứ đã cung cấp hành trang vững chắc cũng
như kiến thức nền tảng để cho tôi và các bạn trong lớp CH08 có khả năng học tốt
những chuyên đề tiếp theo; và đó cũng là hành trang trong quá trình nghiên cứu sau
này.
Với những định hướng và gợi mở về những hướng đi mới, hỗ trợ tài liệu và ý
tưởng, tôi xin gửi lời cảm ơn chân thành đến thầy Nguyễn Phi Khứ.

• Nhược điểm của mạch số
• Trong một số trường hợp. mạch số có thể tiêu tốn nhiều năng lượng hơn khi
thực hiện cùng một công việc so với mạch tương tự.
• Mạch số thường phù hợp với việc sản suất với số lượng lớn nên sản phẩm sẽ
trở nên đắt đỏ nếu sản xuất với số lượng nhỏ.
• Hầu hết các mạch số khi sử dụng đều dùng các tín hiệu được chuyển từ tín
hiệu tương tự (do các số liệu thực tế đều có giá trị tương tự) nên khi sử dụng
mạch số sẽ có sai số lượng từ hóa.
1.2. TẦM QUAN TRỌNG CỦA ĐẠI SỐ BOOL TRONG THIẾT KẾ MẠCH
SỐ
Như chúng ta đã biết, logic mệnh đề là một cơ sở toán học giải quyết với các
biến mệnh đề chấp nhận giá trị 0 hoặc 1. Bên cạnh đó còn có các toán tử logic như
and, or và not. Cơ sở toán học này là một nền tảng để phát triển các mạch số do
mạch số cũng xử lý với các tín hiệu với giá trị 0 hoặc 1 đồng thời đảm bảo tính
đúng đắn của mạch số.
Đại số Bool là đại số trên các đại lượng 0 hoặc 1; dùng để mô tả các các
phương trình logic, tối giản các thiết kế nên được dùng nhiều trong thiết kế mạch.
GVHD: PGS.TS. Nguyễn Phi Khứ HVTH: Nguyễn Ngọc Hoàng
- 7 -
Chương 2: BIỂU DIỄN PHƯƠNG TRÌNH LOGIC - ĐẠI SỐ BOOL
2.1. GIỚI THIỆU
Logic mệnh đề thao tác trên các hằng mệnh đề, biến mệnh đề và các phép toán
mệnh đề trong miền giá trị {0, 1}. Trong chương này, chúng ta sẽ hình thức hóa lại
các khái niệm logic đồng thời nêu lên các định nghĩa, kỹ thuật mới để có thể biểu
diễn được phương trình logic và ứng dụng trong thiết kế mạch số.
Một mạch chuyển đơn giản chứa các phần tử chủ động như các diod hay các
transistor có thể minh họa cho logic nhị phân với thuộc tính ON (công tắc đóng)
hay OFF (công tắc mở). Các hàm chuyển có thể được biểu diễn bằng các phương
trình Bool. Các phương trình Bool phức tạp có thể được tối giản nhờ vào một dạng
số học mới thường được gọi là đại số Bool. Đại số Bool được phát minh bởi nhà

nếu tồn tại phần tử E ∈ S sao cho:
E * A = A * E = A.
Ví dụ trong tập số nguyên I ta có phép + có phần tử xác định là 0 và phép * có
phần tử xác định là 1.
2.2.5. Phần tử bù
Nếu tập S có phần tử xác định là E với phép toán hai ngôi * thì ta định nghĩa
phần tử bù B của phép toán hai ngôi * ứng với mỗi phần tử A ∈ S nếu A * B = E.
2.2.6. Luật phân phối
Nếu * và (.) là hai phép toán hai ngôi trên tập S thì * được gọi là phân phối với
phép (.) nếu thỏa:
A * (B . C) = (A * B) . (A * C)
2.3. ĐỊNH NGHĨA ĐẠI SỐ BOOL
Năm 1854, George Boole giới thiệu một cách tiếp cận logic có hệ thống và
phát triển một hệ thống đại số để giải quyết các hàm logic đó chính là đại số Bool.
Năm 1938, C.E. Shannon phát triển đại số Bool hai giá trị thường được gọi là đại số
chuyển (Switching Algebra) và chứng minh rằng các mạch điện hai trạng thái hay
hai giá trị có thể được biểu diễn bằng đại số này. Các định lý được đưa ra bởi E.V.
Huntington vào năm 1904 được dùng như là định nghĩa chính thức cho đại số Bool.
Tuy nhiên, các định lý này không phải là duy nhất để định nghĩa đại số Bool. Các
GVHD: PGS.TS. Nguyễn Phi Khứ HVTH: Nguyễn Ngọc Hoàng
- 9 -
định lý Huntington dưới đây thỏa điều kiện định nghĩa đại số Bool trên tập S với hai
phép toán nhị phân (+) và (.).
1. Phép (+) thỏa mãn tính đóng.
Phép (.) thỏa mãn tính đóng.
2. Phần tử định danh ứng với phép + là 0. Cụ thể:
A + 0 = 0 + A = A
Phần tử định danh ứng với phép . là 1. Cụ thể:
A . 1 = 1 . A = A
3. Tính giao hoán của phép + : A + B = B + A.

luận này, tôi chỉ xét đến đại số Bool hai giá trị do nó được ứng dụng nhiều trong lý
thuyết tập hợp và logic mệnh đề. Ngoài ra đại số Bool hai giá trị cũng là nền tảng
quan trọng trong thiết kế mạch số.
2.4. ĐẠI SỐ BOOL HAI GIÁ TRỊ
Đại số Bool hai giá trị được định nghĩa trên một tập chỉ có hai phần tử S = {0,
1} với các quy tắc cho phép toán (+), phép toán (.) và phép bù được trình bày như
bên dưới.
Hình 2.1: Quy tắc phép (+) trong đại số Bool hai giá trị.
Hình 2.2: Quy tắc phép (.) trong đại số Bool hai giá trị.
GVHD: PGS.TS. Nguyễn Phi Khứ HVTH: Nguyễn Ngọc Hoàng
- 11 -
Hình 2.3: Quy tắc phép bù trong đại số Bool hai giá trị.
Các quy tắc này giống với phép OR, AND và NOT trong logic mệnh đề. Và ta
cũng có thể kiểm tra dễ dàng các quy tắc này thỏa mãn sáu định lý Hutington đã nêu
ở trên.
Để cho đơn giản từ đây trở đi ta quy ước rằng đại số Bool chính là đại số Bool
hai giá trị được áp dụng với tập S = {0, 1} và các quy tắc cho phép (+) và phép (.)
như trên.
2.5. CÁC TÍNH CHẤT CỦA ĐẠI SỐ BOOL
Dưới đây là các quan hệ cơ bản của đại số Bool.
Ứng với mỗi tính chất đều áp dụng cho 2 phép toán AND và OR. Cột bên trái
nhấn mạnh cho phép toán AND và cột bên phải nhấn mạnh cho phép toán OR và
được gọi là nguyên lý đối tính. Đây là một thuộc tính của đại số Bool và có ứng
dụng quan trọng trong việc nghiên cứu logic và hiện thực các hàm logic với các
thiết bị vật lý.
Trong các tính chất trên thì tính chất cuối cùng được gọi là luật De Morgan.
Luật này quan trọng do nó cho phép chuyển đổi các toán tử Bool từ AND sang OR
và ngược lại.
GVHD: PGS.TS. Nguyễn Phi Khứ HVTH: Nguyễn Ngọc Hoàng
- 12 -

• Dạng tổng: Một hàm OR được gọi là dạng tổng – hàm phụ thuộc vào tổng
logic của các biến khác nhau. Các biến trong dạng tổng cũng có thể ở dạng
thường hay dạng bù. Ví dụ A + B + C’ là một dạng tổng.
• Dạng tổng các tích – SOP: Tổng logic của hai hay nhiều dạng tích logic được
gọi là biểu thức dạng tổng các tích. Ví dụ Y = AB + BC + A’C được gọi là
biểu thức dạng tổng các tích.
• Dạng tích các tổng – POS: Tương tự như SOP, một tích logic của hai hay
nhiều dạng tổng logic. Ví dụ Y = (A + B + C)(A + B’ + C)(A + B + C’) là
một dạng tích các tổng.
• Dạng chuẩn: Dạng chuẩn của một hàm Bool là khi nó được biểu diễn ở dạng
tổng các tích hay tích các tổng.
2.7.1. Minterm
Một dạng tích chứa tất cả n biến của hàm bool bất kể ở dạng nào thì được gọi
là một minterm. Mỗi minterm được tạo ra bằng phép toán AND các biến ở dạng
thường hay dạng bù. Với một hàm hai biến, có tất cả là 4 sự kết hợp tạo ra minterm:
A’B’, A’B, AB’, AB. Các dạng tích này được gọi là tích cơ bản, tích chuẩn hay
minterm. Trong minterm, một biến sẽ có giá trị 1 nếu ở dạng thường và có giá trị 0
nếu ở dạng bù. Hình 2.4 là các minterm của một hàm 3 biến.
Như ta có thể thấy, một hàm có n biến thì sẽ có 2
n
minterm. Thuộc tính chính
của một minterm là nó chỉ có giá trị 1 với duy nhất một tổ hợp của n biến, và có giá
trị 0 với 2
n
– 1 các tổ hợp còn lại. Ví dụ với một hàm ba biến như trên nếu A = 0, B
= 1, C = 1 hay tổ hợp đầu vào là 011 thì chỉ có minterm A’BC có giá trị là 1, tất cả
các minterm còn lại có giá trị là 0.
GVHD: PGS.TS. Nguyễn Phi Khứ HVTH: Nguyễn Ngọc Hoàng
- 14 -
Hình 2.4: Các minterm của một hàm 3 biến.

là tổng cơ bản, tổng chuẩn hay maxterm. Trong maxterm, một biến sẽ có giá trị 0
nếu ở dạng thường và có giá trị 1 nếu ở dạng bù. Hình 2.5 là các maxterm của một
hàm 3 biến.
Hình 2.4: Các maxterm của một hàm 3 biến.
Như ta có thể thấy, một hàm có n biến thì sẽ có 2
n
maxterm. Thuộc tính chính
của một maxterm là nó chỉ có giá trị 0 với duy nhất một tổ hợp của n biến, và có giá
trị 1 với 2
n
– 1 các tổ hợp còn lại. Ví dụ với một hàm ba biến như trên nếu A = 1, B
= 1, C = 0 hay tổ hợp đầu vào là 110 thì chỉ có maxterm A’ + B’ + C có giá trị là 0,
tất cả các maxterm còn lại có giá trị là 1.
GVHD: PGS.TS. Nguyễn Phi Khứ HVTH: Nguyễn Ngọc Hoàng
- 16 -
• Dạng chính tắc tích các tổng: Khi một hàm Bool được biểu diễn từ tích logic
của tất cả các maxterm có trong bảng chân trị có giá trị là 0 thì được gọi là
dạng chính tắc tích các tổng. Tương tự ta cũng có thể biểu diễn ở dạng rút
gọn bằng cách liệt kê tất cả các mã dạng thập phân các maxterm trong hàm
có giá trị là 0. Ví dụ một hàm ba biến F có các minterm A + B + C, A + B’ +
C và A’ + B + C’ có giá trị là 0 có thể được biểu diễn như sau:
F(A,B,C) = Π(0,2,5)
= M
0
M
2
M
5
= (A + B + C)(A + B’ + C)( A’ + B + C’)
Trong đó Π(0,2,5) biểu diễn dạng tích các các maxterm tương ứng với mã thập

Áp dụng tương tự cho bảng chân trị như hình 2.5: ta có các giá trị Y bằng 0
tương ứng với đầu vào 000, 001, 011 và 111 và các dạng tổng tương ứng là A + B +
C, A + B + C’, A + B’ + C’ và A’ + B’ + C’. Từ đây ta có hàm Bool tương ứng với
bảng chân trị hình 2.5 biểu diễn ở dạng tích các tổng là:
Y = (A + B + C)( A + B + C’)( A + B’ + C’)( A’ + B’ + C’)
Tương tự như trên, thủ tục để trích xuất hàm Bool ở dạng tích các tổng từ
bảng chân trị cho trước như sau:
1. Tạo một dạng tổng cho mỗi tổ hợp biến đầu vào trong bảng chân trị có giá
trị hàm là 0.
GVHD: PGS.TS. Nguyễn Phi Khứ HVTH: Nguyễn Ngọc Hoàng
- 18 -
2. Thực hiện phép AND các dạng tổng ở bước trên để nhận được dạng tích
các tổng cho hàm Bool.
2.7.5. Chuyển đổi giữa các dạng chính tắc
Từ ví dụ trên ta có thể thấy rằng: phủ định của hàm biểu diễn ở dạng tổng các
tích bằng với tổng các tích còn thiếu trong hàm gốc. Nguyên nhân của việc này là
do hàm gốc được biểu diễn bởi các minterm làm cho giá trị hàm bằng 1 trong khi đó
phủ định của các minterm có giá trị 1 thì có giá trị là 0. Dựa theo bảng chân trị hình
2.5 ta có :
F(A,B,C) = Σ(2,4,5,6)
= m
2
+ m
4
+ m
5
+ m
6

= A′BC′ + AB′C′ + AB′C + ABC′


= Π(0,1,3,7)
= (A + B + C)( A + B + C’)( A + B’ + C’)( A’ + B’ + C’)
Từ việc biến đổi trên ta có thể rút ra được:
m′
j
= M
j

có nghĩa là dạng maxterm với chỉ số j là dạng bù của minterm có chỉ số tương
ứng và ngược lại.
2.8. TỐI GIẢN HÀM BOOL - BÌA KARNAUGH
Trong thiết kế mạch số, độ phức tạp của các cổng logic số để hiện thực hàm
Bool phụ thuộc trực tiếp vào độ phức tạp của biểu thức đại số. Bên cạnh đó, khi số
lượng biến đầu vào tăng lên thì cũng làm tăng độ phức tạp. Mặc dù biểu diễn bảng
chân trị của mỗi hàm Bool là duy nhất nhưng biểu thức đại số của nó có thể ở nhiều
GVHD: PGS.TS. Nguyễn Phi Khứ HVTH: Nguyễn Ngọc Hoàng
- 19 -
dạng khác nhau. Các hàm Bool có thể được tối giản bằng các phương pháp đại số
tuy nhiên quá trình tối giản không là duy nhất và kết quả nhận được có thể không là
tốt nhất. Phương pháp bản đồ lần đầu tiên được giới thiệu bởi Veith và sau đó được
cải tiến mạnh mẽ bởi Karnaugh cung cấp một thủ tục đơn giản và hiệu quả cho việc
tối giản hàm Bool. Phương pháp này được gọi là biểu đồ Veith hay bản đồ
Karnaugh – bìa Karnaugh.
Bản đồ Karnaugh cung cấp một phương pháp có hệ thống cho việc thao táo và
tối giản các biểu thức Bool. Bản đồ là một sơ đồ chứa các ô vuông. Với một biểu
thức n biến thì bìa Karnaugh có 2
n
ô vuông, mỗi ô thể hiện cho 1 minterm. Hình 2.6
minh họa một bảng chân trị và bìa Karnaugh tương ứng của nó.

= B′
Vậy bìa Karnaugh có thể hiện được việc tối giản này? Chìa khóa vấn đề nằm ở
việc B′ được AND với cả A và A′. Ta thấy trong bài Karnaugh, giá trị 1 của hàm
xuất hiện cả trong đầu và A và A′ như hình 2.12. Thực hiện khoanh tròn các giá trị
hàm là 1 ở cạnh nhau để làm dấu xác định rằng biến A sẽ không xuất hiện trong
biểu thức tối giản do A hay A’ đều thỏa mãn biểu thức. Từ hình 2.12 ta thấy giá trị
hàm X bằng 1 khi B = 0 do đó X = B′.
GVHD: PGS.TS. Nguyễn Phi Khứ HVTH: Nguyễn Ngọc Hoàng
- 22 -
Hình 2.12: Thao tác thực hiện trong quá trình tối giản hàm Bool.
Việc khoanh tròn các giá trị hàm bằng 1 ở gần nhau là một thao tác cơ bản
trong quá trình tối giản hàm Bool. Với một bìa Karnaugh cho 2 biến ta có tổng cộng
5 cách để khoanh tròn như hình 2.13.
Hình 2.13: Tối giản bìa Karnaugh 2 biến.
Quy tắc để khoanh tròn trong quá trình tối giản dùng bìa Karnaugh là tùy theo
vị trí của các ô có giá trị là 1 mà chúng ta khoanh thành nhóm 1, 2, 4, 8 … Phương
pháp dùng bìa Karnaugh yêu cầu mỗi ô số 1 phải được khoanh tròn ít nhất 1 lần.
Với trường hợp bìa Karnaugh cho hàm Bool 3 biến và 4 biến ta cũng có các
quy tắc tương tự để tối giản như hình 2.14 và 2.15. Hình 2.16 minh họa cho quá
trình tối giản hai hàm Bool 4 biến dùng bìa Karnaugh.
GVHD: PGS.TS. Nguyễn Phi Khứ HVTH: Nguyễn Ngọc Hoàng
- 23 -
Hình 2.14: Các cách khoanh tròn cơ bản cho bìa Karnaugh 3 biến.
Hình 2.15: Các cách khoanh tròn cơ bản cho bìa Karnaugh 4 biến.
Hình 2.16: Minh họa cho việc tối giản hàm Bool 4 biến bằng bìa Karnaugh.
GVHD: PGS.TS. Nguyễn Phi Khứ HVTH: Nguyễn Ngọc Hoàng
- 24 -
Chương 3: ỨNG DỤNG TRONG THIẾT KẾ MẠCH SỐ
3.1. CÁC CỔNG LOGIC SỐ
Trong thiết kế mạch số, các phép toán logic dùng trong đại số Bool sẽ được