Bài giảng điện tử số I Chương 2: [Mô tả trọng tâm bài giảng nếu có]

Ch(cid:1133)(cid:1131)ng 2. (cid:264)(cid:1189)i s(cid:1237) BOOLE Trang 11

Ch(cid:1133)(cid:1131)ng 2

(cid:264)(cid:1188)I S(cid:1236) BOOLE

2.1. CÁC TIÊN (cid:264)(cid:1220) VÀ (cid:264)(cid:1230)NH LÝ (cid:264)(cid:1188)I S(cid:1236) BOOLE

Trong các m(cid:1189)ch s(cid:1237), các tín hi(cid:1227)u th(cid:1133)(cid:1249)ng (cid:255)(cid:1133)(cid:1255)c cho (cid:1251) 2 m(cid:1261)c (cid:255)(cid:76)(cid:1227)n áp, ví d(cid:1257): 0V và 5V. Nh(cid:1267)ng linh ki(cid:1227)n (cid:255)(cid:76)(cid:1227)n t(cid:1265) dùng trong m(cid:1189)ch s(cid:1237) làm vi(cid:1227)c (cid:1251) m(cid:1245)t trong hai tr(cid:1189)ng thái, ví d(cid:1257) Transistor l(cid:1133)(cid:1253)ng c(cid:1269)c (BJT) làm vi(cid:1227)c (cid:1251) hai ch(cid:1219)(cid:3)(cid:255)(cid:1245) là t(cid:1203)t ho(cid:1211)c d(cid:1199)n bão hoà… Do v(cid:1201)y, (cid:255)(cid:1223) mô t(cid:1191) các m(cid:1189)ch s(cid:1237) ng(cid:1133)(cid:1249)i ta dùng (cid:75)(cid:1227) nh(cid:1231) phân (binary), hai tr(cid:1189)ng thái c(cid:1259)a các linh ki(cid:1227)n trong m(cid:1189)ch s(cid:1237)(cid:3)(cid:255)(cid:1133)(cid:1255)c mã hoá t(cid:1133)(cid:1131)ng (cid:1261)ng là 0 ho(cid:1211)c 1.

(cid:48)(cid:1245)t b(cid:1245) môn (cid:255)(cid:1189)i s(cid:1237) phát tri(cid:1223)n t(cid:1263) cu(cid:1237)i th(cid:1219) k(cid:1273) 19 mang tên ng(cid:1133)(cid:1249)i sáng l(cid:1201)p ra nó: (cid:255)(cid:1189)i s(cid:1237) Boole, còn (cid:255)(cid:1133)(cid:1255)c g(cid:1233)i là (cid:255)(cid:1189)i s(cid:1237) logic, thích h(cid:1255)p cho vi(cid:1227)c mô t(cid:1191) m(cid:1189)ch s(cid:1237). (cid:264)(cid:1189)i s(cid:1237) Boole là công c(cid:1257) toán h(cid:1233)c quan tr(cid:1233)ng (cid:255)(cid:1223) phân tích và thi(cid:1219)t k(cid:1219) các m(cid:1189)ch s(cid:1237), (cid:255)(cid:1133)(cid:1255)c dùng làm chìa khoá (cid:255)(cid:1223)(cid:3)(cid:255)i sâu vào m(cid:1233)i l(cid:429)nh v(cid:1269)c liên quan (cid:255)(cid:1219)n k(cid:1275) thu(cid:1201)t s(cid:1237).

2.1.1. Các tiên (cid:255)(cid:1221) c(cid:1259)a (cid:255)(cid:1189)i s(cid:1237) Boole

Cho m(cid:1245)t t(cid:1201)p h(cid:1255)p B h(cid:1267)u h(cid:1189)n trong (cid:255)ó ta trang b(cid:1231) các phép toán + (c(cid:1245)ng logic), x (nhân logic), - (bù logic/ngh(cid:1231)ch (cid:255)(cid:1191)o logic) và hai ph(cid:1195)n t(cid:1265) 0 và 1 l(cid:1201)p thành m(cid:1245)t c(cid:1193)u trúc (cid:255)(cid:1189)i s(cid:1237) Boole ((cid:255)(cid:1233)c là Bun). " x,y ˛ B thì: x+y ˛ B, x*y ˛ B và th(cid:1235)a mãn 5 tiên (cid:255)(cid:1221) sau:

1. Tiên (cid:255)(cid:1221) giao hoán

" x,y ˛ B: x + y = y + x

2. Tiên (cid:255)(cid:1221) ph(cid:1237)i h(cid:1255)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 (cid:255)(cid:1221) phân ph(cid:1237)i

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

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

4. Tiên (cid:255)(cid:1221) v(cid:1221) ph(cid:1195)n t(cid:1265) trung hòa

Trong t(cid:1201)p B t(cid:1239)n t(cid:1189)i hai ph(cid:1195)n t(cid:1265) trung hòa là ph(cid:1195)n t(cid:1265) (cid:255)(cid:1131)n v(cid:1231) và ph(cid:1195)n t(cid:1265) không. Ph(cid:1195)n t(cid:1265)(cid:3)(cid:255)(cid:1131)n v(cid:1231)

ký hi(cid:1227)u là 1, ph(cid:1195)n t(cid:1265) không ký hi(cid:1227)u là 0.

" x ˛ B:

x + 1 = 1 x . 1 = x x + 0 = x x . 0 = 0

5. Tiên (cid:255)(cid:1221) v(cid:1221) ph(cid:1195)n t(cid:1265) bù

" x ˛ B, bao gi(cid:1249) c(cid:458)ng t(cid:1239)n t(cid:1189)i ph(cid:1195)n t(cid:1265) bù t(cid:1133)(cid:1131)ng (cid:1261)ng, ký hi(cid:1227)u x , sao cho luôn th(cid:1235)a mãn:

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

Bài gi(cid:1191)ng (cid:264)(cid:44)(cid:1226)N T(cid:1264) S(cid:1236) 1 Trang 12

(cid:49)(cid:1219)u B = B* = {0,1} (B* ch(cid:1229) g(cid:1239)m 2 ph(cid:1195)n t(cid:1265) 0 và 1) và th(cid:1235)a mãn 5 tiên (cid:255)(cid:1221) trên thì c(cid:458)ng l(cid:1201)p thành

(cid:70)(cid:1193)u trúc (cid:255)(cid:1189)i s(cid:1237) Boole nh(cid:1133)ng là c(cid:1193)u trúc (cid:255)(cid:1189)i s(cid:1237) Boole nh(cid:1235) nh(cid:1193)t.

2.1.2. Các (cid:255)(cid:1231)nh lý c(cid:1131) b(cid:1191)n c(cid:1259)a (cid:255)(cid:1189)i s(cid:1237) Boole

1. V(cid:1193)n (cid:255)(cid:1221)(cid:3)(cid:255)(cid:1237)i ng(cid:1199)u trong (cid:255)(cid:1189)i s(cid:1237) Boole

Hai m(cid:1227)nh (cid:255)(cid:1221) (hai bi(cid:1223)u th(cid:1261)c, hai (cid:255)(cid:1231)nh lý) (cid:255)(cid:1133)(cid:1255)c g(cid:1233)i là (cid:255)(cid:1237)i ng(cid:1199)u v(cid:1247)i nhau n(cid:1219)u trong m(cid:1227)nh (cid:255)(cid:1221) này ng(cid:1133)(cid:1249)i ta thay phép toán c(cid:1245)ng thành phép toán nhân và ng(cid:1133)(cid:1255)c l(cid:1189)i, thay 0 b(cid:1205)ng 1 và ng(cid:1133)(cid:1255)c l(cid:1189)i, thì s(cid:1217) suy ra (cid:255)(cid:1133)(cid:1255)c m(cid:1227)nh (cid:255)(cid:1221) kia.

Khi hai m(cid:1227)nh (cid:255)(cid:1221)(cid:3)(cid:255)(cid:1237)i ng(cid:1199)u v(cid:1247)i nhau, n(cid:1219)u 1 trong 2 m(cid:1227)nh (cid:255)(cid:1221)(cid:3)(cid:255)(cid:1133)(cid:1255)c ch(cid:1261)ng minh là (cid:255)úng thì m(cid:1227)nh

(cid:255)(cid:1221) còn l(cid:1189)i là (cid:255)úng. D(cid:1133)(cid:1247)i (cid:255)ây là ví d(cid:1257) v(cid:1221) các c(cid:1211)p m(cid:1227)nh (cid:255)(cid:1221)(cid:3)(cid:255)(cid:1237)i ng(cid:1199)u v(cid:1247)i nhau.

Ví d(cid:877) 2.1: Hai m(cid:847)nh (cid:255)(cid:841) này là (cid:255)(cid:857)i ng(cid:819)u x.(y+z) = (x.y) + (x.z) x + (y.z) = (x+y).(x+z)

Ví d(cid:877) 2.2: x + x = 1 Hai m(cid:847)nh (cid:255)(cid:841) này là (cid:255)(cid:857)i ng(cid:819)u x. x = 0

2. Các (cid:255)(cid:1231)nh lý

a. (cid:264)(cid:851)nh lí 1 ((cid:264)(cid:851)nh lý v(cid:841) ph(cid:815)n t(cid:885) bù là duy nh(cid:813)t) " x, y ˛ B, ta có:

= xy

=+ 1yx = x.y

(cid:252) (cid:239) (cid:222) (cid:253) là duy nh(cid:1193)t (x và y là 2 ph(cid:1195)n t(cid:1265) bù c(cid:1259)a nhau) (cid:239) (cid:254)

Ph(cid:1195)n t(cid:1265) bù c(cid:1259)a m(cid:1245)t ph(cid:1195)n t(cid:1265) b(cid:1193)t k(cid:484) là duy nh(cid:1193)t.

b. (cid:264)(cid:851)nh lí 2 ((cid:264)lý v(cid:841) s(cid:889)(cid:3)(cid:255)(cid:859)ng nh(cid:813)t c(cid:879)a phép c(cid:865)ng và phép nhân logic) " x ˛ B, ta có:

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

c. (cid:264)(cid:851)nh lý 3 ((cid:264)(cid:851)nh lý v(cid:841) ph(cid:879)(cid:3)(cid:255)(cid:851)nh hai l(cid:815)n)

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

=++ zy

. zyx .

++=

x.y.z

d. (cid:264)(cid:851)nh lí 4 ((cid:264)(cid:851)nh lý De Morgan) " x, y, z ˛ B, ta có:

(cid:43)(cid:1227) qu(cid:1191): " x, y, z ˛ B, ta có:

z.y.x

x + y + z = =

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

e. (cid:264)(cid:851)nh lí 5 ((cid:264)(cid:851)nh lý dán) " x, y ˛ B, ta có:

x. ( x + y) = x.y

x + ( x .y) = x + y

Trang 13 Ch(cid:1133)(cid:1131)ng 2. (cid:264)(cid:1189)i s(cid:1237) BOOLE

