Toán rời rạc - Chương 4: Đại số boole

 CHƯƠNG 4: ĐẠI SỐ BOOLE 
 TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN 
NỘI DUNG CHÍNH 
Đại số logic B 
Đại số Boole 
Hàm Boole 
Công thức đa thức tối thiểu 
Biểu đồ Karnaugh của hàm Boole 
Phương pháp Quine – McCluskey 
Các cổng logic 
 3/1/2016 Đại Số Boole Trang 2 
Đại số logic B 
 Trên tập logic B = 0, 1 xét các phép 
toán logic 
  (tích Boole) x  y 
  (tổng Boole) x  y 
  (phép bù) x 
 trong đó x, y B gọi là các biến logic 
hoặc biến Boole. 
3/1/2016 Đại Số Boole Trang 3 
3/1/2016 Đại Số Boole Trang 4 
 Các hằng đẳng thức logic 
 1) Giao hoán 6) Luỹ đẳng 
 2) Kết hợp 7) Phần tử trung hoà 
 3) Phân phối 8) Phần tử bù 
 4) Luật bù kép 9) Luật thống trị 
 5) De Morgan 10) Luật hấp thu 
3/1/2016 Đại Số Boole Trang 5 
Một số phép toán 2 – ngôi 
khác trên đại số logic B 
 1) Tổng modulo 2, x + y 
 2) Kéo theo x y 
 3) Tương đương x  y 
 4) Vebb (NOR) x  y 
 5) Sheffer (NAND) x  y 
3/1/2016 Đại Số Boole Trang 6 
3/1/2016 Đại Số Boole Trang 7 
Đại số Boole 
 Định nghĩa: 
 Cho tập A có ít nhất 2 phần tử, trong đó có 2 
phần tử đặc biệt được ký hiệu là 0 và 1. 
Trên A xét các phép toán 2 – ngôi  và , và 
phép toán 1 – ngôi / 
 Ký hiệu là (A, , , /, 0, 1) 
3/1/2016 Đại Số Boole Trang 8 
 Giao hoán 
 Kết hợp 
 Phân phối 
 Phần tử trung hoà 
 Phần tử bù 
Tập A cùng với các phép toán này được gọi là một 
đại số Boole nếu các phép toán này có tính chất: 
∀ ,  ∈ : 
  ∨  =  ∨ . 
 ∧  =  ∧ . 
∀ , ,  ∈ : 
  ∨  ∨  =  ∨ ( ∨ ). 
( ∧ ) ∧  =  ∧ ( ∧ ). 
1 
∀ , ,  ∈ : 
 ∨ ( ∧ ) = ( ∨ ) ∧ ( ∨ ). 
 ∧ ( ∨ ) = ( ∧ ) ∨ ( ∧ ). 
Trong A tồn tại phần tử 0 và 1: ∀  ∈  
 ∧ 1 = 1 ∧  = . 
 ∨ 0 = 0 ∨  = . 
∀  ∈  , tồn tại duy nhất phần tử bù  sao cho: 
 ∧  = 0. 
 ∨  = 1. 
2 
3 
4 
5 
3/1/2016 Đại Số Boole Trang 9 
Ví dụ: 
 Cho U là tập bất kỳ, trên A = P(U) 
(tập các tập con của U) xét phép  
là phép , phép  là phép , phép 
/ là phép lấy phần bù, phần tử 0 là 
tập rỗng  còn phần tử 1 là tập U. 
 Khi đó P(U) là một đại số Boole. 
3/1/2016 Đại Số Boole Trang 10 
Ví dụ: 
 Tích Descartes A B của các đại số Boole A, 
B là một đại số Boole, trong đó: 
 (a1,b1)  (a2,b2) = (a1  b1, a2  b2), 
 (a1,b1)  (a2,b2) = (a1  b1, a2  b2), 
 (a, b)/ = (a/, b/), 
 (0,0) là phần tử 0 trong A B, 
 (1,1) là phần tử 1 trong A B. 
 Đặc biệt, Bn là một đại số Boole. 
3/1/2016 Đại Số Boole Trang 11 
 Nếu không nói gì thêm, tất cả các tập được nói 
đến trong chương này đều là tập hữu hạn. 
 Nhắc lại: Một tập hữu hạn sắp thứ tự luôn luôn 
có phần tử tối tiểu/tối đại. 
 Trên một đại số Boole tổng quát chúng ta cũng có 
