Chng 1. H thng sm và khái nim v mã Trang 1
Chng 1
 THNG SM VÀ KHÁI NIM V MÃ
1.1. H THNG SM
1.1.1. Hm
1. Khái ni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
ng xác nh gi là các ch s.
2. Phân loi
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
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
 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
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.
1.1.2. C s ca hm
t s A bt k có th biu din bng dãy sau:
A= a
m-1
a

m ó. Mi ký t biu din mt ch s.
Bài ging K THUT S 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
 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 : N =2 ⇒ a
i
= 0, 1.
- H thp phân : N =10 ⇒ a
i
= 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.
- H bát phân : 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-1
.10
m-1
+ a
m-2
.10
m-2
+ + a
0
.10
0
+ + a
-n
.10
-n
1999,959
(10)
=1.10
3
+ 9.10
2
+ 9.10
1
+ 9.10
0
+ 9.10
-1
+ 5.10
-2
+ 9.10

= 13
(10)
i N=16 (h thp lc phân):
A
(16)
= a
m-1
.16
m-1
+ a
m-2
.16
m-2
+ + a
0
.16
0
+ a
-1
16
-1
+ + a
-n
16
-n
3FF
(16)
= 3.16
2
+ 15.16

= 3.8
2
+ 7.8
1
+ 6.8
0
= 254
(10)
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).
1.1.3. i c s
1. 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
 d di dng a thc theo c s ca nó (theo biu thc 1.3).
Ví d 1.1
i s 1101
(2)
 h nh phân sang h thp phân nh sau:
1011
(2)
= 1.2
3
+ 0.2
2
+ 1.2
1
+ 1.2
0
= 11
(10)
2. i t c s 10 sang c s d

(2)
37FH có ngha là 37F
(16)
& Quy tc chuyn i gia các hm c s 2, 8, 16 ?
1.2. HM NH PHÂN VÀ KHÁI NIM V MÃ
1.2.1. 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
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),
 hiu rõ hn mt s khái nim, ta xét s nh phân 4 bít: a
3
a
2
a
1
a
0
. Biu din di dng a thc
theo c s ca nó là:
a
3
a
2
a
1

 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.
1023 16
63 16
3 16
0
15
15
3
A
(10)
=1023
→
A
(16)
=3FFH
13
2
6 2
3
2
1
1
0
1
2
0
1
A
(10)

3
a
2
a
1
a
0
S bát phân S thp lc phân
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
0000
0001
0010
0011
0100
0101

4
5
6
7
8
9
A
B
C
D
E
F
ng 1.1. Các t hp mã nh phân 4 bít
 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
3
= 8 và 2
4
= 16, t bng mã trên có th nhn thy mi ch s trong h bát phân
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
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
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
(2)
.
1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 0
y, có th biu din : 137376
(8)

a. Phép cng
 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
→
0011
2
→
0010
5
→
0101 = 1.2
2
+ 1.2
0
= 5
(10)
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

35 0111
0000
0111
0000
0100011 = 1.2
5
+ 1.2
1
+ 1.2
0
= 35
(10)
d. Phép chia
0 : 1 = 0
1 : 1 = 1
u ý: Khi chia s chia phi khác 0
+
+
-
-
x
x
Bài ging K THUT S Trang 6
Ví d 1.7: 10 5
→
1010 101
2 101 10
(2)
= 2
(10)

ch trái 1 bít
↔
nhân 2
0 0 0 0 0 0 10 1 1
0
Thanh ghi sau khi dch phi 1 bít
ch phi 1 bít
↔
chia 20

Hình 1.1. ng dng thanh ghi dch thc hin phép toán nhân và chia 2
Chng 1. H thng sm và khái nim v mã Trang 7
2. Mã hóa s thp phân
a. Khái nim
Trong thc t mã hóa s thp phân ngi ta s dng các s nh phân 4 bit (a
3
a
2
a
1
a
0
) theo quy
c sau:
0
→
0000 ; 5
→
0101
1→ 0001 ; 6 → 0110

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
 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.
Ví d:
Các bng di ây trình bày mt s loi mã thông dng.
Mã Gray: 2
→
0011
3
→
0010
4
→
0110
Còn vi mã BCD 8421:
3
→
0011
4
→
0100
Bài ging K THUT S Trang 8
ng 1.2: Các mã BCD t nhiên.
BCD 8421 BCD 5421 BCD quá 3
a
3
a
2
a