f. (cid:264)(cid:851)nh lí 6 ((cid:264)(cid:851)nh lý nu(cid:857)t) " x, y ˛ B, ta có:

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

0 = 1

1 = 0

g. (cid:264)(cid:851)nh lí 7 (Quy t(cid:823)c tính (cid:255)(cid:857)i v(cid:867)i h(cid:825)ng) (cid:57)(cid:1247)i 0, 1 ˛ B, ta có:

2.2. HÀM BOOLE VÀ CÁC PH(cid:1132)(cid:1130)NG PHÁP BI(cid:1222)U DI(cid:1224)N

2.2.1. Hàm Boole

1. (cid:264)(cid:1231)nh ngh(cid:429)a Hàm Boole là m(cid:1245)t ánh x(cid:1189) t(cid:1263)(cid:3)(cid:255)(cid:1189)i s(cid:1237) Boole vào chính nó. Ngh(cid:429)a là " x, y ˛ B (cid:255)(cid:1133)(cid:1255)c g(cid:1233)i là các

bi(cid:1219)n Boole thì hàm Boole, ký hi(cid:1227)u là f, (cid:255)(cid:1133)(cid:1255)c hình thành trên c(cid:1131) s(cid:1251) liên k(cid:1219)t các bi(cid:1219)n Boole b(cid:1205)ng các phép toán + (c(cid:1245)ng logic), x / . (nhân logic), ngh(cid:1231)ch (cid:255)(cid:1191)o logic (-).

là h(cid:1205)ng s(cid:1237) ) (a Hàm Boole (cid:255)(cid:1131)n gi(cid:1191)n nh(cid:1193)t là hàm Boole theo 1 bi(cid:1219)n Boole, (cid:255)(cid:1133)(cid:1255)c cho nh(cid:1133) sau: f(x) = x, f(x) = x , f(x) = a

Trong tr(cid:1133)(cid:1249)ng h(cid:1255)p t(cid:1241)ng quát, ta có hàm Boole theo n bi(cid:1219)n Boole (cid:255)(cid:1133)(cid:1255)c ký hi(cid:1227)u nh(cid:1133) sau:

f(x1, x2, ...., xn)

2. Các tính ch(cid:1193)t c(cid:1259)a hàm Boole

(cid:49)(cid:1219)u f(x1, x2, ...., xn) là m(cid:1245)t hàm Boole thì: a - .f(x1, x2, ...., xn) c(cid:458)ng là m(cid:1245)t hàm Boole.

f (x1, x2, ...., xn) c(cid:458)ng là m(cid:1245)t hàm Boole.

(cid:49)(cid:1219)u f1(x1, x2, ...., xn) và f2(x1, x2, ...., xn) là nh(cid:1267)ng hàm Boole thì:

- f1(x1, x2, ...., xn) + f2(x1, x2, ...., xn) c(cid:458)ng là m(cid:1245)t hàm Boole. c(cid:458)ng là m(cid:1245)t hàm Boole. - f1(x1, x2, ...., xn).f2(x1, x2, ...., xn)

(cid:57)(cid:1201)y, m(cid:1245)t hàm Boole f c(cid:458)ng (cid:255)(cid:1133)(cid:1255)c hình thành trên c(cid:1131) s(cid:1251) liên k(cid:1219)t các hàm Boole b(cid:1205)ng các

phép toán + (c(cid:1245)ng logic), x (.) (nhân logic) ho(cid:1211)c ngh(cid:1231)ch (cid:255)(cid:1191)o logic (-).

3. Giá tr(cid:1231) c(cid:1259)a hàm Boole

Gi(cid:1191) s(cid:1265) f(x1, x2, ...., xn) là m(cid:1245)t hàm Boole theo n bi(cid:1219)n Boole.

i (

n,1i =

Trong f ng(cid:1133)(cid:1249)i ta thay các bi(cid:1219)n xi b(cid:1205)ng các giá tr(cid:1231) c(cid:1257) th(cid:1223) a ) thì giá tr(cid:1231) f (a 1, a 2, ..., a n)

(cid:255)(cid:1133)(cid:1255)c g(cid:1233)i là giá tr(cid:1231) c(cid:1259)a hàm Boole theo n bi(cid:1219)n.

Ví d(cid:877) 2.3:

Xét hàm f(x1, x2 ) = x1 + x2 Xét trong t(cid:1201)p B = B* ={0,1} ta có các tr(cid:1133)(cid:1249)ng h(cid:1255)p sau (l(cid:1133)u ý (cid:255)ây là phép (cid:70)(cid:865)ng logic hay còn g(cid:1233)i

phép toán HO(cid:830)C / phép OR): ﬁ f(0,0) = 0 + 0 = 0 - x1 = 0, x2 = 0

Bài gi(cid:1191)ng (cid:264)(cid:44)(cid:1226)N T(cid:1264) S(cid:1236) 1 Trang 14

ﬁ

ﬁ f(0,1) = 0 + 1 = 1 f(1,0) = 1 + 0 = 1 f(1,1) = 1 + 1 = 1 - x1 = 0, x2 = 1 - x1 = 1, x2 = 0 - x1 = 1, x2 = 1

Ta l(cid:1201)p (cid:255)(cid:1133)(cid:1255)c b(cid:1191)ng giá tr(cid:1231) c(cid:1259)a hàm trên. f(x1, x2) = x1+ x2 0 1 1 1 x2 0 1 0 1 x1 0 0 1 1

Ví d(cid:877) 2.4:

Xét hàm cho b(cid:1251)i bi(cid:1223)u th(cid:1261)c sau: f(x1, x2, x3) = x1 + x2.x3 Xét t(cid:1201)p B = B* = {0,1}. Hoàn toàn t(cid:1133)(cid:1131)ng t(cid:1269) ta l(cid:1201)p (cid:255)(cid:1133)(cid:1255)c b(cid:1191)ng giá tr(cid:1231) c(cid:1259)a hàm:

f (x1, x2, x3) = x1 + x2.x3 0 0 0 1 1 1 1 1 x3 0 1 0 1 0 1 0 1 x2 0 0 1 1 0 0 1 1 x1 0 0 0 0 1 1 1 1

2.2.2. Các ph(cid:1133)(cid:1131)ng pháp bi(cid:1223)u di(cid:1225)n hàm Boole

1. Ph(cid:1133)(cid:1131)ng pháp bi(cid:1223)u di(cid:1225)n hàm b(cid:1205)ng b(cid:1191)ng giá tr(cid:1231)

(cid:264)ây là ph(cid:1133)(cid:1131)ng pháp th(cid:1133)(cid:1249)ng dùng (cid:255)(cid:1223) bi(cid:1223)u di(cid:1225)n hàm s(cid:1237) nói chung và c(cid:458)ng (cid:255)(cid:1133)(cid:1255)c s(cid:1265) d(cid:1257)ng (cid:255)(cid:1223) bi(cid:1223)u

di(cid:1225)n các hàm logic. Ph(cid:1133)(cid:1131)ng pháp này g(cid:1239)m m(cid:1245)t b(cid:1191)ng (cid:255)(cid:1133)(cid:1255)c chia làm hai ph(cid:1195)n:

- M(cid:1245)t ph(cid:1195)n dành cho bi(cid:1219)n (cid:255)(cid:1223) ghi các t(cid:1241) h(cid:1255)p giá tr(cid:1231) có th(cid:1223) có c(cid:1259)a bi(cid:1219)n vào. - M(cid:1245)t ph(cid:1195)n dành cho hàm (cid:255)(cid:1223) ghi các giá tr(cid:1231) c(cid:1259)a hàm ra t(cid:1133)(cid:1131)ng (cid:1261)ng v(cid:1247)i các t(cid:1241) h(cid:1255)p bi(cid:1219)n vào.

B(cid:1191)ng giá tr(cid:1231) còn (cid:255)(cid:1133)(cid:1255)c g(cid:1233)i là b(cid:1191)ng chân tr(cid:1231) hay b(cid:1191)ng chân lý (TRUE TABLE). Nh(cid:1133) v(cid:1201)y v(cid:1247)i m(cid:1245)t hàm Boole n bi(cid:1219)n b(cid:1191)ng chân lý s(cid:1217) có:

- (n+1) (cid:70)(cid:1245)t: n c(cid:1245)t t(cid:1133)(cid:1131)ng (cid:1261)ng v(cid:1247)i n bi(cid:1219)n vào, 1 c(cid:1245)t t(cid:1133)(cid:1131)ng (cid:1261)ng v(cid:1247)i giá tr(cid:1231) ra c(cid:1259)a hàm. - 2n hàng: 2n giá tr(cid:1231) khác nhau c(cid:1259)a t(cid:1241) h(cid:1255)p n bi(cid:1219)n.

Ví d(cid:877) 2.5: Hàm 3 bi(cid:1219)n f(x1, x2, x3) có th(cid:1223)(cid:3)(cid:255)(cid:1133)(cid:1255)c cho b(cid:1205)ng b(cid:1191)ng giá tr(cid:1231) nh(cid:1133) sau:

f (x1, x2, x3) 0 0 0 1 1 1 1 1 x3 0 1 0 1 0 1 0 1 x2 0 0 1 1 0 0 1 1 x1 0 0 0 0 1 1 1 1

Trong các ví d(cid:1257) 2.3 và 2.4 chúng ta c(cid:458)ng (cid:255)ã quen thu(cid:1245)c v(cid:1247)i ph(cid:1133)(cid:1131)ng pháp bi(cid:1223)u di(cid:1225)n hàm b(cid:1205)ng

(cid:69)(cid:1191)ng giá tr(cid:1231).

Ch(cid:1133)(cid:1131)ng 2. (cid:264)(cid:1189)i s(cid:1237) BOOLE Trang 15

2. Ph(cid:1133)(cid:1131)ng pháp gi(cid:1191)i tích

(cid:264)ây là ph(cid:1133)(cid:1131)ng pháp bi(cid:1223)u di(cid:1225)n hàm logic b(cid:1205)ng các bi(cid:1223)u th(cid:1261)c (cid:255)(cid:1189)i s(cid:1237). Ph(cid:1133)(cid:1131)ng pháp này có 2 d(cid:1189)ng:

(cid:87)(cid:861)ng c(cid:879)a các tích s(cid:857) ho(cid:1211)c tích c(cid:879)a các t(cid:861)ng s(cid:857).

(cid:39)(cid:1189)ng t(cid:1241)ng c(cid:1259)a các tích s(cid:1237) g(cid:1233)i là d(cid:1189)ng chính t(cid:1203)c th(cid:1261) nh(cid:1193)t (D(cid:1189)ng chính t(cid:1203)c 1 – CT1). (cid:39)(cid:1189)ng tích c(cid:1259)a các t(cid:1241)ng s(cid:1237) g(cid:1233)i là d(cid:1189)ng chính t(cid:1203)c th(cid:1261) hai (D(cid:1189)ng chính t(cid:1203)c 2 – CT2). Hai d(cid:1189)ng chính t(cid:1203)c này là (cid:255)(cid:1237)i ng(cid:1199)u nhau. (cid:39)(cid:1189)ng t(cid:1241)ng các tích s(cid:1237) còn g(cid:1233)i là d(cid:1189)ng chu(cid:817)n t(cid:823)c tuy(cid:843)n (CTT), d(cid:1189)ng tích các t(cid:1241)ng s(cid:1237) còn g(cid:1233)i là

(cid:71)(cid:1189)ng chu(cid:817)n t(cid:823)c h(cid:865)i (CTH).

a. D(cid:809)ng chính t(cid:823)c 1(D(cid:809)ng t(cid:861)ng c(cid:879)a các tích s(cid:857))

là h(cid:1205)ng s(cid:1237)). (a

Xét các hàm Boole m(cid:1245)t bi(cid:1219)n (cid:255)(cid:1131)n gi(cid:1191)n: f(x) = x, f(x) = x , f(x) = a (cid:264)ây là nh(cid:1267)ng tr(cid:1133)(cid:1249)ng h(cid:1255)p có th(cid:1223) có (cid:255)(cid:1237)i v(cid:1247)i hàm Boole 1 bi(cid:1219)n. Chúng ta s(cid:1217)(cid:3)(cid:255)i ch(cid:1261)ng minh bi(cid:1223)u th(cid:1261)c t(cid:1241)ng quát c(cid:1259)a hàm logic 1 bi(cid:1219)n s(cid:1237)(cid:3)(cid:255)(cid:1237)i v(cid:1247)i d(cid:1189)ng chính t(cid:1203)c 1. Sau (cid:255)ó áp d(cid:1257)ng bi(cid:1223)u th(cid:1261)c t(cid:1241)ng quát c(cid:1259)a hàm 1 bi(cid:1219)n (cid:255)(cid:1223) tìm bi(cid:1223)u th(cid:1261)c t(cid:1241)ng quát c(cid:1259)a hàm 2 bi(cid:1219)n v(cid:1247)i vi(cid:1227)c xem 1 bi(cid:1219)n là h(cid:1205)ng s(cid:1237). Cu(cid:1237)i cùng, chúng ta suy ra bi(cid:1223)u th(cid:1261)c t(cid:1241)ng quát c(cid:1259)a hàm logic n bi(cid:1219)n cho tr(cid:1133)(cid:1249)ng h(cid:1255)p d(cid:1189)ng chính t(cid:1203)c 1 (t(cid:1241)ng các tích s(cid:1237)).

Xét f(x) = x:

Ta có: x =0. x + 1.x (cid:80)(cid:1211)t khác:

( ) xf

( ) 1f ( ) 0f

= (cid:236) (cid:237) (cid:222)= x 1 = 0 (cid:238)

Suy ra: f(x) = x có th(cid:1223) bi(cid:1223)u di(cid:1225)n:

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

trong (cid:255)ó: f (0), f (1) (cid:255)(cid:1133)(cid:1255)c g(cid:1233)i là các giá tr(cid:1231) c(cid:1259)a hàm Boole theo m(cid:1245)t bi(cid:1219)n.

x = 1. x + 0. x

Xét f(x) = x :

Ta có: (cid:48)(cid:1211)t khác:

( ) xf

( ) = 1f ( ) 0f

(cid:236) 0 (cid:237) (cid:222)= x = 1 (cid:238)

Suy ra: f(x) = x có th(cid:1223) bi(cid:1223)u di(cid:1225)n:

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

Xét f(x) = a là h(cid:1205)ng s(cid:1237)):

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

