Kỹ thuật số 1 (Nguyễn Như Anh).pdf

Kỹ thuật số 1 (Nguyễn Như Anh).pdf Kỹ thuật số 1 (Nguyễn Như Anh).pdf Kỹ thuật số 1 (Nguyễn Như Anh).pdf Kỹ thuật số 1 (Nguyễn Như Anh).pdf Kỹ thuật số 1 (Nguyễn Như Anh).pdf

Chuong I HE THONG SỐ DEM

LL, Bi@u didn 86 oo ccccecccescsescesssesseeceesasesassseseeesceeeenesesessscseessensnteces 7

1.2 Các loại mã thông dụng HH 11

1.8 Các phép tính trong hệ nhị phân - - c2 "¬ 15

1.4 Cộng trừ số BCD che tre 21

BÀI TẬP TH HH Hee hoa 24

Chuong II DAI SO BOOLE , 27

2.1 Các định nghĩa cơ bản về tập hợp chen 27

2.2 Các tiên để của đại số Boole .c.ccccccccccesesssssssessestsetesessesseeeesnees 28

2.3 Các định lý cơ bản của đại số Boole 29

2.4 Các phần tử logic cơ bản 2H re 30

P0: 8 4A4 34

-9.6 Các phương pháp biểu diễn ham Boole 36

2.7 Các phương pháp tối thiểu hóa hàm Boole 42

3.8 Mach tao và kiểm tra chẵn lẻ ác ncrtiirerrirrree 82

Chương IV HỆ DÃY (Hệ tuần tự) 85

4.1 Khái niệm . - Sàn HH HH HT như 85

4.2 Các phần tử cơ bản của hệ tuần tự 88

4.4 Hệ ghi dịch -

4.5 Hệ tuần tự có đầu vào bosseseeese TH re 125

Chuong V CAC MACH LOGIC LAP TRINH 130

5.1 Bộ nhớ cố định RƠM -. -ceheerrrrrrrtrrrrtrtdrtrrtrdrr 130

5.2 Bộ nhớ linh hoạt RAM kh ttrhrtrtriertetrttrrrttrtrtrttrtrtttrtrie 137