1 0 0 1 1 1 0 0 1 1 0 0 9
ng 1.3: Các mã BCD s hc
BCD 2421 BCD 5121 BCD 84-2-1
a
3
a
2
a
1
a
0
b
3
b
2
b
1
b
0
c
3
c
2
c
1
c
0
 thp
phân
0 0 0 0 0 0 0 0 0 0 0 0 0

G
2
G
1
G
0
g
3
g
2
g
1
g
0
 thp
phân
0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0
0 0 0 1 0 1 0 0 0 0 0 1 0 1 1 0 1
0 0 1 0 0 1 0 1 0 0 1 1 0 1 1 1 2
0 0 1 1 0 1 1 0 0 0 1 0 0 1 0 1 3
0 1 0 0 0 1 1 1 0 1 1 0 0 1 0 0 4
0 1 0 1 1 0 0 0 0 1 1 1 1 1 0 0 5
0 1 1 0 1 0 0 1 0 1 0 1 1 1 0 1 6
0 1 1 1 1 0 1 0 0 1 0 0 1 1 1 1 7
1 0 0 0 1 0 1 1 1 1 0 0 1 1 1 0 8
1 0 0 1 1 1 0 0 1 1 0 1 1 0 1 0 9
Chng 1. H thng sm và khái nim v mã Trang 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.

a
1
a
0
là s BCD 8421
Nh vy, nu mt s nh phân 4 bit không phi là mt s BCD 8421 thì ngõ ra y = 1. T bng
1.1 ta thy mt s nh phân 4 bít không phi là s BCD 8421 khi bít a
3
luôn luôn bng 1 và (bit a
1
ng 1 hoc bít a
2
bng 1).
Suy ra phng trình logic ca ngõ ra y: y = a
3
(a
1
+ a
2
) = a
3
a
1
+ a
3
a
2
 logic:
ng do vic xut hin s BCD nên có hai cách nhp d liu vào máy tính: nhp s nh phân,
nhp bng mã BCD.

3
a
2
a
1
a
1
a
2
a
3
y
a
1
a
2
a
3
y
 hiu chnh
+ + + +
+
Bài ging K THUT S Trang 10
Có hai trng hp phi hiu chnh kt qu ca phép cng 2 s BCD 8421:
- Khi kt qu ca phép cng là mt s không phi là s BCD 8421
- Khi kt qu ca phép cng là mt s BCD 8421 nhng li xut hin s nh bng 1.
Vic hiu chnh c thc hin bng cách cng kt qu vi s hiu chnh là 6 (0110
2
).
 ví d 1.8 ã xem xét trng hp hiu chnh khi kt qu không phi là mt s BCD 8421.

0010
u ý:
- Bù 1 ca mt s nh phân là ly o tt c các bít ca só (bit 0 thành 1, bit 1 thành 0).
- Bù 2 ca mt s nh phân bng s bù 1 cng thêm 1 vào bít LSB.
Xét các trng hp m rng sau ây:
1. Thc hin tr 2 s BCD 1 các mà s b tr nh hn s tr ?
2. M rng cho cng và tr 2 s BCD nhiu các ?
 hiu chnh (6)
+ +
t qu là s BCD 8421 nh
ng
i xut hin s nh bng 1
t qu sau khi hiu chnh là 17
Bù 1 ca 5
- -
+
+
ng 1 LSB  có bù 2 ca 5
i s nh
t qu cui cùng
Chng 2. i s BOOLE Trang 11
Chng 2
I S BOOLE
2.1. 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 n áp, ví d: 0V và 5V. Nhng linh
kin 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
 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.
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

x
= 1 và x.
x
= 0
Bài ging K THUT S Trang 12
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
u trúc i s Boole nhng là cu trúc i s Boole nh nht.
2.1.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 2.1
: x.(y+z) = (x.y) + (x.z)
x + (y.z) = (x+y).(x+z)
Ví d 2.2
: x +
x
= 1
x.
x
= 0
2. Các nh lý
a. nh lí 1 (nh lý v phn t bù là duy nht)
∀
x, y
∈
B, ta có:

