Chỉång 2. Âải säú BOOLE Trang 19
f(x
1
, x
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


Váûy, dảng chênh tàõc thỉï hai l dảng têch ca cạc täøng säú m trong
âọ mäùi täøng säú ny chỉïa âáưy â cạc biãún Boole dỉåïi dảng tháût hồûc
dảng b.

Chụ :
Xẹt vê dủ 1: f(x
1
, x
2
) = x
1
+ x
2
,
Viãút dỉåïi dảng chênh tàõc 1:
f(x
1
, x
2
) = 0.x
1
x
2
+ 1.x
1
.x
2
+ 1.x
1

3
) = x
1
+ x
2
.x
3

Viãút dỉåïi dảng chênh tàõc 2:
f(x
1
, x
2
, x
3
) = [0+x
1
+x
2
+x
3
].[0+x
1
+x
2
+x
3
].[0+x
1
+x

].[1+x
1
+x
2
+x
3
]
Hay: f(x
1
, x
2
, x
3
) = x
1
+ x
2
.x
3
= [x
1
+x
2
+x
3
].[x
1
+x
2
+x

x
2
eỡn
f(x
1
,x
2
)
0
0
1
1
0
1
0
1
0
1
1
1

Vióỳt theo daỷng chờnh từc 1 ta coù:
f(x
1
, x
2
) = 0.x
1
x
2

. x
2
+ x
1
(x
2
+ x
2
)
=
x
1
. x
2
+ x
1
= x
1
+ x
2
Vióỳt theo daỷng chờnh từc 2 ta coù:
f(x
1
, x
2
) = [0+x
1
+x
2
].[1+x


2.2.2.3. Phổồng phaùp bióứu dióựn bũng baớng Karnaugh
ỏy laỡ caùch bióứu dióựn laỷi cuớa phổồng phaùp baớng dổồùi daỷng baớng
gọửm caùc ọ vuọng coù daỷng nhổ hỗnh bón. Chỉång 2. Âải säú BOOLE Trang 21
Trãn bng ny ngỉåìi ta bäú trê cạc biãún vo theo hng hồûc theo cäüt
ca bng. Trong trỉåìng håüp säú lỉåüng biãún vo l chàơn, ngỉåìi ta bäú trê
säú lỉåüng biãún vo theo hng ngang bàòng säú lỉåüng biãún vo theo cäüt
dc ca bng. Trong trỉåìng håüp säú lỉåüng biãún vo l l, ngỉåìi ta bäú trê
säú lỉåüng biãún vo theo hng ngang nhiãưu hån säú lỉåüng biãún vo theo
cäüt dc 1 biãún hồûc ngỉåüc lải.
Cạc täø håüp giạ trë ca biãún vo theo hng ngang hồûc theo cäüt dc
ca bng âỉåüc bäú trê sao cho khi ta âi tỉì mäüt ä sang mäüt ä lán cáûn våïi
nọ chè lm thay âäøi mäüt giạ trë ca biãún, nhỉ váûy thỉï tỉû
bäú trê hay sàõp
xãúp cạc täø håüp giạ trë ca biãún vo theo hng ngang hồûc theo cäüt dc
ca bng Karnaugh hon ton tn th theo m Gray. Giạ trë ghi trong
mäùi ä vng ny chênh l giạ trë ca hm ra tỉång ỉïng våïi cạc täø håüp
giạ trë ca biãún vo. ÅÍ nhỉỵng ä m giạ trë hm l khäng xạc âënh, cọ
nghéa l giạ trë ca hm l ty (hay ty âënh), ngỉåìi ta kê hiãûu bàòng
chỉỵ x. Nãúu cọ n biãún vo s cọ 2n ä vng.

2.3. TÄÚI THIÃØU HM 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 ny âỉåüc âàûc trỉng bàòng mäüt phỉång trçnh logic.
Trong âọ, mỉïc âäü phỉïc tảp ca så âäư ty thüc vo phỉång trçnh logic
biãøu diãùn chụng. Viãûc âảt âỉåüc âäü äøn âënh cao hay khäng l ty thüc

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

Vê dủ:
f(x
1
, x

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

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

2.3.3.2. Phỉång phạp bng Karnaugh
a. Täúi thiãøu họa hm Boole bàòng bng Karnaugh
Âãø täúi thiãøu họa hm Boole bàòng phỉång phạp bng Karnaugh phi
tn th theo qui tàõc vãư ä kãú cáûn: “Hai ä âỉåüc gi l kãú cáûn nhau l hai
ä m khi ta tỉì ä ny sang ä kia chè lm thay âäøi giạ trë ca 1 biãún. “
Quy tàõc chung ca phỉång phạp rụt gn bàòng bng Karnaugh l
gom (kãút håüp) cạc ä kãú cáûn lải våïi nhau. Khi gom 2 ä kãú cáûn nhau s
loải âỉåüc 1 biãún (2 ä =2
1
loải 1 biãún). Khi gom 4 ä kãú cáûn s loải âỉåüc
2 biãún (4 ä =2
2


0 1
x
2
f(x
1
,x
2
)
x
1
0 0 1
1 1 1
Tọỳi thióứu hoùa theo daỷng chờnh từc 2:
f(x
1
,x
2
) = x
1
+ x
2

Vờ duỷ 2: Tọỳi thióứu hoùa haỡm sau bũng phổồng phaùp baớng Karnaugh. 00 01 11 10
x
3
f(x

cỏỷn
(hỗnh veợ).
Baỡi giaớng Kyợ Thuỏỷt Sọỳ Trang 24
ọỳi vồùi voỡng gom 1: Coù 4 ọ = 2
2
nón seợ loaỷi õổồỹc 2 bióỳn. Khi õi
voỡng qua 4 ọ kóỳ cỏỷn trong voỡng gom chố coù giaù trở cuớa bióỳn x
1
khọng
õọứi (luọn bũng 1), coỡn giaù trở cuớa bióỳn x
2
thay õọứi (tổỡ 10) vaỡ giaù trở
cuớa bióỳn x
3
thay õọứi (tổỡ 01) nón caùc bióỳn x
2
vaỡ x
3
bở loaỷi, chố coỡn laỷi
bióỳn x
1
trong kóỳt quaớ cuớa voỡng gom 1. Vỗ x
1
=1 nón kóỳt quaớ cuớa voỡng
gom 1 theo daỷng chờnh từc 1 seợ coù x1 vióỳt ồớ daỷng thỏỷt: x
1

ọỳi vồùi voỡng gom 2: Coù 2 ọ = 2
1
nón seợ loaỷi õổồỹc 1 bióỳn. Khi õi

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

Tọỳi giaớn theo daỷng chờnh từc 2: Ta quan tỏm õóỳn nhổợng ọ coù giaù trở
bũng 0 vaỡ tuỡy õởnh, nhổ vỏỷy cuợng coù 2 voỡng gom (hỗnh veợ), mọựi voỡng
gom õóửu gọửm 2 ọ kóỳ cỏỷn.
ọỳi vồùi voỡng gom 1: Coù 2 ọ = 2
1
nón loaỷi õổồỹc 1 bióỳn, bióỳn bở loaỷi laỡ
x
2
(vỗ coù giaù trở thay õọứi tổỡ 01). Vỗ x
1
=0 vaỡ x
3
=0 nón kóỳt quaớ cuớa
voỡng gom 1 theo daỷng chờnh từc 2 seợ coù x
1
vaỡ x
3
ồớ daỷng thỏỷt: x

2
,x
3
)
0 0 0 1 1
1 0 1 1 1
Voỡn
g

g
om 2: x
1
+ x
2
Voỡn
g

g
om 1: x
1
+ x
3
x
1
,x
2


+ x
2
.x
3
= x
1
+ x
1
.x
2
+ x
1
.x
3
+ x
2
.x
3
Chỉång 2. Âải säú BOOLE Trang 25
= x
1
(1+ x
2
+ x
3
) + x
2
.x
3
= x

00 01 11 10
0
00X1
1
011X
x
3
f(x
1
,x
2
,x
3
)
x
1
,x
2 Lục âọ bng Karnaugh s âỉåüc cho nhỉ hçnh trãn. Tỉì biãøu thỉïc rụt
gn ca hm ta tháúy tải cạc ä ỉïng våïi täø håüp nhë phán cạc biãún vo cọ
giạ trë l 3, 4, 7 thç hm ra cọ giạ trë bàòng 1; tải cạc ä ỉïng våïi täø håüp

nhë phán cạc biãún vo cọ giạ trë l 5,6 thç hm ra cọ giạ trë l ty âënh;
hm ra cọ giạ trë bàòng 0 åí nhỉỵng ä cn lải ỉïng våïi täø håüp cạc biãún vo
cọ giạ trë l 0, 1, 2.

x
3
,x
4
Voỡng gom 1
Voỡng gom 2
f(x
1
,x
2
,x
3
,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
f(x
x
3
,x

Vỏỷy: f(x
1
, x
2
, x
3
, x
4
) = x
4
+ x
1Bi ging K Thût Säú Trang 12
Chỉång 2

ÂẢI SÄÚ BOOLE

2.1. CẠC TIÃN ÂÃƯ V ÂËNH L ÂẢI SÄÚ BOOLE
2.1.1. Cạc tiãn âãư
Cho mäüt táûp håüp B hỉỵu hản trong âọ ngỉåìi ta trang bë cạc phẹp toạn
+ (cäüng logic), x (nhán logic), - (b logic ) v hai pháưn tỉí 0 v 1 láûp
thnh mäüt cáúu trục âải säú Boole.

∀x,y ∈ B thç: x + y ∈ B, x.y ∈ B tha mn 5 tiãn âãư sau:

2.1.1.1. Tiãn âãư giao hoạn
∀x,y ∈ B: x + y = y + x
2.1.1.2. Tiãn âãư phäúi håü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 âãư cn lải l âụng.

Vê dủ: x.(y + z ) = ( x. y) + ( x. z )
x + (y. z ) = ( x + y )( x + z )
Vê dủ: x +
x
= 1
x.
x = 0
2.1.2.2. Cạc âënh l
a. Âënh l vãư pháưn tỉí b l duy nháút
∀x, y ∈ B:
xy
0 x.y
1yx
=⇒
=
=+
⎭
⎬
⎫

∀x ∈ B:
x + x +. . . . . + x = x
x. x. x. . . . . . x = x
b. Âënh l De Morgan
∀x, y, z ∈ B, ta cọ:

(cäüng logic ), x (nhán logic ), hồûc nghëch âo logic (-). Hm Boole
âån gin nháút l hm Boole theo 1 biãún Boole.
K hiãûu: f(x) = x
f(x) =
x
f(x) = α (α: l hàòng säú )
Trong trỉåìng håüp täøng quạt, ta cọ hm Boole theo n biãún Boole
âỉåüc k hiãûu nhỉ sau: f(x
1
, x
2
,. . . . . ., x
n
)
2.2.1.2. Cạc tênh cháút ca hm Boole
Nãúu f(x
1
, x
2
, , x
n
) l mäüt hm Boole thç:
+ α.f(x
1
, x
2
, , x
n
) cng l mäüt hm Boole.
+

2
, , x
n
) + f
2
(x
1
, x
2
, , x
n
) cng l mäüt hm Boole.
+ f
1
(x
1
, x
2
, , x
n
).f
2
(x
1
, x
2
, , x
n
) cng l mäüt hm Boole.
Chổồng 2. aỷi sọỳ BOOLE Trang 15

, x
2
) = x
1
+ x
2
Xeùt B = B* ={0,1}
x
1
x
2
f(x
1
, x
2
)
0
0
1
1
0
1
0
1
0
1
1
1
Nóỳu x
1

3
) = x
1
+ x
2
.x
3
Xeùt B = B* = {0,1 }
Baớng giaù trở cuớa haỡm:
x
1
x
2
x
3
f (x
1
, x
2
, x
3
)
0
0
0
0
1

Laỡ phổồng phaùp thổồỡng duỡng õóứ bióứu dióựn haỡm sọỳ noùi chung.
Phổồng phaùp naỡy gọửm mọỹt baớng õổồỹc chia laỡm hai phỏửn:
- Mọỹt phỏửn daỡnh cho bióỳn õóứ ghi caùc tọứ hồỹp giaù trở coù thóứ coù cuớa
bióỳn.
- Mọỹt phỏửn daỡnh cho haỡm õóứ ghi caùc giaù trở cuớa haỡm ra tổồng ổùng
vồùi caùc tọứ hồỹp cuớa caùc bióỳn vaỡo.

2.2.2.2. Phổồng phaùp giaới tờch
Laỡ phổồng phaùp bióứu dióựn haỡm Boole dổồùi daỷng tọứng caùc tờch sọỳ,
hoỷc dổồùi daỷng tờch cuớa caùc tọứng sọỳ. Daỷng tọứng cuớa caùc tờch sọỳ goỹi laỡ
daỷng chờnh từc thổù nhỏỳt, coỡn daỷng tờch cuớa caùc tọứng laỡ daỷng chờnh từc
thổù hai
cuớa haỡm Boole, vaỡ hai daỷng chờnh từc naỡy laỡ õọỳi ngỏựu nhau.
a. Daỷng chờnh từc 1(Daỷng tọứng cuớa caùc tờch sọỳ)
Xeùt caùc haỡm Boole õồn giaớn sau õỏy: f(x) = x, f(x) = x , f(x) = .
Xeùt f(x) = x:
Ta coù: x =0.
x + 1. x
mỷt khaùc:
()
()
()



=
=
=
00f
11f

Xeùt f(x) = :
Ta coù: = .1 = (x +
x ) = x . + .x
Mỷt khaùc:
()
()
()



=
=
=



0f
1f
xf

Suy ra f(x) = coù thóứ õổồỹc bióứu dióựn:
f(x) = = f(0).
x + f(1).x
Kóỳt luỏỷn:
Duỡ laỡ f(x) = x, f(x) =
x
hay f(x) = , ta õóửu coù daỷng:
f(x) = f(0).
x
+ f(1).x

2
+ f(0,1).x
2
vaỡ: 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
+ f(1,0 )x
1
x
2
+ f(1,1)x
1
x
2

= 1

x
1
nóỳu
1
= 0
=
1
1
x


x
2
nóỳu
2
= 1

x
2
nóỳu
2
= 0
2
=
2
x

Baỡi giaớng Kyợ Thuỏỷt Sọỳ Trang 18

,
2
, ,
n
);
vaỡ: x
i
nóỳu
i
= 1

x
i
nóỳu
i
= 0
=
i
x

i

Vờ duỷ:
f(x
1
, x
2
, x
3
) = f (

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

f(x
1
, x
2
, , x
n
) = [f(


=
1n
2
0e
1
,
2
,
3
) + x
1

1
+ x
2

2
+ + x
n

n

,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
]

Chỉång 2. Âải säú BOOLE Trang 19
f(x
1
, x
2
, x
3
) = [f(0,0,0)+x
1
+ x

].[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
]

Váûy, dảng chênh tàõc thỉï hai l dảng têch ca cạc täøng säú m trong
âọ mäùi täøng säú ny chỉïa âáưy â cạc biãún Boole dỉåïi dảng tháût hồûc
dảng b.

Chụ :
Xẹt vê dủ 1: f(x
1
, x

2
+ x
1
.x
2
+ x
1
.x
2
Tỉì vê dủ trãn ta tháúy: Dảng chênh tàõc thỉï nháút l dảng liãût kã táút c
cạc täø håüp nhë phán cạc biãún vo sao cho tỉång ỉïng våïi nhỉỵng täø håüp
âọ giạ trë ca hm 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), v biãún tỉång ỉïng bàòng 0 âỉåüc viãút åí dảng
b (
x ).

Xẹt vê dủ 2: f(x
1
, x
2
, x
3
) = x
1
+ x
2
.x
3

Viãút dỉåïi dảng chênh tàõc 2:

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
2
+x
3
]
Hay: f(x
1

cạc biãún vo sao cho tỉång ỉïng våïi nhỉỵng täø håüp âọ giạ trë ca hm 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), v biãún tỉång ỉïng bàòng 1 âỉåüc viãút åí dảng b (
x ).

Xẹt vê dủ âån gin sau âãø hiãøu r hån vãư cạch thnh láûp bng giạ trë
ca hm, tçm hm mảch v thiãút kãú mảch: Hy thiãút kãú mảch âiãûn sao
Baỡi giaớng Kyợ Thuỏỷt Sọỳ Trang 20
cho khi cọng từc 1 õoùng thỗ õeỡn õoớ, cọng từc 2 õoùng õeỡn õoớ, caớ hai
cọng từc õoùng õeỡn õoớ.
Giaới
Ta qui õởnh:
- Cọng từc hồớ : 0 eỡn từt : 0
- Cọng từc õoùng : 1 eỡn õoớ : 1
Luùc õoù ta coù baớng traỷng thaùi mọ taớ hoaỷt õọỹng cuớa maỷch: Cọng từc 1
x
1
Cọng từc 2
x
2
eỡn
f(x
1
,x
2
)
0

1
.x
2

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

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

+x
2
]
= [x
1
+ x
2
].1.1.1 = x
1
+ x
2
Vỏỷy, duỡ vióỳt theo daỷng chờnh từc 1 hay chờnh từc 2 ta õóửu coù haỡm
maỷch:
f(x
1
, x
2
) = x
1
+ x
2

2.2.2.3. Phổồng phaùp bióứu dióựn bũng baớng Karnaugh
ỏy laỡ caùch bióứu dióựn laỷi cuớa phổồng phaùp baớng dổồùi daỷng baớng
gọửm caùc ọ vuọng coù daỷng nhổ hỗnh bón. Chỉång 2. Âải säú BOOLE Trang 21
Trãn bng ny ngỉåìi ta bäú trê cạc biãún vo theo hng hồûc theo cäüt
ca bng. Trong trỉåìng håüp säú lỉåüng biãún vo l chàơn, ngỉåìi ta bäú trê