các hằng đẳng thức giống như các hằng đẳng 
thức đã xét trên đại số logic B. 
3/1/2016 Đại Số Boole Trang 12 
3/1/2016 Đại Số Boole Trang 13 
Hàm Boole 
 Định nghĩa: 
 Ánh xạ f: Bn B gọi là một hàm Boole n 
biến. 
 Hàm đồng nhất bằng 1 ký hiệu là 1, hàm 
đồng nhất bằng 0 ký hiệu là 0. Tập tất 
cả các hàm Boole n – biến ký hiệu là Fn. 
3/1/2016 Đại Số Boole Trang 14 
 Cho f và g là hai hàm Boole n biến. Chúng ta 
 có các định nghĩa như sau: 
 1) (f  g)(x1, , xn) = f(x1, , xn)  g(x1, , xn) 
 2) (f  g)(x1, , xn) = f(x1, , xn)  g(x1, , xn) 
 3) f/ (x1, , xn) = (f(x1, , xn))
/ 
 với mọi x1, , xn. 
3/1/2016 Đại Số Boole Trang 15 
 Ta có Fn cùng các phép toán này 
lập thành một đại số Boole. 
 Ngoài ra còn có: 
 f g  f  g = g f  g = f 
 trong đó f g nếu 
 f(x1, , xn) g(x1, , xn). 
3/1/2016 Đại Số Boole Trang 16 
Cách thông thường nhất để xác định một hàm 
Boole là dùng bảng giá trị. 
Hàm Boole 2 biến 
3/1/2016 Đại Số Boole Trang 17 
Ví dụ: 
1. Mỗi phiếu chỉ lấy một trong hai giá trị: 
 1 (tán thành) hoặc 0 (bác bỏ). 
2. Kết quả f 
 là 1 (thông qua quyết định) nếu được đa số 
phiếu tán thành. 
 là 0 (không thông qua quyết định) nếu đa 
số phiếu bác bỏ. 
Xét kết quả f trong việc thông qua một 
quyết định dựa vào 3 phiếu bầu x, y, z 
3/1/2016 Đại Số Boole Trang 18 
Khi đó f là hàm Bool theo 3 biến x,y,x có bảng 
chân trị như sau: 
x y z f 
0 0 0 0 
0 0 1 0 
0 1 0 0 
0 1 1 1 
1 0 0 0 
1 0 1 1 
1 1 0 1 
1 1 1 1 
3/1/2016 Đại Số Boole Trang 19 
 Chúng ta cũng có thể xác định hàm Boole 
bằng một biểu thức Boole. Đó là một biểu 
thức gồm các biến Boole và các phép toán  
(hội),  (tuyển), / (phép lấy bù). 
 Mỗi biểu thức Boole cũng được xem như một 
hàm Boole. 
3/1/2016 Đại Số Boole Trang 20 
Tích sơ cấp 
 Biến x gọi là biến Boole nếu x chỉ 
nhận một trong hai giá trị 0/1. 
 Giả sử x là một biến Boole. Khi đó ký 
hiệu x1 = x, x0 = x. 
3/1/2016 Đại Số Boole Trang 21 
Các phép toán trên hàm Boole: 
• Phép cộng Boole ∨: 
Với f, g ∈Fn, ta định nghĩa tổng Boole của f và g: 
 ∨  =  +  −  
∀  = , ,   ∈ , 
 (f ∨ g)(x) = f(x) + g(x) – f(x)g(x) 
3/1/2016 Đại Số Boole Trang 22 
• Phép nhân Boole ∧: 
Với f,g ∈Fn, ta định nghĩa tích Boole của f và g: 
 ∧  =  
∀  = , ,   ∈ , 
 (f ∧ g)(x) = f(x)g(x) 
• Phép lấy phần bù: 
 =  −  
3/1/2016 Đại Số Boole Trang 23 
Biểu thức Boole: 
Là một biểu thức được tạo bởi các biến và các 
phép toán Boole. 
 VD: E= (x ∧ y ∧ z) ∨ (z ∧ ) 
Để dễ đọc hơn, người ta có thể viết: 
 E = xyz + z 
