Bài giảng Kỹ thuật số ứng dụng - Chương 1: Đại số boole

TRѬӠNG ĈҤI HӐC BÁCH KHOA ĈÀ NҸNG

KHOA Ĉ,ӊN TӰ VIӈN THÔNG

----- oOo -----

BÀI GIҦNG

.Ӻ THUҰT SӔꢀӬNG DӨNG

Ĉà Nҹng, 08 / 2006

Chѭѫng 1. Ĉҥi sӕ Boole

Trang 1

Chѭѫng 1

ĈҤI SӔ BOOLE

1.1. HӊꢀĈӂM NHӎ PHÂN VÀ MÃ

1.1.1. HӋ thӕng sӕꢀÿӃm

1. Khái niӋm và phân loҥi hӋꢀÿӃm

+ӋꢀÿӃm là tұp hӧp các phѭѫng pháp gӑi và biӇu diӉn các con sӕ bҵng các kí hiӋu có giá trӏ sӕ

Oѭӧng xác ÿӏnh gӑi là các chӳ sӕ.

Có thӇ chia các hӋꢀÿӃm làm hai loҥi: hӋꢀÿӃm theo vӏ trí và hӋꢀÿӃm không theo vӏ trí.

a. H͏ꢀÿ͇m theo v͓ trí:

+ӋꢀÿӃm theo vӏ trí là hӋꢀÿӃm mà trong ÿó giá trӏ sӕ lѭӧng cӫa chӳ sӕ còn phө thuӝc vào vӏ trí cӫa

nó ÿӭng trong con sӕ cө thӇ.

Ví dͭ: HӋ thұp phân là mӝt hӋꢀÿӃm theo vӏ trí. Sӕ 1991 trong hӋ thұp phân ÿѭӧc biӇu diӉn bҵng

2 chӳ sӕ “1” và “9”, nhѭng do vӏ trí ÿӭng cӫa các chӳ sӕ này trong con sӕ là khác nhau nên sӁ mang

các giá trӏ sӕ lѭӧng khác nhau, chҷng hҥn chӳ sӕ “1” ӣ vӏ trí hàng ÿѫn vӏ biӇu diӉn cho giá trӏ sӕ

Oѭӧng là 1 song chӳ sӕ “1” ӣ vӏ trí hàng nghìn lҥi biӇu diӉn cho giá trӏ sӕ lѭӧng là 1000, hay chӳ sӕ

“9” khi ӣ hàng chөc biӇu diӉn giá trӏ là 90 còn khi ӣ hàng trăm lҥi biӇu diӉn cho giá trӏ là 900.

b. H͏ꢀÿ͇m không theo v͓ trí:

+ӋꢀÿӃm không theo vӏ trí là hӋꢀÿӃm mà trong ÿó giá trӏ sӕ lѭӧng cӫa chӳ sӕ không phө thuӝc vào

Yӏ trí cӫa nó ÿӭng trong con sӕ.

+ӋꢀÿӃm La Mã là mӝt hӋꢀÿӃm không theo vӏ trí. HӋꢀÿӃm này sӱ dөng các ký tӵ “I”, “V”, “X”...

ÿӇ biӇu diӉn các con sӕ, trong ÿó “I” biӇu diӉn cho giá trӏ sӕ lѭӧng 1, “V” biӉu diӉn cho giá trӏ sӕ

Oѭӧng 5, “X” biӇu diӉn cho giá trӏ sӕ lѭӧng 10... mà không phө thuӝc vào vӏ trí các chӳ sӕ này ÿӭng

trong con sӕ cө thӇ.

Các hӋꢀÿӃm không theo vӏ trí sӁ không ÿѭӧc ÿӅ cұp ÿӃn trong giáo trình này.

2. Cѫ sӕ cӫa hӋꢀÿӃm

0ӝt sӕ A bҩt kǤ có thӇ biӇu diӉn bҵng dãy sau:

A= a_m-1a_m-2.....a₀a_-1......a_-n

Trong ÿó a_ilà các chӳ sӕ, (i = - n ¸ m - 1); i là các hàng sӕ, i nhӓ: hàng trҿ, i lӟn: hàng già.

Giá trӏ sӕ lѭӧng cӫa các chӳ sӕ a_isӁ nhұn mӝt giá trӏ nào ÿó sao cho thӓa mãn bҩt ÿҷng thӭc sau:

0 £ a_i£ N - 1

(a_inguyên)

N ÿѭӧc gӑi là cѫ sӕ cӫa hӋꢀÿӃm. &ѫ sӕ cӫa mӝt hӋꢀÿӃm là sӕ lѭӧng ký tӵ phân biӋt ÿѭӧc sӱ

Gөng trong mӝt hӋꢀÿӃm. Các hӋ thӕng sӕꢀÿӃm ÿѭӧc phân biӋt vӟi nhau bҵng mӝt cѫ sӕ N cӫa hӋ

ÿӃm ÿó. Mӛi ký tӵ biӇu diӉn mӝt chӳ sӕ.

Khoa ĈTVT – ĈHBKĈN – Tháng 08.2006

Trang 2

Trong ÿӡi sӕng hҵng ngày chúng ta quen sӱ dөng hӋꢀÿӃm thұp phân (decimal) vӟi N=10. Trong

KӋ thӕng sӕ còn sӱ dөng nhӳng hӋꢀÿӃm khác là hӋꢀÿӃm nhӏ phân (binary) vӟi N=2, hӋꢀÿӃm bát phân

(octal) vӟi N=8 và hӋꢀÿӃm thұp lөc phân (hexadecimal) vӟi N=16.

- HӋ nhӏ phân

- HӋ thұp phân

- HӋ bát phân

: N =2 Þ a_i= 0, 1.

: N =10 Þ a_i= 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.

: N =8 Þ a_i= 0, 1, 2, 3, 4, 5, 6, 7.

- HӋ thұp lөc phân : N =16 Þ a_i= 0, 1, 2, …8, 9, A, B, C,D, E, F.

Khi ÿã xuҩt hiӋn cѫ sӕ N, ta có thӇ biӇu diӉn sӕ A dѭӟi dҥng mӝt ÿa thӭc theo cѫ sӕ N, ÿѭӧc ký

hiӋu là A_(N)

:

A_(N)= a_m-1.N^m-1+ a_m-2.N^m-2+...+ a₀.N⁰+ a_-1.N^-1+ ... + a_-n.N^-n

Hay:

m-1

i

(1.1)

A

=

a N

i

å

(N)

i=- n

9ͣi N=10 (h͏ th̵p phân):

A₍₁₀₎= a_m-1.10^m-1+ a_m-2.10^m-2+....+ a₀.10⁰+...+ a_-n.10^-n

1999,959₍₁₀₎=1.10³+ 9.10²+ 9.10¹+ 9.10⁰+ 9.10^-1+ 5.10^-2+ 9.10^-3

9ͣi N=2 (h͏ nh͓ phân):

A₍₂₎=a_m-1.2^m-1+ a_m-2.2^m-2+...+ a₀.2⁰....+a_-n2^-n

1101₍₂₎= 1.2³+1.2²+ 0.2¹+ 1.2⁰= 13₍₁₀₎

9ͣi N=16 (h͏ th̵p lͭc phân):

A₍₁₆₎= a_m-1.16^m-1+ a_m-2.16^m-2+...+ a₀.16⁰+ a_-116^-1+ ... + a_-n16^-n

3FF₍₁₆₎= 3.16²+ 15.16¹+ 15.16⁰= 1023₍₁₀₎

9ͣi N=8 (h͏ bát phân):

A₍₈₎= a_m-1.8^m-1+ a_m-2.8^m-2+...+ a₀.8⁰+ a_-1.8^-1+ ... + a_-n.8^-n

376₍₈₎= 3.8²+ 7.8¹+ 6.8⁰= 254₍₁₀₎

Nhѭ vұy, biӇu thӭc (1.1) cho phép ÿәi các sӕꢀӣ bҩt kǤ hӋ nào sang hӋ thұp phân (hӋ 10).

3. Ĉәi cѫ sӕ

a. Ĉ͝i tͳ c˯ s͙ d sang c˯ s͙ 10

ĈӇ chuyӇn ÿәi mӝt sӕꢀӣ hӋꢀÿӃm cѫ sӕ d sang hӋꢀÿӃm cѫ sӕ 10 ngѭӡi ta khai triӇn con sӕ trong cѫ