x. y. z = x.y.z = zyx ++
e. nh lí 5 (nh lý dán)
∀
x, y
∈
B, ta có:
x. (
x
+ y) = x.y
x + (
x
.y) = x + y
Hai m
nh  này là i ngu
Hai m
nh  này là i ngu
Chng 2. i s BOOLE Trang 13
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)
i 0, 1
∈
B, ta có:
0 = 1
1
= 0
2.2. HÀM BOOLE VÀ CÁC PHNG PHÁP BIU DIN
2.2.1. Hàm Boole

, x
2
, , x
n
) cng là mt hàm Boole.
-
f
(x
1
, x
2
, , x
n
) cng là mt hàm Boole.
u f
1
(x
1
, x
2
, , x
n
) và f
2
(x
1
, x
2
, , x
n

, x
2
, , x
n
) cng là mt hàm Boole.
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
1
, x
2
, , 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
α
i
(
n,1i = ) thì giá tr f (
α
1
,
α
2
, ,
α
n

- x
1
= 1, x
2
= 1 → f(1,1) = 1 + 1 = 1
Ta lp c bng giá tr ca hàm trên.
Ví d 2.4
:
Xét hàm cho bi biu thc sau: f(x
1
, x
2
, x
3
) = x
1
+ x
2
.x
3
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:
x
1
x
2
x
3
f (x
1
, x

1
0
1
0
0
0
1
1
1
1
1
2.2.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
ây là phng pháp thng dùng  biu din hàm s nói chung và cng c s dng  biu
din các hàm logic. 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) 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
n
hàng: 2
n
giá tr khác nhau ca t hp n bin.
Ví d 2.5
: Hàm 3 bin f(x
1
, x
2

1
1
0
1
0
1
0
1
0
1
0
0
0
1
1
1
1
1
Trong các ví d 2.3 và 2.4 chúng ta cng ã quen thuc vi phng pháp biu din hàm bng
ng giá tr.
x
1
x
2
f(x
1
, x
2
) = x
1

vic xem 1 bin là h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 tc 1 (tng các tích s).
Xét f(x) = x:
Ta có: x =0.
x
+ 1.x
t khác:
( )
()
( )



=
=
⇒=
00f
11f
xxf
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.

α
=
α
.1 =
α
.(x +
x
) =
α
.
x
+
α
.x
t khác:
( )
(
)
( )



=
=
⇒=
0f
1f
xf
Suy ra f(x) = α có th biu din:
f(x) =

th nht cho hàm 1 bin, ta có:
f(x
1
,x
2
) = f(0,x
2
).
x
1
+ f(1,x
2
).x
1
Bây gi, các hàm f(0,x
2
) và f(1,x
2
) tr thành các hàm 1 bin s theo x
2
. 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ó:
f(0,x
2
) = f(0,0).
x
2
+ f(0,1).x
2
f(1,x

hàm Boole hai bin s f(x
1
,x
2
).
Biu thc tng quát này có th biu din bng công thc sau:
f(x
1
,x
2
) =
2

2
1

12
1
0e
1
x)x,f(
2
2
∑
−
=
Trong ó e là s thp phân tng ng vi mã nh phân (α
1
,α
2

) nh sau:
f(x
1
,x
2
, ,x
n
) =
n
n
2
21
xx)x, ,,f(
n2
1
n
2
0e
1



1

∑
−
=
trong ó e là s thp phân tng ng vi mã nh phân (
α
1


x
=
Chng 2. i s BOOLE Trang 17
Ví d 2.6:
Vit biu thc ca hàm 3 bin theo dng chính tc 1:
f(x
1
,x
2
,x
3
) =
∑
−
=
12
0e
3
f (α
1
,α
2
,α
3
).x
1
α1
.x
2

2
, x
3
) = f(0,0,0)
x
1
x
2
x
3
+ f(0,0,1)
x
1
x
2
x
3
+ f(0,1,0)
x
1
x
2
x
3
+ f(0,1,1)
x
1
x
2
x

c vit nh sau:
f(x
1
, x
2
, , x
n
) =
∏
−
=
12
0e
n
[f(α
1
,α
2
,α
3
) + x
1
α1
+ x
2
α2
+ + x
n
αn
)]

1
+
x
2
][f(1,0)+
x
1
+x
2
][f(1,1)+
x
1
+
x
2
]
Ví d 2.8
: Biu thc ca hàm Boole 3 bin  dng chính tc 2:
f(x
1
,x
2
,x
3
) = [f(0,0,0)+x
1
+ x
2
+x
3

3
].[f(1,0,1)+
x
1
+x
2
+
x
3
].
[f(1,1,0)+
x
1
+
x
2
+x
3
].[f(1,1,1)+
x
1
+
x
2
+
x
3
]
i
i

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

bng 0 c vit  dng bù (
x
i
).
Ví d 2.10
:
Vit biu thc biu din hàm f(x
1
,x
2
,x
3
)  dng chính tc 2 vi bng giá tr ca hàm ra c cho
nh sau:
x
3
x
2
x
1
f(x
1
,x
2,
x
3
)
0 0 0 0
0 0 1 0
0 1 0 0

+x
3
).
(1+x
1
+
x
2
+
x
3
).(1+
x
1
+x
2
+x
3
).(1+
x
1
+x
2
+
x
3
).
(1+
x
1

+x
3
).(x
1
+x
2
+
x
3
).(x
1
+
x
2
+x
3
)
Nhn xét:
• D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
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
h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
b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.

 bng trng thái có th vit biu thc ca hàm f(x
1
,x
2
) 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
1
, x
2
) =
x
1
.x
2
+ x
1
.
x
2
+ x
1
.x
2
=
x
1
.x
2
+ x

