Bài giảng Toán rời rạc - Chương 3: Đại số Bool, hàm Bool

Công thức đa thức tối tiểu

n như nhau:

Nếu F đơn giản hơn G và G đơn giản hơn F thì

ta nói F và G đơn giản như nhau.

Công thức đa thức tối tiểu:

Công thức F của hàm Bool f được gọi là tối tiểu

nếu với bất kỳ công thức G của f mà đơn giản

hơn F thì F và G đơn giản như nhau

2. Hàm Bool

Phương pháp biểu đồ Karnaugh

Với qui ước: Khi một ô nằm trong dãy được đánh dấu

bởi x thì tại đó x =1, bởi thì tại đó x =0, tương tự cho

y, z.

Các ô tại đó f bằng 1 sẽ được đánh dấu (tô đậm hoặc

gạch chéo). Tập các ô được đánh dấ

 

pdf11 trang | Chia sẻ: trungkhoi17 | Lượt xem: 759 | Lượt tải: 1download
Bạn đang xem nội dung tài liệu Bài giảng Toán rời rạc - Chương 3: Đại số Bool, hàm Bool, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
06/05/2010 Chương III 1. ði S Bool Mt ñi s Bool (A,+,.) là mt tp hp A ≠ ∅ ðI S BOOL vi hai phép toán (+), (.), tha 5 tính cht sau: HÀM BOOL • Tính giao hoán: ∀x,y ∈ A x.y = y.x; x+y = y+x; 06/05/2010 2 1. ði S Bool 1. ði S Bool • Tính kt hp: ∀x,y,z ∈ A • Có các phn t trung hòa 1 và 0: ∀x ∈A (x.y).z = x.(y.z); x.1 = 1.x = x; (x+y)+z = x+(y+z). x + 0 = 0 ∨ x = x. • Tính phân b: ∀x,y,z ∈ A x.(y+z) = (x.y)+(x.z); • Mi phn t ñu có phn t bù:∀x∈A, ∃x ∈A, x+(y.z) = (x+y).(x+z). x. x = x .x = 0; X+x = x + x = 1. 06/05/2010 3 06/05/2010 4 1 06/05/2010 1. ði S Bool 1. ði S Bool Ví d: Xét tp hp B = {0, 1}. Trên B ta ñnh nghĩa hai Xét F là tp hp tt c các dng mnh ñ theo n bin phép toán +,. như sau: p1, p2,,p n vi hai phép toán ni lin ∧, phép toán ni . 0 1 ri ∨, trong ñó ta ñng nht các dng mnh ñ tương + 0 1 0 0 0 0 0 0 ñương. Khi ñó F là mt ñi s Bool vi phn t 1 là 1 0 1 1 0 1 hng ñúng 1, phn t 0 là hng sai 0, phn t bù ca dng mnh ñ E là dng mnh ñ bù E Khi ñó, B tr thành mt ñi s Bool 06/05/2010 5 06/05/2010 6 1. ði S Bool 2. Hàm Bool Cho ñi s Bool (A,+,.). Khi ñó vi mi x,y ∈A, ta có: ðnh nghĩa 1. x.x=x;x+x=x. Mt hàm Bool n bin là mt ánh x 2. x.0=0.x=0;x+1=1+x=1. 3. Phntbùcaxlàduynhtvàx =x; f : B n → B , trong ñó B = {0, 1}. 1= 0; 0 = 1. Mt hàm Booln bin là mt hàm s có dng: 4. Công thc De Morgan: f = f(x ,x ,,x ), trong ñó mi bin trong x , x ,, x xy= x + y; 1 2 n 1 2 n ch nhn hai giá tr 0,1 và f nhn giá tr trong B = {0,1}. x+ y = xy. 5. Tínhhpth: Ký hiu Fn ñ ch tp các hàm Bool n bin. x(x+y) = x; x+(xy) = x. 06/05/2010 7 06/05/2010 8 2 06/05/2010 2. Hàm Bool 2. Hàm Bool Bng chân tr Ví d: Xét hàm Bool n bin f(x 1,x 2,,x n). Vì mi bin xi ch Xét kt qu f trong vic thông qua mt Quyt ñnh da nhn hai giá tr 0, 1 nên ch có 2n trưng hp ca b vào3 phiubu x, y, z. bin (x ,x ,,x ). 1. Mi phiu ch ly mt trong hai giá tr: 1 (tán thành) 1 2 n hoc 0 (bác b). Do ñó, ñ mô t f, ta có th lp bng gm 2n hàng ghi 2. Kt qu f là 1 (thông qua Quyt ñnh) nu ñưc ña tt c các giá tr ca f tùy theo 2n trưng hp ca bin. s phiu tán thành, là 0 (không thông qua Quyt ñnh) nu ña s phiu bác b. Ta gi ñây là bng chân tr ca f. Khi ñó f là hàm Bool theo 3 bin x, y, z có bng chân tr như sau: 06/05/2010 9 06/05/2010 10 2. Hàm Bool 2. Hàm Bool x y z f Các phép toán trên hàm Bool 1 1 1 1 Các phép toán trên Fn ñưc ñnh nghĩa như sau: 1 1 0 1 1. Phép cng Bool +: 1 0 1 1 ∈ 1 0 0 0 Vi f, g Fn ta ñnh nghĩa tng Bool ca f và g: n 0 1 1 1 ∀x = (x 1,x 2,,x n)∈ B , 0 1 0 0 (f +g)(x) = f(x) + g(x) – f(x)g(x) 0 0 1 0 D thy 0 0 0 0 f +g ∈ Fn và (f+g)(x) = max{f(x),g(x)} 06/05/2010 11 06/05/2010 12 3 06/05/2010 2. Hàm Bool 2. Hàm Bool Các phép toán trên hàm Bool Các phép toán trên hàm Bool 2. Phép nhân Bool .: 3. Phép ly hàm bù: Vi f, g ∈Fn ta ñnh nghĩa tích Bool ca f và g Vi f ∈ Fn ta ñnh nghĩa hàm bù ca f như sau: n ∀x=(x 1,x 2,,x n)∈B , f=1 − f (f.g)(x) = f(x)g(x) D thy: f.g ∈Fn và (f.g)(x) = min{f(x),g(x)} 06/05/2010 13 06/05/2010 14 2. Hàm Bool 2. Hàm Bool Dng ni ri chính tc ca hàm Bool Công thc ña thc ti tiu •Xét tp hp các hàm Bool ca n bin Fn theo n bin • ðơn gin hơn x1 ,x 2,,x n. Cho hai công thc ña thc ca mt hàm Bool: • Mihàmboolx hayx ñưcgilàtñơn. i i f = m + m +. +m (F) • ðơn thc là tích khác không ca mt s hu hn t 1 2 k ñơn. f =M 1 + M 2 + + M l (G) • T ti tiu là tích khác khôngca ñúngn t ñơn. Ta nói rngcông thc F ñơn gin hơn công thc • Công thc ña thc là công thc biu din hàm Bool G nu tn ti ñơn ánh h: {1,2,..,k} → { 1,2,, thành tng ca các ñơn thc. l} sao cho vi mi i∈ {1,2,..,k} thì s t ñơn ca • Dng ni ri chính tc là công thc biu din hàm mi không nhiu hơn s t ñơn ca Mh(i) Bool thành tng ca các t ti tiu. 06/05/2010 15 06/05/2010 16 4 06/05/2010 2. Hàm Bool 2. Hàm Bool Công thc ña thc ti tiu Phương pháp biu ñ Karnaugh • ðơn gin như nhau: Xétf là mt hàm Booltheo n bin x1,x 2,,x n vin=3hoc4. Nu F ñơn gin hơn G và G ñơn gin hơn F thì ta nói F và G ñơn gin như nhau. Trưng hp n = 3: f là hàm Bool theo 3 bin x, y, z. Khi ñó bng chân tr ca f gm 8 hàng. Thay cho bng chân tr ca f Công thc ña thc ti tiu: ta v mt bng ch nht gm 8 ô, tương ng vi 8 hàng ca Công thc F ca hàm Bool f ñưc gi là ti tiu bng chân tr, ñưc ñánh du như sau: nu vi bt kỳ công thc G ca f mà ñơn gin x x x x hơn F thì F và G ñơn gin như nhau z 101 111 011 001 z 100 110 010 000 y y y y 06/05/2010 17 06/05/2010 18 2. Hàm Bool 2. Hàm Bool Phương pháp biu ñ Karnaugh Phương pháp biu ñ Karnaugh Trưng hp n = 4: f là hàm Bool theo 4 bin x, y, z, t. Khi ñó Vi qui ưc: Khi mt ô nm trong dãy ñưc ñánh du bng chân tr ca f gm 16 hàng. Thay cho bng chân tr ca f ta bi x thì ti ñó x =1, bix thì ti ñó x =0, tương t cho v mt bng ch nht gm 16 ô, tương ng vi 16 hàng ca bng y, z. chân tr, ñưc ñánh du như sau: x x x x Các ô ti ñó f bng 1 s ñưc ñánh du (tô ñm hoc z 1010 1110 0110 0010 t gch chéo). Tp các ô ñưc ñánh du ñưc gi là biu z 1011 1111 0111 0011 t ñ Karnaugh ca f, ký hiu là kar(f). z 1001 1101 0101 0001 t z 1000 1100 0100 0000 t y y y y 06/05/2010 19 06/05/2010 20 5 06/05/2010 2. Hàm Bool 2. Hàm Bool Phương pháp biu ñ Karnaugh T bào Trong c hai trưng hp, hai ô ñưc gi là k Xét các hàm Bool theo n bin x1,x 2,,x n. Khi ñó, nu f là mt ñơn thc có dng tích ca k t ñơn phân bit thì nhau (theo nghĩa rng), nu chúng là hai ô lin kar(f) là mt hình ch nht gm 2nk ô k nhau. Nhng hình ch nht gm mt lũy tha ca 2 nhng ô k nhau nhau hoc chúng là ô ñu, ô cui ca cùng mt ñưc gi là các t bào . Như vy, biu ñ Karnaugh ca hàng (ct) nào ñó. Nhn xét rng, do cách ñánh mt ñơn thc là mt t bào. Ngưc li, nu T là mt t bào thì T là biu ñ Karnaugh ca mt ñơn thc duy du như trên, hai ô k nhau ch lch nhau mt nht m, cách xác ñnh m như sau: ln lưt chiu T lên các cnh, nu toàn b hình chiu nm trn trong mt t bin duy nht. ñơn nào thì t ñơn ñó mi xuthin trong m. 06/05/2010 21 06/05/2010 22 2. Hàm Bool 2. Hàm Bool Ví d: Xét các hàm Bool theo 4 bin x, y, z, t. Ví d: Xét các hàm Bool theo 4 bin x, y, z, t. Biu ñ Karnaugh ca ñơn thc xyzt Biu ñ Karnaugh ca ñơn thc yzt x x x x x x x x z t z t z t z t z t z t z t z t y y y y y y y y 06/05/2010 23 06/05/2010 24 6 06/05/2010 2. Hàm Bool 2. Hàm Bool Ví d: Xét các hàm Bool theo 4 bin x, y, z, t. Ví d: Xét các hàm Bool theo 4 bin x, y, z, t. Biu ñ Karnaugh ca ñơn thc yt Biu ñ Karnaugh ca ñơn thc t x x x x x x x x z t z t z t z t z t z t z t z t y y y y y y y y 06/05/2010 25 06/05/2010 26 2. Hàm Bool 2. Hàm Bool T bào ln Ví d: Xét hàm Bool f theo 4 bin x, y, z, t có biu ñ Cho hàm Bool f. Ta nói T là mt t bào ln ca Karnaugh như sau: kar(f) nu T tho hai tính cht sau: x x x x a. T là mt t bào và T ⊆ kar(f). z t b. Không tn ti t bào T’ nào tha T’ ≠ T và T z t z t ⊆ T’ ⊆ kar(f). z t y y y y 06/05/2010 27 06/05/2010 28 7 06/05/2010 2. Hàm Bool 2. Hàm Bool Kar(f) có 6 t bào ln như sau: x x x x x x x x x x x x x x x x z t z t z t z t z t z t z t z t z t z t z t z t z t z t z t z t y y y y y y y y y y y y y y y y xz yz xt xy 06/05/2010 29 06/05/2010 30 2. Hàm Bool 2. Hàm Bool Thut toán xác ñnh tt c các công thc ña thc x x x x x x x x ti tiu ca hàm Bool f z t z t Bưc 1: V biu ñ Karnaugh ca f. z t z t z t z t Bưc 2: Xác ñnh tt c các t bào ln ca kar(f). z t z t Bưc 3: Xác ñnh các t bào ln nht thit phi chn. y y y y y y y y Ta nht thit phi chn t bào ln T khi tn ti yzt yt mt ô ca kar(f) mà ô này ch nm trong t bào ln T và không nm trong bt kỳ t bào ln nào khác. 06/05/2010 31 06/05/2010 32 8 06/05/2010 2. Hàm Bool 2. Hàm Bool Bưc 4: Xác ñnh các ph ti tiu gm các t bào ln. Bưc 5: Xác ñnh các công thc ña thc ti tiu ca f. Nu các t bào ln chn ñưc bưc 3 ñã ph ñưc T các ph ti tiu gm các t bào ln ca kar(f) tìm kar(f) thì ta có duy nht mt ph ti tiu gm các t bào ñưc bưc 4 ta xác ñnh ñưc các công thc ña thc ln ca kar(f). tương ng ca f. Nu các t bào ln chn ñưc bưc 3 chưa ph So sánh các công thc trên: Loi b các công thc ña ñưc kar(f) thì xét mt ô chưa b ph, s có ít nht hai thc mà có mt công thc ña thc nào ñó thc s ñơn t bào ln cha ô này, ta chn mt trong các t bào ln gin hơn chúng. Các công thc ña thc còn li chính là này. C tip tc như th ta s tìm ñưc tt c các ph các công thc ña thc ti tiu ca f. gm các t bào ln ca kar(f). Loi b các ph không ti tiu, ta tìm ñưc tt c các ph ti tiu gm các t bào ln ca kar(f). 06/05/2010 33 06/05/2010 34 2. Hàm Bool 2. Hàm Bool Ví d 1: Tìm tt c các công thc ña thc ti tiu ca Bưc 2: Kar(f) có các t bào ln như sau: hàm Bool x x x x x x x x fxyzt(,,,)= xyzt ++++ xy xz yz xyz () + t z 1 2 t z 2 3 t Ta có: f= xyzt ++++ x y xz yz xyz + xyt z 4 5 t z 5 6 t z 7 8 t z t Bưc 1:V kar(f): x x x x z 9 10 t z t z 1 2 3 t y y y y y y y y z 4 5 6 t z 7 8 t x yt z 9 10 t y y y y 06/05/2010 35 06/05/2010 36 9 06/05/2010 2. Hàm Bool 2. Hàm Bool Bưc 3: Xác ñnh các t bào ln nht thit phi Bưc 4: Xác ñnh các ph ti tiu gm các t bào ln. chn. Các ô ñưc các t bào ln ñã chn bưc 3 ph như sau: – Ô 1 nm trong mt t bào ln duy nht x. Ta x x x x z 1 2 3 t chn x. z 4 5 6 t z 7 8 t – Ô 3 nm trong mt t bào ln duy nht yz. Ta z 9 10 t chn yz. y y y y Ta ñưc duy nht mt ph ti tiu gm các t bào ln ca kar(f): x; yz. 06/05/2010 37 06/05/2010 38 2. Hàm Bool 3. Mng logic (Mng các cng) Bưc 5: Xác ñnh các công thc ña thc ti tiu ca f. ðnh nghĩa ng vi ph ti tiu gm các t bào ln tìm ñưc Mt mng logic hay mt mng các cng là mt bưc 4 ta tìm ñưc duy nht mt công thc ña thc ti h thng có dng: tiu ca f: x1 x f(x 1,x 2,..., x n) f= x + yz 2 xn 06/05/2010 39 06/05/2010 40 10 06/05/2010 3. Mng logic (Mng các cng) 3. Mng logic (Mng các cng) trong ñó: Cng NOT Input: x1, x2,..., xn là các bin Bool. Cng AND Output: f(x 1, x2,..., xn) là hàm Bool. Ta nói mng logic trên tng hp hay biu din hàm Bool f. Cng OR Mt mng logic bt kỳ luôn luôn ñưc cu to t mt s mng sơ cp mà ta gi là các cng 06/05/2010 41 06/05/2010 42 3. Mng logic (Mng các cng) x y x y xy + xy x x y xy OR x x y y xy + xy x xy 06/05/2010 43 11

Các file đính kèm theo tài liệu này:

  • pdfbai_giang_toan_roi_rac_chuong_3_dai_so_bool_ham_bool.pdf
Tài liệu liên quan