Vӕ d dѭӟi dҥng ÿa thӭc theo cѫ sӕ cӫa nó (theo biӇu thӭc 1.1).

Ví dͭ 1.1

Ĉәi sӕ 1101₍₂₎ꢀӣ hӋ nhӏ phân sang hӋ thұp phân nhѭ sau:

1011₍₂₎= 1.2³+ 0.2²+ 1.2¹+ 1.2⁰= 11₍₁₀₎

b. Ĉ͝i tͳ c˯ s͙ 10 sang c˯ s͙ d

ĈӇ chuyӇn ÿәi mӝt sӕ tӯ cѫ sӕ 10 sang cѫ sӕ d (d = 2, 8, 16) ngѭӡi ta lҩy con sӕ trong cѫ sӕ 10

chia liên tiӃp cho d ÿӃn khi thѭѫng sӕ bҵng không thì dӯng lҥi. KӃt quҧ chuyӇn ÿәi có ÿѭӧc trong

KӋꢀÿӃm cѫ sӕ d là tұp hӧp các sӕ dѭ cӫa phép chia ÿѭӧc viӃt theo thӭ tӵ ngѭӧc lҥi, nghƭa là sӕ dѭ

ÿҫu tiên có trӑng sӕ nhӓ nhҩt. (xem ví dө 1.2)

Chѭѫng 1. Ĉҥi sӕ Boole

Ví dͭ 1.2:

Trang 3

2

13

1023 16

15

1

6

2

3

63 16

2

1

0

3

16

0

15

2

0

1

3

A₍₁₀₎=13 ® A₍₂₎=1101

A₍₁₀₎=1023 ® A₍₁₆₎=3FFH

.Ӄt luұn: Gӑi d₁, d₂, ..,d_nlҫn lѭӧt là dѭ sӕ cӫa phép chia sӕ thұp phân cho cѫ sӕ d ӣ lҫn thӭ 1, 2,

3, 4, .., n thì kӃt quҧ chuyӇn ÿәi mӝt sӕ tӯ hӋꢀÿӃm cѫ sӕ 10 (thұp phân) sang hӋꢀÿӃm cѫ sӕ d sӁ là:

d_nd_n-1d_n-2...d₁,

nghƭa là dѭ sӕ sau cùng cӫa phép chia là bít có trӑng sӕ cao nhҩt (MSB), còn dѭ sӕꢀÿҫu tiên là bít

có trӑng sӕ nhӓ nhҩt (LSB).

Trong các ví dө trên, cѫ sӕ cӫa hӋꢀÿӃm ÿѭӧc ghi ӣ dҥng chӍ sӕ bên dѭӟi. Ngoài ra cǊng có thӇ ký

Wӵ chӳꢀÿӇ phân biӋt nhѭ sau:

B - HӋ nhӏ phân (Binary)

D - HӋ thұp phân (Decmal)

1010B có nghƭa là 1010₍₂₎

37FH có nghƭa là 37F₍₁₆₎

O - HӋ bát phân (Octal)

H - HӋ thұp lөc phân (Hexadecimal)

Ví dͭ:

&

Quy t̷c chuy͋n ÿ͝i giͷa các h͏ꢀÿ͇m c˯ s͙ 2, 8, 16 ?

1.1.2. HӋꢀÿӃm nhӏ phân

1. Khái niӋm

+ӋꢀÿӃm nhӏ phân, còn gӑi là hӋꢀÿӃm cѫ sӕ 2, là hӋꢀÿӃm trong ÿó ngѭӡi ta chӍ sӱ dөng hai kí hiӋu

0 và 1 ÿӇ biӇu diӉn tҩt cҧ các sӕ. Hai ký hiӋu ÿó gӑi chung là bit hoһc digit, nó ÿһc trѭng cho mҥch

ÿLӋn tӱ có hai trҥng thái әn ÿӏnh hay còn gӑi là 2 trҥng thái bӅn cӫa FLIP- FLOP (ký hiӋu là FF).

Trong hӋꢀÿӃm nhӏ phân ngѭӡi ta quy ѭӟc nhѭ sau:

- Mӝt nhóm 4 bít gӑi là 1 nibble.

- Mӝt nhóm 8 bít gӑi là 1 byte.

- Nhóm nhiӅu bytes gӑi là tӯ (word), có thӇ có tӯ 2 bytes (16 bít), tӯ 4 bytes (32 bít), ...

Xét sӕ nhӏ phân 4 bít: a₃a₂a₁a₀. BiӇu diӉn dѭӟi dҥng ÿa thӭc theo cѫ sӕ cӫa nó là:

a₃a₂a₁a_{0 (2)}= a₃.2³+ a₂.2²+ a₁.2¹+ a₀.2⁰

Trong ÿó:

- 2³, 2², 2¹, 2⁰(hay 8, 4, 2, 1) ÿѭӧc gӑi là các trӑng sӕ.

- a₀ꢀ ÿѭӧc gӑi là bit có trӑng sӕ nhӓ nhҩt, hay còn gӑi bit có ý nghƭa nhӓ nhҩt (LSB - Least

Significant Bit), còn gӑi là bít trҿ nhҩt.

- a₃ꢀ ÿѭӧc gӑi là bit có trӑng sӕ lӟn nhҩt, hay còn gӑi là bít có ý nghƭa lӟn nhҩt (MSB - Most

Significant Bit), còn gӑi là bít già nhҩt.

Khoa ĈTVT – ĈHBKĈN – Tháng 08.2006

Trang 4

Nhѭ vұy, vӟi sӕ nhӏ phân 4 bit a₃a₂a₁a₀trong ÿó mӛi chӳ sӕ a_i(i tӯ 0 ÿӃn 3) chӍ nhұn ÿѭӧc hai

giá trӏ {0,1} ta có 2⁴= 16 tә hӧp nhӏ phân phân biӋt.

%ҧng sau ÿây liӋt kê các tә hӧp mã nhӏ phân 4 bít cùng các giá trӏ sӕ thұp phân, sӕ bát phân và sӕ

thұp lөc phân tѭѫng ӭng.

6ӕ thұp phân

a₃a₂a₁a₀

0000

0001

0010

0011

0100

0101

0110

0111

1000

1001

1010

1011

1100

1101

1110

1111

Sӕ bát phân Sӕ thұp lөc phân

0

1

00

01

02

03

04

05

06

07

10

11

12

13

14

15

16

17

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

A

B

C

D

E

F

%̫ng 1.1. Các t͝ hͫp mã nh͓ phân 4 bít

6ӵ 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ã trên có thӇ nhұn thҩy mӛi chӳ sӕ trong hӋ bát phân

Wѭѫng ÿѭѫng vӟi mӝt nhóm ba chӳ sӕ (3 bít) trong hӋ nhӏ phân, mӛi chӳ sӕ trong hӋ thұp lөc phân

Wѭѫng ÿѭѫng vӟi mӝt nhóm bӕn chӳ sӕ (4 bít) trong hӋ nhӏ phân. Do ÿó, khi biӇu diӉn sӕ nhӏ phân

nhiӅu bit trên máy tính ÿӇ tránh sai sót ngѭӡi ta thѭӡng biӇu diӉn thông qua sӕ thұp phân hoһc thұp

Oөc phân hoһc bát phân.

Ví dͭ 1.3: Xét viӋc biӇu diӉn sӕ nhӏ phân 1011111011111110₍₂₎.

3

7

6

3

1

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

B

E

F

E

9ұy, có thӇ biӇu diӉn : 137376₍₈₎theo hӋ bát phân

hoһc : BEFE_(H)theo hӋ thұp lөc phân.

&

Vͣi s͙ nh͓ phân n bít có bao nhiêu t͝ hͫp nh͓ phân khác nhau? Xét tr˱ͥng hͫp s͙ nh͓

phân 8 bít (n=8) a₇a₆a₅a₄a₃a₂a₁a₀có bao nhiêu t͝ hͫp nh͓ phân (tͳ mã nh͓ phân) khác nhau?

2. Các phép tính trên sӕ nhӏ phân

a. Phép c͡ng

Chѭѫng 1. Ĉҥi sӕ Boole

Trang 5

ĈӇ cӝng hai sӕ nhӏ phân, ngѭӡi ta dӵa trên qui tҳc cӝng nhѭ sau:

0 + 0 = 0 nhӟ 0

0 + 1 = 1 nhӟ 0

