Bài giảng Cấu trúc máy tính - Bài 2: Đại số Boolean

Nội dung text: Bài giảng Cấu trúc máy tính - Bài 2: Đại số Boolean

1. ĐẠI SỐ BOOLEAN
2. ĐẠI SỐ BOOLEAN ▪ Đại số Boolean là đại số dùng để mô tả các hoạt động logic. ▪ Các biến Boolean là các biến logic, chỉ mang giá trị 0 hoặc 1 (đôi khi gọi là True hoặc False) (True = 1; Faslse = 0) ▪ Hàm Boolean là hàm của các biến Boolean, chỉ mang giá trị 0 hoặc 1. ▪ Đại số Boolean gồm các phép toán cơ bản: Đảo (NOT), Giao (AND), Hợp (OR)
3. CÁC PHÉP TOÁN ◼ NOT: Bảng sự thật X not X Kí hiệu cổng 0 1 1 0 x x’ x,x Input Output Nếu đưa mức HIGH vào ngõ vào của cổng, ngõ ra sẽ là mức LOW và ngược lại. F() x= x
4. CÁC PHÉP TOÁN ◼ AND: Cổng AND có ít nhất 2 ngõ vào Ngõ ra là 1 khi tất cả các ngõ vào là 1, ngược lại là 0 x xy x and y x • y,x  y,x& y,xy y Bảng sự thật: X Y X and Y 0 0 0 0 1 0 1 0 0 1 1 1
5. CÁC PHÉP TOÁN ◼ OR: Cổng OR có ít nhất là 2 ngõ vào Ngõ ra là 1, nếu có một ngõ vào là 1, ngược lại là 0 x or y x + y,x  y,x|y x x+y y X Y X or Y Bảng sự thật: 0 0 0 0 1 1 1 0 1 1 1 1
6. CÁC PHÉP TOÁN ◼ NAND: Là cổng bù của AND Có ngõ ra là ngược lại với cổng AND X nand Y = not (X and Y) = X • Y X Y Z 0 0 1 0 1 1 1 0 1 1 1 0
7. CÁC PHÉP TOÁN ◼ NOR: Là cổng bù của OR Có ngõ ra ngược với cổng OR X nor Y = not (X or Y) = X + Y X Y Z 0 0 1 0 1 0 1 0 0 1 1 0
8. CÁC PHÉP TOÁN ◼ XOR (Exclusive-OR): Tương tự cổng OR, nhưng có thêm 1 vòng ở trước Ngõ ra là 1 nếu số ngõ vào có giá trị 1 là một số lẻ, ngược lại là 0 Exclusive OR - XOR X Y Z XOR - True if both inputs 0 0 0 are different 0 1 1 1 0 1 Z = X  Y 1 1 0
9. BIỂU DIỄN HÀM BOOLEAN FABCABC(,,)()=+ Biểu diễn đại số: Biểu diễn cổng: A B F C
10. BIỂU DIỄN HÀM BOOLEAN A B C F 0 0 0 0 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 0
11. TÍNH CHẤT CỦA ĐẠI SỐ BOOLEAN ◼ X.1 = X AA+=1 ◼ X+1 = 1 AA.0= ◼ X.0 = 0 A.A = A ◼ X+1 = 1 A+A=A ◼ X+Y = Y+X ◼ X.Y = Y.X ◼ A+(B+C) = (A+B)+C ◼ A.(B.C) = (A.B).C
12. CÁC ĐỊNH LÝ ◼ Một mệnh đề được gọi là đối ngẫu với một mệnh đề khác khi ta thay 0→1, 1→0, +→., .→+ Định lý: Khi một mệnh đề đúng thì mệnh đề đối ngẫu của nó cũng đúng VD: hai mệnh đề đối ngẫu: AA+=1 AA.0=
13. CÁC ĐỊNH LÝ Định lý De-Morgan: ◼ Bù của tổng bằng tích các bù ◼ Bù của tích bằng tổng các bù A1+A2+ +An=A1.A2. .An A1.A2 An = A1+A2+ +An
14. CÁC ĐỊNH LÝ ◼ Luật nuốt: A(A+B) = A A+AB = A ◼ Luật dán: A() A+= B AB A+ AB = A + B
15. BÀI TẬP 1 Dùng bảng chân trị chứng minh Định lý De Morgan 3 biến: (ABC)’ = A’ + B’ + C’ 2. Lập bảng chân trị hàm XOR 3 biến: x = A  B  C 3. Dùng Đại số Boolean đơn giản các biểu thức sau a. A + AB b. AB + AB’ c. A’BC + AC d. A’B + ABC’ + ABC 4. Dùng Định lý De Morgan chứng minh: a. (A + B)’ (A’ + B’)’ = 0 b. A + A’B + A’B’ = 1