Chương 6

ðẠI SỐ BOOLE VÀ CÁC CỔNG LOGIC

I. CẤU TRÚC ðẠI SỐ BOOLE

- ðại số Boole là ñại số dùng ñể mô tả các hoạt ñộng logic.

- Các biến Boole là các biến logic, chỉ mang giá trị 0 hoặc 1

(ñôi khi gọi là True hoặc False).

- Hàm Boolean là hàm của các biến Boole, chỉ mang giá trị

0 hoặc 1.

- ðại số Boole gồm các phép toán cơ bản: ðảo (NOT),

1

Bài giảng môn Kỹ thuật ðiện tử C GV: Lê Thị Kim Anh

Giao hay Nhân (AND), Hợp hay Cộng (OR).

Các tiên ñề của ñại số Boole

1. Giao hoán

A + B = B + A

A*B = B*A

2. Phối hợp

A + (B + C) = (A + B) + C

A*(B*C) = (A*B)*C

3. Phân bố

A * (B + C) = A * B +A * C

2

Bài giảng môn Kỹ thuật ðiện tử C GV: Lê Thị Kim Anh

A + (B*C) = (A+B)*(A+C)

4. ∃∃∃∃ hai phần tử trung hòa ñược ký hiệu là 0 và 1

A + 0 = A

A*1= A

: 5. ∀∀∀∀A∈∈∈∈X, ∃∃∃∃ phần tử bù của A, ñược ký hiệu là

A

++++

====

1AA

====

0A*A

3

Bài giảng môn Kỹ thuật ðiện tử C GV: Lê Thị Kim Anh

Tập (X,+,*,0,1, NOT) thỏa 5 tiên ñề sẽ hình thành nên cấu trúc ñại số Boole.

II. CÁC ðỊNH LÝ

ðịnh lý 1 (ðịnh lý ñối ngẫu)

Một mệnh ñề ñược gọi là ñối ngẫu với một mệnh ñề khác khi ta thay thế:

0 ↔↔↔↔ 1; (+) ↔↔↔↔ (.)

Phát biểu ñịnh lý: khi một mệnh ñề ñúng thì mệnh ñề ñối ngẫu của nó cũng ñúng.

ðịnh lý DeMorgan

====++++++++

Bù của một tổng bằng tích các bù:

....B*A...BA

++++++++====

Bù của một tích bằng tổng các bù:

...BA...*B*A

4

Bài giảng môn Kỹ thuật ðiện tử C GV: Lê Thị Kim Anh

ðịnh lym 3: (luật phun ñịnh của phun ñịnh) AA ====

ðịnh lym 4:

A + 1 = 1 A . 0 = 0

Tổng quát:

A + B + C + …..+ 1 = 1 A . B . C . …… . 0 = 0

ðịnh lym 5: (luật ñồng nhất)

A + A = A A . A = A

Tổng quát:

5

Bài giảng môn Kỹ thuật ðiện tử C GV: Lê Thị Kim Anh

A + A + A + … + A = A A . A . A . …. . A = A

ðịnh lym 6: (luật hấp thu hay luật nuốt)

A + ( A . B) = A

A . (A + B) = A

++++

====

ðịnh lym 7: (luật dán)