1 + 0 = 1 nhӟ 0

1 + 1 = 0 nhӟ 1

Ví dͭ 1.4:

3

2

5

®

0011

+

0010

0101 = 1.2²+ 1.2⁰= 5₍₁₀₎

b. Phép trͳ

0 - 0 = 0 mѭӧn 0

0 - 1 = 1 mѭӧn 1

1 - 0 = 1 mѭӧn 0

1 - 1 = 0 mѭӧn 0

Ví dͭ 1.5:

-

7

5

2

®

0111

0101

0010 = 0.2³+ 0.2²+ 1.2¹+ 0.2⁰= 2₍₁₀₎

c. Phép nhân

0 . 0 = 0

0 . 1 = 0

1 . 0 = 0

1 . 1 = 1

Ví dͭ 1.6:

7

5

®

0111

0101

0111

0000

x

35

0111

0000

0100011 = 1.2⁵+ 1.2¹+ 1.2⁰= 35₍₁₀₎

d. Phép chia

0 : 1 = 0

1 : 1 = 1

/˱u ý: Khi chia s͙ chia ph̫i khác 0

Ví dͭ 1.7: 10 5

® 1010 101

101 10₍₂₎= 2₍₁₀₎

00

2

0

Khoa ĈTVT – ĈHBKĈN – Tháng 08.2006

Trang 6

1.1.3. Khái niӋm vӅ mã

1. Ĉҥi cѭѫng

Trong ÿӡi sӕng hàng ngày, con ngѭӡi giao tiӃp vӟi nhau thông qua mӝt hӋ thӕng ngôn ngӳ qui

ѭӟc, nhѭng trong máy tính và các hӋ thӕng sӕ chӍ xӱ lý các dӳ liӋu nhӏ phân. Do ÿó, mӝt vҩn ÿӅꢀÿһt

ra là làm thӃ nào tҥo ra mӝt giao diӋn dӉ dàng giӳa ngѭӡi và máy tính, nghƭa là máy tính thӵc hiӋn

ÿѭӧc nhӳng bài toán do con ngѭӡi ÿһt ra.

Vì các máy tính sӕ hiӋn nay chӍ hiӇu các sӕ 0 và sӕ 1, nên bҩt kǤ thông tin nào dѭӟi dҥng các chӳ

Vӕ, chӳ cái hoһc các ký tӵ phҧi ÿѭӧc biӃn ÿәi thành dҥng sӕ nhӏ phân trѭӟc khi nó có thӇꢀÿѭӧc xӱ

lý bҵng các mҥch sӕ.

ĈӇ thӵc hiӋn ÿLӅu ÿó, ngѭӡi ta ÿһt ra vҩn ÿӅ vӅ mã hóa dӳ liӋu. Nhѭ vұy, mã hóa là quá trình

biӃn ÿәi nhӳng ký hiӋu quen thuӝc cӫa con ngѭӡi sang nhӳng ký hiӋu quen thuӝc vӟi máy tính.

Nhӳng sӕ liӋu ÿã mã hóa này ÿѭӧc nhұp vào máy tính, máy tính tính toán xӱ lý và sau ÿó máy tính

thӵc hiӋn quá trình ngѭӧc lҥi là giҧi mã ÿӇ chuyӇn ÿәi các bít thông tin nhӏ phân thành các ký hiӋu

quen thuӝc vӟi con ngѭӡi mà con ngѭӡi có thӇ hiӇu ÿѭӧc.

Các lƭnh vӵc mã hóa bao gӗm:

- Mã hóa sӕ thұp phân

- Mã hóa ký tӵ

- Mã hóa tұp lӋnh

- Mã hóa tiӃng nói

- Mã hóa hình ҧnh ..v..v..

Phҫn tiӃp theo chúng ta khҧo sát lƭnh vӵc mã hóa ÿѫn giҧn nhҩt là mã hóa sӕ thұp phân bҵng

cách sӱ dөng các tӯ mã nhӏ phân. ViӋc mã hóa ký tӵ, tұp lӋnh, tiӃng nói, hình ҧnh... ÿӅu dӵa trên cѫ

Vӣ mã hóa sӕ thұp phân.

2. Mã hóa sӕ thұp phân

a. Khái ni͏m

ĈӇ mã hóa sӕ thұp phân ngѭӡi ta sӱ dөng các sӕ nhӏ phân 4 bit (a₃a₂a₁a₀) theo quy tҳc sau:

0 ® 0000 ;

1 ® 0001 ;

2 ® 0010 ;

3 ® 0011 ;

4 ® 0100 ;

5 ® 0101

6 ® 0110

7 ® 0101

8 ® 1000

9 ® 1001

Các sӕ nhӏ phân dùng ÿӇ mã hóa các sӕ thұp phân ÿѭӧc gӑi là các sӕ BCD (Binary Coded

Decimal: Sӕ thұp phân ÿѭӧc mã hóa bҵng sӕ nhӏ phân).

b. Phân lo̩i

Khi sӱ dөng sӕ nhӏ phân 4 bit ÿӇ mã hóa các sӕ thұp phân tѭѫng ӭng vӟi 2⁴= 16 tә hӧp mã nhӏ

phân phân biӋt.

Do viӋc chӑn 10 tә hӧp trong 16 tә hӧp ÿӇ mã hóa các ký hiӋu thұp phân tӯ 0 ÿӃn 9 mà trong

thӵc tӃ xuҩt hiӋn nhiӅu loҥi mã BCD khác nhau.

0һc dù tӗn tҥi nhiӅu loҥi mã BCD khác nhau, nhѭng có thӇ chia làm hai loҥi chính: Mã BCD có

tr͕ng s͙ và Mã BCD không có tr͕ng s͙.

Chѭѫng 1. Ĉҥi sӕ Boole

Trang 7

b1. Mã BCD có trӑng sӕ là loҥi mã cho phép phân tích thành ÿa thӭc theo trӑng sӕ cӫa nó. Mã

BCD có trӑng sӕꢀÿѭӧc chia làm 2 loҥi là: mã BCD tӵ nhiên và mã BCD sӕ hӑc.

Mã BCD t͹ nhiên là loҥi mã mà trong ÿó các trӑng sӕ thѭӡng ÿѭӧc sҳp xӃp theo thӭ tӵ tăng

Gҫn. Ví dө: Mã BCD 8421, BCD 5421.

Mã BCD s͙ h͕c là loҥi mã mà trong ÿó có tәng các trӑng sӕ luôn luôn bҵng 9.Ví dө: BCD

2421, BCD 5121, BCD8 4-2-1

Ĉһc trѭng cӫa mã BCD sӕ hӑc là có tính chҩt ÿӕi xӭng qua mӝt ÿѭӡng trung gian. Do

Yұy, ÿӇ tìm tӯ mã BCD cӫa mӝt sӕ thұp phân nào ÿó ta lҩy bù (ÿҧo) tӯ mã BCD cӫa sӕ bù 9

Wѭѫng ӭng.

Ví dͭ xét mã BCD 2421. Ĉây là mã BCD sӕ hӑc (tәng các trӑng sӕ bҵng 9), trong ÿó sӕ 3

(thұp phân) có tӯ mã là 0011, sӕ 6 (thұp phân) là bù 9 cӫa 3. Do vұy, có thӇ suy ra tӯ mã cӫa 6

Eҵng cách lҩy bù tӯ mã cӫa 3, nghƭa là lҩy bù 0011, ta sӁ có tӯ mã cӫa 6 là 1100.

b2. Mã BCD không có trӑng sӕ là loҥi mã không cho phép phân tích thành ÿa thӭc theo trӑng

Vӕ cӫa nó. Các mã BCD không có trӑng sӕ là: Mã Gray, Mã Gray thӯa 3.

Ĉһc trѭng cӫa mã Gray là bӝ mã trong ÿó hai tӯ mã nhӏ phân ÿӭng kӃ tiӃp nhau bao giӡ cǊng chӍ

khác nhau 1 bit.

Còn vӟi mã BCD 8421:

3 ® 0011

Mã Gray: 2 ® 0011

3 ® 0010

Ví dө:

4 ® 0100

4 ® 0110

Các bҧng dѭӟi ÿây trình bày mӝt sӕ loҥi mã thông dөng.

%ҧng 1.2:

Các mã BCD t͹ nhiên.

BCD 8421

BCD 5421

BCD quá 3

6ӕ thұp

phân

0