3/1/2016 Đại Số Boole Trang 24 
Dạng nối rời chính tắc của hàm Boole: 
Xét tập hợp các hàm Boole n biến Fn theo n biến x1, x2, ,xn. 
• Mỗi hàm Boole xi hay ̅i được gọi là một từ đơn. 
• Đơn thức là tích khác không của một số hữu hạn từ đơn. 
• Từ tối tiểu (đơn thức tối tiểu) là tích khác không của đúng 
n từ đơn. 
• Công thức đa thức là công thức biểu diễn hàm Boole 
thành tổng của các đơn thức. 
• Dạng nối rời chính tắc là công thức biểu diễn hàm Boole 
thành tổng của các từ tối tiểu. 
3/1/2016 Đại Số Boole Trang 25 
VD: Xét hàm boole, với 3 biến: x, y, z 
 x, y, z, ̅, , ̅ là các từ đơn. 
 xy, yz là đơn thức 
 xy̅ là từ tối tiểu 
 E= xy + yz là một công thức đa thức 
Và F=xyz + ̅̅ là một dạng nối rời chính tắc 
3/1/2016 Đại Số Boole Trang 26 
 Cho  ∈ F,  có thể viết dưới dạng sau: 
(*) 
Với  là các đơn thức tối tiểu bậc  ( = 1,  , ). 
(*) được gọi là dạng nối rời chính tắc của . 
 Ví dụ: Trong F có dạng biểu diễn sau đây: 
  , , ,  = ̅ ∨ ̅ ∨ ̅̅ 
 ⇒  có dạng nối rời chính tắc của hàm Bool. 
 =  ∨  ∨ ∨∨  
3/1/2016 Đại Số Boole Trang 27 
Có 2 cách để xác định dạng nối rời chính tắc một hàm Bool: 
 Cách 1: Bổ sung từ đơn còn thiếu vào các đơn thức. 
Bước 1: Khai triển hàm Bool thành tổng của các đơn thức. 
Bước 2: Với mỗi đơn thức thu được ở bước 1, ta nhân đơn 
thức đó với các tổng dạng với xi là những từ đơn bị thiếu 
trong đơn thức đó. 
Bước 3: Tiếp tục khai triển hàm thu được ở bước 2 và loại 
bỏ những đơn thức bị trùng. Công thức đa thức thu được 
chính là dạng nối rời chính tắc của hàm Bool ban đầu. 
 Vídụ: Trong  tìm dạng nối rời chính tắc 
 , ,  =  ∨  ∨  
 =   ∨  .  ∨  ∨  ∨   ∨  
 =  ∨  ∨  ∨  ∨  ∨  ∨  
  có dạng nối rời chính tắc của hàm Bool. 
3/1/2016 Đại Số Boole Trang 28 
 Cách2: Dùng bảng chân trị. Để ý đến các vector boole 
trong bảng chân trị mà tại đó  = 1 
Tại đó Vector bool thứ  là , ,,và (, ,,) = 1 
Ví dụ: Cho  ,  =  ∨ . 
 Tìm biểu thức dạng nối rời chính tắc của  
Lập bảng chân trị của  
Các thể hiện làm cho  =  là , ,  
 lập được các từ tối tiểu tương ứng. 
 Vậy dạng nối rời chính tắc của  là  ,  = ̅ ∨  ∨  
x y  ∨  
0 0 1 
0 1 0 
1 0 1 
1 1 1 
3/1/2016 Đại Số Boole Trang 29 
Công thức đa thức tối tiểu: 
1. Đơn giản hơn: 
Cho hai công thức đa thức của một hàm Boole: 
F = m1∨ m2∨ m3 ∨ ........ mk 
G = M1∨ M2∨ M3 ∨ ........ Ml 
Ta nói rằng công thức F đơn giản hơn công thức G 
nếu tồn tại đơn ánh h: 
 1,2,  ,  → {1,2,  , } sao cho với mọi  ∈
{1,2,  , } thì số từ đơn của  không nhiều hơn số 
từ đơn của () 
3/1/2016 Đại Số Boole Trang 30 
2. Đơn giản như nhau 
Nếu F đơn giản hơn G và G đơn giản hơn F thì ta nói 
F và G đơn giản như nhau. 
Ví dụ: 
3/1/2016 Đại Số Boole Trang 31 
 f ∈ F4 có 3 dạng đa thức 
 f(x,y,z,t): f1 = x   V ̅yz V x  ̅ V xyz (1) 
 : f2 = x   V ̅yz V xy  V yzt (2) 
 : f3 = x   V ̅yzt V ̅yz  V xy  V yzt 
(3) 
 (1) và (2) đơn giản như nhau 
Vì 
 =  = 4