(BAL PAL ieeeeeeererreereerrrrrrerrrrdrrtrrrerterndrrrererrire 141

Chương VI VI MẠCH SỐ VÀ VẤN ĐỀ GIAO TIẾP 144

6.1 Phân loại ` 144

6.2 Giao tiếp giữa các loại vi mạch SỐ sen _ 154

S a ©.- ede a ®, E

Ngày nay uới sự phát triển mạnh mẽ của khoa học kỹ thuật, các mạch số đã trở thành cơ sở của các hệ thống đo lường, điều khiển, cấu trúc máy tính cũng nhụ các hệ thống thông tin hiện đại Những tiến bộ lớn uễ công nghệ trong kỹ thuật điện tử cho phép tạo ra cde vi mach sé uới mức độ tích hợp cao, điều này mớ ra nhiêu' khả năng cho các loại mach số khác nhau Đây chính là cơ sở cho uiệc phát triển các thiết bị

số trong nhiều lĩnh uực

Sau nhiều năm giảng dạy hỹ thuật số, chúng tôi rút hinh nghiệm 0à biên soạn một giáo trình có hệ thống dùng làm tài liệu học tập chính cho môn KỸ THUẬT SỐ 1 được giảng dạy cho sinh uiên ngành Kỹ thuật điện, Tự động uà Điện tử oiễn thông ,

Quyển sách KỸ THUẬT SỐ 1 gồm 6 chương tập trung uào các uấn đề:

- Các hệ thống số đếm va mã số học

- Các lý thuyết cơ sở uễ đại số logic

- Hệ tố hợp ,

- Hệ tuân tự

- Cae mach logic lap trinh va cde vdn dé vé giao tiép

Quyến sách này được biên soạn nhằm đáp ứng yêu câu 0ê giảng dạy

cũng như tự học của sinh oiên trong hệ tín chi Chúng tội rất mong các bạn trong cũng như ngoài ngành góp ÿ hiến để chúng tôi có điều kiện

sửa chữa tài liệu hoàn hảo hơn

Tac gid Tién si NGUYEN NHU ANH

Chuong I

HE THỐNG SỐ DEM

1.1 BIỂU DIỄN SỐ

Hệ thống số đếm là tập hợp những ký tự và quan hệ giữa các ký tự

để biểu diễn số Trong thực tế tôn tại hai loại hệ thống số đếm:

- Loại vị trí: giá trị của số tùy thuộc vị trí các ký tự biểu diễn số

- Loại không có vị trí Loại này không phổ biến nên chúng ta sẽ không

để cập tới sau này

Trong cuộc sống hàng ngày chúng ta quen sứ dụng hệ thống số thập phân (decima) Tuy nhiên trong các thiết bị số nói chung thường

sử dụng hệ nhị phân (binary), hé bat phan (octal) va thập lạc phân (hexadecimal) Vi du vé các hệ thống số này cho trên bảng 1.1

FO sẽ

Các hệ thống số đếm được phân biệt với nhau bằng cơ số của hệ

Cơ số là số lượng ký tự phân biệt trong một hệ đếm Mỗi ký tự biểu điễn một chữ số Ví dự, trong hệ nhị phân cơ số là 2 tương ứng với hai chữ số: 0 và 1 Hệ bát phân có cơ số bằng 8 tương ứng với các chữ số 0,

1, 2, 3, 4, 5, 6, 7 Còn hệ thập phân với cơ số bằng 10 có mười chữ số từ

Biểu thức (1.1) cho phép đổi các số ở bất kỳ hệ nào sang hệ thập

: Trong số của chữ số trong một hệ đếm đặc trưng cho vị trí của chữ

số đó nằm trong day ký tự biểu diễn số Trong biểu thức (1.1) các số si

- Phân phân: lấy phần phân nhân cho cơ số 8, ghi lại phần nguyên -

của kết quả, còn phần phân của nó lại tiếp tục nhân cho 8 Lặp lại phép

nhân nhiều lần cho tới độ chính xác mà ta muốn Phần phan trong hé

cơ số 8 sẽ là tập hợp các phần nguyên của phép nhân, trong đó số đầu tiên có trọng số lớn nhất

Vi dy: đổi 13.68751ạ sang hệ nhị phân

Kết quả chuyển đổi 13.6875,) = 1101101) ©

Vi dụ: đổi 153.513 sang hệ bát phân

Kết quả chuyển đổi 153.513,9 = 23140651 g

Sự chuyển đổi giữa các hệ thống số đếm khác nhau giữ vai trò quan

trọng trong máy tính số Chúng ta biết rằng 2 =8 và 2' =16 từ bảng

mã các hệ thống số đếm (1.1) có thể nhận thấy mỗi chữ số trong hệ bát

phân tương đương với nhóm ba chữ số trong hệ nhị phân và mỗi chữ số

trong hệ thập lục phân tương đương với nhóm bốn chữ số trong hệ nhị

phân Do đó ngoài những quy tắc đổi đã nêu trên, người ta có thể đổi số

trên cơ sở dùng hệ nhị phân làm phép biến đổi trung gian

Để đổi một số từ hệ nhị phân sang hệ bát phân trước hệt phải gom

các số thành nhóm gồm ba chữ số tính từ dấu chấm ngăn cách phần nguyên và phần phân Mỗi nhóm này được thay thế bằng một chữ số

kết quả biến đổi là: 156.3;

Một số ví dụ khác đổi số nhị phân sang hệ bát phân:

phân cách giữa phần nguyên và phần phân Mỗi nhóm này sau đó được

thay thế bằng một chữ số hệ thập lục phân theo bảng mã (1.1)

Ví dụ: đổi 111101011010.01012 sang hệ thập luc phan

1111 0101 1010 0101

mm Ww Ww

Kết quả biến đổi F5A.5 s

Bằng cách biến đổi như trên có thể nhận được kết qua biến đổi của các ví dụ sau: 1000 1100 111¿ = 8C.Es

`—_.o*_`~

1 1101 1011 1010 10012 = 1DB.A9¡s

wy KM KY `“

1 D B A 9

Đổi một số hệ bát phân hay hệ thập lục phân sang hệ nhị phân

được thực hiện theo quy trình ngược lại, nghĩa là mỗi chữ số trong hệ

bát phân được thay thế bằng ba chữ số nhị phân và tương tự mỗi chữ số trong hệ thập lục phân được thay thế bằng bốn chữ số nhị phân

5B1.ADH có nghĩa là ðB1.A Dịa

1.2 CÁC LOẠI MÃ THONG DUNG

Với từ mã nhị phân n chữ số có thể dùng để mã hóa cho 2” phan

tử tin tức Trong cuộc sống hàng ngày chúng ta thường quen sử dụng hệ

- thập phần Tuy nhiên để máy tính có thể thao tác được các hệ đếm đều phải chuyển về hệ nhị phân Các loại mã trong thực tế rất đa dạng,

người ta phân biệt chúng theo nhóm mã ký tự và nhóm mã số học

Các loại mã ký tự dùng để mã hóa các ký tự như:

- Ma ASCII (American Standard Code for Information Interchange):

mỗi ký tự được mã hóa bằng 8 bit nhị phân

- Ma EBCDI (Extended Binary Coded Decimal Interchange): mỗi ký

tự cũng được mã hóa bằng 8 bit nhị phân

- Mã BAUDOT thường dùng trong bưu điện Mỗi ký tự được mã hóa

bang 5 bit nhị phân

Các loại mã số học dùng để mã hóa các sô như mã nhị phân, mã

Mã nhị phân là loại mã có trọng số, trọng số các bit được sắp xếp

thứ tự từ thấp tới cao là 1, 2, 4, 8,

Mã quá 3 được tạo thành từ mã nhị phân bằng cách cộng mỗi giá trị mã nhị phân với 0011 (tương ứng với 3 hệ thập phân)

Mã Gray là loại mã không có trọng số Hai tổ hợp mã kế cận của

bộ mã Gray chỉ khác nhau một bit

Ma thap phan héa BCD (Binary Coded Decimal): mỗi chữ số thập

phân từ 0 đến 9 được mã hóa bằng một tổ hợp mã bốn hoặc năm bit

Mã BCD thường (normai): dùng mười tổ hợp đầu tiên của bộ mã nhị phân bốn bit để mã hóa các chữ số thập phân Loại mã này còn có tên gọi BCD 8-4-2-1, trong đó 8, 4, 2, 1 là trọng số các bit từ cao xuống thấp (bang 1.3)

Ngoài ra cũng có thể tạo mã BCD từ các loại mã mà trọng số các

bit không theo thứ tự vị trí như 3321, 3521, 7421, 5421, 5211, Trên

bảng 1.4 là các loại mã BCD bốn bít

12

Bang 1.4

năm bit Việc thêm bit thứ năm cho phép phát hiện và sửa sai trong

tá trình truyền số liệu Bảng 1.5 liệt kê một số bộ mã năm bit

Mã 51111 là mã trọng số, năm tổ hợp đầu của bộ mã là bù - 1 của

năm tổ hợp sau Đặc điểm nổi bật của mã 51111 là rất dé giải mã bằng

cổng logic

13

Mã 63210 cũng là mã trọng số, ngoại trừ tổ hợp mã tương ứng với 0

của hệ thập phân Trọng số theo thứ tự từ cao tới thấp là 6, 3, 3, 1, 0

Đặc điểm của loại mã này là trong mỗi tổ hợp mã số lượng các chữ số l luôn bằng 9, đặc điểm này rất có lợi cho việc phát hiện và sửa sai khi

truyền số liệu

Mã 9 trong 5 không phải mã trọng số Loại mã này thường được sử dụng trong kỹ thuật điện thoại và thông tin Cũng như mã 63210, trong mỗi tổ hợp mã 2 trong 5 luôn có hai chữ sé bang.1

Mã đohnson cũng không phải là mã trọng số Nó thường được ứng dụng trong các bộ đếm Cũng như mã 51111, ma Johnson rat dé giải mã

Mã Diamond có năm tổ hợp đầu là bù-1 của năm tổ hợp sau

Mã kiểm tra lẻ có bốn bit thấp là những bit mang thông tin, riêng bit lớn nhất được thêm vào sao cho số lượng các chữ số 1 trong từ mã là một số lẻ Để có thể xác định vị trí sai trong các mã kiểm tra lẻ để sửa _sai, cần gửi thêm một thông tin để kiểm tra tính lẻ theo các cột Muốn

vậy người ta thường đặt bộ mã thành một ma trận mà các hàng là các

tổ hợp mã chứa cả bit kiểm tra lẻ Dọc theo các cột người ta thêm một bit để kiểm tra tính lẻ của tổng số các chữ số 1 trong một cột

Giao điểm của hàng và cột sai chỉ ra vị trí của bit sai

8 : 01000

7 : 00111

3 :_ 10011

bit kiểm tra cột : 011010

Để truyền nhóm số (9, 8, 7, 3) người ta truyền đi nhóm mã tương

ứng (11001, 01000, 00111, 10011, 011010), trong đó có tổ hợp mã dài

n + 1 = 6 chữ số để phân biệt với các tổ hợp mã khác và được sử dụng

để kiểm tra tính lẻ của các cột trong ma trận mã

Khi đã phát hiện được vị trí bit sai sửa lại bằng cách lấy đảo bịt

1.3 CAC PHEP TINH TRONG HE NH] PHAN