2
T biu thc mô t trng thái /tt ca èn f(x
1
,x
2
) thy rng có th thc hin mch bng phn
 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.
Bài ging K THUT S Trang 20
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
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
 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.
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
a hàm là tùy ý (hay tùy nh), ngi ta kí hiu bng ch X.
u hàm có n bin vào s có 2
n
ô vuông

0
1
00 0111 10
f
x
1
x
2
x
3
x
4
00
01
11
10
00 0111 10
f
x
2
x
3
x
4
x
5
00
01
11
10

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 d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 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 2.12
Ti thiu hoá hàm f(x
1
,x
2
) =
x
1
x
2
+ x
1
x
2
+ x
1
x
2
f(x
1

x
2
= x
2
+ x
1
Ví d 2.13
Ti thiu hoá hàm 3 bin sau
f(x
1
,x
2
,x
3
) =
x
1
x
2
x
3
+ x
1
x
2
x
3
+ x
1
x

1
x
2
x
3
+ x
1
x
2
(
x
3
+ x
3
)
=
x
1
x
2
x
3
+ x
1
x
2
(
x
3
+ x

1
+ x
2
x
3
Ví d 2.14
Rút gn biu thc: f = BCACAB +++
Áp dng nh lý De Morgan ta có:
f =
BCACAB ++.
=
BCACBA +++ ).(
=
BCACBCA +++
= CBCACA +++
= BCACA +++ ).1(
=
BACC ++
=
CBA
+
+
Vy,  thc hin mch này có th dùng cng OR 3 ngõ vào.
2. Phng pháp bng Karnaugh
 ti thiu hóa hàm Boole bng phng pháp bng Karnaugh phi tuân th theo qui tc v ô k
n: “Hai ô c gi là k cn nhau là hai ô mà khi ta t ô này sang ô kia ch làm thay
i giá tr ca 1 bin.”
Quy tc chung ca phng pháp rút gn bng bng Karnaugh là gom (kt hp) các ô k cn li
i nhau.
Khi gom 2 ô k cn s loi c 1 bin (2=2

ng ô k cn là 2
n
ln nht. u ý các ô tùy nh (X) ch là nhng ô thêm vào vòng gom  rút
n hn các bin mà thôi.
Các vòng gom bt buc phi ph ht tt c các ô có giá tr bng 1 có trong bng (nu ti thiu
theo dng chính tc 1), tng t các vòng gom bt buc phi ph ht tt c các ô có giá tr bng 0
có trong bng (nu ti thiu theo dng chính tc 2) thì kt qu ti thiu hoá mi hp l.
Các trng hp c bit:
u tt c các ô ca bng Karnaugh u bng 1 và tunh (X) ngha là tt c các ô u k cn
→ giá tr ca hàm bng 1.
u tt c các ô ca bng Karnaugh u bng 0 và tunh (X) ngha là tt c các ô u k cn
→ giá tr ca hàm bng 0.
Ví d 2.15
: Ti thiu hóa hàm sau
0 1
0 0 1
1 1 1
Ví d 2.16:
i thiu theo chính tc 1: Ta ch quan tâm n nhng ô có giá tr bng 1 và tùy nh (X), nh
y s có 2 vòng gom  ph ht các ô có giá tr bng 1: vòng gom 1 gm 4 ô k cn, và vòng gom
2 gm 2 ô k cn (hình v).
i vi vòng gom 1: Có 4 ô = 2
2
nên loi c 2 bin. Khi i vòng qua 4 ô k cn trong vòng
gom ch có giá tr ca bin x
1
không i (luôn bng 1), còn giá tr ca bin x
2
thay i (t 1→0) và
giá tr ca bin x

3
c gi li, ch có bin x
1
b loi. Vì x
2
=1 và x
3
=1 nên kt qu ca vòng gom 2 theo dng chính
c 1 s có x
2
và x
3
vit  dng tht: x
2
.x
3
t hp 2 vòng gom ta có kt qu ti gin theo chính tc 1:
f(x
1
,x
2
,x
3
) = x
1
+ x
2
.x
3
00 01 11 10

,x
3
)
Vòng gom 2:
x
2
.x
3
Vòng gom 1: x
1
Bài ging K THUT S Trang 24
i thiu theo chính tc 2: Ta quan tâm n nhng ô có giá tr bng 0 và tùy nh (X), nh vy
ng có 2 vòng gom (hình v), mi vòng gom u gm 2 ô k cn.
i vi vòng gom 1: Có 2 ô = 2
1
nên loi c 1 bin, bin b loi là x
2
(vì có giá tr thay i t
0→1). Vì x
1
=0 và x
3
=0 nên kt qu ca vòng gom 1 theo dng chính tc 2 s có x
1
và x
3
 dng
tht: x
1
+ x

) = (x
1
+x
3
).(x
1
+x
2
)
= x
1
.x
1
+ x
1
.x
2
+ x
1
.x
3
+ x
2
.x
3
= x
1
+ x
1
.x

Ngi ta thng cho hàm Boole di dng biu thc rút gn. Vì có 2 cách biu din hàm
Boole theo dng chính tc 1 hoc 2 nên s có 2 cách cho giá tr ca hàm Boole ng vi 2 dng
chính tc ó:
ng chính tc 1: Tng các tích s.
f(x
1
,x
2
,x
3
) =
Σ
(3,4,7) + d(5,6)
Trong ó ký hiu d ch giá tr các ô này là tùy nh (d: Don’t care)
Lúc ó bng Karnaugh sc cho nh hình trên. T biu thc rút gn ca hàm ta thy ti các ô
ng vi t hp nh phân các bin vào có giá tr là 3, 4, 7 hàm ra có giá tr bng 1; ti các ô ng vi
 hp nh phân các bin vào có giá tr là 5, 6 hàm ra có giá tr là tùy nh; hàm ra có giá tr bng 0
 nhng ô còn li ng vi t hp các bin vào có giá tr là 0, 1, 2.
ng chính tc 2: Tích các tng s.
Phng trình trên cng tng ng vi cách cho hàm nh sau:
f(x
1
,x
2
,x
3
) =
Π
(0, 1, 2) + d(5, 6)
00 01 11 10

x
3
f(x
1
,x
2
,x
3
)
Chng 2. i s BOOLE Trang 25
Ví d 2.17: Ti thiu hóa hàm 4 bin cho di dng biu thc sau:
f(x
1
,x
2
,x
3
,x
4
) =
Σ
(2,6,10,11,12,13) + d(0,1,4,7,8,9,14,15)
Thc hin ti thiu hóa theo dng chính tc 1: t bn  Karnaugh ta có 2 vòng gom, vòng gom 1
m 8 ô k cn và vòng gom 2 gm 8 ô k cn. Kt qu ti thiu hóa nh sau:
Vòng gom 1:
x
1
Vòng gom 2: x
4
y: f(x

x
4
x
3
x
2
x
1
f(x
1
,x
2
,x
3
,x
4
)
x
4
x
3
x
2
x
1
f(x
1
,x
2
,x