Bài giảng Kỹ thuật điện tử số: Đại số Boole-Đại số logic - Nguyễn Quốc Cường

1ðại số Boole
ðại số logic
Nguyễn Quốc Cường – 3I
2
Nội dung
• Giới thiệu
• Các tiên ñề trong ñại số logic
• Các ñịnh lý
• Nguyên lý của tính ñối ngẫu (duality)
• Cách biểu diễn hàm logic
3Tài liệu tham khảo
• Digital Design: Principles & Practices – John F 
Wakerly – Printice Hall
4
Giới thiệu
• 1854 nhà toán học Anh, Gorge Boole (1815-
1864) phát minh ra hệ thống ñại số chỉ có hai
giá trị
• Năm 1938, tại Bell Lab, Claude E. Shannon ñã
chỉ ra cách áp dụng ñại số Boole vào phân tích
và mô tả các mạch sử dụng rơle (còn gọi là
switching algebra), và cũng ñược áp dụng cho
các phân tích mạch số hiện nay.
5Tiên ñề
• Tiên ñề 1:
(A1) X = 0 if X ≠ 1
(A1’) X = 1 if X ≠ 0
• Tiên ñề 2: (ñịnh nghĩa toán tử ñảo)
(A2): If X = 0 then X’ = 1
(A2’): If X = 1 then X’ = 0
Toán tử “ ‘ “ là toán tử ñảo hay bù
(một số ký hiệu khác của toán tử ñảo: )
Tuy nhiên việc sử dụng ‘ thường ñược sử dụng trong
các ngôn ngữ lập trình HDLs)
~ ,X X
6
• Tiên ñề 3 , 4 và 5 :ðịnh nghĩa các toán VÀ và
HOẶC logic:
Toán tử AND sử dụng ký hiệu ·
Toán tử OR sử dụng ký hiệu +
Tất cả các hệ thống logic ñều có thể mô tả và phân tích dựa trên 5 tiên ñề trên
7Ký hiệu các phần tử logic trên sơ ñồ
8
ðịnh lý cho một biến
Việc chứng minh các ñịnh lý này có thể sử dụng phương pháp quy nạp
hoàn toàn (vì số giá trị của các biến chỉ có 0 và1 nên rất dễ áp dụng
phương pháp quy nạp)
9cho 2 và ba biến
Chú ý: ñể thuận tiện thường viết X · Y thay cho ( X · Y )
10
Cho n biến
ðể chứng minh sử dụng phương pháp quy nạp hữu hạn:
• chứng minh ñúng với n = 2
• giả thiết ñúng với n = i, chúng minh ñúng với n = i+1
11
Nguyên lý ñối ngẫu
• Các ñịnh lý hay ñồng nhất thức trong ñại số
logic sẽ luôn ñúng nếu thay 0 và 1 tráo ñổi cho
nhau và ñồng thời · và + cũng ñược tráo ñổi cho
nhau.
• Hàm ñối ngẫu:
– Cho hàm logic F(X1,X2,,Xn, + , · , ’)
– Hàm ñối ngẫu của F ñược ñịnh nghĩa là hàm có cùng
dạng biểu thức với các toán tử · và + ñược ñổi chỗ
cho nhau
FD(X1,X2,,Xn, + , · , ’) = F(X1,X2,,Xn, · , + , ’)
+ và · ñổi chỗ
12
Nguyên lý ñối ngẫu và ñịnh lý DeMorgan
[F(X1,X2,,Xn)]’ = FD(X1’, X2’,,Xn’)
F(X1,X2,,Xn) = [FD(X1’, X2’,,Xn’)]’
(ñịnh lý DeMorgan)
13
Biểu diễn hàm logic thông qua bảng
Bảng sự thực (không bao
gồm hàng ROW), tuy nhiên
thường ñược sử dụng ñể
chỉ giá trị tổ hợp của các
biến
14
15
Một số khái niệm
• Hệ số chữ (literal): là một biến ñơn , hoặc phần bù của
nó. Ví dụ: X, Y, X’,...
• Số hạng tích (product term): là một literal hoặc tích logic 
của nhiều literal
Ví dụ: Z’, X ¢ Y, X’ ¢ Y ¢ Z’
• Biểu thức tổng của các tích: là một tổng logic của các số
hạng tích
• Số hạng tổng (sum term): là một literal hoặc tổng logic 
của nhiều literal
Ví dụ: X’, X+Y+Z’
• Biểu thức tích của các tổng: là tích logic của các số hạng
tổng
16
• Một số hạng chuẩn (normal term): là một số hạng tích
hoặc tổng mà trong ñó không có biến nào xuất hiện hơn
một lần
• Ví dụ các số hạng không chu
n:
• X + Y + X’, Y ¢ X ¢ X’ ¢ Z
• Ví dụ các số hạng chuẩn:
• X + Y, X ¢ Y ¢ Z
• minterm n biến: là một số hạng tích chuẩn của n literal
• maxterm n biến: là số hạng tổng chuẩn của n literal
17
18
• Minterm: có thể ñược ñịnh nghĩa là số hạng tích
ứng với một hàng của bảng chân lý sao cho tích
ñó bằng 1
• Maxterm: có thể ñược ñịnh nghĩa là số hạng
tổng ứng với một hàng của bảng chân lý sao
cho tổng ñó bằng 0 
19
20
Biểu diễn hàm qua minterm và maxterm
• Hàm logic có thể biểu diễn dưới dạng:
– canonical sum: tổng của các minterm ứng với các
hàng của bảng chân lý mà tại ñó giá trị hàm bằng 1
– canonical product: tích của các maxterm ứng với các
hàng của bảng chân lý mà tại ñó giá trị hàm bằng 0
21
22
• ðể ñơn giản trong ký hiệu, người ta thường sử
dụng dạng viết rút gọn sau:
X, Y , Z là các biến, ñi kèm với chỉ số các hàng tương ứng của các
minterm hoặc maxterm
23
Tối thiểu hóa hàm logic
• Hàm logic có thể biểu diễn thông qua:
– canonical sum
– canonical product
Tuy nhiên ñó là các dạng chưa ñược tối thiểu.
• ðể giảm số input hay số gate sử dụng trong
mạch cần phải tối thiểu hóa mạch.
24
Bìa Karnaugh
• Là cách biểu diễn ñồ họa của bảng chân lý
25
• K-map : n biến sẽ có 2n ô
• Mỗi một ô trong K-map ứng với một hàng trong
bảng chân lý.
• Quy ước các ô kề nhau thì tổ hợp các biến chỉ
ñược khác nhau một giá trị
• K-map chỉ thuận tiện sử dụng cho hàm logic có
6 biến trở xuống
• Từ K-map có thể viết ñược các canonical sum 
hoặc canonical product tương tự như bảng chân
lý
26
Tối thiểu hóa dạng tổng các tích
‘
‘
27
• Quy tắc nhóm các ô của K-map:
– Nhóm 2k các ô có giá trị 1 kề nhau sao cho k là max ( 
1 ≤ k ≤ n, với n là số biến)
– Có chính xác (n-k) biến có giá trị không ñổi trong số
các ô ñược nhóm
• Dạng tích:
– nếu biến có giá trị là 1 trong 2k ô ñược nhóm thì
product term sẽ chứa biến ñó
– nếu biến có giá trị 0 trong 2k ô ñược nhóm thì product 
term sẽ chứa bù của biến ñó
– nếu biến có cả giá trị 1 và 0 trong 2k ô ñược nhóm thì
nó sẽ không xuất hiện trong product term
28
các nhóm không ñúng
29
ví dụ
30
• Dạng tối giản sử dụng K-map không phải là duy
nhất
31
Tối thiểu hóa dạng tích các tổng
• Nhóm 2k các ô có giá trị 0 kề nhau sao cho k là
max:
– nếu biến có giá trị là 1 trong 2k ô ñược nhóm thì sum-
term sẽ chứa bù của biến ñó
– nếu biến có giá trị 0 trong 2k ô ñược nhóm thì sum-
term sẽ chứa biến ñó
– nếu biến có cả giá trị 1 và 0 trong 2k ô ñược nhóm thì
nó sẽ không xuất hiện trong sum term
32
Các tổ hợp ñầu vào “Don’t-Care”
• Trong trường hợp ứng với một số tổ hợp giá trị
các inputs giá trị hàm logic có thể tùy ý (bằng 0 
hoặc bằng 1) 
 các tổ hợp “don’t-care”
• Sử dụng các tổ hợp “don’t-care” trong tối giản
hàm:
– Cho phép tổ hợp don’t-care tham gia vào các ô sao
cho số ô 2k là lớn nhất
– Không nhóm các ô chỉ toàn don’t-care
33
34
Các phương pháp tối giản sử dụng chương
trình
• Khi số biến lớn, sử dụng thuật toán:
– Queen-McCluskey (tham khảo)
– Espresso II, Espresso-MV (tham khảo)