Các số nhị phân được thao tác giống như với các số thập phân, điều khác biệt cơ bản là cơ số của hệ nhị phân bằng 2 Do đó việc tính toán

số nhị phân đễ hơn rất nhiều Chúng ta sẽ xem xét các phép cộng, trừ,

nhân, chia

Trong hệ nhị phân, mỗi chữ số được gọi là một bịt Số nhị phân n bit biểu diễn được 2? giá trị khác nhau tương ứng từ 0 đến 2"- 1 trong

hệ thập phân Bit có trọng số lớn nhất ký hiệu MSB (Most Significant

Bit) va bit cé trong sé nhé nhat LSB (Least Significant Bit)

MSB LSB

8 bit tạo thành 1 Byte

1 KByte (KiloByte) = 2'° Byte = 1024 Byte

1 MByte (MegaByte) = 210 KByte = 220 Byte

Khi tiến hành trừ hai số một bit có thể xây ra bốn khả năng như sau:

_ Số bị trừ Số trừ Hiệu Số mượn (borrow)

Phép trừ thực hiện thông qua phép cộng chúng ta sẽ xem xét ở các

ví dụ đối với số có dấu

Số bù ~L

Bù —-1 của số nhị phân là một số khi cộng với số nhị phân đã cho

thì tổng bằng 1 ở tất cả các bit Để tìm bù —1 của một số nhị phan bat

1 Cộng trừ số biểu diễn bằng ký hiệu bù -1 „

Số có dấu được biểu điễn bằng ký hiệu bù ~1 theo quy tắc sau:

- Bit lớn nhất (MSB) là bit đấu, trong đó 0 là số đương và 1 là số âm

- Các bít còn lại biểu diễn trị thực của số đương hoặc trị bù —1 của

Phép trừ được thay thế bằng phép cộng, trong đó số bị trừ cộng với bù-

1 của số trừ, số nhớ của bit lớn nhất nếu có sẽ được cộng vào bit nhỏ nhất

17

2 Cộng trừ số biểu diễn bằng ký hiệu bù -2

Biểu diễn số có đấu bằng ký hiệu bù ~2 được thực hiện như sau:

- Bit lớn nhất (MSB) là bit đấu Số dương có bit dấu bằng 0 và số

âm có bit đấu bằng 1

- Các bit còn lại biểu điễn trị thực của số dương hay trị bù ~2 của

sô âm "

- Số có dấu n bit biểu diễn các giá trị từ (2°1~ 1) đến -(2""1)

Ví dụ, các số có dấu 4 bit biểu diễn bằng ký hiệu bù -2:

Phép cộng hai số n bit được thực hiện như cộng hai số nhị phân

không dấu, kể cả bit dấu Cần lưu ý: bit có trọng số 2” trong kết quả bị

Thực hiện phép cộng bằng ký hiệu bù ~2 bốn bit:

-4 : „1100

-5 1011

Kết quả của phép tính là +7 thay vì -9 Ở ví dụ này kết quả sai vì

-9 nằm ngoài phạm vi biểu diễn của số có dấu 4 bit Bây giờ chúng ta lặp lại phép tính trên nhưng bằng ký hiệu bù —2 nam bit:

Phép nhân Trong hệ nhị phân phép nhân được thực hiện tương tự như ở hệ

thập phân, trong đó thừa số thứ nhất sẽ được dich bit sang trái tùy theo

vị trí mỗi bit trong thừa số thứ hai Nhân hai bit nhị phân rất đơn giản

vì kết quả chỉ có thể là 1 hoặc 0 Xét ví dụ sau đây:

Đối với số có dấu phép nhân cũng được thực hiện bằng cách dịch

“bit sang trái và cộng giống như số không dấu, tuy nhiên cần lưu ý

những điểm sau:

- Trong quá trình cộng nếu bit lớn nhất của thừa số thứ nhất có trọng số thấp hơn bit lớn nhất của thừa số thứ hai thì phải thêm bit

đấu cho thừa số thứ nhất

- Khi nhân bit dấu của thừa số thứ hai thì nếu bit dấu bằng 1 phải

cộng trị bù -2 của thừa số thứ nhất

Sau đây là một số ví dụ thực hiện trên số biểu diễn bằng ký hiệu

bù -2, khi thực hiện cộng đồn bỏ carry của bit lớn nhất

Vidu: -8 1101

-15 thêm bit ddu > + 11101

0000 thêm bịt dấu — + 111101

Pháp chia số có đấu được thực hiện giống số không dấu tuy có một

số điểm khác như sau:

- Nếu số bị chia và số chia cùng đấu thì kết quả phép chia là đương,

ngược lại hai số khác dấu cho kết quả âm

_ > Bố dư mang đấu của số bị chia

1.4 CỘNG TRỪ SỐ BCD

Khi cộng hai chữ số trong hệ thập phân, nếu kết quả lớn hơn hay bằng 10 thì có số nhớ lên đơn vị cao hơn Ngược lại ở phép trừ nếu số bị

trừ nhỏ hơn số trừ thì phải mượn một chục từ đơn vị cao hơn

Đối với số BCD, mỗi chữ số thập phân được mã hóa bằng 4 bit nhị phân 8421 và được gọi là một decade Mặt khác 4 bit nhị phân có thể

biểu điến được 16 giá trị khác nhau Những điểm khác nhau giữa hệ

thập phân và nhị phân đòi hỏi trong quá trình cộng trừ các số BCD phải hiệu đính lại kết quả

21

Phép cộng A + B = S

Trong phép cộng, các số nhớ của đecade thấp được chuyển lên decade cao hơn cùng với việc hiệu đính lại đecade thấp Ngoài ra nếu , bat ky decade nao của tổng có trị số lớn hơn 9 hay số nhớ bằng 1 cũng phải hiệu đính Phép hiệu đính được thực hiện bằng cách cộng thêm 6

Ở ví dụ này sau khi thực hiện phép cộng ta thay decade S, lớn hơn

9 nén phai hiéu dinh bằng cách cộng thêm với 6

Trường hợp A > B kết quả phép trừ là dương

vào với đecade cao hơn, còn số nhớ của đecade cao nhất bị loại bỏ

đương 16 Số nhớ của decade thấp khi hiệu đính bỏ ,

Trường hợp A < B kết quả phép trừ âm

Sau khi lấy bù kết quả sẽ là 0000 1000

Ở đây số nhớ của decade cao Ơ¡ =0, số nhớ của decade thấp Cọạ =1

Phải hiệu đính đecade thấp Dạ bằng cách trừ 10 (hay cộng 6 theo

nguyên tắc bù —2) Do kết quá là âm nên phải lấy bù kết quả để đọc giá