BA)BA(.A

====

++++

++++

BAB.AA

6

Bài giảng môn Kỹ thuật ðiện tử C GV: Lê Thị Kim Anh

III. CÁC PHƯƠNG PHÁP BIỂU DIỄN HÀM BOOLE

1. Phương pháp ñại sôm

Hàm Boole ñược biểu diễn dưới dạng một biểu thức ñại sôm của các biến boole (biến nhix phân), quan hêx với nhau bởi các phép toán cộng(OR), nhân (AND) hay phép lấy bu{ (NOT).

Với các giam trị cho trước của các biến, hàm Boole có thên có giam trị 1 hoặc 0.

++++

Ví du(cid:27) :

==== zxyx)z,y,x(F

7

Bài giảng môn Kỹ thuật ðiện tử C GV: Lê Thị Kim Anh

MSB

2. Phương pháp bảng chân trị ðên biểu diễn hàm Boole dưới dạng bảng chân trị, ta liệt kêx một

danh sách 2n tôn hợp các giam trị 0 va{ 1 của các biến Boole va{ một

cột chỉ ra giam trị của hàm F.

A B C

F

Ví du(cid:27):

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

8

Bài giảng môn Kỹ thuật ðiện tử C GV: Lê Thị Kim Anh

3. Phương pháp dạng chính tắc và dạng chuẩn Minterm (Tích chuẩn): là tích số của ñầy ñủ các biến ở dạng bù hay không bù. Nếu giá trị của biến là 0 thì biến sẽ ở dạng bù, còn nếu giá trị của biến là 1 thì biến sẽ ở dạng không bù. Với n biến có thể tạo ra 2n minterm. Minterm ñược ký hiệu là mi, với i là tổ hợp nhị phân tạo bởi giá trị các biến.

minterm

A B Ví dux: Biểu thức

0 0

A B

Ky(cid:30) hiệu m0

1 0

A B

1 0 m1 m2

A B

1

A B

9

Bài giảng môn Kỹ thuật ðiện tử C GV: Lê Thị Kim Anh

1 m3

Maxterm (tổng chuẩn): là tổng số của ñầy ñủ các biến ở dạng bù hay không bù. Nếu giá trị của biến là 1 thì biến sẽ ở dạng bù, còn nếu giá trị của biến là 0 thì biến sẽ ở dạng không bù.

Với n biến có thể tạo ra 2n Maxterm.

Maxterm ñược ký hiệu là Mi, với i là tổ hợp nhị phân tạo bởi giá

trị các biến.

Maxterm

A B Ví dux: Ky(cid:30) hiệu

Biểu thức BA ++++ 0 0 M0

0 1

BA ++++

1 0 M1 M2

BA ++++

1 1 M3

BA ++++

10

Bài giảng môn Kỹ thuật ðiện tử C GV: Lê Thị Kim Anh

Dạng chính tắc 1: là dạng tổng của các tích chuẩn (SOP – Standard Sum-Of-Products) làm cho hàm Boole có giá trị 1.

F(x, y, z) =

zyx

zyx++++

zyx++++

zyx++++

zyx++++

= m1 + m2 + m5 + m6 + m7 = ΣΣΣΣm(1, 2, 5, 6, 7)

= ΣΣΣΣ(1, 2, 5, 6, 7)

F(x, y, z) =

++++++++ )zyx(

++++++++ )zyx( . M3

++++++++ )zyx( . M4

= ΠΠΠΠ(0, 3, 4) = M0 = ΠΠΠΠM(0, 3, 4)

x y z 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 F 0 1 1 0 0 1 1 1

11

Bài giảng môn Kỹ thuật ðiện tử C GV: Lê Thị Kim Anh

Dạng chính tắc 2: là dạng tích của các tổng chuẩn (POS – Standard Product-Of-Sums) làm cho hàm Boole có giá trị 0.

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)

12

Bài giảng môn Kỹ thuật ðiện tử C GV: Lê Thị Kim Anh

= (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

13

Bài giảng môn Kỹ thuật ðiện tử C GV: Lê Thị Kim Anh

= ΠΠΠΠ(1, 2, 3, 6, 7)

Ghi chú: Bù của minterm là Maxterm và ngược lại.

m ====

M ====

i M

i

i m

i

Ví dux chứng minh:

m7 của hàm 3 biến: ABC

++++

B

C

m 7 ==== ABC ==== ++++ A 7M====

14

Bài giảng môn Kỹ thuật ðiện tử C GV: Lê Thị Kim Anh

TRƯỜNG HỢP TÙY ðỊNH

====

)1(d)2,0(

)B,A(F

Trong thực tế có những trường hợp một vài tổ hợp nhị phân của các biến là không xảy ra. Do ñó, giá trị của hàm tương ứng với những tổ hợp nhị phân này có thể là 0 hay 1 ñều ñược, người ta gọi ñó là những trường hợp tùy ñịnh (don’t care, viết tắt là d). Khi ñiền vào bảng chân trị những trường hợp tùy ñịnh, ta dùng ký hiệu X. Ví du(cid:27):

1 X 1

A 0 0 1 1

∑∑∑∑ ++++ B F 0 1 0 1

15

Bài giảng môn Kỹ thuật ðiện tử C GV: Lê Thị Kim Anh

0

4. Phương pháp bìa KARNAUGH

Bìa K cho hàm 2 biến

F(A,B)

A

0 1 B

MSB

10 00 0

2 0

11 01 1

16

Bài giảng môn Kỹ thuật ðiện tử C GV: Lê Thị Kim Anh

1 3

Bìa K cho hàm 3 biến

A f(A,B,C) AB

11 00 01 10 MSB C

000 010 110 100 0

0 4 2 6

101 001 011 111 C 1

1 5 3 7

17

Bài giảng môn Kỹ thuật ðiện tử C GV: Lê Thị Kim Anh

B

Bìa K cho hàm 4 biến

f(A,B,C,D) A

AB

00 01 10 11 CD

00 0 8 4 12

1 9 5 13 01

D

11 3 11 7 15

C

10 2 10 6 14

18

Bài giảng môn Kỹ thuật ðiện tử C GV: Lê Thị Kim Anh

B

Bìa K cho hàm 5 biến

A = 1 A = 0

F BC

00 01 11 10 10 01 00 11 DE

00 0 4 12 8 24 28 20 16

1 5 13 9 25 29 21 17 01

11 3 7 15 11 27 31 23 19

19

Bài giảng môn Kỹ thuật ðiện tử C GV: Lê Thị Kim Anh

10 2 6 14 10 26 30 22 18

Cách ñiền vào bìa K 1. Nếu hàm F ñược biểu diễn dưới dạng chính tắc 1 (dạng ∑∑∑∑) thi{ ta ñiền giam trị 1 vào các ô có sôm thưm tưx tương ứng với các minterm (tích chuẩn), ñiền X vào các ô ứng với các trường hợp tùy ñịnh va{ ñiền 0 vào các ô còn lại.

====

++++ )7,4(d)6,3,1,0(

Ví dux: Ta có thên chỉ ñiền vào bìa K hai kym hiệu 0 va{ X, hoặc 1 va{ X. Các ô bon trống ñược ngầm hiểu. ∑∑∑∑

)C,B,A(F F

AB

00 01 11 10

C

0

1

0

X

1 0 2 6 4

1

1

1

X

0

1 3 7 5

20

Bài giảng môn Kỹ thuật ðiện tử C GV: Lê Thị Kim Anh

2. Nếu hàm F ñược biểu diễn dưới dạng chính tắc 2 (dạng ∏∏∏∏) thi{ ta ñiền giam trị 0 vào các ô có sôm thưm tưx tương ứng với các Maxterm (tổng chuẩn), ñiền X vào các ô ứng với các trường hợp tùy ñịnh va{ ñiền 1 vào các ô còn lại.

Ta có thên chỉ ñiền vào bìa K hai kym hiệu 0 va{ X, hoặc 1 va{ X. Các ô bon trống ñược ngầm hiểu.

)D,C,B,A(F

)11,7,1(D).15,14,12,6,4,3(

∏∏∏∏====

F

Ví dux:

AB

00 01 11 10

CD

00

1

0

0

1

01

1

1

1

X

X

0

X

11

0

1

1

0

0

10

21

Bài giảng môn Kỹ thuật ðiện tử C GV: Lê Thị Kim Anh

3. Nếu hàm F ñược biểu diễn dưới dạng bảng chân trị thi{ ta ñiền 0, 1 hoặc X vào các ô có tôn hợp nhix phân trùng với tôn hợp nhix phân của bảng chân trị.

F Ví dux: AB

00 01 11 10 C

A

B

C

F

0

1

X

1

0

0

0

1

1

1

X

0

0

1

X

0

1

0

X

F AB

0

1

1

0

00 01 11 10 C

1

0

0

1

0

0

X

1

0

1

0

0

1

0

1

1

0

0

X

1

1

1

1

22

Bài giảng môn Kỹ thuật ðiện tử C GV: Lê Thị Kim Anh

====

++++

4. Nếu hàm Boole ñược cho dưới dạng chuẩn 1.

DCBA)D,C,B,A(F

++++DCB

DC

++++DBA

0011

0111

0101

XX11

1110

X101

1011

0100

1101

01X0

1111

0110

F

AB

00 01 11 10

CD

00

1

01

1

1

11

1

1

1

1

10

1

1

23

Bài giảng môn Kỹ thuật ðiện tử C GV: Lê Thị Kim Anh

====

++++++++++++

++++

5. Nếu hàm Boole ñược cho dưới dạng chuẩn 2.

)D,C,B,A(F

B)CA)(DCBA(

1000

0100

X0XX

1001

1X0X

1100

0000

1101

F

AB

0001

00 01 11 10

CD

0010

00

0

0

0

0

01

0

0

0

11

0

0

0011 1000 1001 1010 1011

10

0

0

24

Bài giảng môn Kỹ thuật ðiện tử C GV: Lê Thị Kim Anh

IV. GIỚI THIỆU CÁC CỔNG LOGIC

1. Cổng NOT (ðảo, Inverter)

A F Kym hiệu cổng:

Hàm logic:

AF =

Bảng chân trị:

A F

25

Bài giảng môn Kỹ thuật ðiện tử C GV: Lê Thị Kim Anh

0 1 1 0

2. Cổng AND

A

F Kym hiệu cổng:

B

BAF ====

∧∧∧∧==== BAF

B&AF ====

Hàm logic: ••••==== BAF

Bảng chân trị:

A B F

X....XXF= 1 n

2

Tổng quát Cổng AND có n ngo‘ vào

26

Bài giảng môn Kỹ thuật ðiện tử C GV: Lê Thị Kim Anh

0 0 1 1 0 1 0 1 0 0 0 1

3. Cổng NAND

A

F Kym hiệu cổng:

B

•= BAF

Hàm logic:

Bảng chân trị:

X....XXF= 1 n

2

A B F Tổng quát Cổng NAND có n ngo‘ vào

27

Bài giảng môn Kỹ thuật ðiện tử C GV: Lê Thị Kim Anh

0 0 1 1 0 1 0 1 1 1 1 0

4. Cổng OR

A

F Kym hiệu cổng:

B

B|AF ====

∨∨∨∨==== BAF

Hàm logic: ++++==== BAF

Bảng chân trị:

=

+

++

XXF 1 2

X.... n

A B F Tổng quát Cổng OR có n ngo(cid:30) vào

28

Bài giảng môn Kỹ thuật ðiện tử C GV: Lê Thị Kim Anh

0 0 1 1 0 1 0 1 0 1 1 1

5. Cổng NOR

A

F Kym hiệu cổng:

B

Hàm logic:

++++==== BAF

Bảng chân trị:

=

+

++

XXF 1 2

X.... n

A B F Tổng quát Cổng NOR có n ngo‘ vào

29

Bài giảng môn Kỹ thuật ðiện tử C GV: Lê Thị Kim Anh

1 0 0 0 0 1 0 1 0 0 1 1

6. Cổng EXOR (XOR – Exclusive OR)

A

F Kym hiệu cổng:

B

====⊕⊕⊕⊕====

++++

Hàm logic:

BABABAF

Bảng chân trị:

A B F

Lưu ý Cổng XOR chỉ có 2 ngo‘ vào

30

Bài giảng môn Kỹ thuật ðiện tử C GV: Lê Thị Kim Anh

0 0 1 1 0 1 0 1 0 1 1 0

7. Cổng EXNOR (XNOR – Exclusive NOR)

A

F Kym hiệu cổng:

B

====⊕⊕⊕⊕====

++++

Hàm logic:

BABABAF

Bảng chân trị:

A B F

31

Bài giảng môn Kỹ thuật ðiện tử C GV: Lê Thị Kim Anh

0 0 1 1 0 1 0 1 1 0 0 1