Giản đồ xung (Waveform) của tín hiệu số:
Trạng thái logic của tín hiệu số (Digital Signal):
Chương 2: ĐẠI SỐ BOOLE - CỔNG LOGIC
I. Cấu trúc đại số Boole:
Là cấu trúc đại số được định nghĩa trên 1 tập phần tử nhị phân B = {0, 1} và các phép toán nhị phân: AND (.), OR (+), NOT (`).
1. Các tiên đề (Axioms):
a. Tính kín (Closure Property)
b. Phần tử đồng nhất (Identity Element):
x + 0 = 0 + x = x
x . 1 = 1 . x = x
c. Tính giao hoán (Commutative Property):
x + y = y + x
x . y = y . x
d. Tính phân bố (Distributive Property):
x + ( y . z ) = ( x + y ) . ( x + z )
x . ( y + z ) = x . y + x . z
e. Phần tử bù (Complement Element):
x + x` = 1 x . x` = 0
* Thứ tự phép toán: theo thứ tự dấu ngoặc (), NOT, AND, OR
2. Các định lý cơ bản (Basic Theorems):
a. Định lý 1: (x`)` = x
b. Định lý 2: x + x = x x . x = x

c. Định lý 3: x + 1 = 1 x . 0 = 0


d. Định lý 4: định lý hấp thu (Absorption)
x + x . y = x x . (x + y) = x


e. Định lý 5: định lý kết hợp (Associative)
x + (y + z) = (x + y) + z x . (y . z) = (x . y) . z


f. Định lý 6: định lý De Morgan
(x + y)` = x` . y` (x . y)` = x` + y`

Mở rộng: (x1 + x2 + .. + xn)` = x1` . x2` .. xn`
(x1 . x2 .. xn)` = x1` + x2` + .. + xn`
II. Hàm Boole (Boolean Function):
1. Định nghĩa:
* Hàm Boole là 1 biểu thức được tạo bởi các biến nhị phân và các phép toán nhị phân NOT, AND, OR.
F (x, y, z) = x . y + x`. y`. z
* Với giá trị cho trước của các biến, hàm Boole sẽ có giá trị là 0 hoặc 1.
* Bảng giá trị:
2. Bù của 1 hàm:
- Sử dụng định lý De Morgan:
F = x . y + x` . y` . z
F` = ( x . y + x` . y` . z )`
= ( x . y )` . ( x` . y` . z )`
F` = ( x` + y` ) . ( x + y + z` )
- Lấy biểu thức đối ngẫu và lấy bù các biến:
* Tính đối ngẫu (Duality): Hai biểu thức được gọi là đối ngẫu của nhau khi ta thay phép toán AND bằng OR, phép toán OR bằng AND, 0 thành 1 và 1 thành 0.
F = x . y + x` . y` . z
Lấy đối ngẫu: ( x + y ) . ( x` + y` + z )
Bù các biến: F` = ( x` + y` ) . ( x + y + z` )
III. Dạng chính tắc và dạng chuẩn của hàm Boole:
1. Các tích chuẩn (minterm) và tổng chuẩn (Maxterm):
- Tích chuẩn (minterm): mi (0 ? i ? 2n-1) là các số hạng tích (AND) của n biến mà hàm Boole phụ thuộc với quy ước biến đó có bù nếu nó là 0 và không bù nếu là 1.
- Tổng chuẩn (Maxterm): Mi (0 ? i ? 2n-1) là các số hạng tổng (OR) của n biến mà hàm Boole phụ thuộc với quy ước biến đó có bù nếu nó là 1 và không bù nếu là 0.
m0 = x` y` z`
m1 = x` y` z
m2 = x` y z`
m3 = x` y z
m4 = x y` z`
m5 = x y` z
m6 = x y z`
m7 = x y z
M0 = x + y + z
M1 = x + y + z`
M2 = x + y` + z
M3 = x + y` + z`
M4 = x` + y + z
M5 = x` + y + z`
M6 = x` + y` + z
M7 = x` + y` + z`
2. Dạng chính tắc (Canonical Form):
a. Dạng chính tắc 1:
là dạng tổng của các tích chuẩn (minterm) làm cho hàm Boole có giá trị 1
F(x, y, z) =
x`y`z
+ x`y z`
+ x y`z
+ x y z`
+ x y z
= m1
+ m2
+ m5
+ m6
+ m7
= ? (1, 2, 5, 6, 7)
b. Dạng chính tắc 2:
là dạng tích của các tổng chuẩn (Maxterm) làm cho hàm Boole có giá trị 0
F(x, y, z) =
(x + y + z)
(x + y` + z`)
(x` + y + z)
= M0
. M3
. M4
= ? (0, 3, 4)
* Trường hợp hàm Boole tùy định (don`t care):
Hàm Boole n biến có thể không được định nghĩa hết tất cả 2n tổ hợp của n biến phụ thuộc. Khi đó tại các tổ hợp không sử dụng này, hàm Boole sẽ nhận giá trị tùy định (don`t care), nghĩa là hàm Boole có thể nhận giá tri 0 hoặc 1.
F (x, y, z) = ? (1, 2, 5, 6) + d (0, 7)
= ? (3, 4) . D (0, 7)
3. Dạng chuẩn (Standard Form):
a. Dạng chuẩn 1:
là dạng tổng các tích (S.O.P - Sum of Product)
F (x, y, z) = x y + z
* F (x, y, z) = x y + z
= x y (z` + z) + (x` + x) (y` + y) z
= x y z` + x y z + x`y`z + x y`z + x`y z + x y z
= m6 + m7 + m1 + m5 + m3
= ? (1, 3, 5, 6, 7)
* F (x, y, z) = x y + z
= (x + z) (y + z)
= (x + y`y + z) (x`x + y + z)
= (x + y` + z) (x + y + z) (x` + y + z) (x + y + z)
= M2 . M0 . M4
= ? (0, 2, 4)
b. Dạng chuẩn 2:
là dạng tích các tổng (P.O.S - Product of Sum)
F (x, y, z) = (x + z`) y`
* F (x, y, z) = (x + z`) y`
= x y` (z` + z) + (x` + x) y`z`
= x y`z` + x y`z + x`y`z` + x y`z`
= m4 + m5 + m0
= ? (0, 4, 5)
= x y` + y`z`
* F (x, y, z) = (x + z`) y`
= (x + y`y + z`) (x`x + y` + z z`)
= (x + y`+ z`) (x + y + z`)
(x` + y` + z`)(x` + y` + z)(x + y` + z`)(x + y` + z)
= M3 . M1 . M7 . M6 . M2
= ? (1, 2, 3, 6, 7)
IV. Cổng logic:
1. Cổng NOT:
2. Cổng AND:
Với cổng AND có nhiều ngõ vào,
ngõ ra sẽ là 1 nếu tất cả các ngõ vào đều là 1
3. Cổng OR:
Với cổng OR có nhiều ngõ vào,
ngõ ra sẽ là 0 nếu tất cả các ngõ vào đều là 0
4. Cổng NAND:
Với cổng NAND có nhiều ngõ vào,
ngõ ra sẽ là 0 nếu tất cả các ngõ vào đều là 1
5. Cổng NOR:
Với cổng NOR có nhiều ngõ vào,
ngõ ra sẽ là 1 nếu tất cả các ngõ vào đều là 0
6. Cổng XOR (Exclusive_OR):
Với cổng XOR 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ố lẻ
6. Cổng XNOR (Exclusive_NOR):
Vớ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
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ố.
1. Phương pháp đại số:
Dùng các định lý và tiên đề để rút gọn hàm.
F (A, B, C) = ? (2, 3, 5, 6, 7)
= B + AC
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 n biến. 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 dó. Ở� 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, dạng chính tắc 2 thì chỉ đưa giá trị 0 và X.
* Bìa 2 biến:
0
1
2
3
F (A, B) = ? (0, 2) + d(3) = ? (1) . D(3)
1
1
X
0
X
* Bìa 3 biến:
0
1
2
3
6
7
4
5
F (A, B, C) = ? (2, 4, 7) + d(0, 1) = ? (3, 5, 6) . D(0, 1)
X
X
1
1
1
X
X
0
0
0
* Bìa 4 biến:
AB
CD
F
00
00
01
11
10
01
11
10
0
1
4
5
8
9
3
2
7
6
10
14
15
13
12
11
* Bìa 5 biến:
30
31
29
28
18
19
17
16
22
23
21
20
26
27
25
24
b. Rút gọn bìa Karnaugh:
- Liên kết đôi: Khi liên kết (OR) hai ô có giá trị 1 (Ô_1) kề cận với nhau trên bìa K, ta sẽ được 1 số hạng tích 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 ô). Hoặc khi liên kết (AND) hai ô có giá trị 0 (Ô_0) kề cận với nhau trên bìa K, ta sẽ được 1 số hạng 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 ô).
* Nguyên tắc:
1
1
0
0
- Liên kết 4: Tương tự như liên kết đôi khi liên kết 4 Ô_1 có giá trị 1 hoặc 4 Ô_ 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 ô)
- Liên kết 8: liên kết 8 ô kề cận với nhau, ta sẽ loại đi được 3 biến (3 biến khác nhau giữa 8 ô)
AB
CD
F
00
01
11
10
D
B
- Liên kết 2k: khi ta liên kết 2k Ô_1 hoặc 2k Ô_0 kề cận với nhau ta sẽ loại đi được k biến (k biến khác nhau giữa 2k ô)
* Các bước thực hiện rút gọn theo dạng S.O.P:
- Biểu diễn các Ô_1 lên bìa Karnaugh
- Thực hiện các liên kết có thể có sao cho các Ô_1 được liên kết ít nhất 1 lần; mỗi liên kết cho ta 1 số hạng tích.
(Nếu Ô_1 không có kề cận với các Ô_1 khác thì ta có liên kết 1: số hạng tích chính bằng minterm của ô đó).
- Biểu thức rút gọn có được bằng cách lấy tổng (OR) của các số h?ng tích liên kết trên.
F(A, B, C) = ? (0, 1, 3, 5, 6)
* Các bước thực hiện rút gọn theo dạng P.O.S:
- Biểu diễn các Ô_0 lên bìa Karnaugh
- Thực hiện các liên kết có thể có sao cho các Ô_0 được liên kết ít nhất 1 lần; mỗi liên kết cho ta 1 số hạng t?ng.
- Biểu thức rút gọn có được bằng cách lấy tích (AND) của các số h?ng t?ng liên kết trên.
F(A, B, C, D) = ? (0, 4, 8, 9, 12, 13, 15)
(C + D)
* Trường hợp rút gọn hàm Boole có tùy định: thì ta có thể coi các Ô tùy định này là Ô_1 hoặc Ô_0 sao cho có lợi khi liên kết (nghĩa là có được liên kết nhiều Ô kề cận nhất)
F(A, B, C, D) = ? (0, 4, 8, 10) + d (2, 12, 15)
F(A, B, C, D) = ? (0, 2, 3, 4, 6, 10, 14) . D (8, 9, 11, 12, 13)
D
* Chú ý:
- Ưu tiên liên kết cho các ô chỉ có 1 kiểu liên kết (phải là liên kết có nhiều ô nhất).
- Khi liên kết phải đảm bảo có chứa ít nhất 1 ô chưa được liên kết lần nào.
- Ta coi các tùy định như là những ô đã 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
F1(A, B, C, D) = ? (1, 3, 5, 12, 13, 14, 15) + d (7, 8, 9)

F2(A, B, C, D) = ? (1, 3, 7, 11, 15) . D(0, 2, 5)

F1(A, B, C, D, E) = ? (1, 3, 5, 7, 12, 14, 29, 31)
+ d (13, 15, 17, 19, 20, 21, 22, 23)
F2(A, B, C, D, E) = ? (0, 8, 12, 13, 16, 18, 28, 30)
. D(2, 6, 10, 14, 15, 24, 26)
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)
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).
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 có biểu thức là 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
- 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 chỉ có dạng bù trên 1 số hạng tích chỉ có 2 biến
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 có biểu thức là dạng bù của 1 số hạng tổng.
- Dùng định lý De-Morgan để biến đổi số hạng tích thành tổng
- Cổng NOT cũng được thay thế bằng cổng NOR