_ Sau khi lấy bù kết quả sẽ là 00010010

Trong trường hợp này số nhớ của decade cao Ci và số nhớ của decade thấp C, đều bằng không Kết quả không cần phải hiệu đính Do kết quả là âm nên phải lấy bù kết quả để đọc giá trị thực

Quy tắc cộng trừ hai số BCD tóm tắt trong bảng 1.6, trong đó n là chỉ số

của đecade có trọng số lớn nhất Các decade còn lại có chỉ số từ 0 đến n - 1

23

A-B Dị = A¡ -Bị Hiệu đính D;: Dị =D,+6

C, =0 D, =A, -B, Không hiệu inh D;

BÀI TẬP

1.1 Đổi các số thập phân sau sang dạng nhị phân:

a) 57 b) 0.40625 c) 15/64 = d) 0.865 e) 432.5625 Ð 2048 g) 125 h) 209 i) 132 k) 1435 1) 3489 m) 9714

1.2 Đổi các số thập phân sau sang dạng bát phân:

e) 419.35 f) 634.58 g) 57 h) 0.40625 i) 15/64 k) 0.865 1) 482.5625 m) 2048

1.3 Đổi các số thập phân sau sang hệ thập lục phân: ,

a) 429 b) 1758 2143 d) 57 e) 0.40625 - Ð 15/64 g) 0.865 h) 432.5625

1.7 Đổi các số nhị phân sang hệ bát phân, thập phân và thập lục phân:

d) 10110111, e) 10100.1101, f) 111001010010

g) 101000010011 h) 101100101110 _ i) 1110101101.001

1.8 Đổi các số thập lục phân sang hệ nhị phân và bát phân:

a) 102816 b)BABRI\s c) 9E36.7 Aig

d)7E6Ane - e)C350¡s f DEAD.0AHG

1.9 Đổi các số thập lục phân sang hệ thập phân: -

-a) 2716 b) 3946 c) B4aig d) A2lig

e)5CDis f)4F2.Cjg g) 6B3Eqjs h) 6CEAie

1)EA76Is k)F94Ùùs DEA8S741s m)FEF.B2

1.10 Cộng các số nhị phân sau đây và đánh dấu số nhớ của tất cả các

a) 110101 b) 101110 c)11011101 d) 1110010 e) 1110011

11001 100101 1100011 1101101 101101 1.11 Thực hiện phép trừ đối với các số nhị phân sau và chỉ ra số mượn

1.15 Tự tìm ví dụ để chứng minh: ký hiệu bù ~2 n bit của số x bất kỳ '

khi biểu diễn thành m bit, trong đó m > n thì chỉ cần thêm (m~n) bit

1.16 Thực hiện phép trừ thông qua phép cộng bằng ký hiệu bù —1:

a)1011 b) 1101 c)11010 d) 110101

101 1001 10101 101101

25

1.19 Thực hiện phép cộng đối với các số sau ở dạng mã BCD:

a) 19+59 b) 25+18 c) 68+57 d) 26+55 e) 28438 _ f) 48429 g) 76+54 h) 15+22 1 36+28

1.20 Thực hiện phép trừ đối với các số sau ở dạng mã BCD:

a) 34-81 b) 57-32 c) 37-12 d) 46-58 | e) 97-39

f) 16-40 g) 28-42 h)26-87 i) 61-18

26

Số lượng các phần tử trong tập hợp D và tập hợp trái cây là hữu

hạn nên các tập hợp này được gọi là tập hợp hữu bạn Ngược lại tập

hợp vô hạn có vô số các phần tử, ví dụ tập các số tự nhiên

N = {x:x là số tự nhiên} là vô hạn Phần tử x bất kỳ thuộc tập hợp N

được ký hiệu x e N

Một tập hợp không chứa một phần tử nào được gọi là tập hợp rỗng

và ký hiệu {Ø}

' Tập hợp A chứa một phần hoặc toàn bộ các phần tử của tập hợp B

