Bài giảng Kỹ thuật số - Chương 2: Đại số Boole – cổng logic

i cổng XNOR có nhiều ngõ vào, ngõ ra sẽ là 1 nếu tổng số bit 1 ở các ngõ vào là số chẵn.
z
0	0
0	1
1	0
1	1
1
0
0
1
	 z = x Å y = x y + x y = (x + y) (x + y)
V. Rút gọn hàm Boole:
	Rút gọn (tối thiểu hóa) hàm Boole nghĩa là đưa hàm Boole về dạng biểu diễn đơn giản nhất, sao cho:
- Biểu thức có chứa ít nhất các thừa số và mỗi thừa số chứa ít nhất các biến.
	- Mạch logic thực hiện có chứa ít nhất các vi mạch số.
	Có 2 phương pháp thực hiện 
	1. Phương pháp đại số:
	Dùng các định lý và tiên đề để rút gọn hàm.
	Vd: 	F (A, B, C) 	= S (2, 3, 5, 6, 7)
	= A B C + A B C + A B C + A B C + A B C 
	= A B (C + C) + A C (B + B) + A B (C + C)
	= A B + A C + A B 	
	= (A + A) B + A C
	= B + A C
	2. Phương pháp bìa KARNAUGH:
	a. Cách biểu diễn:
	- Bìa K gồm các ô vuông, mỗi ô vuông biểu diễn cho tổ hợp các biến mà hàm Boole phụ thuộc. Như vậy bìa K cho n biến sẽ có 2n ô.
	- Hai ô được gọi là kề cận nhau khi tổ hợp biến mà chúng biểu diễn chỉ khác nhau 1 biến.
	- Trong ô sẽ ghi giá trị tương ứng của hàm Boole tại tổ hợp biến đó. Nếu sử dụng hàm Boole ở dạng chính tắc 1 thì đưa các giá trị 1 và X lên các ô, không đưa các giá trị 0. Ngược lại, nếu sử dụng dạng chính tắc 2 thì chỉ đưa giá trị 0 và X.
A
B
F
0
1
2
3
0
0
1
1
	* Bìa 2 biến:
A
B
F
0
1
X
0
0
1
A
B
F
0
1
1
X
1
0
1
	Vd:	F (A, B) = S (0, 2) + d(3) = P (1) . D(3)
AB
C
F
00
01
2
3
0
0
1
1
11
10
4
5
6
7
	* Bìa 3 biến:
	 	Vd: F (A, B, C) = S (2, 4, 7) + d(0,1) = P (3, 5, 6) . D(0, 1)
AB
C
F
00
01
1
X
0
X
1
11
10
1
1
AB
C
F
00
01
0
X
0
X
1
11
10
0
0
AB
CD
F
00
01
4
5
0
00
1
01
11
10
8
9
12
13
7
6
3
11
2
10
11
10
15
14
	* Bìa 4 biến:
AB
CD
F
00
01
X
X
00
1
01
11
10
X
1
1
1
1
11
10
1
1
1
AB
CD
F
00
01
X
0
X
00
01
11
10
X
0
0
11
0
10
0
	Vd:	F (A, B, C, D) = S (1, 3, 9, 11, 12, 13, 14, 15) + d(0, 4, 8)
	* Bìa 5 biến:
BC
DE
F
00
01
4
5
0
00
1
01
11
10
8
9
12
13
7
6
3
11
2
10
11
10
15
14
A
0
10
11
28
29
24
25
01
00
16
17
20
21
31
30
27
26
19
18
23
22
1
	b. Rút gọn bìa Karnaugh:
	* Nguyên tắc: 
	- Liên kết đôi: Khi liên kết (OR) 2 minterm_1 kề cận với nhau trên bìa K, ta sẽ được 1 tích số mất đi 1 biến so với tích chuẩn (biến mất đi là biến khác nhau giữa 2 minterm). Hoặc khi liên kết (AND) 2 Maxterm_0 kề cận với nhau trên bìa K, ta sẽ được 1 tổng mất đi 1 biến so với tổng chuẩn (biến mất đi là biến khác nhau giữa 2 Maxterm).
AB
C
F
00
01
1
0
1
11
10
1
	A B C + A B C = (A + A) B C = B C
B C : B = 1 và C = 0 
AB
C
F
00
01
0
1
11
10
0
0
AB
C
F
00
01
0
1
11
10
0
0
	(A + B + C) (A + B + C) 
	 = 	(A + B + C C) = (A + B)
(A + B) : A =1 và B = 0
AB
C
F
00
01
1
0
1
1
11
10
1
1
AB
C
F
00
01
0
0
0
1
11
10
0
0
B
C
	- Liên kết 4: Tương tự như liên kết đôi khi ta liên kết 4 minterm_1 hoặc 4 Maxterm_0 kề cận với nhau ta sẽ loại đi được 2 biến (2 biến khác nhau giữa 4 tổ hợp)