Ta có: (cid:48)(cid:1211)t khác:

( ) xf

( ) = 1f ( ) 0f

(cid:236) (cid:302) (cid:237) (cid:222)= (cid:302) = (cid:302) (cid:238)

Suy ra f(x) = a có th(cid:1223) bi(cid:1223)u di(cid:1225)n:

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

, ta (cid:255)(cid:1221)u có bi(cid:1223)u th(cid:1261)c t(cid:1241)ng quát c(cid:1259)a hàm m(cid:1245)t bi(cid:1219)n vi(cid:1219)t (cid:46)(cid:839)t lu(cid:821)n: Dù f(x) = x, f(x) = x hay f(x) = a

theo d(cid:1189)ng chính t(cid:1203)c th(cid:1261) nh(cid:1193)t nh(cid:1133) sau:

Bài gi(cid:1191)ng (cid:264)(cid:44)(cid:1226)N T(cid:1264) S(cid:1236) 1 Trang 16

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

(cid:57)(cid:1201)y f(x) = f(0). x + f(1).x, trong (cid:255)ó f(0), f(1) là giá tr(cid:1231) c(cid:1259)a hàm Boole theo m(cid:1245)t bi(cid:1219)n, (cid:255)(cid:1133)(cid:1255)c g(cid:1233)i là

bi(cid:1223)u th(cid:1261)c t(cid:1241)ng quát c(cid:1259)a hàm 1 bi(cid:1219)n vi(cid:1219)t (cid:1251) (cid:71)(cid:809)ng chính t(cid:823)c th(cid:881) nh(cid:813)t (d(cid:809)ng t(cid:861)ng c(cid:879)a các tích).

Bi(cid:1223)u th(cid:1261)c t(cid:1241)ng quát c(cid:1259)a hàm hai bi(cid:1219)n f(x1, x2):

Bi(cid:1223)u th(cid:1261)c t(cid:1241)ng quát c(cid:1259)a hàm 2 bi(cid:1219)n vi(cid:1219)t theo d(cid:1189)ng chính t(cid:1203)c th(cid:1261) nh(cid:1193)t c(cid:458)ng hoàn toàn d(cid:1269)a trên

cách bi(cid:1223)u di(cid:1225)n c(cid:1259)a d(cid:1189)ng chính t(cid:1203)c th(cid:1261) nh(cid:1193)t c(cid:1259)a hàm 1 bi(cid:1219)n, trong (cid:255)ó xem m(cid:1245)t bi(cid:1219)n là h(cid:1205)ng s(cid:1237).

(cid:38)(cid:1257) th(cid:1223) là: n(cid:1219)u xem x2 là h(cid:1205)ng s(cid:1237), x1 là bi(cid:1219)n s(cid:1237) và áp d(cid:1257)ng bi(cid:1223)u th(cid:1261)c t(cid:1241)ng quát c(cid:1259)a d(cid:1189)ng chính t(cid:1203)c

th(cid:1261) nh(cid:1193)t cho hàm 1 bi(cid:1219)n, ta có:

f(x1,x2) = f(0,x2). x 1 + f(1,x2).x1

Bây gi(cid:1249), các hàm f(0,x2) và f(1,x2) tr(cid:1251) thành các hàm 1 bi(cid:1219)n s(cid:1237) theo x2. Ti(cid:1219)p t(cid:1257)c áp d(cid:1257)ng bi(cid:1223)u

th(cid:1261)c t(cid:1241)ng quát c(cid:1259)a d(cid:1189)ng chính t(cid:1203)c th(cid:1261) nh(cid:1193)t cho hàm 1 bi(cid:1219)n, ta có:

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

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

Suy ra:

f(x1,x2) = f(0,0). x 1 x 2 + f(0,1). x 1x2 + f(1,0).x1 x 2 + f(1,1).x1x2

(cid:264)ây chính là bi(cid:1223)u th(cid:1261)c t(cid:1241)ng quát c(cid:1259)a d(cid:1189)ng chính t(cid:1203)c th(cid:1261) nh(cid:1193)t (d(cid:1189)ng t(cid:1241)ng c(cid:1259)a các tích s(cid:1237)) vi(cid:1219)t cho

hàm Boole hai bi(cid:1219)n s(cid:1237) f(x1,x2).

Bi(cid:1223)u th(cid:1261)c t(cid:1241)ng quát này có th(cid:1223) bi(cid:1223)u di(cid:1225)n b(cid:1205)ng công th(cid:1261)c sau:

2(cid:302)

1(cid:302)

1 )x(cid:302),(cid:302)f(

- (cid:229) f(x1,x2) =

x

= 0e

Trong (cid:255)ó e là s(cid:1237) th(cid:1201)p phân t(cid:1133)(cid:1131)ng (cid:1261)ng v(cid:1247)i mã nh(cid:1231) phân (a 1,a 2) và: = 1x (cid:302) x1 n(cid:1219)u a 1 = 1 x 1 n(cid:1219)u a 1 = 0

2 = 2x (cid:302) x2 n(cid:1219)u a 2 = 1 x 2 n(cid:1219)u a 2 = 0

Bi(cid:1223)u th(cid:1261)c t(cid:1241)ng quát cho hàm Boole n bi(cid:1219)n: T(cid:1263) bi(cid:1223)u th(cid:1261)c t(cid:1241)ng quát vi(cid:1219)t (cid:1251) d(cid:1189)ng chính t(cid:1203)c th(cid:1261) nh(cid:1193)t c(cid:1259)a hàm Boole 2 bi(cid:1219)n, ta có th(cid:1223) t(cid:1241)ng quát hoá cho hàm Boole n bi(cid:1219)n f(x1,x2, ..,xn) nh(cid:1133) sau:

(cid:302)

(cid:302)1

(cid:302)

,....,

...x

1n2 f(

(cid:302)(cid:302) , 1

= 0e

(cid:229) f(x1,x2, ..,xn) =

trong (cid:255)ó e là s(cid:1237) th(cid:1201)p phân t(cid:1133)(cid:1131)ng (cid:1261)ng v(cid:1247)i mã nh(cid:1231) phân (a 1,a 2, ...,a n);

i = 1

i = 0

và: (cid:302)x = i (v(cid:1247)i i = 1, 2, 3,…,n) xi n(cid:1219)u a x i n(cid:1219)u a

Ch(cid:1133)(cid:1131)ng 2. (cid:264)(cid:1189)i s(cid:1237) BOOLE Trang 17

Ví d(cid:877) 2.6:

Vi(cid:1219)t bi(cid:1223)u th(cid:1261)c c(cid:1259)a hàm 3 bi(cid:1219)n theo d(cid:1189)ng chính t(cid:1203)c 1:

a 3

a 2.x3

a 1.x2

2 f(x1,x2,x3) = (cid:229)

= 0e

f (a 1,a 2,a 3).x1

(cid:37)(cid:1191)ng d(cid:1133)(cid:1247)i (cid:255)ây cho ta giá tr(cid:1231) c(cid:1259)a s(cid:1237) th(cid:1201)p phân e và t(cid:1241) h(cid:1255)p mã nh(cid:1231) phân (a 1,a 2,a 3) t(cid:1133)(cid:1131)ng (cid:1261)ng: a 1 0 0 0 0 1 1 1 1 a 2 0 0 1 1 0 0 1 1 a 3 0 1 0 1 0 1 0 1 0 1 2 3 4 5 6 7

Bi(cid:1223)u th(cid:1261)c c(cid:1259)a hàm 3 bi(cid:1219)n vi(cid:1219)t theo d(cid:1189)ng t(cid:1241)ng các tích nh(cid:1133) sau:

f(x1, x2, x3) = f(0,0,0) x 1 x 2 x 3 + f(0,0,1) x 1 x 2 x3

+ f(0,1,0) x 1x2 x 3 + f(0,1,1) x 1 x2 x3 + f(1,0,0) x1 x 2 x 3

(cid:57)(cid:821)y d(cid:809)ng chính t(cid:823)c th(cid:881) nh(cid:813)t là d(cid:809)ng t(cid:861)ng c(cid:879)a các tích s(cid:857) mà trong m(cid:863)i tích s(cid:857) ch(cid:881)a (cid:255)(cid:815)y

(cid:255)(cid:879) các bi(cid:839)n Boole d(cid:753)(cid:867)i d(cid:809)ng th(cid:821)t ho(cid:831)c d(cid:809)ng bù (ngh(cid:851)ch (cid:255)(cid:811)o).

+ f(1,0,1)x1 x 2 x3 + f(1,1,0) x1 x2 x 3 + f(1,1,1) x1 x2 x3

b. D(cid:809)ng chính t(cid:823)c 2 (tích c(cid:879)a các t(cid:861)ng s(cid:857)):

(cid:39)(cid:1189)ng chính t(cid:1203)c 2 là d(cid:1189)ng (cid:255)(cid:1237)i ng(cid:1199)u c(cid:1259)a d(cid:1189)ng chính t(cid:1203)c 1 nên bi(cid:1223)u th(cid:1261)c t(cid:1241)ng quát c(cid:1259)a d(cid:1189)ng

chính t(cid:1203)c 2 cho n bi(cid:1219)n(cid:3)(cid:255)(cid:1133)(cid:1255)c vi(cid:1219)t nh(cid:1133) sau:

a n)]