thì nói A thuộc B và ký hiệu A c B `

Vi du: A= {a,b} B= {abedef} vậy Ac B

Các phép toán trong đại số tập hợp được định nghĩa như sau:

a) Phép giao ký hiệu ¬ Kết quả phép giao giữa các tập hợp là tập

hợp chứa các phần tử có mặt trong tất cả các tập hợp tham gia phép

"toán

Ví dụ: A= {ab,cd,f£k} B= {a,c.d,e,f,h} C= {a,b,e,d,g.h,k}vậy

ANBoCe {acd}, ANB = {acd.f}, BOC = {a,c.d,h}

b) Phép hợp ký hiệu +2 cho kết quả là tập hợp chứa tất cả các phần

tử của các tập hợp tham gia phép toán

Vi du: A = {a,b,c,d,e.f} B= {a,k.l} C = {b,cg,h}

vậy: AoBz{a,b,c.d,ef,kl}, BC = {a,b,c,g.h,k.]}

c) Phép hiệu ký hiệu \ Kết quả phép hiệu giữa hai tập hợp là tập hợp gồm các phần tử của tập hợp thứ nhất không trùng với các phần tử

của tập hợp thứ hai.

Vi du: A= {a.b,d,f,g} B= {bcdef} A\B = {ag}

d) Phép bù Bù của tập hop A (ky hiéu A) cho két qua la mot tap hợp gồm những phần tử không nằm trong A nhưng cùng chứa trong mọt

tập hợp tổng thể nào đó

Ví dụ: cho B = {a,b.c,d.e,f,g.h,¡,kHà một tập hợp tổng thể

- Ai ={a,b,c}, As ={a,d,f,i}, As ={f.h} là các tập hợp thuộc B Phép

bù đối với các tập hợp này cho kết quả như sau:

á ={d,e.f,g,h,i,k}, Ấạ ={b,c.e,g,h,k}, Ãạ ={a.b,c.d,e,g,i,k}

2 2 CÁC TIÊN ĐỀ CUA ĐẠI Số B00LE

Cho một tập hợp nhiều phân ti B = {x,y,z, } Trang bi cho tập

hợp B hai phép toán “+” và “.” Với mọi phần tử x, y, z, thuộc B thỏa

Tiên đê 4 Với mọi phần tử x tổn tại phần tử bù x, sao cho:

- Nếu x là số lượng sinh viên nam gồm 80 người thì sinh viên nữ

biểu điễn bằng biến % gồm 20 người

— Trong lớp có 10 sinh viên deo kính được biểu diễn bằng biến y thì

90 sinh viên mắt tốt được biểu diễn bằng ÿ

- Dùng biến z để chỉ số sinh viên có độ 'tuổi từ 2B trở xuống Nếu

toàn bộ 100 sinh viên đều ở độ tuổi này thì z = 1 Khi đó z là số người

có độ tuổi trên 25, trong trường hợp này Z = 0

Thứ tự ưu tiên các phép toán trong đại số Boole như sau: trước hết

là lấy bù, sau đó là phép nhân logic rồi mới đến phép cộng logic

2.3 CÁC ĐỊNH LÝ CŨ BẢN CỦA ĐẠI SỐ B00LE

Định lý 5 Luật nuốt

X(x+y)=x

_X†XY=Xx , Ching minh: x(x+y)=xx+xy= x+xy= x(lty)= xl=x

Suy ra: (x+y)CA; va: (x+y)+zGA Hay: BoA

-Bằng cách tương tự có thể chứng minh AB Do đó A = B

2.4 CAC PHAN TU LOGIC CO BAN

_Các tín hiệu số thường được xử lý bằng mạch điện tứ Tuy nhiên để mạch điện tử có thể nhận ra các số 0 và 1, các số này phải được biểu

30

diễn dưới dạng mức điện thế Về nguyên tắc các mức điện thế phải rất khác nhau để mạch có thể phân biệt chính xác Ngoài ra tùy theo yêu

cầu về khả năng chống nhiễu của mạch điện tử mà người ta đặt ra

khoảng cách cụ thể về điện thế giữa hai mức logic 1 và 0 Các mức điện thế này cũng có giá trị khác nhau tùy loại mạch logic (TTL, CMOS, ECL hay các loại khác)

Người ta phân biệt ra hai loại logic:

Logie dương: mức điện thế cao tương ứng logic 1, mức điện thế thấp tương ứng logic 0

Logie âm: mức điện thế cao tương ứng logic 0, mức điện thế thấp tương ứng logic 1

Nhu đã nói ở trên, mạch điện tử xử lý trực tiếp các tín hiệu điện thế Khi dùng các mạch điện tử để biểu diễn hàm Boole, trạng thái của mạch được xác định bằng điện thế ngẽ ra Trong các sách tra cứu, mức điện thế cao được ký biệu bằng H và mức thấp là L Cá thé dé dang nhận thấy với mỗi mạch điện tử xác định, nếu đổi cách sử dụng từ logic đương sang âm hay ngược lại thì hàm chức năng của mạch logic có thể

bị thay đổi Ta xét ví dụ sau: bảng chân lý của một mạch logic cho ở

đạng mức điện thế, logic dương và logic âm

Cổng NOT thực hiện lấy bù một bịt nhị phân Hàm chức năng của

cổng NOT có dang: y=

Ham logic cia cổng NOT được diễn tả bằng bảng chân lý 2.1 Ký

"hiệu cổng và giản đồ xung mô tả hoạt động của cổng cho trên H.2.1

81

Với hàm AND nhiều biến ta viết như sau:

1 khi mọi xị đêu bằng 1

Xe

- Hình 2.3 lý hiệu uà giản đỗ xung mình họa cổng OR

0 khi moi x; déu bằng 0

Y=fÍOR(X1,Xa Xn}= XỊ +Xo + + Xa =

ORME AB AE ALEX Foe Ey LH 0

32

' Hình 39.4 Ký hiệu uò giản đô xung mình họa cổng NAND

Hàm NAND nhiều biến được viết như sau:

0 khi mọi x¡ đều bằng 1

y=f (X1,Xa Xp )= X1Xa Xn = -

NANDS2 " 12x n 1 ở các trường hợp khác

Cổng NOR

_—_ Hoạt động của cổng NOR hai ngõ vào xị và xạ được định nghĩa

bằng bảng chân lý 2.5 Hàm chức năng của cổng y=xị +Xa

Hàm NOR nhiều biến được viết như sau: l

1 khi mọi xị đều bằng 0

=f, X1,Xo, Xa )= XỊ + Xg + +Xn =

Y = NOR(.X2 nm + Xe l 0 ở các trường hợp khác

Céng EX.OR (exclusive OR)

Exclusive OR cho phép nhaén biét hai số nhị phân 1 bit nhập ở ngõ

vào có khác nhau hay không Theo bảng chân lý 8.7 có thể thấy nếw-dữ

liệu ở hai ngõ vào bằng nhau thì ngõ ra y = 0, ngược lại khi hai ngõ vào

- Hàm chức năng của cổng EX OR, được viết như sau:

5 88 `