a₃a₂a₁a₀b₃b₂b₁b₀c₃c₂c₁c₀

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

2

3

4

5

6

7

8

9

Khoa ĈTVT – ĈHBKĈN – Tháng 08.2006

Trang 8

%ҧng 1.3:

Các mã BCD s͙ h͕c

BCD 2421

BCD 5121

BCD 84-2-1

6ӕ thұp

phân

0

a₃a₂a₁a₀b₃b₂b₁b₀c₃c₂c₁c₀

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

2

3

4

5

6

7

8

9

%ҧng 1.4:

BCD 8421

a₃a₂a₁

BCD t͹ nhiên và mã Gray.

BCD quá 3

c₃c₂c₁c₀G₃G₂G₁G₀g₃g₂g₁g₀

Mã Gray

Gray quá 3

6ӕ thұp

A

phân

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

2

3

4

5

6

7

8

9

Chú ý: Mã Gray ÿѭӧc suy ra tӯ mã BCD 8421 bҵng cách: các bit 0,1 ÿӭng sau bit 0 (ӣ mã

BCD 8421) khi chuyӇn sang mã Gray ÿѭӧc giӳ nguyên, còn các bit 0,1 ÿӭng sau bit 1 (ӣ mã BCD

8421) khi chuyӇn sang mã Gray thì ÿҧo bít, nghƭa là tӯ bit 1 thành bit 0 và bit 0 thành bit 1.

1.2. CÁC TIÊN Ĉӄ VÀ ĈӎNH LÝ ĈҤI SӔ BOOLE

Trong các mҥch sӕ, các tín hiӋu thѭӡng ÿѭӧc cho ӣ 2 mӭc ÿLӋn áp, ví dө: 0V và 5V. Nhӳng linh

kiӋn ÿLӋn tӱ dùng trong mҥch sӕ làm viӋc ӣ mӝt trong hai trҥng thái, ví dө Transistor lѭӥng cӵc

(BJT) làm viӋc ӣ hai chӃꢀÿӝ là tҳt hoһc dүn bão hoà… Do vұy, ÿӇ mô tҧ các mҥch sӕ ngѭӡi ta dùng

KӋ nhӏ phân (binary), hai trҥng thái cӫa các linh kiӋn trong mҥch sӕꢀÿѭӧc mã hoá tѭѫng ӭng là 0

hoһc 1.

0ӝt bӝ môn ÿҥi sӕ phát triӇn tӯ cuӕi thӃ kӹ 19 mang tên ngѭӡi sáng lұp ra nó: ÿҥi sӕ Boole, còn

ÿѭӧc gӑi là ÿҥi sӕ logic, thích hӧp cho viӋc mô tҧ mҥch sӕ. Ĉҥi sӕ Boole là công cө toán hӑc quan

Chѭѫng 1. Ĉҥi sӕ Boole

Trang 9

trӑng ÿӇ phân tích và thiӃt kӃ các mҥch sӕ, ÿѭӧc dùng làm chìa khoá ÿӇꢀÿi sâu vào mӑi lƭnh vӵc liên

quan ÿӃn kӻ thuұt sӕ.

1.2.1. Các tiên ÿӅ cӫa ÿҥi sӕ Boole

Cho mӝt tұp hӧp B hӳu hҥn trong ÿó ta trang bӏ các phép toán + (cӝng logic), x (nhân logic), -

(bù logic/nghӏch ÿҧo logic) và hai phҫn tӱ 0 và 1 lұp thành mӝt cҩu trúc ÿҥi sӕ Boole (ÿӑc là Bun).

" x,y Î B thì:

x+y Î B, x*y Î B và thӓa mãn 5 tiên ÿӅ sau:

1. Tiên ÿӅ giao hoán

" x,y Î B:

x + y = y + x

2. Tiên ÿӅ phӕi hӧp

" x,y,z Î B: (x+y)+z = x+(y+z) = x+y+z

(x.y).z = x.(y.z) = x.y.z

3. Tiên ÿӅ phân phӕi

" x,y, z Î B: x.(y + z ) = x.y + x.z

x + (y.z) = (x + y).(x + z)

4. Tiên ÿӅ vӅ phҫn tӱ trung hòa

Trong tұp B tӗn tҥi hai phҫn tӱ trung hòa là phҫn tӱ ÿѫn vӏ và phҫn tӱ không. Phҫn tӱꢀÿѫn vӏ

ký hiӋu là 1, phҫn tӱ không ký hiӋu là 0.

" x Î B:

x + 1 = 1

x . 1 = x

x + 0 = x

x . 0 = 0

5. Tiên ÿӅ vӅ phҫn tӱ bù

" x Î B, bao giӡ cǊng tӗn tҥi phҫn tӱ bù tѭѫng ӭng, ký hiӋu x , sao cho luôn thӓa mãn:

x + x = 1 và x. x = 0

1Ӄu B = B* = {0,1} (B* chӍ gӗm 2 phҫn tӱ 0 và 1) và thӓa mãn 5 tiên ÿӅ trên thì cǊng lұp thành

Fҩu trúc ÿҥi sӕ Boole nhѭng là cҩu trúc ÿҥi sӕ Boole nhӓ nhҩt.

1.2.2. Các ÿӏnh lý cѫ bҧn cӫa ÿҥi sӕ Boole

1. Vҩn ÿӅꢀÿӕi ngүu trong ÿҥi sӕ Boole

Hai mӋnh ÿӅ (hai biӇu thӭc, hai ÿӏnh lý) ÿѭӧc gӑi là ÿӕi ngүu vӟi nhau nӃu trong mӋnh ÿӅ này

ngѭӡi ta thay phép toán cӝng thành phép toán nhân và ngѭӧc lҥi, thay 0 bҵng 1 và ngѭӧc lҥi, thì sӁ

suy ra ÿѭӧc mӋnh ÿӅ kia.

Khi hai mӋnh ÿӅꢀÿӕi ngүu vӟi nhau, nӃu 1 trong 2 mӋnh ÿӅꢀÿѭӧc chӭng minh là ÿúng thì mӋnh

ÿӅ còn lҥi là ÿúng. Dѭӟi ÿây là ví dө vӅ các cһp mӋnh ÿӅꢀÿӕi ngүu vӟi nhau.

Ví dͭ 1.8:

x.(y+z) = (x.y) + (x.z)

x + (y.z) = (x+y).(x+z)

Hai m͏nh ÿ͉ này là ÿ͙i ng̳u

Ví dͭ 1.9:

x + x = 1

Hai m͏nh ÿ͉ này là ÿ͙i ng̳u

x. x = 0

Khoa ĈTVT – ĈHBKĈN – Tháng 08.2006

2. Các ÿӏnh lý cѫ bҧn

Trang 10

a. Ĉ͓nh lí 1 (Ĉ͓nh lý v͉ ph̯n t͵ bù là duy nh̭t)

" x, y Î B, ta có:

ü

x + y =1

x.y = 0

ï

_ýÞ y = x là duy nhҩt (x và y là 2 phҫn tӱ bù cӫa nhau)

ï

þ

Phҫn tӱ bù cӫa mӝt phҫn tӱ bҩt kǤ là duy nhҩt.

b. Ĉ͓nh lí 2 (Ĉlý v͉ s͹ꢀÿ͛ng nh̭t cͯa phép c͡ng và phép nhân logic)

" x Î B, ta có:

x + x +. . . . . + x = x

x. x. x. . . . . . x = x

c. Ĉ͓nh lý 3 (Ĉ͓nh lý v͉ phͯꢀÿ͓nh hai l̯n)

" x Î B, ta có: x = x

d. Ĉ͓nh lí 4 (Ĉ͓nh lý De Morgan)

" x, y, z Î B, ta có:

x + y + z = x.y.z

x.y.z = x + y + z

+Ӌ quҧ: " x, y, z Î B, ta có:

x + y + z = x + y + z = x.y.z

x. y. z = x.y.z = x + y + z

e. Ĉ͓nh lí 5 (Ĉ͓nh lý dán)

" x, y Î B, ta có:

x. ( x + y) = x.y

x + ( x .y) = x + y

f. Ĉ͓nh lí 6 (Ĉ͓nh lý nu͙t)

" x, y Î B, ta có:

x + x. y = x

x.(x + y) = x

g. Ĉ͓nh lí 7 (Quy t̷c tính ÿ͙i vͣi h̹ng)

9ӟi 0, 1 Î B, ta có:

= 1

0

1 = 0

Chѭѫng 1. Ĉҥi sӕ Boole

Trang 11

1.3. HÀM BOOLE VÀ CÁC PHѬѪNG PHÁP BIӆU DIӈN

1.3.1. Hàm Boole

1. Ĉӏnh nghƭa

Hàm Boole là mӝt ánh xҥ tӯꢀÿҥi sӕ Boole vào chính nó. Nghƭa là " x, y Î B ÿѭӧc gӑi là các

biӃn Boole thì hàm Boole, ký hiӋu là f, ÿѭӧc hình thành trên cѫ sӣ liên kӃt các biӃn Boole bҵng các

phép toán + (cӝng logic), x / . (nhân logic), nghӏch ÿҧo logic (-).

Hàm Boole ÿѫn giҧn nhҩt là hàm Boole theo 1 biӃn Boole, ÿѭӧc cho nhѭ sau:

f(x) = x, f(x) = x , f(x) = a (a là hҵng sӕ )

Trong trѭӡng hӧp tәng quát, ta có hàm Boole theo n biӃn Boole ÿѭӧc ký hiӋu nhѭ sau:

f(x₁, x₂, ...., x_n)

2. Các tính chҩt cӫa hàm Boole

1Ӄu f(x₁, x₂, ...., x_n) là mӝt hàm Boole thì:

- a .f(x₁, x₂, ...., x_n) cǊng là mӝt hàm Boole.

- f (x₁, x₂, ...., x_n) cǊng là mӝt hàm Boole.

1Ӄu f₁(x₁, x₂, ...., x_n) và f₂(x₁, x₂, ...., x_n) là nhӳng hàm Boole thì:

- f₁(x₁, x₂, ...., x_n) + f₂(x₁, x₂, ...., x_n)

- f₁(x₁, x₂, ...., x_n).f₂(x₁, x₂, ...., x_n)

cǊng là mӝt hàm Boole.

9ұy, mӝt hàm Boole f cǊng ÿѭӧc hình thành trên cѫ sӣ liên kӃt các hàm Boole bҵng các

phép toán + (cӝng logic), x (.) (nhân logic) hoһc nghӏch ÿҧo logic (-).

3. Giá trӏ cӫa hàm Boole

Giҧ sӱ f(x₁, x₂, ...., x_n) là mӝt hàm Boole theo n biӃn Boole.

^{Trong f ngѭӡi ta thay các biӃn x}_i^{bҵng các giá trӏ cө thӇ a}_i⁽i =1,n) thì giá trӏ f (a ₁, a ₂, ..., a _n)

ÿѭӧc gӑi là giá trӏ cӫa hàm Boole theo n biӃn.

Ví dͭ 1.10:

Xét hàm f(x₁, x₂) = x₁+ x₂

Xét trong tұp B = B* ={0,1}, ta có các trѭӡng hӧp sau (lѭu ý ÿây là phép cӝng logic hay còn gӑi

phép toán HOҺC / phép OR):

- x₁= 0, x₂= 0 ® f(0,0) = 0 + 0 = 0

x₁

0

x₂

0

f(x₁, x₂) = x₁+ x₂

- x₁= 0, x₂= 1 ® f(0,1) = 0 + 1 = 1

- x₁= 1, x₂= 0 ® f(1,0) = 1 + 0 = 1

- x₁= 1, x₂= 1 ® f(1,1) = 1 + 1 = 1

Ta lұp ÿѭӧc bҧng giá trӏ cӫa hàm trên.

0

1

0

1

0

1

Ví dͭ 1.11:

Xét hàm cho bӣi biӇu thӭc sau: f(x₁, x₂, x₃) = x₁+ x₂.x₃

Xét tұp B = B* = {0,1}. Hoàn toàn tѭѫng tӵ ta lұp ÿѭӧc bҧng giá trӏ cӫa hàm:

Khoa ĈTVT – ĈHBKĈN – Tháng 08.2006

Trang 12

x₁

0

1

x₂

0

1

0

1

x₃

0

1

0

1

0

1

0

1

f (x₁, x₂, x₃) = x₁+ x₂.x₃

0

1

1.3.2. Các phѭѫng pháp biӇu diӉn hàm Boole

1. Phѭѫng pháp biӇu diӉn hàm bҵng bҧng giá trӏ

Phѭѫng pháp này gӗm mӝt bҧng ÿѭӧc chia làm hai phҫn:

- Mӝt phҫn dành cho biӃn ÿӇ ghi các tә hӧp giá trӏ có thӇ có cӫa biӃn vào.

- Mӝt phҫn dành cho hàm ÿӇ ghi các giá trӏ cӫa hàm ra tѭѫng ӭng vӟi các tә hӧp biӃn vào.

Bҧng giá trӏ còn ÿѭӧc gӑi là bҧng chân trӏ hay bҧng chân lý (TRUE TABLE). Nhѭ vұy vӟi mӝt

hàm Boole n biӃn bҧng chân lý sӁ có:

- (n+1) Fӝt: n cӝt tѭѫng ӭng vӟi n biӃn vào, 1 cӝt tѭѫng ӭng vӟi giá trӏ ra cӫa hàm.

- 2ⁿhàng: 2ⁿgiá trӏ khác nhau cӫa tә hӧp n biӃn.

Ví dͭ 1.12: Hàm 3 biӃn f(x₁, x₂, x₃) có thӇꢀÿѭӧc cho bҵng bҧng giá trӏ nhѭ sau:

x₁

0

1

x₂

0

1

0

1

x₃

0

1

0

1

0

1

0

1

f (x₁, x₂, x₃)

0

1

2. Phѭѫng pháp giҧi tích

Ĉây là phѭѫng pháp biӇu diӉn hàm logic bҵng các biӇu thӭc ÿҥi sӕ. Phѭѫng pháp này có 2 dҥng:

Wәng cӫa các tích sӕ hoһc tích cӫa các tәng sӕ.

'ҥng tәng cӫa các tích sӕ gӑi là dҥng chính tҳc thӭ nhҩt (Dҥng chính tҳc 1).

'ҥng tích cӫa các tәng sӕ gӑi là dҥng chính tҳc thӭ hai (Dҥng chính tҳc 2).

Hai dҥng chính tҳc này là ÿӕi ngүu nhau.

'ҥng tәng các tích sӕ còn gӑi là dҥng chu̱n t̷c tuy͋n (CTT), dҥng tích các tәng sӕ còn gӑi là

Gҥng chu̱n t̷c h͡i (CTH).

a. D̩ng chính t̷c 1(D̩ng t͝ng cͯa các tích s͙)

Xét các hàm Boole mӝt biӃn ÿѫn giҧn: f(x) = x, f(x) = x , f(x) = a (a là hҵng sӕ).

Ĉây là nhӳng trѭӡng hӧp có thӇ có ÿӕi vӟi hàm Boole 1 biӃn.

Chѭѫng 1. Ĉҥi sӕ Boole

Trang 13

Chúng ta sͅꢀÿi chͱng minh bi͋u thͱc t͝ng quát cͯa hàm logic 1 bi͇n s͙ꢀÿ͙i vͣi d̩ng chính t̷c 1. Sau ÿó

áp dͭng bi͋u thͱc t͝ng quát cͯa hàm 1 bi͇n ÿ͋ tìm bi͋u thͱc t͝ng quát cͯa hàm 2 bi͇n vͣi vi͏c xem 1 bi͇n là

K̹ng s͙. Cu͙i cùng, chúng ta suy ra bi͋u thͱc t͝ng quát cͯa hàm logic n bi͇n cho tr˱ͥng hͫp d̩ng chính

W̷c 1 (t͝ng các tích s͙).

Xét f(x) = x:

Ta có:

x =0. x + 1.x

P̿t khác:

f(1)= 1

f(0)= 0

ì

_f(_x)_{= x Þ}

í

î

Suy ra: f(x) = x có th͋ bi͋u di͍n:

f(x) = x = f(0). x + f (1).x

trong ÿó: f (0), f (1) ÿ˱ͫc g͕i là các giá tr͓ cͯa hàm Boole theo m͡t bi͇n.

Xét f(x) = x :

Ta có:

x = 1. x + 0. x

0̿t khác:

f(1)= 0

f(0)=1

ì

í

î

_f(_x)_{= x Þ}

Suy ra: f(x) = x có th͋ bi͋u di͍n:

f(x) = x = f(0). x + f(1).x

Xét f(x) = a (a là h̹ng s͙):

Ta có: a = a .1 = a .(x + x ) = a . x + a .x

0̿t khác:

f(1)= Į

f(0)= Į

ì

í

î

_f(_x)_{= Į Þ}

Suy ra f(x) = a có th͋ bi͋u di͍n:

f(x) = a = f(0). x + f(1).x

.Ӄt luұn: Dù f(x) = x, f(x) = x hay f(x) = a , ta ÿӅu có biӇu thӭc tәng quát cӫa hàm mӝt biӃn

viӃt theo dҥng chính tҳc thӭ nhҩt nhѭ sau:

^{f(x) = f(0).}x + f(1).x

9ұy f(x) = f(0). x + f(1).x, trong ÿó f(0), f(1) là giá trӏ cӫa hàm Boole theo mӝt biӃn, ÿѭӧc gӑi là

biӇu thӭc tәng quát cӫa hàm 1 biӃn viӃt ӣ G̩ng chính t̷c thͱ nh̭t (d̩ng t͝ng cͯa các tích).

BiӇu thӭc tәng quát cӫa hàm hai biӃn f(x₁, x₂):

BiӇu thӭc tәng quát cӫa hàm 2 biӃn viӃt theo dҥng chính tҳc thӭ nhҩt cǊng hoàn toàn dӵa trên

cách biӇu diӉn cӫa dҥng chính tҳc thӭ nhҩt cӫa hàm 1 biӃn, trong ÿó xem mӝt biӃn là hҵng sӕ.

&ͭ th͋ là: n͇u xem x₂là h̹ng s͙, x₁là bi͇n s͙ và áp dͭng bi͋u thͱc t͝ng quát cͯa d̩ng chính t̷c thͱ

nh̭t cho hàm 1 bi͇n, ta có:

f(x₁,x₂) = f(0,x₂). x ₁+ f(1,x₂).x₁

Bây giͥ, các hàm f(0,x₂) và f(1,x₂) trͧ thành các hàm 1 bi͇n s͙ theo x₂. Ti͇p tͭc áp dͭng bi͋u thͱc t͝ng

quát cͯa d̩ng chính t̷c thͱ nh̭t cho hàm 1 bi͇n, ta có:

Khoa ĈTVT – ĈHBKĈN – Tháng 08.2006

f(0,x₂) = f(0,0). x ₂+ f(0,1).x₂

Trang 14

f(1,x₂) = f(1,0). x ₂+ f(1,1).x₂

Suy ra:

f(x₁,x₂) = f(0,0). x ₁x ₂+ f(0,1). x ₁x₂+ f(1,0).x₁x ₂+ f(1,1).x₁x₂

Ĉây chính là biӇu thӭc tәng quát cӫa dҥng chính tҳc thӭ nhҩt (dҥng tәng cӫa các tích sӕ) viӃt cho

hàm Boole hai biӃn sӕ f(x₁,x₂).

BiӇu thӭc tәng quát này có thӇ biӇu diӉn bҵng công thӭc sau:

2

²å^-1

Į

2

1

f(x₁,x₂) =

f(Į₁,Į₂)x₁x₂

e=0

Trong ÿó e là sӕ thұp phân tѭѫng ӭng vӟi mã nhӏ phân (a ₁,a ₂) và:

x₁

x ₁nӃu a ₁= 0

x₂nӃu a ₂= 1

x ₂nӃu a ₂= 0

nӃu a ₁= 1

x₁^Į

x^Į₂

1

=

2

=

BiӇu thӭc tәng quát cho hàm Boole n biӃn:

Tӯ biӇu thӭc tәng quát viӃt ӣ dҥng chính tҳc thӭ nhҩt cӫa hàm Boole 2 biӃn, ta có thӇ tәng quát

hoá cho hàm Boole n biӃn f(x₁,x₂, ..,x_n) nhѭ sau:

n

2 -1

Į

2

n

1

f(x₁,x₂, ..,x_n) =

f(Į ,Į ,....,Į )x x ...x

å

1 2 n

1

2

n

e=0

trong ÿó e là sӕ thұp phân tѭѫng ӭng vӟi mã nhӏ phân (a ₁,a ₂, ...,a _n);

và:

x_i

nӃu a _i= 1

Į

i

=

x_i

x _inӃu a _i= 0

(vӟi i = 1, 2, 3,…,n)

Ví dͭ 1.13:

ViӃt biӇu thӭc cӫa hàm 3 biӃn theo dҥng chính tҳc 1:

3

²å^{- 1}

a 1

a 2

a 3

f(x₁,x₂,x₃) =

f (a ₁,a ₂,a ₃).x₁.x₂.x₃

e=0

%ҧng dѭӟi ÿây cho ta giá trӏ cӫa sӕ thұp phân e và tә hӧp mã nhӏ phân (a ₁,a ₂,a ₃) tѭѫng ӭng:

e

0

1

2

3

4

5

6

7

a ₁

0

a ₂a ₃

0

1

0

1

0

1

0

1

0

1

0

1

0

1

Chѭѫng 1. Ĉҥi sӕ Boole

Trang 15

BiӇu thӭc cӫa hàm 3 biӃn viӃt theo dҥng tәng các tích nhѭ sau:

f(x₁, x₂, x₃) = f(0,0,0) x ₁x ₂x ₃+ f(0,0,1) x ₁x ₂x₃

+ f(0,1,0) x ₁x₂x ₃+ f(0,1,1) x ₁x₂x₃+ f(1,0,0) x₁x ₂x ₃

+ f(1,0,1)x₁x ₂x₃+ f(1,1,0) x₁x₂x ₃+ f(1,1,1) x₁x₂x₃

9̵y d̩ng chính t̷c thͱ nh̭t là d̩ng t͝ng cͯa các tích s͙ mà trong m͟i tích s͙ chͱa ÿ̯y

ÿͯ các bi͇n Boole d˱ͣi d̩ng th̵t ho̿c d̩ng bù (ngh͓ch ÿ̫o).

b. D̩ng chính t̷c 2 (tích cͯa các t͝ng s͙):

'ҥng chính tҳc 2 là dҥng ÿӕi ngүu cӫa dҥng chính tҳc 1 nên biӇu thӭc tәng quát cӫa dҥng

chính tҳc 2 cho n biӃnꢀÿѭӧc viӃt nhѭ sau:

n

2 -1

a 2

a n

f(x₁, x₂, ..., x_n) =

[f(a ₁,a ₂,a ₃) + x₁^{a 1}+ x₂+ ...+ x_n)]

Õ

e=0

trong ÿó e là sӕ thұp phân tѭѫng ӭng vӟi mã nhӏ phân (a ₁,a ₂, ...,a _n);

và:

x _inӃu a _i= 1

x_i^Į

i

=

x_i

nӃu a _i= 0

(vӟi i = 1, 2, 3,…,n)

Ví dͭ 1.14: BiӇu thӭc cӫa hàm Boole 2 biӃn ӣ dҥng tích các tәng sӕ (dҥng chính tҳc 2) ÿѭӧc viӃt

nhѭ sau:

f(x₁,x₂)=[f(0,0)+x₁+x₂][f(0,1)+x₁+ x ₂][f(1,0)+ x ₁+x₂][f(1,1)+ x ₁+ x ₂]

Ví dͭ 1.15: BiӇu thӭc cӫa hàm Boole 3 biӃn ӣ dҥng chính tҳc 2:

f(x₁,x₂,x₃) = [f(0,0,0)+x₁+ x₂+x₃].[f(0,0,1)+x₁+x₂+ x ₃].

[f(0,1,0)+x₁+ x ₂+x₃].[f(0,1,1)+x₁+ x ₂+ x ₃].

[f(1,0,0)+ x ₁+x₂+x₃].[f(1,0,1)+x ₁+x₂+ x ₃].

[f(1,1,0)+ x ₁+ x ₂+x₃].[f(1,1,1)+x ₁+ x ₂+ x ₃]

9̵y, d̩ng chính t̷c thͱ hai là d̩ng tích cͯa các t͝ng s͙ mà trong ÿó m͟i t͝ng s͙ này

chͱa ÿ̯y ÿͯ các bi͇n Boole d˱ͣi d̩ng th̵t ho̿c d̩ng bù.

Ví dͭ 1.16:

Hãy viӃt biӇu thӭc biӇu diӉn cho hàm Boole 2 biӃn f(x₁,x₂) ӣ dҥng chính tҳc 1, vӟi bҧng giá trӏ

Fӫa hàm ÿѭӧc cho nhѭ sau:

x₁

0

x₂

0

f(x₁,x₂)

0

1

0

1

0

1

ViӃt dѭӟi dҥng chính tҳc 1 ta có:

f(x₁,x₂) = f(0,0). x ₁x ₂+ f(0,1). x ₁.x₂+ f(1,0).x₁. x ₂+ f(1,1).x₁.x₂

Khoa ĈTVT – ĈHBKĈN – Tháng 08.2006

Trang 16

= 0. x ₁x ₂+ 1. x ₁.x₂+ 1.x₁. x ₂+ 1.x₁.x₂

= x ₁.x₂+ x₁. x ₂+ x₁.x₂

Nhұn xét:

· '̩ng chính t̷c thͱ nh̭t, t͝ng cͯa các tích s͙, là d̩ng li͏t kê ṱt c̫ các t͝ hͫp nh͓

phân các bi͇n vào sao cho t˱˯ng ͱng vͣi nhͷng t͝ hͫp ÿó giá tr͓ cͯa hàm ra b̹ng 1

® ch͑ c̯n li͏t kê nhͷng t͝ hͫp bi͇n làm cho giá tr͓ hàm ra b̹ng 1.

· Khi li͏t kê n͇u bi͇n t˱˯ng ͱng b̹ng 1 ÿ˱ͫc vi͇t ͧ d̩ng th̵t (x_i), n͇u bi͇n t˱˯ng ͱng

E̹ng 0 ÿ˱ͫc vi͇t ͧ d̩ng bù ( x _i).

Ví dͭ 1.17:

ViӃt biӇu thӭc biӇu diӉn hàm f(x₁,x₂,x₃) ӣ dҥng chính tҳc 2 vӟi bҧng giá trӏ cӫa hàm ra ÿѭӧc cho

nhѭ sau:

x₃

0

1

x₂

0

1

0

1

x₁

0

1

0

1

0

1

0

1

f(x₁,x_2,x₃)

0

1

ViӃt dѭӟi dҥng chính tҳc 2 (tích các tәng sӕ):

f(x₁,x₂,x₃) = (0+x₁+x₂+x₃).(0+x₁+x₂+ x ₃).(0+x₁+ x ₂+x₃).

(1+x₁+ x ₂+ x ₃).(1+ x ₁+x₂+x₃).(1+ x ₁+x₂+ x ₃).

(1+ x ₁+ x ₂+x₃).(1+ x ₁+ x ₂+ x ₃)

Áp dөng tiên ÿӅ vӅ phҫn tӱ trung hòa 0 và 1 ta có:

x + 1 = 1,

x + 0 = x,

x . 1 = x

x . 0 = 0

nên suy ra biӇu thӭc trên có thӇ viӃt gӑn lҥi:

f(x₁,x₂,x₃) = (x₁+x₂+x₃).(x₁+x₂+ x ₃).(x₁+ x ₂+x₃)

Nhұn xét:

· '̩ng chính t̷c thͱ hai là d̩ng li͏t kê ṱt c̫ các t͝ hͫp nh͓ phân các bi͇n vào sao cho

W˱˯ng ͱng vͣi nhͷng t͝ hͫp ÿó giá tr͓ cͯa hàm ra b̹ng 0 ® ch͑ c̯n li͏t kê nhͷng t͝

Kͫp bi͇n làm cho giá tr͓ hàm ra b̹ng 0.

· Khi li͏t kê n͇u bi͇n t˱˯ng ͱng b̹ng 0 ÿ˱ͫc vi͇t ͧ d̩ng th̵t (x_i), n͇u bi͇n t˱˯ng ͱng

E̹ng 1 ÿ˱ͫc vi͇t ͧ d̩ng bù ( x _i).

Ví dөꢀÿѫn giҧn sau giúp SV hiӇu rõ hѫn vӅ cách thành lұp bҧng giá trӏ cӫa hàm, tìm hàm mҥch

và thiӃt kӃ mҥch.

Chѭѫng 1. Ĉҥi sӕ Boole

Ví dͭ 1.18

Trang 17

Hãy thiӃt kӃ mҥch ÿLӋn sao cho khi công tҳc 1 ÿóng thì ÿèn ÿӓ, khi công tҳc 2 ÿóng ÿèn ÿӓ, khi

Fҧ hai công tҳc ÿóng ÿèn ÿӓ ?

/ӡi giҧi:

Ĉҫu tiên, ta qui ÿӏnh trҥng thái cӫa các công tҳc và bóng ÿèn:

- Công tҳc hӣ : 0

- Công tҳc ÿóng: 1

Ĉèn tҳt : 0

Ĉèn ÿӓ : 1

%ҧng trҥng thái mô tҧ hoҥt ÿӝng cӫa mҥch nhѭ sau:

Công tҳc 1

Công tҳc 2

Trҥng thái ÿèn

x₁

x₂

f(x₁,x₂)

0

1

0

1

0

1

0

1

7ӯ bҧng trҥng thái có thӇ viӃt biӇu thӭc cӫa hàm f(x₁,x₂) theo dҥng chính tҳc 1 hoһc chính tҳc 2.

- Theo dҥng chính tҳc 1 ta có:

f(x₁, x₂) = x ₁.x₂+ x₁. x ₂+ x₁.x₂

= x ₁.x₂+ x₁( x ₂+ x₂)

= x ₁.x₂+ x₁

= x₁+ x₂

- Theo dҥng chính tҳc 2 ta có:

f(x₁, x₂) = (0+x₁+x₂) = x₁+ x₂

Tӯ biӇu thӭc mô tҧ trҥng thái ÿӓ/tҳt cӫa ÿèn f(x₁,x₂) thҩy rҵng có thӇ thӵc hiӋn mҥch bҵng phҫn

Wӱ logic HOҺC có 2 ngõ vào (cәng OR 2 ngõ vào).

Bài t̵p áp dͭng: M͡t h͡i ÿ͛ng giám kh̫o g͛m 3 thành viên. M͟i thành viên có th͋ l͹a ch͕n Ĉ͚NG

Ý ho̿c KHÔNG Ĉ͚NG Ý. K͇t qu̫ g͕i là Ĉ̨T khi ÿa s͙ các thành viên trong h͡i ÿ͛ng giám kh̫o

Ĉ͚NG Ý, ng˱ͫc l̩i là KHÔNG Ĉ̨T. Hãy thi͇t k͇ m̩ch gi̫i quy͇t bài toán trên.

3. BiӇu diӉn hàm bҵng bҧng Karnaugh (bìa Karnaugh)

Ĉây là cách biӇu diӉn lҥi cӫa phѭѫng pháp bҧng dѭӟi dҥng bҧng gӗm các

ô vuông nhѭ hình bên.

Trên bҧng này ngѭӡi ta bӕ trí các biӃn vào theo hàng hoһc theo cӝt cӫa

Eҧng. Trong trѭӡng hӧp sӕ lѭӧng biӃn vào là chҹn, ngѭӡi ta bӕ trí sӕ lѭӧng

biӃn vào theo hàng ngang bҵng sӕ lѭӧng biӃn vào theo cӝt dӑc cӫa bҧng.

Trong trѭӡng hӧp sӕ lѭӧng biӃn vào là lҿ, ngѭӡi ta bӕ trí sӕ lѭӧng biӃn vào

theo hàng ngang nhiӅu hѫn sӕ lѭӧng biӃn vào theo cӝt dӑc 1 biӃn hoһc ngѭӧc lҥi.

Các tә hӧp giá trӏ cӫa biӃn vào theo hàng ngang hoһc theo cӝt dӑc cӫa bҧng ÿѭӧc bӕ trí sao cho

khi ta ÿi tӯ mӝt ô sang mӝt ô lân cұn vӟi nó chӍ làm thay ÿәi mӝt giá trӏ cӫa biӃn, nhѭ vұy thӭ tӵ

Eӕ trí hay sҳp xӃp các tә hӧp giá trӏ cӫa biӃn vào theo hàng ngang hoһc theo cӝt dӑc cӫa bҧng

Karnaugh hoàn toàn tuân thӫ theo mã Gray.

Khoa ĈTVT – ĈHBKĈN – Tháng 08.2006

Trang 18