AB
CD
F
00
01
1
00
1
01
11
10
1
1
1
1
11
10
1
1
AB
CD
F
00
01
0
0
0
00
0
01
11
10
0
0
0
11
0
10
A
D
	- Liên kết 8: khi ta liên kết 8 minterm_1 hoặc 8 Maxterm_0 kề cận với nhau ta sẽ loại đi được 3 biến (3 biến khác nhau giữa 8 tổ hợp)
	- Liên kết 2n: khi ta liên kết 2n minterm_1 hoặc 2n Maxterm_0 kề cận với nhau ta sẽ loại đi được n biến (n biến khác nhau giữa 2n tổ hợp)
	* Các bước thực hiện (rút gọn theo dạng S.O.P):
	- Biểu diễn các minterm_1 lên bìa Karnaugh
	- Thực hiện các liên kết có thể có sao cho các minterm_1 được liên kết ít nhất 1 lần. (Nếu minterm_1 không có kề cận với các minterm_1 khác thì ta có liên kết 1 chính bằng biểu thức minterm đó). Mỗi liên kết cho ta 1 tích số.
	- Biểu thức rút gọn có được bằng cách lấy tổng (OR) của các tích số liên kết trên.
	Vd: 	F(A, B, C) = S (0, 1, 3, 5, 6) = A B + A C + B C + A B C
AB
C
F
00
01
1
1
0
1
1
11
10
1
1
A B C
A B 
A C
 B C
AB
CD
F
00
01
1
1
1
00
1
01
11
10
1
1
1
1
1
11
1
10
1
A
B C
B D
	Vd: F(A, B, C, D) = S (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11) 
	 F(A, B, C, D) = A + B D + B C
	 Trường hợp rút gọn hàm Boole có tùy định thì ta có thể coi các minterm này là minterm_1 hoặc minterm_0 sao cho có lợi khi liên kết các minterm_1 (nghĩa là có được liên kết nhiều minterm kề cận hơn)
	Vd: F(A, B, C, D) = S (0, 4, 8, 10) + d (2, 7, 12, 15)
F
AB
10
11
01
00
CD
X
1
00
1
1
01
B D
C D
11
X
X
1
10
X
	 F(A, B, C, D) = B D + C D
	Khi liên kết có thể tạo ra các liên kết dư không cần thiết
 A C
 (liên kết dư)
AB
C
F
00
01
 1
0
1
11
10
1
1
1
	Vd: 	
B C
A B
	 F(A, B, C) = B C + A C + A B
 	 = B C + A B C + A B C + A B
	 	 = B C (1+ A ) + A B (C + 1)
	 = B C + A B
	* Lưu ý:
	- Ưu tiên liên kết cho các minterm_1 chỉ có 1 kiểu liên kết (phải là liên kết tối ưu nhất).
	- Khi liên kết phải đảm bảo có chứa ít nhất 1 minterm_1 chưa được liên kết lần nào. 
	- Ta coi các tùy định như là những minterm_1 đã liên kết rồi.
	- Có thể có nhiều cách liên kết có kết quả tương đương nhau.
	Vd: 	Rút gọn các hàm F(A, B, C, D) = S (1, 3, 5, 12, 13, 14, 15) + d (7, 8, 9)
	 F(A, B, C, D) = S (1, 3, 7, 11, 15) + d (0, 2, 5)
AB
CD
F
00
01
X
X
00
1
01
11
10
1
1
11
X
10
1
1
AB
CD
F
00
01
1
00
1
01
11
10
X
X
1
1
X
1
11
10
1
1
	* Rút gọn hàm Boole theo dạng P.O.S (dạng chính tắc 2): 
	- Biểu diễn các Maxterm_0 và tùy định lên bìa Karnaugh
	- Thực hiện các liên kết trên các Maxterm_0 và tùy định, mỗi liên kết cho ta 1 tổng (biến có giá trị 0 thí biểu diễn không bù, biến có giá trị 1 thì có bù). 
	- Biểu thức rút gọn có được bằng cách lấy tích (AND) của các liên kết tổng trên.
AB
CD
F
00
01
0
0
00
01
11
10
0
0
0
0
11
10
0
(C + D)
(A + C)
(A + B + D)
	Vd: 	F(A, B, C, D) = P (0, 4, 8, 9, 12, 13, 15)
	F(A, B, C, D) = (C + D) (A + C) (A + B + D)
	Vd: F(A, B, C, D) = P (0, 2, 3, 4, 6, 10, 14) . D (7, 8, 9, 11, 12)
AB
CD
F
00
01
0
0
00
01
11
10
X
X
X
X
0
0
11
0
10
X
0
0
D
(A + C)
	 F(A, B, C, D) = D (A + C) 
	* Rút gọn hàm cho dưới dạng biểu thức: ta chuyển hàm về dạng chính tắc 1 hoặc 2 rồi rút gọn trên bìa. Tuy nhiên, ta có thể đưa thẳng lên bìa K.
	- Biểu thức có dạng S.O.P: mỗi tích số sẽ tương đương với các minterm_1 trên bìa theo nguyên tắc 1 tích số ít hơn tích chuẩn n biến sẽ tương đương với 2n ô có giá trị 1 kề cận.