deg  = deg  = 3
 (2) đơn giản hơn (3) hay (3) phức tạp hơn (2) 
Vì  
 = 4 <  = 5
deg  ≤ deg  
 3/1/2016 Đại Số Boole Trang 32 
3/1/2016 Đại Số Boole Trang 33 
3. Công thức đa thức tối tiểu: 
Công thức F của hàm Boole f được gọi là 
 Công thức đa thức tối tiểu 
nếu với bất kỳ công thức G của f mà đơn giản hơn F 
thì F và G đơn giản như nhau. 
3/1/2016 Đại Số Boole Trang 34 
Bản đồ Karnaugh 
• Sử dụng bảng Karnaugh là phương pháp xác định 
công thức đa thức tối tiểu. 
• Quy tắc gom nhóm: 
 - Gom các tiểu hạng mang biểu diễn là số 1. 
 - Khi gom 2 Ô kế cận sẽ loại được n biến. 
Những biến bị loại là những biến khi ta đi vòng qua các 
ô kế cận mà giá trị của chúng thay đổi. 
 - Các vòng phải được gom sao cho số ô có thể 
vào trong vòng là lớn nhất và để đạt được điều đó, 
thường ta phải gom cả những ô đã gom vào trong các 
vòng khác. 
 - Vòng gom phải là 1 hình chữ nhật. 
3/1/2016 Đại Số Boole Trang 35 
Karnaugh 2 biến 
 • Đối với hàm Boole 2 biến x, y : 
• Bảng karnaugh 2 biến có 4 ô vuông, trong đó: 
Ô được đánh số 1 để biểu diễn tiểu hạng có 
mặt trong hàm. 
Các ô được cho là liền nhau nếu các tiểu hạng 
mà chúng biểu diễn chỉ khác nhau 1 biến. 
 y 
x 
3/1/2016 Đại Số Boole Trang 36 
Karnaugh 2 biến 
Vd1: Tìm bảng Karnaugh cho F =  +  
 F y  
x 1 1 
̅ 
3/1/2016 Đại Số Boole Trang 37 
Vd2: Tìm bảng Karnaugh cho: A =  + ̅ + ̅ 
 A y  
x 1 
 1 1 
3/1/2016 Đại Số Boole Trang 38 
Gom nhóm: 
Ví dụ: F =  +  
F y  
x 1 1 
̅ 
• Từ bảng Karnaugh Tổ hợp các tiểu hạng 
mang biểu diễn là số 1. 
• Các tổ hợp được gom phải là khối khả dĩ lớn 
nhất và số ô là 2 , với n = 1, 2. 
3/1/2016 Đại Số Boole Trang 39 
Ví dụ: B =  + ̅ + ̅  
 B y  
x 1 
̅ 1 1 
 B =  + ̅ 
3/1/2016 Đại Số Boole Trang 40 
karnaugh 3 biến 
• Bảng karnaugh 3 biến là 1 hình chữ nhật chia 
thành 8 ô. 
• Sau khi có bảng Karnaugh, ta bắt đầu gom nhóm 
các tiểu hạng. 
• Quy tắc tương tự Bảng Karnaugh 2 biến. 
3/1/2016 Đại Số Boole Trang 41 
  ̅ ̅  
 1 1 
̅ 1 1 1 
 ̅ + ̅ 
VD: Dùng bảng Karnaugh 3 biến để rút gọn tổng 
các tích sau 
̅ + ̅ + ̅ + ̅̅ + ̅̅ 
3/1/2016 Đại Số Boole Trang 42 
Karnaugh 4 biến 
• Bảng gồm 16 ô vuông như sau: 
3/1/2016 Đại Số Boole Trang 43 
VD: Dùng bảng Karnaugh 4 biến để rút gọn hàm sau: 
D =  +  +  +  +  +  +  +  
D   ̅  ̅  
 1 1 1 
̅ 1 1 
̅ 1 1 
 1 
 D =  +  + ̅ + ̅ +  
3/1/2016 Đại Số Boole Trang 44 
Phủ tối tiểu của một tập 
 Việc tìm tất cả các tổng chuẩn tắc 
không dư thừa của hàm Boole f, từ 
các tsc tối đại của f, là một vấn đề 
khá phức tạp. 
 Trước hết, chúng ta xét bài toán tìm 
phủ tối tiểu của một tập như sau. 
3/1/2016 Đại Số Boole Trang 45 
 Phủ của tập X 
 Cho S = X1, , Xn là họ các tập con của 
