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

=
=+





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ó:
zyx ..zyx =++
zyxx.y.z ++=
 qu:
∀x, y, z ∈ B, ta có:
x + y + z =
zyx ++ = z.y.x
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

u f(x
1
, x
2
, ...., x
n
) là mt hàm Boole thì:
- α.f(x
1
, 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

, x
2
, ...., x
n
).f
2
(x
1
, 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

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

0
1
0
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
0
0
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

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à 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. x + 0. x
t khác:
( )
()
( )

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 N T S 1 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
):
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
2
là hng s, x
1
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
1
,x
2
) = f(0,x
2
).

,x
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
â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
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

1
= 0
x
2
nu α
2
= 1
x
2
nu α
2
= 0
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
1
,x
2
, ..,x
n
) nh sau:
f(x
1
,x
2
, ..,x
n
) =
n

x
i
nu α
i
= 0 (vi i = 1, 2, 3,…,n)
1
1
x

=
2
2
x

=
i
i

x
=