AB
CD
F
00
01
00
01
11
10
11
10
1
AB
CD
F
00
01
1
00
01
11
10
1
11
10
AB
CD
F
00
01
1
1
00
01
11
10
1
1
11
10
AB
CD
F
00
01
00
1
01
11
10
1
11
10
A B C D
1 1 1 0
A B D
0 1 X 0
(thiếu biến C)
 B C D
 X 0 0 1
(thiếu biến A)
 B C 
 X 1 0 X
(thiếu biến A, D)
AB
CD
F
00
01
1
1
00
1
01
11
10
1
1
1
1
11
10
1
B D
C D
	Vd: 	 F(A, B, C, D) = A B D + B C + B C D + A B C D
	 F(A, B, C, D) = B D + C D
	- Biểu thức có dạng P.O.S: mỗi tổng sẽ tương đương với các Maxterm_0 trên bìa theo nguyên tắc 1 số hạng tổng ít hơn tổng chuẩn n biến sẽ tương đương với 2n ô có giá trị 0 kề cận.
	Vd: 	F(A, B, C, D) = (A + B + C + D) (A + C + D) (A + B + D) (A + B)
AB
CD
F
00
01
00
01
11
10
0
11
10
AB
CD
F
00
01
00
01
11
10
11
10
0
0
AB
CD
F
00
01
0
00
01
11
10
11
0
10
AB
CD
F
00
01
00
01
11
10
0
0
11
10
0
0
(A+ C+ D)
 1 X 1 1
(thiếu biến B)
 (A+B )
 1 0 X X
(thiếu biến C, D)
 (A+B+ D) 
 0 0 X 0
(thiếu biến C)
AB
CD
F
00
01
0
00
01
11
10
0
0
0
11
0
10
0
0
0
(B + D)
(A + D)
(A+B+C+D)
 1 1 0 1
	 F(A, B, C, D) = (A + D) (B + D)
VI. Thực hiện hàm Boole bằng cổng logic:
 	1. Cấu trúc cổng AND_OR:
	Cấu trúc AND_OR là sơ đồ logic thực hiện cho hàm Boole biểu diễn theo dạng tổng cách tích (S.O.P).
	Vd:	F(A, B, C, D) = A B D + C D
A
B
F(A, B, C, D)
C
.
D
OR
AND
 	2. Cấu trúc cổng OR_AND:
	Cấu trúc OR_AND là sơ đồ logic thực hiện cho hàm Boole biểu diễn theo dạng tích cách tổng (P.O.S).
A
F(A, B, C, D)
B
C
D
.
OR
AND
	Vd:	F(A, B, C, D) = (A + D) ( B + C+ D)
 	3. Cấu trúc toàn cổng NAND:
	Cấu trúc NAND là sơ đồ logic thực hiện cho hàm Boole mà biểu thức có dạng bù của 1 số hạng tích.
	- Dùng định lý De-Morgan để biến đổi số hạng tổng thành tích.
	- Cổng NOT cũng được thay thế bằng cổng NAND nối chung 2 ngõ vào.
	Vd:	F(A, B, C, D) = A B D + C D
	 = A B D + C D
	 = (A B D) (C D)
A
F(A, B, C, D)
B
C
D
.
	Vd:	F(A, B, C, D) = 	(A + D) (B + C+ D)
	 = 	(A + D) (B + C+ D)
	 = 	(A D) (B C D) 
	 = 	(A D) (B C D) 
	A
F(A, B, C, D)
B
C
D
.
	- Trong thực tế người ta chỉ sử dụng 1 loại cổng NAND 2 ngõ vào; khi đó ta phải biến đổi biểu thức sao cho có dạng bù trên 1 tích số chỉ có 2 biến.
	Vd:	F(A, B, C, D) = A B D + C D
	 = A B D + C D
	 = (A B D) (C D)
	 =	(A B D) (C D) 
A
F(A, B, C, D)
B
C
D
.
	Vd:	F(A, B, C, D) = 	(A + D) (B + C) (C + D)
	 =	(A + D) (B + C) (C + D)
	 =	(A D) (B C) (C D)
	 =	(A D) (B C) (C D)
A
F
B
C
D
.
.
 	4. Cấu trúc toàn cổng NOR:
	Cấu trúc NOR là sơ đồ logic thực hiện cho hàm Boole mà biểu thức có dạng bù của 1 số hạng tổng.
	Vd:	F(A, B, C, D) = (A + D) ( B + C + D)
	 =	(A + D) + ( B + C + D)
A
F(A, B, C, D)
B
C
D
.
	Vd:	F(A, B, C, D) =	(A + D) + (B + C + D)
	 = 	(A + D) + (B + C + D)	
A
B
F(A, B, C, D)
.
D
C