X. S gọi là phủ của X nếu X = Xi. 
 Phủ tối tiểu của X 
 Giả sử S là một phủ của X. S gọi là phủ tối 
tiểu của X nếu với mọi i, S\Xi không phủ X. 
3/1/2016 Đại Số Boole Trang 46 
Ví dụ 
 X = a, b, c, d 
 A = a,b B = c,d 
 C = a,d D = b,c 
 A, B, C, D phủ không tối tiểu. 
 A, B, C, D là các phủ tối tiểu. 
 A, C, D phủ không tối tiểu. 
 B, D không phủ. 
3/1/2016 Đại Số Boole Trang 47 
Gồm 5 bước: 
Bước 1: Vẽ biểu đồ karnaugh của f. 
Bước 2: Xác định tất cả các tế bào lớn của 
kar(f). 
Bước 3: Xác định các tế bào lớn nhất thiết 
phải chọn. 
Ta nhất thiết phải chọn tế bào lớn T khi tồn tại 
một ô của kar(f) mà ô này chỉ nằm trong tế 
bào lớn T và không nằm trong bất kỳ tế bào 
lớn nào khác. 
Thuật toán tìm công thức đa thức tối tiểu 
3/1/2016 Đại Số Boole Trang 48 
Bước 4: Xác định các phủ tối tiểu gồm các tế bào lớn: 
• Nếu các tế bào lớn chọn được ở bước 3 đã phủ 
được kar(f) thì ta có duy nhất một phủ tối tiểu 
gồm các tế bào lớn của kar(f). 
• Nếu các tế bào lớn chọn được ở bước 3 chưa 
phủ được kar(f) thì: 
o Xét một ô chưa bị phủ, sẽ có ít nhất hai tế 
bào lớn chứa ô này, ta chọn một trong các 
tế bào lớn này. Cứ tiếp tục như thế ta sẽ 
tìm được tất cả các phủ gồm các tế bào lớn 
của kar(f). 
o Loại bỏ các phủ không tối tiểu, ta tìm được 
tất cả các phủ tối tiểu gồm các tế bào lớn 
của kar(f). 
3/1/2016 Đại Số Boole Trang 49 
Bước 5: Xác định các công thức đa thức tối tiểu 
của f. 
• Từ các phủ tối tiểu gồm các tế bào lớn của 
kar(f) tìm được ở bước 4 ta xác định được các 
công thức đa thức tương ứng của f. 
• Loại bỏ các công thức đa thức mà có một công 
thức đa thức nào đó thực sự đơn giản hơn 
chúng. 
• Các công thức đa thức còn lại chính là các công 
thức đa thức tối tiểu của f. 
3/1/2016 Đại Số Boole Trang 50 
Ví dụ 1 
Tìm các công thức đa thức tối tiểu của hàm : 
 (x,y,z,t) = xyzt ∨ x ∨ x̅ ∨ yz ∨ xy̅ ∨ xy̅ 
B1: Bảng Kar() 
 (x,y,z,t) = xyzt ∨ x ∨ x̅ ∨ yz ∨ xy̅ ∨ xy̅ 
  ̅ ̅ 
̅ 1 1 1 
 1 1 1 
̅ 1 1 
̅̅ 1 1 
3/1/2016 Đại Số Boole Trang 51 
  ̅ ̅ 
̅ 1 1 1 
 1 1 1 
̅ 1 1 
̅̅ 1 1 
B3: Chọn tế bào lớn nhất thiết phải chọn: 
(Vì chúng chứa các các ô không nằm trong 
tế bào nào khác – minh hoạ với ô vàng) 
 + chọn tế bào lớn thứ 1: x 
 + chọn tế bào lớn thứ 2: yz 
B2: Xác định tất cả các tế bào lớn của f. 
3/1/2016 Đại Số Boole Trang 52 
B4: Xác định họ phủ của các tế bào lớn: 
Ta thấy các tế bào chọn ở bước 3 đã phủ hết bảng 
 đây là họ phủ tối thiểu gồm các tế bào 
 Kar(): x ∨ yz 
B5: Ứng với họ phủ tối thiểu của tế bào lớn tìm 
được ta được duy nhất 1 công thức đa thức tối tiểu 
của f: 
 f = x ∨ yz 
  ̅ ̅ 
̅ 1 1 1 
 1 1 1 
