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
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
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.
2.1.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.
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ó:
xy
0x.y
1yx
=⇒
=
=
+





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

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
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) = α (α 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
1
, x
2
, , x
n
)
2. Các tính cht ca hàm Boole

n
) và f
2
(x
1
, x
2
, , x
n
) là nhng hàm Boole thì:
- f
1
(x
1
, x
2
, , x
n
) + f
2
(x
1
, x
2
, , x
n
) cng là mt hàm Boole.
- f
1
(x

n,1i = ) thì giá tr f (
α
1
,
α
2
, ,
α
n
)
c gi là giá tr ca hàm Boole theo n bin.
Ví d 2.3
:
Xét hàm f(x
1
, x
2
) = x
1
+ x
2
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
1
= 0, x
2
= 0 → f(0,0) = 0 + 0 = 0
Bài ging K THUT S Trang 14
- x

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

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
, x
3
) có thc cho bng bng giá tr nh sau:
x
1
x
2
x
3
f (x
1
, x
2
, x
3
)
0
0
0
0
1

1
x
2
f(x
1
, x
2
) = x
1
+ x
2
0
0
1
1
0
1
0
1
0
1
1
1
Chng 2. i s BOOLE Trang 15
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:
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.

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
t khác:
( )
(
)
( )



=
=
⇒=
10f
01f
xxf
Suy ra: f(x) =
x
có th biu din:
f(x) =
x


=
=
⇒=
0f
1f
xf
Suy ra f(x) = α có th biu din:
f(x) =
α
= f(0).
x
+ f(1).x
t lun
: Dù f(x) = x, f(x) =
x
hay f(x) = α, 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:
Bài ging K THUT S Trang 16
f(x) = f(0).
x
+ f(1).x
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  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
1
, x
2

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
2
) = f(1,0).
x
2
+ f(1,1).x
2
Suy ra:
f(x
1
,x
2
) = f(0,0).
x
1
x
2
+ f(0,1).
x
1
x
2

2
2
∑
−
=
Trong ó e là s thp phân tng ng vi mã nh phân (α
1
,α
2
) và:
x
1
nu α
1
= 1
x
1
nu α
1
= 0
x
2
nu α
2
= 1
x
2
nu α
2
= 0


1

∑
−
=
trong ó e là s thp phân tng ng vi mã nh phân (
α
1
,
α
2
, ,
α
n
);
và: x
i
nu
α
i
= 1
x
i
nu α
i
= 0 (vi i = 1, 2, 3,…,n)
1
1
x

,α
2
,α
3
).x
1
α1
.x
2
α2
.x
3
α3
ng di ây cho ta giá tr ca s thp phân e và t hp mã nh phân (α
1
,α
2
,α
3
) tng ng:
e
α
1
α
2
α
3
0 0 0 0
1 0 0 1
2 0 1 0

2
x
3
+ f(0,1,1)
x
1
x
2
x
3
+ f(1,0,0) x
1
x
2
x
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

1
α1
+ x
2
α2
+ + x
n
αn
)]
trong ó e là s thp phân tng ng vi mã nh phân (α
1
,α
2
, ,α
n
);
và:
x
i
nu
α
i
= 1
x
i
nu α
i
= 0 (vi i = 1, 2, 3,…,n)
Ví d 2.7: 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:

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
2
+
x
3
]
i
i
x