trong đó đấu ® được dùng để diễn tả phép cộng theo modul 2 (còn gọi

là XOR)

Hình 3:6 Ký hiệu uà giản đô xung mình họa cổng EX.OR

Cổng EX.NOR (exclusive NOR)

Exclusive NOR thuc hién so sánh bằng nhau đối với các tín hiệu | vào xị và xạ Hoạt động của cổng EX.NOR được định nghĩa trên bảng chân lý 2.7 Chỉ khi hai tín hiệu vào x, va xg bang nhau tín hiệu ra y

mới bằng #

Biểu thức ngõ ra của a cổng EX.NOR:

, y =xị ®X¿ =X1X¿ +XỊXa

và 0 Hàm Boole được định nghĩa như sau:

Định nghĩa: cho xị,xạ, x› là các biến thuộc tập hợp B Một ánh '_

xạ f của B vào chính bản thân nó gọi là một hàm Boole n biến nếu nó được cấu tạo theo nguyên tắc sau:

a) Hàm hằng số f (x,Xxạ Xa) = a và hàm f(XỊ,Xạ, Xn) = Xị cũng

là các hàm Boole

34

Miền xác định của hàm là tập hợp các tổ hợp biến Với hàm n biến _

thì sẽ có 2” các tổ hợp khác nhau của các biến Mặt khác với một miền

có n biến có thể xác định được 22" hàm khác nhau Ví dụ với loại hàm

một biến có 4 hàm (bảng 2.8), với loại hàm 9 biến có 16 hàm khác nhau

Một vài hàm trong bảng 2.8 có thể mở rộng ra cho trường hợp số biến lớn hơn hai Ví dụ các hàm:

f(X,Xạ, Xụ)=XỊ.Xg Xa ` f1 ŒXỊ.Xạ, Xn ) = XỊ + Xa + +Xn fj(XỊ,Xa, Xạ)= XỊ +Xg + +Xn Í1(X1.Xa Xn )= XỊ.X2 Xn

Những hàm Boole mới có thể được tạo nên từ những hàm Boole

.khác bằng phương pháp xếp chéng Su xếp chồng được thực hiện bằng cách đùng những hàm Boole này làm đối số cho hàm Boole khác, hoặc bằng cách đổi tên đối số của hàm Boole Gó thể làm như vậy vì đối số

cũng như chính hàm Boole chỉ có thể nhận một trong hai giá trị 0 và 1

_ Ví dụ trong bảng 2.9 hàm fịs có thể suy từ hàm fị; bằng cách đổi tôn,

đối số, hàm f¡¿ có thể thu được từ hàm f(x)= bằng cách dùng hàm

f, =x Xp thay cho đối số x.-

35

Đối số Hàm XỊ 0 0 L 1 Ký hiệu hàm Tên hàm

2.6 CÁC PHƯƠNG PHÁP BIỂU DIỄN HÀM B00LE

Biểu điễn hàm bằng bảng giá trị Bảng giá trị còn được gọi là

bảng chân lý, trong đó liệt kê tất cả các giá trị có thể có của tất cả các biến và giá trị tương ứng của hàm Với hàm n biến, có thể có 2" tổ hợp các giá trị khác nhau của các biến Sau đây là bảng giá trị của một số

hàm:

- Hàm đa số f¡ (bảng 2.10) có đặc điểm hàm có trị bằng 1 nếu số

lượng biến bằng 1 nhiêu hơn số lượng biến bằng 0

- Hàm f; chọn ra các số chia hết cho 3 hoặc 5 (bang 2.12) |

- Hàm fạ chọn các số lớn hon 2 với điều kiện xịxaxạ=0, nếu

không thỏa điểu kiện thì hàm có trị không xác định ký hiệu X (bảng

2.11) Trị không xác định là giá trị tùy định, 0 hay 1 đều được

-86

Bang 2.10 Bang 2.11

Hàm được gọi là xác định toàn phần nếu tại mỗi tổ hợp biến hàm

đều có một trị cụ thể (hoặc bằng 1 hoặc bằng 0) Ví dụ ham fj va fo

Hàm được gọi là xác định bộ phận nếu tồn tại một số tổ hợp bién 6

đó hàm không xác định Ví dụ hàm fs

Bia Karnaugh

Toàn bộ miển xác định của hàm được biểu diễn trên một ô vuông

hay chữ nhật Ô này được chia thành 2° ô vuông nhỏ, trong đó n là số

biến của hàm Như vậy số lượng ô bằng với tổng số các tổ hợp trị của

các biến Dọc theo hai cạnh của bìa Karnaugh ghi các tổ hợp trị của các

biến, và phân bố sao cho các tổ hợp liên tiếp nhau chỉ khác trị của một

biến Đây là điểu kiện kế cận để tiến hành rút gọn hàm bằng bìa

Karnaugh sau này Trong mỗi ô nhỏ của bìa Karnaugh ghi trị tương ứng

của hàm Thông thường người ta chỉ đánh dấu các ô hàm bằng 1 và X,

các ô bỏ trống coi như hàm bằng 0 Hoặc cũng có thể chỉ đánh dấu các ô

hàm bằng 0 và X, các ô bổ trống coi như hàm bằng 1 Trên H.2.8 biểu

diễn bìa Karnaugh của cdc ham fj, ƒ2, fạ

37

Biểu diễn bằng biểu thức đợi số Ngoài bảng giá trị và bìa Karnaugh, để xét và so sánh giữa các hàm Boole với nhau người ta có thể dùng biểu thức đại số ở đạng chính tác Nói cách khác: dạng chính tắc của một hàm Boole bất kỳ là biểu thức duy nhất Với một hàm Boole n biến có hai dạng chính tắc sau:

x, néu e; =O

và e=(@,es en) là số nhị phân n ký hiệu

Dạng chính tắc thứ nhất liệt kê các tổ hợp biến mà ở đó hàm có trị bằng 1, trong đó nếu biến bằng 1.viết dang thực và biến bằng 0 viết đạng bù

Mỗi số hạng của tổng trong dạng chính tắc thứ

nhất được gọi là một mintec Ở tổ hợp 0 các biến

X1X9X3=000 nén mintec cia tổ hợp này là

#iX;#a, ở tổ hợp 2 xịxaxạ=010 nên mintec của

nó là 5¡x;%ạ, ở tổ hợp 3 xxaxạ =011 nên mintec là Xxaxs, tổ: hợp £ 5

38

với xịXaxa = 101 tương ứng mintec xịXaxạ, và tổ hợp 7 có xịxaxạ =111

tuorig ứng mintec XịXaXa

Tương tự biểu thức chính tắc thứ nhất của hàm f ¡ có dạng sau đây:

'- fị =ÑjXaXs +X1XoXa +XỊX2Xs +XIX2XS

(3) (5) (6) (7) Dạng chính tắc thứ hai (còn gợi là hội chuẩn toàn phần): là dang

tích của các tổng cơ bản, có thể nhận được bằng cách lấy hàm phủ định

của dạng chính tắc thứ nhất theo quy tắc De Morgan Có thể viết dạng

và e=(e,ea en) là số nhị phân n ký hiệu

Dạng chính tắc thứ hai liệt kê các tổ hợp biến mà ở đó hàm có trị

bằng 0, trong đó nếu biến bằng 0 viết dạng thực và biến bằng 1 viết

dạng bù Mỗi thừa số trong biểu thức chính tắc thứ hai được gọi là một

v6i x,X9X3=001 cé maxtec JA (x, +xg+%3), té hop 2 vdi x1xgx3 =010

tuong ting maxtec (x, +¥g+%3), td hop 4 với xịxaxa =100 tương ứng

Bang 2.14 |

Ví dụ, có thể viết tắt ham f, như sau:

f1(X1.Xa,xạ)= £(011,101,110,111) trong đó mỗi mintec là một trị nhị

phân, hoặc fj(xị.xa,xạ) = Em(3,5.6,7)= >(3.5,6,7) trong đó mỗi mintec là

một trị thập phân và trọng số các biến tương ứng xỊXaXs

4 2 1

Tương tự có thể dùng cách viết tắt bằng cách thay thế các maxtee

bằng số nhị phân hay thập phân tương ứng

Ví du: f4 =7](001,100,110) maxtec 6 dang nhị phân `

fq =T]M(1.4,6)=[0,.4.6) maxtec ở dạng thập phân với trọng

số các biến xỊXaXa

Đối với hàm xác định bộ phận, các tổ hợp biến nơi hàm không xác

định được ký hiệu bằng d hay D Ví dự, hàm fạ có thể biểu dién như

sau:

£3(X1,X2.%3) = Zm(8,4,5,6) + Zd(7)

hay: f3(%1,%2-x3) = XM(0,1,2).IID(7)

Biểu diễn hàm bằng phương pháp hình học

Miền xác định của hàm được chuyển thành không gian n chiều,

trong đó n là số biến của hàm Như vậy mỗi biến đại điện cho một tọa

độ trong không gian và mỗi mintec là một điểm trong không gian đó

Dạng tuyển chuẩn toàn phần của hàm Boole được biểu diễn thành một tập hợp các điểm Biểu diễn hình học của hàm f¿ cho trên H.2.14

40