̅ 1 1 
̅̅ 1 1 
3/1/2016 Đại Số Boole Trang 53 
Ví dụ 2 
Tìm các công thức đa thức tối thiểu của hàm : 
  , , ,  =  ∨  ∨ ̅̅ ∨  ∨ ̅z̅ 
B1: Bảng Kar() 
  , , ,  =  ∨  ∨ ̅̅ ∨  ∨ ̅z̅ 
x  ̅y ̅ 
z̅ 1 1 
 1 1 1 
̅t 
̅̅ 1 1 1 1 
3/1/2016 Đại Số Boole Trang 54 
B2: Xác định các tế bào lớn 
+ Tế bào lớn thứ 1: ̅ ̅
+ Tbào lớn thứ 2: ̅z 
+ Tế bào lớn thứ 3: zt 
+ Tế bào lớn thú 4: xzt 
+ Tế bào lớn thứ 5: ̅ ̅
x  ̅y ̅ 
z̅ 1 1 
 1 1 1 
̅t 
̅̅ 1 1 1 1 
3/1/2016 Đại Số Boole Trang 55 
x  ̅y ̅ 
z̅ 1 1 
 1 1 1 
̅t 
̅̅ 1 1 1 1 
B3: Xác định các tế bào lớn nhất thiết phải chọn 
Có 3 ô chỉ nằm trong 1 tế bào lớn 
Các tế bào lớn nhất thiết phải chọn là 
̅ ̅+ xzt + ̅ ̅
3/1/2016 Đại Số Boole Trang 56 
B4: Xác định họ phủ tối thiểu của các tế bào lớn: 
Ta có họ phủ :  ∨ ̅̅ ∨ xzt 
Ta thấy còn một ô chưa được phủ và ô đó nằm ở 1 
trong 2 tế bào lớn. 
Ta có 2 cách chọn: 
• Cách chọn thứ 1:  ∨ ̅̅ ∨ xzt ∨ 
̅z 
• Cách chọn thứ 2:  ∨ ̅̅ ∨ xzt ∨ zt 
x  ̅y ̅ 
z̅ 1 1 
 1 1 1 
̅t 
̅̅ 1 1 1 1 
3/1/2016 Đại Số Boole Trang 57 
B5: Xác định công thức đa thức cực tiểu: 
Ta thấy 2 công thức đơn giản như nhau cho nên 
công thức đa thức tối thiểu của hàm  là: 
 ∨ ̅̅ ∨ xzt ∨ z 
 ∨ ̅̅ ∨ xzt ∨ zt 
3/1/2016 Đại Số Boole Trang 58 
 Về cơ bản, phương pháp Quine-McCluskey 
có hai phần. Phần đầu là tìm các số hạng là ứng 
viên để đưa vào khai triển cực tiểu của hàm 
Boole như dưới dạng chuẩn tắc tuyển. Phần thứ 
hai là xác định xem trong số các ứng viên đó, 
các số hạng nào là thực sự dùng được. 
Phương pháp Quine-McCluskey 
3/1/2016 Đại Số Boole Trang 59 
Phương pháp Quine-McCluskey tìm dạng tổng 
chuẩn tắc thu gọn: 
Bước 1: Viết vào cột thứ nhất các biểu diễn của 
các nguyên nhân hạng n của hàm Boole F. Các 
biểu diễn được chia thành từng nhóm, các biểu 
diễn trong mỗi nhóm có số các ký hiệu 1 bằng 
nhau và các nhóm xếp theo thứ tự số các ký hiệu 1 
tăng dần. 
3/1/2016 Đại Số Boole Trang 60 
Bước 2: Lần lượt thực hiện tất cả các phép dán 
các biểu diễn trong nhóm i với các biểu diễn 
trong nhóm i+1 (i=1, 2, ). Biểu diễn nào tham 
gia ít nhất một phép dán sẽ được ghi nhận một 
dấu * bên cạnh. Kết quả dán được ghi vào cột 
tiếp theo. 
Bước 3: Lặp lại Bước 2 cho cột kế tiếp cho đến 
khi không thu thêm được cột nào mới. Khi đó 
tất cả các biểu diễn không có dấu * sẽ cho ta tất 
cả các nguyên nhân nguyên tố của F. 
3/1/2016 Đại Số Boole Trang 61 
3/1/2016 Đại Số Boole Trang 62 
Phương pháp Quine-McCluskey tìm dạng 
tổng chuẩn tắc tối thiểu: 
 Bước 1: Phát hiện tất cả các nguyên nhân 