a 2+ ...+ xn

a 1 + x2

2 f(x1, x2, ..., xn) = (cid:213)

= 0e

[f(a 1,a 2,a 3) + x1

ix (cid:302) =

trong (cid:255)ó e là s(cid:1237) th(cid:1201)p phân t(cid:1133)(cid:1131)ng (cid:1261)ng v(cid:1247)i mã nh(cid:1231) phân (a 1,a 2, ...,a n); và:

x i n(cid:1219)u a xi n(cid:1219)u a

i = 1 i = 0

(v(cid:1247)i i = 1, 2, 3,…,n)

Ví d(cid:877) 2.7: Bi(cid:1223)u th(cid:1261)c c(cid:1259)a hàm Boole 2 bi(cid:1219)n (cid:1251) d(cid:1189)ng tích các t(cid:1241)ng s(cid:1237) (d(cid:1189)ng chính t(cid:1203)c 2) (cid:255)(cid:1133)(cid:1255)c vi(cid:1219)t nh(cid:1133) sau:

f(x1,x2)=[f(0,0)+x1+x2][f(0,1)+x1+ x 2][f(1,0)+ x 1+x2][f(1,1)+ x 1+ x 2]

Ví d(cid:877) 2.8: Bi(cid:1223)u th(cid:1261)c c(cid:1259)a hàm Boole 3 bi(cid:1219)n (cid:1251) d(cid:1189)ng chính t(cid:1203)c 2:

f(x1,x2,x3) = [f(0,0,0)+x1+ x2+x3].[f(0,0,1)+x1+x2+ x 3].

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

[f(1,0,0)+ x 1+x2+x3].[f(1,0,1)+ x 1+x2+ x 3].

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

(cid:57)(cid:821)y, d(cid:809)ng chính t(cid:823)c th(cid:881) hai là d(cid:809)ng tích c(cid:879)a các t(cid:861)ng s(cid:857) mà trong (cid:255)ó m(cid:863)i t(cid:861)ng s(cid:857) này

ch(cid:881)a (cid:255)(cid:815)y (cid:255)(cid:879) các bi(cid:839)n Boole d(cid:753)(cid:867)i d(cid:809)ng th(cid:821)t ho(cid:831)c d(cid:809)ng bù.

Bài gi(cid:1191)ng (cid:264)(cid:44)(cid:1226)N T(cid:1264) S(cid:1236) 1 Trang 18

Ví d(cid:877) 2.9:

Hãy vi(cid:1219)t bi(cid:1223)u th(cid:1261)c bi(cid:1223)u di(cid:1225)n cho hàm Boole 2 bi(cid:1219)n f(x1,x2) (cid:1251) d(cid:1189)ng chính t(cid:1203)c 1, v(cid:1247)i b(cid:1191)ng giá tr(cid:1231)

(cid:70)(cid:1259)a hàm (cid:255)(cid:1133)(cid:1255)c cho nh(cid:1133) sau:

x1 0 0 1 1 x2 0 1 0 1 f(x1,x2) 0 1 1 1

Vi(cid:1219)t d(cid:1133)(cid:1247)i d(cid:1189)ng chính t(cid:1203)c 1 ta có:

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

= 0. x 1 x 2 + 1. x 1.x2 + 1.x1. x 2 + 1.x1.x2

= x 1.x2 + x1. x 2 + x1.x2

• (cid:39)(cid:809)ng chính t(cid:823)c th(cid:881) nh(cid:813)t, t(cid:861)ng c(cid:879)a các tích s(cid:857), là d(cid:809)ng li(cid:847)t kê t(cid:813)t c(cid:811) các t(cid:861) h(cid:875)p nh(cid:851) phân các bi(cid:839)n vào sao cho t(cid:753)(cid:751)ng (cid:881)ng v(cid:867)i nh(cid:887)ng t(cid:861) h(cid:875)p (cid:255)ó giá tr(cid:851) c(cid:879)a hàm ra b(cid:825)ng 1

Nh(cid:1201)n xét:

ch(cid:849) c(cid:815)n li(cid:847)t kê nh(cid:887)ng t(cid:861) h(cid:875)p bi(cid:839)n làm cho giá tr(cid:851) hàm ra b(cid:825)ng 1.

• Khi li(cid:847)t kê n(cid:839)u bi(cid:839)n t(cid:753)(cid:751)ng (cid:881)ng b(cid:825)ng 1 (cid:255)(cid:753)(cid:875)c vi(cid:839)t (cid:871) d(cid:809)ng th(cid:821)t (xi), n(cid:839)u bi(cid:839)n t(cid:753)(cid:751)ng (cid:881)ng

(cid:69)(cid:825)ng 0 (cid:255)(cid:753)(cid:875)c vi(cid:839)t (cid:871) d(cid:809)ng bù ( x i).

ﬁ

Ví d(cid:877) 2.10:

Vi(cid:1219)t bi(cid:1223)u th(cid:1261)c bi(cid:1223)u di(cid:1225)n hàm f(x1,x2,x3) (cid:1251) d(cid:1189)ng chính t(cid:1203)c 2 v(cid:1247)i b(cid:1191)ng giá tr(cid:1231) c(cid:1259)a hàm ra (cid:255)(cid:1133)(cid:1255)c cho

nh(cid:1133) sau:

x3 0 0 0 0 1 1 1 1 x2 0 0 1 1 0 0 1 1 x1 0 1 0 1 0 1 0 1 f(x1,x2,x3) 0 0 0 1 1 1 1 1

Vi(cid:1219)t d(cid:1133)(cid:1247)i d(cid:1189)ng chính t(cid:1203)c 2 (tích các t(cid:1241)ng s(cid:1237)):

f(x1,x2,x3) = (0+x1+x2+x3).(0+x1+x2+ x 3).(0+x1+ x 2+x3).

(1+x1+ x 2+ x 3).(1+ x 1+x2+x3).(1+ x 1+x2+ x 3).

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

Ch(cid:1133)(cid:1131)ng 2. (cid:264)(cid:1189)i s(cid:1237) BOOLE Trang 19

Áp d(cid:1257)ng tiên (cid:255)(cid:1221) v(cid:1221) ph(cid:1195)n t(cid:1265) trung hòa 0 và 1 ta có:

x . 1 = x x . 0 = 0

x + 1 = 1, x + 0 = x, nên suy ra bi(cid:1223)u th(cid:1261)c trên có th(cid:1223) vi(cid:1219)t g(cid:1233)n l(cid:1189)i:

f(x1,x2,x3) = (x1+x2+x3).(x1+x2+ x 3).(x1+ x 2+x3)

• (cid:39)(cid:809)ng chính t(cid:823)c th(cid:881) hai là d(cid:809)ng li(cid:847)t kê t(cid:813)t c(cid:811) các t(cid:861) h(cid:875)p nh(cid:851) phân các bi(cid:839)n vào sao cho ch(cid:849) c(cid:815)n li(cid:847)t kê nh(cid:887)ng t(cid:861)

(cid:87)(cid:753)(cid:751)ng (cid:881)ng v(cid:867)i nh(cid:887)ng t(cid:861) h(cid:875)p (cid:255)ó giá tr(cid:851) c(cid:879)a hàm ra b(cid:825)ng 0 ﬁ (cid:75)(cid:875)p bi(cid:839)n làm cho giá tr(cid:851) hàm ra b(cid:825)ng 0.

• Khi li(cid:847)t kê n(cid:839)u bi(cid:839)n t(cid:753)(cid:751)ng (cid:881)ng b(cid:825)ng 0 (cid:255)(cid:753)(cid:875)c vi(cid:839)t (cid:871) d(cid:809)ng th(cid:821)t (xi), n(cid:839)u bi(cid:839)n t(cid:753)(cid:751)ng (cid:881)ng

(cid:69)(cid:825)ng 1 (cid:255)(cid:753)(cid:875)c vi(cid:839)t (cid:871) d(cid:809)ng bù ( x i).

Nh(cid:1201)n xét:

Ví d(cid:1257)(cid:3)(cid:255)(cid:1131)n gi(cid:1191)n sau giúp SV hi(cid:1223)u rõ h(cid:1131)n v(cid:1221) cách thành l(cid:1201)p b(cid:1191)ng giá tr(cid:1231) c(cid:1259)a hàm, tìm hàm m(cid:1189)ch

và thi(cid:1219)t k(cid:1219) m(cid:1189)ch.

Ví d(cid:877) 2.11

Hãy thi(cid:1219)t k(cid:1219) m(cid:1189)ch (cid:255)(cid:76)(cid:1227)n sao cho khi công t(cid:1203)c 1 (cid:255)óng thì (cid:255)èn (cid:255)(cid:1235), khi công t(cid:1203)c 2 (cid:255)óng (cid:255)èn (cid:255)(cid:1235), khi

(cid:70)(cid:1191) hai công t(cid:1203)c (cid:255)óng (cid:255)èn (cid:255)(cid:1235) ?

(cid:47)(cid:1249)i gi(cid:1191)i: (cid:264)(cid:1195)u tiên, ta qui (cid:255)(cid:1231)nh tr(cid:1189)ng thái c(cid:1259)a các công t(cid:1203)c và bóng (cid:255)èn:

- Công t(cid:1203)c h(cid:1251) : 0 - Công t(cid:1203)c (cid:255)óng : 1 (cid:264)èn t(cid:1203)t : 0 (cid:264)èn (cid:255)(cid:1235) : 1

(cid:37)(cid:1191)ng tr(cid:1189)ng thái mô t(cid:1191) ho(cid:1189)t (cid:255)(cid:1245)ng c(cid:1259)a m(cid:1189)ch nh(cid:1133) sau:

Công t(cid:1203)c 1 Công t(cid:1203)c 2 Tr(cid:1189)ng thái (cid:255)èn

x1 x2 f(x1,x2)

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

(cid:55)(cid:1263) b(cid:1191)ng tr(cid:1189)ng thái có th(cid:1223) vi(cid:1219)t bi(cid:1223)u th(cid:1261)c c(cid:1259)a hàm f(x1,x2) theo d(cid:1189)ng chính t(cid:1203)c 1 ho(cid:1211)c chính t(cid:1203)c 2. - Theo d(cid:1189)ng chính t(cid:1203)c 1 ta có:

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

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

= x 1.x2 + x1 = x1 + x2

- Theo d(cid:1189)ng chính t(cid:1203)c 2 ta có:

f(x1, x2) = (0+x1+x2) = x1 + x2

T(cid:1263) bi(cid:1223)u th(cid:1261)c mô t(cid:1191) tr(cid:1189)ng thái (cid:255)(cid:1235)/t(cid:1203)t c(cid:1259)a (cid:255)èn f(x1,x2) th(cid:1193)y r(cid:1205)ng có th(cid:1223) th(cid:1269)c hi(cid:1227)n m(cid:1189)ch b(cid:1205)ng ph(cid:1195)n (cid:87)(cid:1265) logic HO(cid:1210)C có 2 ngõ vào (c(cid:1241)ng OR 2 ngõ vào).

Bài t(cid:821)p áp d(cid:877)ng: M(cid:865)t h(cid:865)i (cid:255)(cid:859)ng giám kh(cid:811)o g(cid:859)m 3 thành viên. M(cid:863)i thành viên có th(cid:843) l(cid:889)a ch(cid:853)n (cid:264)(cid:858)NG Ý ho(cid:831)c KHÔNG (cid:264)(cid:858)NG Ý. K(cid:839)t qu(cid:811) g(cid:853)i là (cid:264)(cid:808)T khi (cid:255)a s(cid:857) các thành viên trong h(cid:865)i (cid:255)(cid:859)ng giám kh(cid:811)o (cid:264)(cid:858)NG Ý, ng(cid:753)(cid:875)c l(cid:809)i là KHÔNG (cid:264)(cid:808)T. Hãy thi(cid:839)t k(cid:839) m(cid:809)ch gi(cid:811)i quy(cid:839)t bài toán trên.

Bài gi(cid:1191)ng (cid:264)(cid:44)(cid:1226)N T(cid:1264) S(cid:1236) 1 Trang 20

3. Bi(cid:1223)u di(cid:1225)n hàm b(cid:1205)ng b(cid:1191)ng Karnaugh (bìa Karnaugh)

(cid:264)ây là cách bi(cid:1223)u di(cid:1225)n l(cid:1189)i c(cid:1259)a ph(cid:1133)(cid:1131)ng pháp b(cid:1191)ng d(cid:1133)(cid:1247)i d(cid:1189)ng b(cid:1191)ng g(cid:1239)m các

ô vuông nh(cid:1133) hình bên.

Trên b(cid:1191)ng này ng(cid:1133)(cid:1249)i ta b(cid:1237) trí các bi(cid:1219)n vào theo hàng ho(cid:1211)c theo c(cid:1245)t c(cid:1259)a (cid:69)(cid:1191)ng. Trong tr(cid:1133)(cid:1249)ng h(cid:1255)p s(cid:1237) l(cid:1133)(cid:1255)ng bi(cid:1219)n vào là ch(cid:1209)n, ng(cid:1133)(cid:1249)i ta b(cid:1237) trí s(cid:1237) l(cid:1133)(cid:1255)ng bi(cid:1219)n vào theo hàng ngang b(cid:1205)ng s(cid:1237) l(cid:1133)(cid:1255)ng bi(cid:1219)n vào theo c(cid:1245)t d(cid:1233)c c(cid:1259)a b(cid:1191)ng. Trong tr(cid:1133)(cid:1249)ng h(cid:1255)p s(cid:1237) l(cid:1133)(cid:1255)ng bi(cid:1219)n vào là l(cid:1215), ng(cid:1133)(cid:1249)i ta b(cid:1237) trí s(cid:1237) l(cid:1133)(cid:1255)ng bi(cid:1219)n vào theo hàng ngang nhi(cid:1221)u h(cid:1131)n s(cid:1237) l(cid:1133)(cid:1255)ng bi(cid:1219)n vào theo c(cid:1245)t d(cid:1233)c 1 bi(cid:1219)n ho(cid:1211)c ng(cid:1133)(cid:1255)c l(cid:1189)i.

Các t(cid:1241) h(cid:1255)p giá tr(cid:1231) c(cid:1259)a bi(cid:1219)n vào theo hàng ngang ho(cid:1211)c theo c(cid:1245)t d(cid:1233)c c(cid:1259)a b(cid:1191)ng (cid:255)(cid:1133)(cid:1255)c b(cid:1237) trí sao cho khi ta (cid:255)i t(cid:1263) m(cid:1245)t ô sang m(cid:1245)t ô lân c(cid:1201)n v(cid:1247)i nó ch(cid:1229) làm thay (cid:255)(cid:1241)i m(cid:1245)t giá tr(cid:1231) c(cid:1259)a bi(cid:1219)n, nh(cid:1133) v(cid:1201)y th(cid:1261) t(cid:1269) (cid:69)(cid:1237) trí hay s(cid:1203)p x(cid:1219)p các t(cid:1241) h(cid:1255)p giá tr(cid:1231) c(cid:1259)a bi(cid:1219)n vào theo hàng ngang ho(cid:1211)c theo c(cid:1245)t d(cid:1233)c c(cid:1259)a b(cid:1191)ng Karnaugh hoàn toàn tuân th(cid:1259) theo mã Gray.

Giá tr(cid:1231) ghi trong m(cid:1243)i ô vuông này chính là giá tr(cid:1231) c(cid:1259)a hàm ra t(cid:1133)(cid:1131)ng (cid:1261)ng v(cid:1247)i các t(cid:1241) h(cid:1255)p giá tr(cid:1231) c(cid:1259)a bi(cid:1219)n vào. (cid:1250) nh(cid:1267)ng ô mà giá tr(cid:1231) hàm là không xác (cid:255)(cid:1231)nh (có th(cid:1223) b(cid:1205)ng 0 hay b(cid:1205)ng 1), có ngh(cid:429)a là giá tr(cid:1231) (cid:70)(cid:1259)a hàm là tùy ý (hay tùy (cid:255)(cid:1231)nh), ng(cid:1133)(cid:1249)i ta kí hi(cid:1227)u b(cid:1205)ng ch(cid:1267) X.

(cid:49)(cid:1219)u hàm có n bi(cid:1219)n vào s(cid:1217) có 2n ô vuông.

Ph(cid:1133)(cid:1131)ng pháp bi(cid:1223)u di(cid:1225)n hàm b(cid:1205)ng b(cid:1191)ng Karnaugh ch(cid:1229) thích h(cid:1255)p cho hàm có t(cid:1237)i (cid:255)a 6 bi(cid:1219)n, n(cid:1219)u

(cid:89)(cid:1133)(cid:1255)t quá vi(cid:1227)c bi(cid:1223)u di(cid:1225)n s(cid:1217) r(cid:1193)t r(cid:1203)c r(cid:1237)i.

(cid:39)(cid:1133)(cid:1247)i (cid:255)ây là b(cid:1191)ng Karnaugh cho các tr(cid:1133)(cid:1249)ng h(cid:1255)p hàm 2 bi(cid:1219)n, 3 bi(cid:1219)n, 4 bi(cid:1219)n và 5 bi(cid:1219)n:

x1

x1x2

f(x1,x2) x2

f x3

0 1

00 01 11 10

0 1

x1=0

x1=1

x1x2

x2x3

f x4x5

f x3x4

00 01 11 10

00 01 11 10 10 11 01 00

00 01 11 10

2.3. T(cid:1236)I THI(cid:1222)U HÓA HÀM BOOLE

2.3.1. (cid:264)(cid:1189)i c(cid:1133)(cid:1131)ng

Trong thi(cid:1219)t b(cid:1231) máy tính ng(cid:1133)(cid:1249)i ta th(cid:1133)(cid:1249)ng thi(cid:1219)t k(cid:1219) g(cid:1239)m nhi(cid:1221)u modul (khâu) và m(cid:1243)i modul này (cid:255)(cid:1133)(cid:1255)c (cid:255)(cid:1211)c tr(cid:1133)ng b(cid:1205)ng m(cid:1245)t ph(cid:1133)(cid:1131)ng trình logic. Trong (cid:255)ó, m(cid:1261)c (cid:255)(cid:1245) ph(cid:1261)c t(cid:1189)p c(cid:1259)a s(cid:1131)(cid:3)(cid:255)(cid:1239) tùy thu(cid:1245)c vào ph(cid:1133)(cid:1131)ng trình logic bi(cid:1223)u di(cid:1225)n chúng. Vi(cid:1227)c (cid:255)(cid:1189)t (cid:255)(cid:1133)(cid:1255)c (cid:255)(cid:1245)(cid:3) (cid:1241)n (cid:255)(cid:1231)nh cao hay không là tùy thu(cid:1245)c vào ph(cid:1133)(cid:1131)ng trình logic bi(cid:1223)u di(cid:1225)n chúng (cid:1251) d(cid:1189)ng t(cid:1237)i thi(cid:1223)u hóa hay ch(cid:1133)a. (cid:264)(cid:1223) th(cid:1269)c hi(cid:1227)n (cid:255)(cid:1133)(cid:1255)c (cid:255)(cid:76)(cid:1221)u (cid:255)ó, khi thi(cid:1219)t k(cid:1219) m(cid:1189)ch s(cid:1237) ng(cid:1133)(cid:1249)i ta (cid:255)(cid:1211)t ra v(cid:1193)n (cid:255)(cid:1221) t(cid:1237)i thi(cid:1223)u hóa các hàm logic. (cid:264)(cid:76)(cid:1221)u (cid:255)ó có ngh(cid:429)a là ph(cid:1133)(cid:1131)ng

Ch(cid:1133)(cid:1131)ng 2. (cid:264)(cid:1189)i s(cid:1237) BOOLE Trang 21

trình logic bi(cid:1223)u di(cid:1225)n sao cho th(cid:1269)c s(cid:1269) g(cid:1233)n nh(cid:1193)t (s(cid:1237) l(cid:1133)(cid:1255)ng các phép tính và s(cid:1237) l(cid:1133)(cid:1255)ng các s(cid:1237)(cid:3)(cid:255)(cid:1133)(cid:1255)c bi(cid:1223)u di(cid:1225)n d(cid:1133)(cid:1247)i d(cid:1189)ng th(cid:1201)t ho(cid:1211)c bù là ít nh(cid:1193)t).

Các k(cid:1275) thu(cid:1201)t (cid:255)(cid:1223)(cid:3)(cid:255)(cid:1189)t (cid:255)(cid:1133)(cid:1255)c s(cid:1269) th(cid:1269)c hi(cid:1227)n hàm Boole m(cid:1245)t cách (cid:255)(cid:1131)n gi(cid:1191)n nh(cid:1193)t ph(cid:1257) thu(cid:1245)c vào nhi(cid:1221)u

(cid:92)(cid:1219)u t(cid:1237) mà chúng ta c(cid:1195)n cân nh(cid:1203)c:

(cid:48)(cid:865)t là s(cid:857) l(cid:753)(cid:875)ng các phép tính và s(cid:857) l(cid:753)(cid:875)ng các s(cid:857) (s(cid:1237) l(cid:1133)(cid:1255)ng literal) (cid:255)(cid:1133)(cid:1255)c bi(cid:1223)u di(cid:1225)n d(cid:1133)(cid:1247)i d(cid:1189)ng th(cid:1201)t ho(cid:1211)c bù là ít nh(cid:1193)t, (cid:255)(cid:76)(cid:1221)u này (cid:255)(cid:1239)ng ngh(cid:429)a v(cid:1247)i vi(cid:1227)c s(cid:1237) l(cid:1133)(cid:1255)ng dây n(cid:1237)i và s(cid:1237) l(cid:1133)(cid:1255)ng (cid:255)(cid:1195)u vào c(cid:1259)a m(cid:1189)ch là ít nh(cid:1193)t.

Hai là s(cid:857) l(cid:753)(cid:875)ng c(cid:861)ng c(cid:1195)n thi(cid:1219)t (cid:255)(cid:1223) th(cid:1269)c hi(cid:1227)n m(cid:1189)ch ph(cid:1191)i ít nh(cid:1193)t, chính s(cid:1237) l(cid:1133)(cid:1255)ng c(cid:1241)ng xác (cid:255)(cid:1231)nh kích th(cid:1133)(cid:1247)c c(cid:1259)a m(cid:1189)ch. M(cid:1245)t thi(cid:1219)t k(cid:1219)(cid:3)(cid:255)(cid:1131)n gi(cid:1191)n nh(cid:1193)t ph(cid:1191)i (cid:1261)ng v(cid:1247)i s(cid:1237) l(cid:1133)(cid:1255)ng c(cid:1241)ng ít nh(cid:1193)t ch(cid:1261) không ph(cid:1191)i s(cid:1237) (cid:79)(cid:1133)(cid:1255)ng literal ít nh(cid:1193)t.

Ba là s(cid:857) m(cid:881)c logic c(cid:1259)a các c(cid:1241)ng. Gi(cid:1191)m s(cid:1237) m(cid:1261)c logic s(cid:1217) gi(cid:1191)m tr(cid:1225) t(cid:1241)ng c(cid:1245)ng c(cid:1259)a m(cid:1189)ch vì tín hi(cid:1227)u (cid:86)(cid:1217) qua ít c(cid:1241)ng h(cid:1131)n. Tuy nhiên n(cid:1219)u chú tr(cid:1233)ng (cid:255)(cid:1219)n v(cid:1193)n (cid:255)(cid:1221) gi(cid:1191)m tr(cid:1225) s(cid:1217) ph(cid:1191)i tr(cid:1191) giá s(cid:1237) l(cid:1133)(cid:1255)ng c(cid:1241)ng t(cid:259)ng lên.

(cid:37)(cid:1251)i v(cid:1201)y trong th(cid:1269)c t(cid:1219) không ph(cid:1191)i lúc nào c(cid:458)ng (cid:255)(cid:1189)t (cid:255)(cid:1133)(cid:1255)c l(cid:1249)i gi(cid:1191)i t(cid:1237)i (cid:1133)u cho bài toán t(cid:1237)i thi(cid:1223)u hóa.

2.3.2. Các b(cid:1133)(cid:1247)c ti(cid:1219)n hành t(cid:1237)i thi(cid:1223)u hóa

• Dùng các phép t(cid:1237)i thi(cid:1223)u (cid:255)(cid:1223) t(cid:1237)i thi(cid:1223)u hóa các hàm s(cid:1237) logic. • Rút ra nh(cid:1267)ng th(cid:1263)a s(cid:1237) chung nh(cid:1205)m m(cid:1257)c (cid:255)ích t(cid:1237)i thi(cid:1223)u hóa thêm m(cid:1245)t b(cid:1133)(cid:1247)c n(cid:1267)a các ph(cid:1133)(cid:1131)ng

trình logic.

2.3.3. Các ph(cid:1133)(cid:1131)ng pháp t(cid:1237)i thi(cid:1223)u hóa

Có nhi(cid:1221)u ph(cid:1133)(cid:1131)ng pháp th(cid:1269)c hi(cid:1227)n t(cid:1237)i thi(cid:1223)u hoá hàm Boole và có th(cid:1223)(cid:3)(cid:255)(cid:1133)a v(cid:1221) 2 nhóm là bi(cid:839)n (cid:255)(cid:861)i (cid:255)(cid:809)i s(cid:857) và dùng thu(cid:821)t toán. Ph(cid:1133)(cid:1131)ng pháp bi(cid:1219)n (cid:255)(cid:1241)i (cid:255)(cid:1189)i s(cid:1237) (ph(cid:1133)(cid:1131)ng pháp gi(cid:1191)i tích) d(cid:1269)a vào các tiên (cid:255)(cid:1221), (cid:255)(cid:1231)nh lý, tính ch(cid:1193)t c(cid:1259)a hàm Boole (cid:255)(cid:1223) th(cid:1269)c hi(cid:1227)n t(cid:1237)i thi(cid:1223)u hoá.

(cid:1250) nhóm thu(cid:821)t toán có 2 ph(cid:1133)(cid:1131)ng pháp th(cid:1133)(cid:1249)ng (cid:255)(cid:1133)(cid:1255)c dùng là: ph(cid:1133)(cid:1131)ng pháp b(cid:1191)ng Karnaugh (còn (cid:74)(cid:1233)i là bìa Karnaugh – bìa K) dùng cho các hàm có t(cid:1263) 6 bi(cid:1219)n tr(cid:1251) xu(cid:1237)ng, và ph(cid:1133)(cid:1131)ng pháp Quine- Mc.Cluskey có th(cid:1223) s(cid:1265) d(cid:1257)ng cho hàm có s(cid:1237) bi(cid:1219)n b(cid:1193)t k(cid:484) c(cid:458)ng nh(cid:1133) cho phép th(cid:1269)c hi(cid:1227)n t(cid:1269)(cid:3)(cid:255)(cid:1245)ng theo ch(cid:1133)(cid:1131)ng trình (cid:255)(cid:1133)(cid:1255)c vi(cid:1219)t trên máy tính.

Trong ph(cid:1195)n này ch(cid:1229) gi(cid:1247)i thi(cid:1227)u 2 ph(cid:1133)(cid:1131)ng pháp (cid:255)(cid:1189)i di(cid:1227)n cho 2 nhóm:

• Ph(cid:1133)(cid:1131)ng pháp bi(cid:839)n (cid:255)(cid:861)i (cid:255)(cid:809)i s(cid:857) (nhóm bi(cid:1219)n (cid:255)(cid:1241)i (cid:255)(cid:1189)i s(cid:1237)). • Ph(cid:1133)(cid:1131)ng pháp (cid:69)(cid:811)ng Karnaugh (nhóm thu(cid:1201)t toán).

1. Ph(cid:1133)(cid:1131)ng pháp bi(cid:1219)n (cid:255)(cid:1241)i (cid:255)(cid:1189)i s(cid:1237)

(cid:264)ây là ph(cid:1133)(cid:1131)ng pháp t(cid:1237)i thi(cid:1223)u hóa hàm Boole (ph(cid:1133)(cid:1131)ng trình logic) d(cid:1269)a vào các tiên (cid:255)(cid:1221), (cid:255)(cid:1231)nh lý,

tính ch(cid:1193)t c(cid:1259)a (cid:255)(cid:1189)i s(cid:1237) Boole.

Ví d(cid:877) 2.12 T(cid:1237)i thi(cid:1223)u hoá hàm f(x1,x2) = x 1x2 + x1 x 2 + x1x2

f(x1,x2) = x 1x2 + x1 x 2 + x1x2

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

= x2 + x1 x 2 = x2 + x1

Ví d(cid:877) 2.13 T(cid:1237)i thi(cid:1223)u hoá hàm 3 bi(cid:1219)n sau

f(x1,x2,x3) = x 1x2x3 + x1 x 2 x 3 + x1 x 2x3 + x1x2 x 3 + x1x2x3

Bài gi(cid:1191)ng (cid:264)(cid:44)(cid:1226)N T(cid:1264) S(cid:1236) 1 Trang 22

= x 1x2x3 + x1 x 2 x 3 + x1 x 2x3 + x1x2 ( x 3 + x3)

= x 1x2x3 + x1 x 2( x 3 + x3) + x1x2

= x 1x2x3 + x1( x 2 + x2)

= x 1x2x3 + x1 = x1 + x2 x3

BCAC

Ví d(cid:877) 2.14 Rút g(cid:1233)n bi(cid:1223)u th(cid:1261)c: f =

Áp d(cid:1257)ng (cid:255)(cid:1231)nh lý De Morgan ta có:

BCACAB

+ BCACBA

(

f =

+. + ). +

+ BCACBCA

CBCACA +

BCAC

+ ).1