Giá trӏ ghi trong mӛi ô vuông này chính là giá trӏ cӫa hàm ra tѭѫng ӭng vӟi các tә hӧp giá trӏ cӫa

biӃn vào. Ӣ nhӳng ô mà giá trӏ hàm là không xác ÿӏnh (có thӇ bҵng 0 hay bҵng 1), có nghƭa là giá trӏ

Fӫa hàm là tùy ý (hay tùy ÿӏnh), ngѭӡi ta kí hiӋu bҵng chӳ X.

1Ӄu hàm có n biӃn vào sӁ có 2ⁿô vuông.

Phѭѫng pháp biӇu diӉn hàm bҵng bҧng Karnaugh chӍ thích hӧp cho hàm có tӕi ÿa 6 biӃn, nӃu

Yѭӧt quá viӋc biӇu diӉn sӁ rҩt rҳc rӕi.

'ѭӟi ÿây là bҧng Karnaugh cho các trѭӡng hӧp hàm 2 biӃn, 3 biӃn, 4 biӃn và 5 biӃn:

f(x₁,x₂)

f

x₁

0 1

x₁x₂

00 01 11 10

x₂

x₃

0

1

0

1

f

x₁=0

x₁=1

x₁x₂

x₂x₃

x₄x₅

x₃x₄

00 01 11 10

00 01 11 10 10 11 01 00

00

01

11

10

00

01

11

10

1.4. TӔI THIӆU HÓA HÀM BOOLE

1.4.1. Ĉҥi cѭѫng

Trong thiӃt bӏ máy tính ngѭӡi ta thѭӡng thiӃt kӃ gӗm nhiӅu modul (khâu) và mӛi modul này

ÿѭӧc ÿһc trѭng bҵng mӝt phѭѫng trình logic. Trong ÿó, mӭc ÿӝ phӭc tҥp và ÿӝꢀәn ÿӏnh cӫa sѫꢀÿӗ

tùy thuӝc vào phѭѫng trình logic biӇu diӉn chúng ӣ dҥng tӕi thiӇu hay chѭa. ĈӇ thӵc hiӋn ÿѭӧc ÿLӅu

ÿó, khi thiӃt kӃ mҥch sӕ ngѭӡi ta ÿһt ra vҩn ÿӅ tӕi thiӇu hóa các hàm logic, nghƭa là phѭѫng trình

logic biӇu diӉn sao cho thӵc sӵ gӑn nhҩt (sӕ lѭӧng các phép tính và sӕ lѭӧng các sӕꢀÿѭӧc biӇu diӉn

Gѭӟi dҥng thұt hoһc bù là ít nhҩt).

Các kӻ thuұt ÿӇꢀÿҥt ÿѭӧc sӵ thӵc hiӋn hàm Boole mӝt cách ÿѫn giҧn nhҩt phө thuӝc vào nhiӅu

\Ӄu tӕ mà chúng ta cҫn cân nhҳc:

0͡t là s͙ l˱ͫng các phép tính và s͙ l˱ͫng các s͙ (sӕ lѭӧng literal) ÿѭӧc biӇu diӉn dѭӟi dҥng thұt

hoһc bù là ít nhҩt, ÿLӅu này ÿӗng nghƭa vӟi viӋc sӕ lѭӧng dây nӕi và sӕ lѭӧng ÿҫu vào cӫa mҥch là ít

nhҩt.

Hai là s͙ l˱ͫng c͝ng cҫn thiӃt ÿӇ thӵc hiӋn mҥch phҧi ít nhҩt, chính sӕ lѭӧng cәng xác ÿӏnh kích

thѭӟc cӫa mҥch. Mӝt thiӃt kӃꢀÿѫn giҧn nhҩt phҧi ӭng vӟi sӕ lѭӧng cәng ít nhҩt chӭ không phҧi sӕ

Oѭӧng literal ít nhҩt.

Ba là s͙ mͱc logic cӫa các cәng. Giҧm sӕ mӭc logic sӁ giҧm trӉ tәng cӝng cӫa mҥch vì tín hiӋu

VӁ qua ít cәng hѫn. Tuy nhiên nӃu chú trӑng ÿӃn vҩn ÿӅ giҧm trӉ sӁ phҧi trҧ giá sӕ lѭӧng cәng tăng

lên.

%ӣi vұy trong thӵc tӃ không phҧi lúc nào cǊng ÿҥt ÿѭӧc lӡi giҧi tӕi ѭu cho bài toán tӕi thiӇu hóa.

Chѭѫng 1. Ĉҥi sӕ Boole

Trang 19

Các bѭӟc tiӃn hành tӕi thiӇu hóa:

·

Dùng các phép tӕi thiӇu ÿӇ tӕi thiӇu hóa các hàm sӕ logic.

Rút ra nhӳng thӯa sӕ chung nhҵm mөc ÿích tӕi thiӇu hóa thêm mӝt bѭӟc nӳa các phѭѫng

trình logic.

1.4.2. Các phѭѫng pháp tӕi thiӇu hóa

Có nhi͉u ph˱˯ng pháp th͹c hi͏n t͙i thi͋u hoá hàm Boole và có th͋ꢀÿ˱a v͉ 2 nhóm là bi͇n ÿ͝i ÿ̩i s͙ và

dùng thu̵t toán. Ph˱˯ng pháp bi͇n ÿ͝i ÿ̩i s͙ (ph˱˯ng pháp gi̫i tích) d͹a vào các tiên ÿ͉, ÿ͓nh lý, tính ch̭t

Fͯa hàm Boole ÿ͋ th͹c hi͏n t͙i thi͋u hoá.

ͦ nhóm thu̵t toán có 2 ph˱˯ng pháp th˱ͥng ÿ˱ͫc dùng là: ph˱˯ng pháp b̫ng Karnaugh (còn g͕i là bìa

Karnaugh – bìa K) dùng cho các hàm có tͳ 6 bi͇n trͧ xu͙ng, và ph˱˯ng pháp Quine-Mc.Cluskey có th͋ s͵

Gͭng cho hàm có s͙ bi͇n b̭t kǤ cǊng nh˱ cho phép th͹c hi͏n t͹ꢀÿ͡ng theo ch˱˯ng trình ÿ˱ͫc vi͇t trên máy

tính.

Trong phҫn này chӍ giӟi thiӋu 2 phѭѫng pháp ÿҥi diӋn cho 2 nhóm:

·

Phѭѫng pháp bi͇n ÿ͝i ÿ̩i s͙ (nhóm biӃn ÿәi ÿҥi sӕ).

Phѭѫng pháp E̫ng Karnaugh (nhóm thuұt toán).

1. Phѭѫng pháp biӃn ÿәi ÿҥi sӕ

Ĉây là phѭѫng pháp tӕi thiӇu hóa hàm Boole (phѭѫng trình logic) dӵa vào các tiên ÿӅ, ÿӏnh lý,

tính chҩt cӫa ÿҥi sӕ Boole.

Ví dͭ 1.19 Tӕi thiӇu hoá hàm f(x₁,x₂) = x ₁x₂+ x₁x ₂+ x₁x₂

f(x₁,x₂) = x ₁x₂+ x₁x ₂+ x₁x₂

= ( x ₁+ x₁).x₂+ x₁x ₂

= x₂+ x₁x ₂

= x₂+ x₁

Ví dͭ 1.20 Tӕi thiӇu hoá hàm 3 biӃn sau

f(x₁,x₂,x₃) = x ₁x₂x₃+ x₁x ₂x ₃+ x₁x ₂x₃+ x₁x₂x ₃+ x₁x₂x₃

= x ₁x₂x₃+ x₁x ₂x ₃+ x₁x ₂x₃+ x₁x₂( x ₃+ x₃)

= x ₁x₂x₃+ x₁x ₂( x ₃+ x₃) + x₁x₂

= x ₁x₂x₃+ x₁( x ₂+ x₂)

= x ₁x₂x₃+ x₁

= x₁+ x₂x₃

Ví dͭ 1.21 Rút gӑn biӇu thӭc: f =

AB + C + AC + B

Áp dөng ÿӏnh lý De Morgan ta có:

f =

AB.C + AC + B

= (A+ B).C + AC + B

=

AC + BC + AC + B

AC + AC + B +C

= (A+1).C + AC + B

=

C +CA+ B

A + B + C

®

ĈӇ thӵc hiӋn mҥch này có thӇ dùng cәng OR 3 ngõ vào.