nguyên tố cốt yếu. 
 Bước 2: Xoá tất cả các cột được phủ bởi 
các nguyên nhân nguyên tố cốt yếu. 
 Bước 3: Trong bảng còn lại, xoá nốt 
những dòng không còn dấu + và sau đó nếu 
có hai cột giống nhau thì xoá bớt một cột. 
 Bước 4: Sau các bước trên, tìm một hệ S 
các nguyên nhân nguyên tố với số biến ít 
nhất phủ các cột còn lại. 
3/1/2016 Đại Số Boole Trang 63 
wxyz 
+ + + + 
+ + + + 
+ + + + 
3/1/2016 Đại Số Boole Trang 64 
Các cổng logic 
1. Các phép toán ở đại số boole 
 Phép cộng thể hiện qua hàm OR 
 Phép nhân thể hiện qua hàm AND 
 Phép phủ định thể hiện qua hàm NOT 
Các phép tính trên khi áp dụng cho logic 0 và 1 
3/1/2016 Đại Số Boole Trang 65 
Các cổng cơ bản 
Cổng AND 
Cổng OR 
Cổng NOT 
Đầu ra = 1 khi có 1 ngõ 
 vào =1 
Đầu ra chỉ =1 khi tất cả 
 ngõ vào =1 
Bù của giá trị đầu vào A ̅ 
3/1/2016 Đại Số Boole Trang 66 
Cổng NAND 
Cổng NOR 
Cổng XOR 
Chỉ = 0 khi tất cả 
ngõ vào =1 
Chỉ = 1 khi tất cả 
ngõ vào =0 
2 ngõ khác nhau thì =1 
Cổng X-NOR 
2 ngõ giống nhau thì =1 
3/1/2016 Đại Số Boole Trang 67 
Sự chuyển đổi giữa các cổng cơ bản sang cổng NAND 
3/1/2016 Đại Số Boole Trang 68 
Sự chuyển đổi giữa các cổng cơ bản sang cổng NOR 
3/1/2016 Đại Số Boole Trang 69 
VD: Viết lại biểu thức logic sau từ mạch logic: 
Kết quả: Y = (̅ + )( +  + )̅ 
3/1/2016 Đại Số Boole Trang 70 
Các bước thiết kế logic tổng hợp: 
Bước 1: Đặt các biến cho ngõ vào và các hàm 
 của ngõ ra tương ứng. 
Bước 2: Thiết lập bảng chân trị cho ngõ ra và 
 ngõ vào 
Bước 3: Viết biểu thức logic liên hệ giữa ngõ ra 
 và các ngõ vào. 
Bước 4: Tìm công thức đa thức tối tiểu của biểu 
 thức logic vừa tìm được. 
Bước 5: Từ biểu thức logic rút gọn chuyển sang 
 mạch logic tương ứng 
3/1/2016 Đại Số Boole Trang 71 
 Ví dụ: 
Một ngôi nhà có 3 công tắc, người chủ nhà muốn 
bóng đèn sáng khi cả 3 công tắc đều hở, hoặc khi 
công tắc 1 và 2 đóng còn công tắc thứ 3 hở. Hãy 
thiết kế mạch logic thực hiện sao cho số cổng là 
ít nhất. 
 Giải: 
Bước 1: 
Gọi 3 công tắc lần lượt là A, B, C. 
Bóng đèn là Y. 
Trạng thái công tắc đóng là logic 1, hở là 0. 
Trạng thái đèn sáng là logic 1 và tắt là 0. 
 3/1/2016 Đại Số Boole Trang 72 
Bước 2: 
Từ yêu cầu bài toán ta có bảng chân trị: 
3/1/2016 Đại Số Boole Trang 73 
A B C 
Y 
 Bước 3: Từ bảng chân trị ta có biểu thức logic ngõ ra 
 = ̅̅ + ̅ 
 Bước 4: Rút gọn biểu thức logic:  = ̅̅ + ̅ 
 Bước 5: Mạch logic tương ứng của biểu thức 
3/1/2016 Đại Số Boole Trang 74 
 Ngoài ra, ta cũng có thể sử dụng cổng XOR cho bài toán như sau: 
3/1/2016 Đại Số Boole Trang 75 
CHÂN THÀNH CẢM ƠN CÔ 
VÀ CÁC BẠN 
ĐÃ LẮNG NGHE VÀ THEO DÕI