=
Bài ging K THUT S Trang 18
V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 2.9:
Hãy vit biu thc biu din cho hàm Boole 2 bin f(x
1
,x
2
)  dng chính tc 1, vi bng giá tr
a hàm c cho nh sau:
x
1
x
2
f(x
1
,x
2

x
1
x
2
+ 1.
x
1
.x
2
+ 1.x
1
.
x
2
+ 1.x
1
.x
2
=
x
1
.x
2
+ x
1
.
x
2
+ x
1

1
,x
2,
x
3
)
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 1
1 0 1 1
1 1 0 1
1 1 1 1
Vit di dng chính tc 2 (tích các tng s):
f(x
1
,x
2
,x
3
) = (0+x
1
+x
2
+x
3
).(0+x
1
+x

+x
2
+
x
3
).
(1+
x
1
+
x
2
+x
3
).(1+
x
1
+
x
2
+
x
3
)
Chng 2. i s BOOLE Trang 19
Áp dng tiên  v phn t trung hòa 0 và 1 ta có:
x + 1 = 1, x . 1 = x
x + 0 = x, x . 0 = 0
nên suy ra biu thc trên có th vit gn li:
f(x

• 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.
Ví d 2.11
Hãy thit k mch n sao cho khi công tc 1 óng thì èn , khi công tc 2 óng èn , khi
 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 èn tt : 0
- Công tc óng : 1 è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
1
x
2
f(x
1
,x
2
)
0
0
1

1
.x
2
=
x
1
.x
2
+ x
1
(
x
2
+ x
2
)
=
x
1
.x
2
+ x
1
= x
1
+ x
2
- Theo dng chính tc 2 ta có:
f(x
1

, 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
.
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
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:
2.3. TI THIU HÓA HÀM BOOLE
2.3.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 ca s tùy thuc vào
phng trình logic biu din chúng. Vic t c  n nh cao hay không là tùy thuc vào
phng trình logic biu din chúng  dng ti thiu hóa hay cha.  thc hin c 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. u ó có ngha là phng
f(x
1
,x
2
)
x
1
x
2
0

3
x
4
x
5
00
01
11
10
0001 1110 1011 0100
x
1
=0 x
1
=1
Chng 2. i s BOOLE Trang 21
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 d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:
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, 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
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
 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.

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

+ x
1
x
2
x
3
+ x
1
x
2
x
3
+ x
1
x
2
x
3
+ x
1
x
2
x
3
Bài ging K THUT S Trang 22
=
x
1
x
2

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

+
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
1
loi 1 bin).
Khi gom 4 ô k cn vòng tròn s loi c 2 bin (4=2
2
loi 2 bin).
Khi gom 8 ô k cn vòng tròn s loi c 3 bin (8=2
3
loi 3 bin).
Tng quát, khi gom 2
n
ô k cn vòng tròn s loi c n bin. Nhng bin b loi là
nhng bin khi ta i vòng qua các ô k cn mà giá tr ca chúng thay i.
Nhng u cn lu ý:
Vòng gom c gi là hp l khi trong vòng gom ó có ít nht 1 ô cha thuc vòng gom nào.
Các ô k cn mun gom c phi là k cn vòng tròn ngha là ô k cn cui cng là ô k cn
u tiên.
Vic kt hp nhng ô k cn vi nhau còn tùy thuc vào phng pháp biu din hàm Boole theo
ng chính tc 1 hoc chính tc 2, c th là:
•
u biu din hàm theo dng chính tc 1 (tng các tích s) ta ch quan tâm nhng ô k
n có giá tr bng 1 và tùy nh. Kt qu mi vòng gom lúc này s là mt tích rút gn.

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
thay i (t 0→1) nên các bin x
2
và x
3
b loi, ch còn li bin x
1
trong kt qu
a vòng gom 1. Vì x
1
=1 nên kt qu ca vòng gom 1 theo dng chính tc 1 s có x
1
vit  dng
tht: x
1
i vi vòng gom 2: Có 2 ô = 2
1
nên s loi c 1 bin. Khi i vòng qua 2 ô k cn trong vòng
gom giá tr ca bin x
2
và x

,x
3
) = x
1
+ x
2
.x
3
00 01 11 10
0 0 0 1 1
1 0 1 1 1
x
1
x
2
f(x
1
,x
2
)
i thiu hoá theo chính tc 2:
f(x
1
,x
2
) = x
1
+ x
2
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
3
.
i vi vòng gom 2: Có 2 ô = 2
1
nên loi c 1 bin, bin b loi là x
3
(vì có giá tr thay i t
0
→
1). Vì x
1
=0 và x
2
=0 nên kt qu ca vòng gom 2 theo dng chính tc 2 s có x
1
và x
2
 dng
tht: x
1
+x

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

1
,x
2
,x
3
) =
Π
(0, 1, 2) + d(5, 6)
00 01 11 10
0 0 0 1 1
1 0 1 1 1
00 01 11 10
0 0 0 X 1
1 0 1 1 X
x
1
,x
2
x
3
f(x
1
,x
2
,x
3
)
Vòng gom 2: x
1
+ x

(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
1
,x
2
,x
3
,x
4
) =
x
1
+ x
4
00 01 11 10
00
X X 1 X
01
X 0 1 X
11
0 X X 1
10
1 1 X 1

x
2
x
1
f(x
1
,x
2
,x
3
,x
4
)
Vòng gom 2
Vòng gom 1