(

+ BACC ++ CBA

= =

V(cid:1201)y, (cid:255)(cid:1223) th(cid:1269)c hi(cid:1227)n m(cid:1189)ch này có th(cid:1223) dùng c(cid:1241)ng OR 3 ngõ vào.

2. Ph(cid:1133)(cid:1131)ng pháp b(cid:1191)ng Karnaugh

(cid:264)(cid:1223) t(cid:1237)i thi(cid:1223)u hóa hàm Boole b(cid:1205)ng ph(cid:1133)(cid:1131)ng pháp b(cid:1191)ng Karnaugh ph(cid:1191)i tuân th(cid:1259) theo qui t(cid:1203)c v(cid:1221) ô k(cid:1219) (cid:70)(cid:1201)n: “Hai ô (cid:255)(cid:753)(cid:875)c g(cid:853)i là k(cid:839) c(cid:821)n nhau là hai ô mà khi ta t(cid:883) ô này sang ô kia ch(cid:849) làm thay (cid:255)(cid:861)i giá tr(cid:851) c(cid:879)a 1 bi(cid:839)n.”

Quy t(cid:1203)c chung c(cid:1259)a ph(cid:1133)(cid:1131)ng pháp rút g(cid:1233)n b(cid:1205)ng b(cid:1191)ng Karnaugh là gom (k(cid:1219)t h(cid:1255)p) các ô k(cid:1219) c(cid:1201)n l(cid:1189)i

(cid:89)(cid:1247)i nhau.

Khi gom 2 ô k(cid:1219) c(cid:1201)n s(cid:1217) lo(cid:1189)i (cid:255)(cid:1133)(cid:1255)c 1 bi(cid:1219)n (2=21 lo(cid:1189)i 1 bi(cid:1219)n). Khi gom 4 ô k(cid:1219) c(cid:1201)n vòng tròn s(cid:1217) lo(cid:1189)i (cid:255)(cid:1133)(cid:1255)c 2 bi(cid:1219)n (4=22 lo(cid:1189)i 2 bi(cid:1219)n). Khi gom 8 ô k(cid:1219) c(cid:1201)n vòng tròn s(cid:1217) lo(cid:1189)i (cid:255)(cid:1133)(cid:1255)c 3 bi(cid:1219)n (8=23 lo(cid:1189)i 3 bi(cid:1219)n).

(cid:55)(cid:861)ng quát, khi gom 2n ô k(cid:839) c(cid:821)n vòng tròn s(cid:837) lo(cid:809)i (cid:255)(cid:753)(cid:875)c n bi(cid:839)n. Nh(cid:887)ng bi(cid:839)n b(cid:851) lo(cid:809)i là

nh(cid:887)ng bi(cid:839)n khi ta (cid:255)i vòng qua các ô k(cid:839) c(cid:821)n mà giá tr(cid:851) c(cid:879)a chúng thay (cid:255)(cid:861)i.

Nh(cid:1267)ng (cid:255)(cid:76)(cid:1221)u c(cid:1195)n l(cid:1133)u ý:

Vòng gom (cid:255)(cid:1133)(cid:1255)c g(cid:1233)i là h(cid:1255)p l(cid:1227) khi trong vòng gom (cid:255)ó có ít nh(cid:1193)t 1 ô ch(cid:1133)a thu(cid:1245)c vòng gom nào. Các ô k(cid:1219) c(cid:1201)n mu(cid:1237)n gom (cid:255)(cid:1133)(cid:1255)c ph(cid:1191)i là k(cid:1219) c(cid:1201)n vòng tròn ngh(cid:429)a là ô k(cid:1219) c(cid:1201)n cu(cid:1237)i c(cid:458)ng là ô k(cid:1219) c(cid:1201)n

(cid:255)(cid:1195)u tiên.

Vi(cid:1227)c k(cid:1219)t h(cid:1255)p nh(cid:1267)ng ô k(cid:1219) c(cid:1201)n v(cid:1247)i nhau còn tùy thu(cid:1245)c vào ph(cid:1133)(cid:1131)ng pháp bi(cid:1223)u di(cid:1225)n hàm Boole theo

(cid:71)(cid:1189)ng chính t(cid:1203)c 1 ho(cid:1211)c chính t(cid:1203)c 2, c(cid:1257) th(cid:1223) là:

• (cid:49)(cid:839)u bi(cid:843)u di(cid:845)n hàm theo d(cid:809)ng chính t(cid:823)c 1 (t(cid:861)ng các tích s(cid:857)) ta ch(cid:1229) quan tâm nh(cid:1267)ng ô k(cid:1219) (cid:70)(cid:1201)n có giá tr(cid:1231) b(cid:1205)ng 1 và tùy (cid:255)(cid:1231)nh. K(cid:1219)t qu(cid:1191) m(cid:1243)i vòng gom lúc này s(cid:1217) là m(cid:1245)t tích rút g(cid:1233)n. (cid:46)(cid:1219)t qu(cid:1191) c(cid:1259)a hàm bi(cid:1223)u di(cid:1225)n theo d(cid:1189)ng chính t(cid:1203)c 1 s(cid:1217) là t(cid:1241)ng t(cid:1193)t c(cid:1191) các tích s(cid:1237) rút g(cid:1233)n c(cid:1259)a (cid:87)(cid:1193)t c(cid:1191) các vòng gom.

• (cid:49)(cid:839)u bi(cid:843)u di(cid:845)n hàm theo d(cid:809)ng chính t(cid:823)c 2 (tích các t(cid:861)ng s(cid:857)) ta ch(cid:1229) quan tâm nh(cid:1267)ng ô k(cid:1219) (cid:70)(cid:1201)n có giá tr(cid:1231) b(cid:1205)ng 0 và tùy (cid:255)(cid:1231)nh. K(cid:1219)t qu(cid:1191) m(cid:1243)i vòng gom lúc này s(cid:1217) là m(cid:1245)t t(cid:1241)ng rút g(cid:1233)n.

Ch(cid:1133)(cid:1131)ng 2. (cid:264)(cid:1189)i s(cid:1237) BOOLE Trang 23

(cid:46)(cid:1219)t qu(cid:1191) c(cid:1259)a hàm bi(cid:1223)u di(cid:1225)n theo d(cid:1189)ng chính t(cid:1203)c 2 s(cid:1217) là tích t(cid:1193)t c(cid:1191) các t(cid:1241)ng s(cid:1237) rút g(cid:1233)n c(cid:1259)a (cid:87)(cid:1193)t c(cid:1191) các vòng gom.

Ta quan tâm nh(cid:1267)ng ô tùy (cid:255)(cid:1231)nh (X) sao cho nh(cid:1267)ng ô này k(cid:1219)t h(cid:1255)p v(cid:1247)i nh(cid:1267)ng ô có giá tr(cid:1231) b(cid:1205)ng 1 (n(cid:1219)u bi(cid:1223)u di(cid:1225)n theo d(cid:1189)ng chính t(cid:1203)c 1) ho(cid:1211)c b(cid:1205)ng 0 (n(cid:1219)u bi(cid:1223)u di(cid:1225)n theo d(cid:1189)ng chính t(cid:1203)c 2) làm cho s(cid:1237) (cid:79)(cid:1133)(cid:1255)ng ô k(cid:1219) c(cid:1201)n là 2n l(cid:1247)n nh(cid:1193)t. (cid:47)(cid:1133)u ý các ô tùy (cid:255)(cid:1231)nh (X) ch(cid:1229) là nh(cid:1267)ng ô thêm vào vòng gom (cid:255)(cid:1223) rút (cid:74)(cid:1233)n h(cid:1131)n các bi(cid:1219)n mà thôi.

Các vòng gom b(cid:1203)t bu(cid:1245)c ph(cid:1191)i ph(cid:1259) h(cid:1219)t t(cid:1193)t c(cid:1191) các ô có giá tr(cid:1231) b(cid:1205)ng 1 có trong b(cid:1191)ng (n(cid:1219)u t(cid:1237)i thi(cid:1223)u theo d(cid:1189)ng chính t(cid:1203)c 1), t(cid:1133)(cid:1131)ng t(cid:1269) các vòng gom b(cid:1203)t bu(cid:1245)c ph(cid:1191)i ph(cid:1259) h(cid:1219)t t(cid:1193)t c(cid:1191) các ô có giá tr(cid:1231) b(cid:1205)ng 0 có trong b(cid:1191)ng (n(cid:1219)u t(cid:1237)i thi(cid:1223)u theo d(cid:1189)ng chính t(cid:1203)c 2) thì k(cid:1219)t qu(cid:1191) t(cid:1237)i thi(cid:1223)u hoá m(cid:1247)i h(cid:1255)p l(cid:1227).

Các tr(cid:1133)(cid:1249)ng h(cid:1255)p (cid:255)(cid:1211)c bi(cid:1227)t:

ﬁ

ﬁ (cid:49)(cid:1219)u t(cid:1193)t c(cid:1191) các ô c(cid:1259)a b(cid:1191)ng Karnaugh (cid:255)(cid:1221)u b(cid:1205)ng 1 và tu(cid:484)(cid:3)(cid:255)(cid:1231)nh (X) ngh(cid:429)a là t(cid:1193)t c(cid:1191) các ô (cid:255)(cid:1221)u k(cid:1219) c(cid:1201)n giá tr(cid:1231) c(cid:1259)a hàm b(cid:1205)ng 1. (cid:49)(cid:1219)u t(cid:1193)t c(cid:1191) các ô c(cid:1259)a b(cid:1191)ng Karnaugh (cid:255)(cid:1221)u b(cid:1205)ng 0 và tu(cid:484)(cid:3)(cid:255)(cid:1231)nh (X) ngh(cid:429)a là t(cid:1193)t c(cid:1191) các ô (cid:255)(cid:1221)u k(cid:1219) c(cid:1201)n giá tr(cid:1231) c(cid:1259)a hàm b(cid:1205)ng 0.

Ví d(cid:877) 2.15: T(cid:1237)i thi(cid:1223)u hóa hàm sau

x1

f(x1,x2) x2

(cid:55)(cid:1237)i thi(cid:1223)u hoá theo chính t(cid:1203)c 2: f(x1,x2) = x1 + x2 0 0 1 0 1 1 1 1

Ví d(cid:877) 2.16:

Vòng gom 1: x1 f(x1,x2,x3) x3

Vòng gom 2: x2.x3 x1,x2 0 1 00 0 0 01 0 1 11 1 1 10 1 1

(cid:55)(cid:857)i thi(cid:843)u theo chính t(cid:823)c 1: Ta ch(cid:1229) quan tâm (cid:255)(cid:1219)n nh(cid:1267)ng ô có giá tr(cid:1231) b(cid:1205)ng 1 và tùy (cid:255)(cid:1231)nh (X), nh(cid:1133) (cid:89)(cid:1201)y s(cid:1217) có 2 vòng gom (cid:255)(cid:1223) ph(cid:1259) h(cid:1219)t các ô có giá tr(cid:1231) b(cid:1205)ng 1: vòng gom 1 g(cid:1239)m 4 ô k(cid:1219) c(cid:1201)n, và vòng gom 2 g(cid:1239)m 2 ô k(cid:1219) c(cid:1201)n (hình v(cid:1217)).

(cid:264)(cid:1237)i v(cid:1247)i vòng gom 1: Có 4 ô = 22 nên lo(cid:1189)i (cid:255)(cid:1133)(cid:1255)c 2 bi(cid:1219)n. Khi (cid:255)i vòng qua 4 ô k(cid:1219) c(cid:1201)n trong vòng gom ch(cid:1229) có giá tr(cid:1231) c(cid:1259)a bi(cid:1219)n x1 không (cid:255)(cid:1241)i (luôn b(cid:1205)ng 1), còn giá tr(cid:1231) c(cid:1259)a bi(cid:1219)n x2 thay (cid:255)(cid:1241)i (t(cid:1263) 1ﬁ 0) và giá tr(cid:1231) c(cid:1259)a bi(cid:1219)n x3 thay (cid:255)(cid:1241)i (t(cid:1263) 0ﬁ 1) nên các bi(cid:1219)n x2 và x3 b(cid:1231) lo(cid:1189)i, ch(cid:1229) còn l(cid:1189)i bi(cid:1219)n x1 trong k(cid:1219)t qu(cid:1191) (cid:70)(cid:1259)a vòng gom 1. Vì x1=1 nên k(cid:1219)t qu(cid:1191) c(cid:1259)a vòng gom 1 theo d(cid:1189)ng chính t(cid:1203)c 1 s(cid:1217) có x1 vi(cid:1219)t (cid:1251) d(cid:1189)ng th(cid:1201)t: x1

(cid:264)(cid:1237)i v(cid:1247)i vòng gom 2: Có 2 ô = 21 nên s(cid:1217) lo(cid:1189)i (cid:255)(cid:1133)(cid:1255)c 1 bi(cid:1219)n. Khi (cid:255)i vòng qua 2 ô k(cid:1219) c(cid:1201)n trong vòng gom giá tr(cid:1231) c(cid:1259)a bi(cid:1219)n x2 và x3 không (cid:255)(cid:1241)i, còn giá tr(cid:1231) c(cid:1259)a bi(cid:1219)n x1 thay (cid:255)(cid:1241)i (t(cid:1263) 0ﬁ 1) nên các bi(cid:1219)n x2 và x3(cid:3)(cid:255)(cid:1133)(cid:1255)c gi(cid:1267) l(cid:1189)i, ch(cid:1229) có bi(cid:1219)n x1 b(cid:1231) lo(cid:1189)i. Vì x2=1 và x3=1 nên k(cid:1219)t qu(cid:1191) c(cid:1259)a vòng gom 2 theo d(cid:1189)ng chính (cid:87)(cid:1203)c 1 s(cid:1217) có x2 và x3 vi(cid:1219)t (cid:1251) d(cid:1189)ng th(cid:1201)t: x2.x3

(cid:46)(cid:1219)t h(cid:1255)p 2 vòng gom ta có k(cid:1219)t qu(cid:1191) t(cid:1237)i gi(cid:1191)n theo chính t(cid:1203)c 1:

f(x1,x2,x3) = x1 + x2.x3

Bài gi(cid:1191)ng (cid:264)(cid:44)(cid:1226)N T(cid:1264) S(cid:1236) 1 Trang 24

(cid:55)(cid:857)i thi(cid:843)u theo chính t(cid:823)c 2: Ta quan tâm (cid:255)(cid:1219)n nh(cid:1267)ng ô có giá tr(cid:1231) b(cid:1205)ng 0 và tùy (cid:255)(cid:1231)nh (X), nh(cid:1133) v(cid:1201)y (cid:70)(cid:458)ng có 2 vòng gom (hình v(cid:1217)), m(cid:1243)i vòng gom (cid:255)(cid:1221)u g(cid:1239)m 2 ô k(cid:1219) c(cid:1201)n.

(cid:264)(cid:1237)i v(cid:1247)i vòng gom 1: Có 2 ô = 21 nên lo(cid:1189)i (cid:255)(cid:1133)(cid:1255)c 1 bi(cid:1219)n, bi(cid:1219)n b(cid:1231) lo(cid:1189)i là x2 (vì có giá tr(cid:1231) thay (cid:255)(cid:1241)i t(cid:1263) 0ﬁ 1). Vì x1=0 và x3=0 nên k(cid:1219)t qu(cid:1191) c(cid:1259)a vòng gom 1 theo d(cid:1189)ng chính t(cid:1203)c 2 s(cid:1217) có x1 và x3(cid:3)(cid:1251) d(cid:1189)ng th(cid:1201)t: x1+ x3.

(cid:264)(cid:1237)i v(cid:1247)i vòng gom 2: Có 2 ô = 21 nên lo(cid:1189)i (cid:255)(cid:1133)(cid:1255)c 1 bi(cid:1219)n, bi(cid:1219)n b(cid:1231) lo(cid:1189)i là x3 (vì có giá tr(cid:1231) thay (cid:255)(cid:1241)i t(cid:1263) 0ﬁ 1). Vì x1=0 và x2=0 nên k(cid:1219)t qu(cid:1191) c(cid:1259)a vòng gom 2 theo d(cid:1189)ng chính t(cid:1203)c 2 s(cid:1217) có x1 và x2(cid:3)(cid:1251) d(cid:1189)ng th(cid:1201)t: x1+x2.

Vòng gom 1: x1 + x3 f(x1,x2,x3) x3 x1,x2

00 0 0 01 0 1 11 1 1 10 1 1 0 1 Vòng gom 2: x1 + x2

(x1,x2,x3) = (x1+x3).(x1+x2)

x1.x1 + x1.x2 + x1.x3 + x2.x3

(cid:46)(cid:1219)t h(cid:1255)p 2 vòng gom có k(cid:1219)t qu(cid:1191) c(cid:1259)a hàm f vi(cid:1219)t theo d(cid:1189)ng chính t(cid:1203)c 2 nh(cid:1133) sau: f = = x1 + x1.x2 + x1.x3 + x2.x3 x1(1+ x2 + x3) + x2.x3 = x1 + x2.x3 =

Nh(cid:1201)n xét: Trong ví d(cid:1257) này, hàm ra vi(cid:1219)t theo d(cid:1189)ng chính t(cid:1203)c 1 và hàm ra vi(cid:1219)t theo d(cid:1189)ng chính t(cid:1203)c 2 là gi(cid:1237)ng nhau. Tuy nhiên có tr(cid:1133)(cid:1249)ng h(cid:1255)p hàm ra c(cid:1259)a hai d(cid:1189)ng chính t(cid:1203)c 1 và 2 là khác nhau, nh(cid:1133)ng giá tr(cid:1231) c(cid:1259)a hàm ra (cid:1261)ng v(cid:1247)i m(cid:1245)t t(cid:1241) h(cid:1255)p bi(cid:1219)n (cid:255)(cid:1195)u vào là duy nh(cid:1193)t trong c(cid:1191) 2 d(cid:1189)ng chính t(cid:1203)c.

Chú ý: Ng(cid:1133)(cid:1249)i ta th(cid:1133)(cid:1249)ng cho hàm Boole d(cid:1133)(cid:1247)i d(cid:1189)ng bi(cid:1223)u th(cid:1261)c rút g(cid:1233)n. Vì có 2 cách bi(cid:1223)u di(cid:1225)n hàm Boole theo d(cid:1189)ng chính t(cid:1203)c 1 ho(cid:1211)c 2 nên s(cid:1217) có 2 cách cho giá tr(cid:1231) c(cid:1259)a hàm Boole (cid:1261)ng v(cid:1247)i 2 d(cid:1189)ng chính t(cid:1203)c (cid:255)ó:

(cid:39)(cid:809)ng chính t(cid:823)c 1: T(cid:861)ng các tích s(cid:857).

(3,4,7) + d(5,6) f(x1,x2,x3) = S

Trong (cid:255)ó ký hi(cid:1227)u d ch(cid:1229) giá tr(cid:1231) các ô này là tùy (cid:255)(cid:1231)nh (d: Don’t care)

x1,x2 f(x1,x2,x3) x3

00 0 0 01 0 1 11 X 1 10 1 X 0 1

Lúc (cid:255)ó b(cid:1191)ng Karnaugh s(cid:1217)(cid:3)(cid:255)(cid:1133)(cid:1255)c cho nh(cid:1133) hình trên. T(cid:1263) bi(cid:1223)u th(cid:1261)c rút g(cid:1233)n c(cid:1259)a hàm ta th(cid:1193)y t(cid:1189)i các ô (cid:1261)ng v(cid:1247)i t(cid:1241) h(cid:1255)p nh(cid:1231) phân các bi(cid:1219)n vào có giá tr(cid:1231) là 3, 4, 7 hàm ra có giá tr(cid:1231) b(cid:1205)ng 1; t(cid:1189)i các ô (cid:1261)ng v(cid:1247)i (cid:87)(cid:1241) h(cid:1255)p nh(cid:1231) phân các bi(cid:1219)n vào có giá tr(cid:1231) là 5, 6 hàm ra có giá tr(cid:1231) là tùy (cid:255)(cid:1231)nh; hàm ra có giá tr(cid:1231) b(cid:1205)ng 0 (cid:1251) nh(cid:1267)ng ô còn l(cid:1189)i (cid:1261)ng v(cid:1247)i t(cid:1241) h(cid:1255)p các bi(cid:1219)n vào có giá tr(cid:1231) là 0, 1, 2.

(cid:39)(cid:809)ng chính t(cid:823)c 2: Tích các t(cid:861)ng s(cid:857). Ph(cid:1133)(cid:1131)ng trình trên c(cid:458)ng t(cid:1133)(cid:1131)ng (cid:255)(cid:1133)(cid:1131)ng v(cid:1247)i cách cho hàm nh(cid:1133) sau: P (0, 1, 2) + d(5, 6) f(x1,x2,x3) =

Ch(cid:1133)(cid:1131)ng 2. (cid:264)(cid:1189)i s(cid:1237) BOOLE Trang 25

Ví d(cid:877) 2.17: T(cid:1237)i thi(cid:1223)u hóa hàm 4 bi(cid:1219)n cho d(cid:1133)(cid:1247)i d(cid:1189)ng bi(cid:1223)u th(cid:1261)c sau:

(2,6,10,11,12,13) + d(0,1,4,7,8,9,14,15) f(x1,x2,x3,x4) = S

x4x3 x4x3 f(x1,x2,x3,x4) x2x1 f(x1,x2,x3,x4) x2x1

00 01 11 10 1 X 1 X 1 1

00 X X 01 X 0 0 X X 11 1 X 1 10

00 01 11 10 1 X 1 X 1 1

00 X X 0 01 X 0 X X 11 1 X 1 10

Vòng gom 1 Vòng gom 2

Th(cid:1269)c hi(cid:1227)n t(cid:1237)i thi(cid:1223)u hóa theo d(cid:1189)ng chính t(cid:1203)c 1: t(cid:1263) b(cid:1191)n (cid:255)(cid:1239) Karnaugh ta có 2 vòng gom, vòng gom 1

(cid:74)(cid:1239)m 8 ô k(cid:1219) c(cid:1201)n và vòng gom 2 g(cid:1239)m 8 ô k(cid:1219) c(cid:1201)n. K(cid:1219)t qu(cid:1191) t(cid:1237)i thi(cid:1223)u hóa nh(cid:1133) sau:

Vòng gom 1: x 1 Vòng gom 2: x4

(cid:57)(cid:1201)y: f(x1,x2,x3,x4) = x 1 + x4