Đại số Boole và các 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 (‘).

c25e125ba25a5u2btr25c325bac2b25c4259125e125ba25a1i2bs25e125bb25912bboole

* Thứ tự phép toán: theo thứ tự dấu ngoặc (), NOT, AND, OR
1. Các tiên đề (Axioms):

a. Tính kín (Closure Property)Trên tập E là một phép toán mà khi tác động giữa hai phần tử thuộc E, chỉ cho ra một kết quả duy nhất và kết quả này cũng thuộc E. Closure là một ánh xạ $E \times E \mapsto E$ .

Etimes Emapsto E

Lúc này ta gọi E là một tập kín (closed set) dưới phép toán nói trên.

Ví dụ, trong tập N, phép cộng (+) và phép nhân (*) là các luật thành trong, nhưng phép trừ (-) thì không phải, vì kết quả phép trừ có thể là số âm, nằm ngoài phạm vi của tập N.

b. Phần tử đồng nhất (Identity Element):
x . 1 = 1 . x = x
x + 0 = 0 + 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

2. Các định lý cơ bản (Basic Theorems):

Định lý 1: (x’)’ = x
Định lý 2: x + x = x, x . x = x
Định lý 3: x + 1 = 1, x . 0 = 0
Định lý 4: định lý hấp thu (Absorption)
x + x . y = x x . (x + y) = x
Định lý 5: định lý kết hợp (Associative)
x + x . y = x x . (x + y) = x
Định lý 6: định lý De Morgan
x + (y + z) = (x + y) + z x . (y . z) = (x . y) . z
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. Dang 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ến 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.

t25e125bb2595ng2bchu25e125ba25a9n2bmaxterm

d25e125ba25a1ng2bch25c325adnh2bt25e125ba25afc 2. Dạng chính tắc (Canonical Form):
a. Dang 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)

F(x, y, z) = (x + y + z) (x + y’ + z’) (x’ + y + z)
= M0 . M3 . M4
= Π(0, 3, 4)

ha25c325b8m2bboole2btu25c325b8y2b25c325b125c325b2nh2b2528don25e225802599t2bcare2529 b. Dang 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
* 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’ + y’z’
= 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)

* 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