BÀI GIẢNG KỸ THUẬT SỐ

Bài giảng kỹ thuật số tất cả 5 chương, nội dung trình bày về hệ thống số đếm, định nghĩa về mật mã, đại số Boole, các bộ phận logic cơ bản, hệ tổ hợp và hệ tuần tự. Đây là tài liệu tham khảo hữu ích cho mình đọc nghiên cứu và học tập chăm ngành Điện tử - Viễn thông.

Bạn đang xem: Bài giảng kỹ thuật số


*

ĐẠI HỌC ĐÀ NẴNG TRƯỜNG ĐẠI HỌC BÁCH KHOA KHOA ĐIỆN TỬ - VIỄN THÔNG ----- oOo ----- BÀI GIẢNG tiên tiến nhất T (Lưu hành nội bộ) U EDET
Đà Nẵng, 2013Ch ng 1. H th ng s m với khái ni m v mã Trang 1Ch ng 1 TH NG S M VÀ KHÁI NI M V MÃ1.1. H TH NG S M1.1.1. H m 1. Khái ni m m là t phường h p các ph ng pháp g i cùng bi u di n những con s b ng các kí hi u có giá tr s ng xác nh g i là các ch s . T 2. Phân lo i bao gồm th chia những h m làm cho hai lo i: h m theo v trí và h m không theo v trí. U a. H m theo v trí: m theo v trí là h m nhưng mà trong ó giá tr s l ng c a ch s còn ph thu c vào v trí c a EDnó ng trong bé s c th . Ví d : H th p. Phân là m t h m theo v trí. S 1991 trong h th p phân c bi u di n b ng2 ch s “1” với “9”, nh ng do v trí ng c a những ch s này trong con s là khác nhau nên s mangcác giá bán tr s l ng khác nhau, ch ng h n ch s “1” v trí sản phẩm n v bi u di n mang lại giá tr s ET ng là 1 song ch s “1” v trí hàng nghìn l i bi u di n mang lại giá tr s l ng là 1000, tuyệt ch s“9” khi mặt hàng ch c bi u di n giá tr là 90 còn khi hàng tr m l i bi u di n mang đến giá tr là 900. B. H m không tuân theo v trí: m không tuân theo v trí là h m nhưng trong ó giá chỉ tr s l ng c a ch s không ph thu c vào
trí c a nó ng trong bé s . M La Mã là m t h m không tuân theo v trí. H m này s d ng các ký t “I”, “V”, “X”... Bi u di n những con s , vào ó “I” bi u di n mang đến giá tr s l ng 1, “V” bi u di n cho giá tr s ng 5, “X” bi u di n cho giá tr s l ng 10... Nhưng mà không ph thu c vào v trí các ch s này ngtrong con s c th . Các h m không tuân theo v trí s không c c p n vào giáo trình này.1.1.2. C s c ah m t s A b t k có th bi u di n b ng hàng sau: A= am-1am-2.....a0a-1......a-n vào ó ai là những ch s , ( i = − n ÷ m − 1 ); i là các hàng s , i nh : mặt hàng tr , i l n: sản phẩm già. Giá tr s l ng c a những ch s ai s nh n m t giá bán tr làm sao ó sao cho th a mãn b t ng th c sau: 0 ≤ ai ≤ N − 1 (ai nguyên) N c g i là c s c a h m. S c am th m là s l ng ký kết t phân bi t cs ng vào m t h m. Các h th ng s m c phân bi t v i nhau b ng m t c s N c a h m ó. M i cam kết t bi u di n m t ch s .Bài gi ng K THU T S Trang 2 vào i s ng h ng ngày họ quen s d ng h m th phường phân (decimal) v i N=10. Vào th ng s còn s d ng nh ng h m không giống là h m nh phân (binary) v i N=2, h m bát phân(octal) v i N=8 và h m th phường l c phân (hexadecimal) v i N=16. - H nh phân : N =2 ⇒ ai = 0, 1. - H th p phân : N =10 ⇒ ai = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. - H bát phân : N =8 ⇒ ai = 0, 1, 2, 3, 4, 5, 6, 7. - H th p l c phân : N =16 ⇒ ai = 0, 1, 2, …8, 9, A, B, C,D, E, F. Lúc ã xu t hi n c s N, ta có th bi u di n s A d i d ng m t a th c theo c s N, c kýhi u là A(N) : A(N) = am-1.Nm-1 + am-2.Nm-2 +...+ a0.N0 + a-1.N-1 + ... + a-n.N-nHay: m −1 A (N) = ∑ a i Ni (1.1) i =− n T i N=10 (h th phường phân): A(10) = am-1.10m-1 + am-2.10m-2 +....+ a0.10 0 +...+ a-n.10 -n U 1999,959(10) =1.103 + 9.102 + 9.101 + 9.100 + 9.10-1 + 5.10-2 + 9.10-3 i N=2 (h nh phân): ED A(2) = am-1.2m-1 + am-2.2m-2 +...+ a0.20 ....+a-n2 -n 1101(2) = 1.23 +1.22 + 0.21 + 1.20 = 13(10) i N=16 (h th phường l c phân): A(16) = am-1.16m-1 + am-2.16m-2 +...+ a0.16 0 + a-116-1 + ... + a-n16-n 3FF(16) = 3.162 + 15.161 + 15.160 = 1023(10) ET i N=8 (h bát phân): A(8) = am-1.8 m-1 + am-2.8m-2 +...+ a0.80 + a-1.8 -1 + ... + a-n.8 -n 376 (8) = 3.82 + 7.81 + 6.80 = 254(10)
Nh v y, bi u th c (1.1) có thể chấp nhận được i những s b t k h làm sao sang h th p phân (h 10).1.1.3. Ic s 1. I t c s d sang trọng c s 10 chuy n i m t s h m c s d sang trọng h m c s 10 ng i ta khai tri n con s trong c d d i d ng a th c theo c s c a nó (theo bi u th c 1.3).Ví d 1.1 i s 1101(2) h nh phân thanh lịch h th p phân nh sau: 1011(2) = 1.23 + 0.22 + 1.21 + 1.20 = 11(10) 2. I t c s 10 sang c s d chuy n i m t s t c s 10 quý phái c s d (d = 2, 8, 16) ng i ta l y con s trong c s 10chia liên ti p cho d n khi th ng s b ng không thì d ng l i. K t qu chuy n i tất cả c trong m c s d là t phường h p những s d c a phép phân tách c vi t theo th t ng c l i, ngh a là s d u tiên tất cả tr ng s nh nh t. (xem ví d 1.2)Ch ng 1. H th ng s m và khái ni m v mã Trang 3Ví d 1.2: 13 2 1 6 2 1023 16 0 3 2 15 63 16 1 1 2 15 3 16 1 0 3 0 A(10)=13 → A(2)=1101 A(10)=1023 → A(16)=3FFH t lu n: G i d1, d2, ..,dn l n l t là d s c a phép phân chia s th p. Phân mang đến c s d l n th 1, 2,3, 4, .., n thì k t qu chuy n i m t s t h m c s 10 (th p phân) thanh lịch h m c s d s là: dndn-1dn-2...d1, Tngh a là d s ở đầu cuối c a phép phân tách là bít có tr ng s cao nh t (MSB), còn d s u tiên là bítcó tr ng s nh nh t (LSB). U trong các ví d trên, c s c a h m c ghi d ng ch s mặt d i. Bên cạnh đó c ng có th ký kết ch phân bi t nh sau: B - H nh phân (Binary) O - H bát phân (Octal) ED D - H th phường phân (Decmal) H - H th p. L c phân (Hexadecimal)Ví d : 1010B có ngh a là 1010 (2) 37FH gồm ngh a là 37F(16)& ET Quy t c chuy n i gi a những h m c s 2, 8, 16 ?1.2. H M NH PHÂN VÀ KHÁI NI M V MÃ1.2.1. H m nh phân
15 1111 17 F ng 1.1. Các t h phường mã nh phân 4 bịt chuy n i gi a những h th ng s m khác biệt gi vai trò quan tr ng trong máy tính xách tay s . 3 4Chúng ta bi t r ng 2 = 8 và 2 = 16, t b ng mã trên có th nh n th y m i ch s trong h chén bát phân ng ng v i m t nhóm ba ch s (3 bít) trong h nh phân, m i ch s trong h th p. L c phân ng ng v i m t team b n ch s (4 bít) trong h nh phân. Vày ó, khi bi u di n s nh phânnhi u bit trên laptop tránh sai sót ng i ta th ng bi u di n trải qua s th p phân ho c th phường c phân ho c bát phân.Ví d 1.3: Xét vi c bi u di n s nh phân 1011111011111110 (2). 1 3 7 3 7 6 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 0 B E F E y, gồm th bi u di n : 137376(8) theo h chén bát phân ho c : BEFE(H) theo h th p l c phân.Ch ng 1. H th ng s m với khái ni m v mã Trang 5& V i s nh phân n bít gồm bao nhiêu t h p. Nh phân không giống nhau? Xét tr ng h p. S nhphân 8 đậy (n=8) a7a6a 5a4a 3a2a 1a0 bao gồm bao nhiêu t h phường nh phân (t mã nh phân) khác nhau? 2. Những phép tính bên trên s nh phân a. Phép c ng c ng nhị s nh phân, ng i ta d a trên qui t c c ng nh sau: 0 + 0 = 0 nh 0 0 + 1 = 1 nh 0 1 + 0 = 1 nh 0 1 + 1 = 0 nh 1Ví d 1.4: + 3 → + 0011 2 → 0010 T 5 → 0101 = 1.22 + 1.20 = 5 (10) b. Phép tr U 0-0 = 0 m n 0 0-1 = 1 m n 1 ED 1-0 = 1 m n 0 đơn = 0 m n 0Ví d 1.5: - 7 → - 0111 → 0101 ET 5 2 → 0010 = 0.23 + 0.22 + 1.21 + 0.20 = 2(10) c. Phép nhân 0.0 = 0
0.1 = 0 1.0 = 0 1.1 = 1Ví d 1.6: x 7 → 0111 x 5 → 0101 35 0111 0000 0111 0000 0100011 = 1.25 + 1.21 + 1.20 = 35(10) d. Phép phân chia 0: 1 = 0 1: 1 = 1 u ý: Khi phân tách s phân tách ph i khác 0Bài gi ng K THU T S Trang 6Ví d 1.7: 10 5 → 1010 101 2 101 10(2) = 2(10) 00 0 ng d ng thanh ghi d ch th c hi n phép toán nhân hai, phân chia hai: 0 0 0 0 0 0 1 1 1 0 0 Thanh ghi sau thời điểm d ch trái 1 bít ch trái 1 bít ↔ nhân 2 0 0 0 0 0 0 1 1 1 Thanh ghi ban u Thanh ghi sau thời điểm d ch ph i 1 che 0 0 0 0 0 0 0 0 1 1 1 ch ph i 1 bịt ↔ chia 2 T Hình 1.1. Ng d ng thanh ghi d ch th c hi n phép toán nhân và phân tách 21.2.2. Khái ni m v mã U ED 1. Ic ng trong i s ng hàng ngày, bé ng i giao ti p v i nhau thông qua m t h th ng ngôn ng qui c, nh ng trong máy vi tính và những h th ng s ch x lý những d li u nh phân. Vày ó, m t v n t ETra là có tác dụng th nào t o ra m t giao di n d dàng gi a ng i với máy tính, ngh a là máy tính xách tay th c hi n c nh ng vấn đề do nhỏ ng i t ra. Do các máy tính s hi n ni ch hi u các s 0 với s 1, đề nghị b t k thông tin nào d i d ng những ch , ch loại ho c những ký t ph i c bi n i thành d ng s nh phân tr c lúc nó có th cx
lý b ng những m ch s . Th c hi n u ó, ng i ta t ra v n v mã hóa d li u. Nh v y, mã hóa là thừa trìnhbi n i nh ng cam kết hi u quen thuộc thu c c a bé ng i lịch sự nh ng ký hi u quen thu c v i vật dụng tính.Nh ng s li u ã mã hóa này c nh p. Vào lắp thêm tính, trang bị tính thống kê giám sát x lý với sau ó sản phẩm công nghệ tínhth c hi n quá trình ng c l i là gi i mã chuy n i những bít thông tin nh phân thành các ký kết hi uquen thu c v i bé ng i mà bé ng i có th hi u c. Các l nh v c mã hóa bao g m: - Mã hóa s th phường phân - Mã hóa ký kết t - Mã hóa t phường l nh - Mã hóa ti ng nói - Mã hóa hình nh ..v..v.. Ph n ti p theo bọn họ kh o ngay cạnh l nh v c mã hóa n gi n nh t là mã hóa s th p phân b ngcách s d ng các t mã nh phân. Vi c mã hóa cam kết t , t p. L nh, ti ng nói, hình nh... U d a trên c mã hóa s th p. Phân.Ch ng 1. H th ng s m và khái ni m v mã Trang 7 2. Mã hóa s th phường phân a. Khái ni m trong th c t mã hóa s th phường phân ng i ta s d ng các s nh phân 4 bit (a3a2a1a0) theo quy c sau: 0 → 0000 ; 5 → 0101 1 → 0001 ; 6 → 0110 2 → 0010 ; 7 → 0101 3 → 0011 ; 8 → 1000 4 → 0100 ; 9 → 1001 các s nh phân cần sử dụng mã hóa những s th phường phân c g i là các s BCD (Binary CodedDecimal: S th p. Phân c mã hóa b ng s nh phân). B. Phân lo i lúc s d ng s nh phân 4 bit mã hóa những s th phường phân t ng ng v i 2 4 = 16 t h p mã nh Tphân phân bi t. Vì vi c ch n 10 t h phường trong 16 t h p mã hóa những ký hi u th phường phân t 0 n 9 nhưng trong Uth c t xu t hi n nhi u lo i mã BCD khác nhau. C cho dù t n t i nhi u lo i mã BCD không giống nhau, nh ng tất cả th chia làm hai lo i chính: Mã BCD tất cả EDtr ng s và mã BCD không có tr ng s . B1. Mã BCD gồm tr ng s là lo i mã có thể chấp nhận được phân tích thành a th c theo tr ng s c a nó. MãBCD gồm tr ng s c chia làm 2 lo i là: mã BCD t nhiên và mã BCD s h c. Mã BCD t nhiên là lo i mã nhưng mà trong ó các tr ng s th ng c s phường x p theo th t t ng ET n. Ví d : Mã BCD 8421, BCD 5421. Mã BCD s h c là lo i mã nhưng mà trong ó gồm t ng các tr ng s luôn luôn b ng 9.Ví d : BCD 2421, BCD 5121, BCD8 4-2-1 c tr ng c a mã BCD s h c là bao gồm tính ch t i x ng qua m t ng trung gian. Bởi
y, tra cứu t mã BCD c a m t s th phường phân như thế nào ó ta l y bù ( o) t mã BCD c a s bù 9 ng ng. Ví d xét mã BCD 2421. ây là mã BCD s h c (t ng những tr ng s b ng 9), trong ó s 3 (th p phân) có t mã là 0011, s 6 (th phường phân) là bù 9 c a 3. Bởi vì v y, tất cả th suy ra t mã c a 6 ng bí quyết l y bù t mã c a 3, ngh a là l y bù 0011, ta s tất cả t mã c a 6 là 1100. B2. Mã BCD không tồn tại tr ng s là lo i mã không có thể chấp nhận được phân tích thành a th c theo tr ng c a nó. Các mã BCD không có tr ng s là: Mã Gray, Mã Gray th a 3. C tr ng c a mã Gray là b mã trong ó hai t mã nh phân ng k ti phường nhau bao gi c ng chkhác nhau 1 bit. Ví d : Mã Gray: 2 → 0011 Còn v i mã BCD 8421: 3 → 0010 3 → 0011 4 → 0110 4 → 0100Các b ng d i ây trình bày m t s lo i mã thông d ng.Bài gi ng K THU T S Trang 8 ng 1.2: những mã BCD t nhiên. BCD 8421 BCD 5421 BCD vượt 3 th phường a3 a2 a1 a0 b 3 b2 b 1 b0 c3 c2 c1 c0 phân 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 0 0 0 1 0 1 0 0 1 0 0 1 0 0 0 1 0 0 1 0 1 2 0 0 1 1 0 0 1 1 0 1 1 0 3 0 1 0 0 0 1 0 0 0 1 1 1 4 0 1 0 1 1 0 0 0 1 0 0 0 5 0 1 1 0 1 0 0 1 1 0 0 1 6 0 1 1 1 1 0 1 0 1 0 1 0 7 1 0 0 0 1 0 1 1 1 0 1 1 8 1 0 0 1 1 1 0 0 1 1 0 0 9 T ng 1.3: những mã BCD s h c U BCD 2421 BCD 5121 BCD 84-2-1 th phường a3 a2 a1 a0 b3 b2 b 1 b0 c3 c2 c1 c0 phân ED 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 1 1 1 1 0 0 1 0 0 0 1 0 0 1 1 0 2 0 0 1 1 0 0 1 1 0 1 0 1 3 0 1 0 0 0 1 1 1 0 1 0 0 4 ET 1 0 1 1 1 0 0 0 1 0 1 1 5 1 1 0 0 1 1 0 0 1 0 1 0 6 1 1 0 1 1 1 0 1 1 0 0 1 7 1 1 1 0 1 1 1 0 1 0 0 0 8
1 1 1 1 1 1 1 1 1 1 1 1 9 ng 1.4: BCD t nhiên với mã Gray. BCD 8421 BCD thừa 3 Mã Gray Gray thừa 3 th p a3 a2 a1 a0 c3 c2 c1 c0 G3 G2 G1 G0 g3 g2 g1 g0 phân 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 1 1 0 1 0 0 1 0 0 1 0 1 0 0 1 1 0 1 1 1 2 0 0 1 1 0 1 1 0 0 0 1 0 0 1 0 1 3 0 1 0 0 0 1 1 1 0 1 1 0 0 1 0 0 4 0 1 0 1 1 0 0 0 0 1 1 1 1 1 0 0 5 0 1 1 0 1 0 0 1 0 1 0 1 1 1 0 1 6 0 1 1 1 1 0 1 0 0 1 0 0 1 1 1 1 7 1 0 0 0 1 0 1 1 1 1 0 0 1 1 1 0 8 1 0 0 1 1 1 0 0 1 1 0 1 1 0 1 0 9Ch ng 1. H th ng s m cùng khái ni m v mã Trang 9Chú ý: Mã Gray c suy ra t mã BCD 8421 b ng cách: những bit 0,1 ng sau bit 0 ( mãBCD 8421) lúc chuy n sang mã Gray c gi nguyên, còn các bit 0,1 ng sau bit 1 ( mã BCD8421) lúc chuy n sang mã Gray thì o bít, ngh a là t bit 1 thành bit 0 cùng bit 0 thành bit 1. 3. M ch nh n d ng s BCD 8421: a3 ch nh n d ng y a2 BCD 8421 a1 ch nh n d ng s BCD 8421 nh n tín hi u vào là các bít a3, a2, a1 c a s nh phân 4 bíta3a2a1a0, u ra y c quy nh nh sau: - N u y = 1 thìa3a2a1a0 ko ph i s BCD 8421 - N u y = 0 thìa3a2a1a0 là s BCD 8421 T Nh v y, n u m t s nh phân 4 bit ko ph i là m t s BCD 8421 thì ngõ ra y = 1. T b ng1.1 ta th y m t s nh phân 4 bịt không ph i là s BCD 8421 khi bịt a3 luôn luôn luôn b ng 1 với (bit a1 U ng 1 ho c bịt a 2 b ng 1). Suy ra ph ng trình ngắn gọn xúc tích c a ngõ ra y: y = a3(a1 + a2) = a3a1 + a3a2 ED logic: a1 a1 y a3 a2 y ET a3 a2 ng vì chưng vi c xu t hi n s BCD nên có hai giải pháp nh p. D li u vào máy tính: nh p. S nh phân,nh p. B ng mã BCD.
nh p s BCD th p phân nhị ch s thì laptop chia s th p chia thành các những và m i những c bi u di n b ng s BCD t ng ng. Ch ng h n: 11(10) gồm th c nh p. Vào máy tínhtheo 2 cách: - S nh phân : 1011 - Mã BCD : 0001 0001 4. Những phép tính bên trên s BCD a. Phép c ng bởi vì s BCD ch tất cả t 0 n 9 bắt buộc i v i nh ng s th phường phân l n h n s chia s th phường phân thànhnhi u các, m i các c bi u di n b ng s BCD t ng ng.Ví d 1.8 C ng 2 s BCD m t các: 5 → 0101 7 → 0111 + + + + 3 → 0011 5 → 0101 8 1000 12 + 1100 0110 hi u ch nh 0001 0010Bài gi ng K THU T S Trang 10 gồm hai tr ng h phường ph i hi u ch nh k t qu c a phép c ng 2 s BCD 8421: - lúc k t qu c a phép c ng là m t s ko ph i là s BCD 8421 - khi k t qu c a phép c ng là m t s BCD 8421 nh ng l i xu t hi n s nh b ng 1. Vi c hi u ch nh c th c hi n b ng cách c ng k t qu v i s hi u ch nh là 6 (0110 2). Ví d 1.8 ã để mắt tới tr ng h p hi u ch nh khi k t qu ko ph i là m t s BCD 8421.Tr ng h phường hi u ch nh lúc k t qu là m t s BCD 8421 nh ng phép c ng l i xu t hi n s nh b ng1 c chu đáo trong ví d sau ây:Ví d 1.9 Hi u ch nh k t qu c ng 2 s BCD m t những khi xu t hi n s nh b ng 1: 8 → 1000 t qu là s BCD 8421 nh ng + + 9 → 1001 i xu t hi n s nh b ng 1 17 1 0001 0110 T hi u ch nh (6) 0001 0111 U t qu sau khi hi u ch nh là 17 ED b. Phép tr Phép toán tr 2 s BCD c th c hi n theo quy t c sau ây: A-B =A+ B trong ó B là s bù 2 c a B. ETVí d 1.10 Th c hi n tr 2 s BCD m t các: - 7 → - 0111 0111 + Bù 1 c a 5 5 → 0101 1010
2 0010 1 0001 + 1 ng 1 LSB bao gồm bù 2 c a 5 i s nh 0010 t qu cu i thuộc u ý: - Bù 1 c a m t s nh phân là l y o t t c các bít c a s ó (bit 0 thành 1, bit 1 thành 0). - Bù 2 c a m t s nh phân b ng s bù 1 c ng thêm một vào đậy LSB.Xét các tr ng h p. M r ng sau ây: 1. Th c hi n tr 2 s BCD 1 các mà s b tr nh h n s tr ? 2. M r ng mang đến c ng cùng tr 2 s BCD nhi u những ?Ch ng 2. I s BOOLE Trang 11Ch ng 2 IS BOOLE2.1. CÁC TIÊN VÀ NH LÝ IS BOOLE trong những m ch s , các tín hi u th ng c mang lại 2 m c n áp, ví d : 0V và 5V. Nh ng linhki n n t dùng trong m ch s làm cho vi c m t trong hai tr ng thái, ví d Transistor l ng c c(BJT) có tác dụng vi c nhị ch là t t ho c d n bão hoà… vì v y, tế bào t các m ch s ng i ta cần sử dụng nh phân (binary), hai tr ng thái c a các linh ki n vào m ch s c mã hoá t ng ng là 0ho c 1. T b môn i s vạc tri n t cu i th k 19 sở hữu tên ng i sáng l phường ra nó: i s Boole, còn c g i là i s logic, say đắm h phường cho vi c mô t m ch s . I s Boole là công c toán h c quan tiền Ttr ng phân tích và thi t k các m ch s , c cần sử dụng làm chìa khoá i sâu vào m i l nh v c liênquan n k thu t s .2.1.1. Những tiên c a U i s Boole ED đến m t t p h p. B h u h n trong ó ta trang b những phép toán + (c ng logic), x (nhân logic), -(bù logic/ngh ch o logic) với hai ph n t 0 cùng 1 l phường 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ới th a mãn 5 tiên sau: 1. Tiên giao hoán ET ∀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 nhì ph n t trung hòa - nhân chính là ph n t n v với ph n t không. Ph n t nvký hi u là 1, ph n t không ký kết hi u là 0. ∀x ∈ B: x+1= 1 x. 1= x x+0= x x. 0= 0 5. Tiên v ph n t bù ∀x ∈ B, bao gi c ng t n t i ph n t bù t ng ng, ký kết hi u x , làm thế nào cho luôn th a mãn: x + x = 1 và x. X = 0Bài gi ng NT S 1 Trang 12 u B = B* = 0,1 (B* ch g m 2 ph n t 0 với 1) và th a mãn 5 tiên bên trên thì c ng l p thành u trúc i s Boole nh ng là c u trúc i s Boole nh nh t.2.1.2. Những nh lý c b n c a i s Boole 1. V n i ng u vào i s Boole hai m nh (hai bi u th c, nhì nh lý) c g i là i ng u v i nhau n u vào m nh nàyng i ta cố gắng phép toán c ng thành phép toán nhân và ng c l i, vắt 0 b ng 1 cùng ng c l i, thì ssuy ra c m nh kia. Khi hai m nh i ng u v i nhau, n u 1 trong các 2 m nh c ch ng minh là úng thì m nh còn l i là úng. D i ây là ví d v các c p. M nh i ng u v i nhau.Ví d 2.1: x.(y+z) = (x.y) + (x.z) nhì m nh này là i ng u x + (y.z) = (x+y).(x+z)Ví d 2.2: x +x = 1 nhị m nh này là i ng u x. X = 0 T 2. Các nh lý a. Nh lí 1 ( nh lý v ph n t ∀x, y ∈ B, ta có: U bù là duy nh t) ED x + y = 1 ⇒ y= x là duy nh t (x và y là 2 ph n t bù c a nhau) x.y = 0  Ph n t bù c a m t ph n t b t k là duy nh t. ET b. Nh lí 2 ( lý v s ng nh t c a phép c ng với 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 nhì l n) ∀x ∈ B, ta có: x =x d. Nh lí 4 ( nh lý De Morgan) ∀x, y, z ∈ B, ta có: x + y + z = x. Y.z x.y.z = x + y + z qu : ∀x, y, z ∈ B, ta có: x + y + z = x + y + z = x.y.z x. Y. Z = x.y.z = x + y + z e. Nh lí 5 ( nh lý dán) ∀x, y ∈ B, ta có: x. ( x + y) = x.y x + ( x .y) = x + yCh ng 2. I s BOOLE Trang 13 f. Nh lí 6 ( nh lý nu t) ∀x, y ∈ B, ta có: x + x. Y = x x.(x + y) = x g. Nh lí 7 (Quy t c tính i v i h ng) i 0, 1 ∈ B, ta có: 0 =1 1 =02.2. HÀM BOOLE VÀ CÁC PH NG PHÁP BI U DI N2.2.1. Hàm Boole 1. Nh ngh a T 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ácbi n Boole thì hàm Boole, ký hi u là f, c ra đời trên c s liên k t các bi n Boole b ng các Uphé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 mang lại nh sau: ED f(x) = x, f(x) = x , f(x) = α (α là h ng s ) vào tr ng h p. T ng quát, ta bao gồm hàm Boole theo n bi n Boole c cam kết hi u nh sau: f(x1, x2, ...., xn) 2. Những tính ch t c a hàm Boole ET u f(x1, x2, ...., xn) là m t hàm Boole thì: - α.f(x1, x2, ...., xn) c ng là m t hàm Boole. - f (x1, x2, ...., xn) c ng là m t hàm Boole.
u f1(x1, x2, ...., xn) với f2(x1, x2, ...., xn) là nh ng hàm Boole thì: - f1(x1, x2, ...., xn) + f2(x1, x2, ...., xn) c ng là m t hàm Boole. - f1(x1, x2, ...., xn).f2(x1, x2, ...., xn) c ng là m t hàm Boole. Y, m t hàm Boole f c ng c sinh ra trên c s liên k t các hàm Boole b ng cácphép toán + (c ng logic), x (.) (nhân logic) ho c ngh ch o xúc tích (-). 3. Giá chỉ tr c a hàm Boole Gi s f(x1, x2, ...., xn) là m t hàm Boole theo n bi n Boole. Vào f ng i ta thay những bi n xi b ng các giá tr c th αi ( i = 1, n ) 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(x1, x2 ) = x1 + x2 Xét trong t p B = B* =0,1 ta có các tr ng h phường sau (l u ý ây là phép ng xúc tích và ngắn gọn hay còn g iphép toán HO C / phép OR): - x1 = 0, x2 = 0 → f(0,0) = 0 + 0 = 0Bài gi ng NT S 1 Trang 14 - x1 = 0, x2 = 1 → f(0,1) = 0 + 1 = 1 x1 x2 f(x1, x2) = x1+ x2 - x1 = 1, x2 = 0 → f(1,0) = 1 + 0 = 1 0 0 0 - x1 = 1, x2 = 1 → f(1,1) = 1 + 1 = 1 0 1 1 Ta l p c b ng giá chỉ tr c a hàm trên. 1 0 1 1 1 1Ví d 2.4: Xét hàm cho b i bi u th c sau: f(x1, x2, x3) = x1 + x2.x3 Xét t phường B = B* = 0,1. Hoàn toàn t ng t ta l p c b ng giá bán tr c a hàm: x1 x2 x3 f (x1, x2, x3) = x1 + x2.x3 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 1 T 1 0 1 1 1 1 0 1 1 1 U 1 1 ED2.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á bán tr ây là ph ng pháp th ng dùng bi u di n hàm s nói thông thường và c ng c s d ng bi u ETdi n các hàm logic. Ph ng pháp này g m m t b ng c chia thành hai ph n: - M t ph n dành riêng cho bi n ghi những t h phường giá tr gồm th bao gồm c a bi n vào. - M t ph n giành riêng cho hàm ghi những giá tr c a hàm ra t ng ng v i những t h p. Bi n vào. B ng giá chỉ tr còn c g i là b ng chân tr tuyệt b ng đạo 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. - 2n hàng: 2n giá bán tr không giống nhau c a t h phường n bi n.Ví d 2.5: Hàm 3 bi n f(x1, x2, x3) gồm th c đến b ng b ng giá chỉ tr nh sau: x1 x2 x3 f (x1, x2, x3) 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 trong số ví d 2.3 với 2.4 chúng ta c ng ã quen thuộc thu c v i ph ng pháp bi u di n hàm b ng ng giá chỉ tr .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 ngắn gọn xúc tích b ng những bi u th c i s . Ph ng pháp này còn có 2 d ng: ng c a những tích s ho c tích c a các t ng s . Ng t ng c a những tích s g i là d ng chủ yếu t c th nh t (D ng thiết yếu t c 1 – CT1). Ng tích c a các t ng s g i là d ng chủ yếu t c th nhì (D ng bao gồm t c 2 – CT2). Hai d ng bao gồm t c này là i ng u nhau. Ng t ng các tích s còn g i là d ng chu n t c tuy n (CTT), d ng tích những t ng s còn g i là ng chu n t c h i (CTH). A. D ng thiết yếu t c 1(D ng t ng c a những tích s ) Xét các hàm Boole m t bi n n gi n: f(x) = x, f(x) = x , f(x) = α (α là h ng s ). ây là nh ng tr ng h p có th tất cả i v i hàm Boole 1 bi n. Chúng ta s i ch ng minh bi u th c t ng quát c a hàm xúc tích 1 bi n s i v i d ng bao gồm t c 1.Sau ó áp d ng bi u th c t ng quát c a hàm 1 bi n search bi u th c t ng quát lác c a hàm 2 bi n v ivi c xem 1 bi n là h ng s . Cu i cùng, họ suy ra bi u th c t ng quát tháo c a hàm logic n bi n cho Ttr ng h phường d ng bao gồm t c 1 (t ng các tích s ).Xét f(x) = x: Ta có: t khác: x =0. X + 1.x U ED f (1) = 1 f (x ) = x ⇒  f (0) = 0 Suy ra: f(x) = x bao gồm th bi u di n: f(x) = x = f(0). X + f (1).x ET vào ó: f (0), f (1) c g i là những 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 (1) = 0 f (x ) = x ⇒  f (0 ) = 1 Suy ra: f(x) = x tất cả th bi u di n: f(x) = x = f(0). X + f(1).xXét f(x) = α (α là h ng s ): Ta có: α = α.1 = α.(x + x ) = α. X + α.x t khác: f (1) = f (x ) = ⇒  f (0 ) = Suy ra f(x) = α tất cả th bi u di n: f(x) = α = f(0). X + f(1).x t lu n: dù f(x) = x, f(x) = x xuất xắc f(x) = α, ta u tất cả bi u th c t ng quát lác c a hàm m t bi n vi ttheo d ng chủ yếu t c th nh t nh sau:Bài gi ng NT S 1 Trang 16 f(x) = f(0). X + f(1).x y f(x) = f(0). X + f(1).x, vào ó 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 lác c a hàm 1 bi n vi t ng chủ yếu t c th nh t (d ng t ng c a các tích).Bi u th c t ng quát mắng c a hàm hai bi n f(x1, x2): Bi u th c t ng quát tháo 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êncách bi u di n c a d ng bao gồm t c th nh t c a hàm 1 bi n, trong ó coi m t bi n là h ng s . Th là: n u xem x2 là h ng s , x1 là bi n s cùng áp d ng bi u th c t ng quát c a d ng chính t cth nh t cho hàm 1 bi n, ta có: f(x1,x2) = f(0,x2). X 1 + f(1,x2).x1 Bây gi , các hàm f(0,x2) và f(1,x2) tr thành các hàm 1 bi n s theo x2. Ti p t c áp d ng bi uth c t ng quát lác c a d ng chính t c th nh t mang đến hàm 1 bi 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 T Suy ra: U f(x1,x2) = f(0,0). X 1 x 2 + f(0,1). X 1x2 + f(1,0).x1 x 2 + f(1,1).x1 x2 ây đó là bi u th c t ng quát c a d ng bao gồm t c th nh t (d ng t ng c a những tích s ) vi t mang lại EDhàm Boole nhì bi n s f(x1,x2). Bi u th c t ng quát này có th bi u di n b ng công th c sau: 22 −1 f(x1,x2) = ∑ f( 1 , )x1 1 x 2 2 ET 2 e =0 vào ó e là s th phường phân t ng ng v i mã nh phân (α1,α2) và: x1 n u α1 = 1 x1 1 =
x 1 n u α1 = 0 x2 n u α2 = 1 x2 = 2 x2 n u α2 = 0Bi u th c t ng quát đến hàm Boole n bi n: T bi u th c t ng quát vi t d ng bao gồm t c th nh t c a hàm Boole 2 bi n, ta tất cả th t ng quáthoá đến hàm Boole n bi n f(x1,x2, ..,xn) nh sau: 2n −1 f(x1,x2, ..,xn) = ∑ f( 1 , 2 ,...., n )x 1 1 x 2 2 ...x n n e =0trong ó e là s th p. Phân t ng ng v i mã nh phân (α1,α2, ...,αn);và: xi n u αi = 1 xi i = xi n u αi = 0 (v i i = 1, 2, 3,…,n)Ch ng 2. I s BOOLE Trang 17Ví d 2.6: Vi t bi u th c c a hàm 3 bi n theo d ng bao gồm t c 1: 2 3 −1 f(x1,x2,x3) = ∑ f (α1,α2,α3).x1α1.x2α2.x3 α3 e =0 ng d i ây mang đến ta giá tr c a s th p. Phân e với 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 3 0 1 1 4 1 0 0 5 1 0 1 6 1 1 0 7 1 1 1 T Bi u th c c a hàm 3 bi n vi t theo d ng t ng những tích nh sau: f(x1, x2, x3) = f(0,0,0) x 1 x 2 x 3 + f(0,0,1) x 1 x 2 x3 U + 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 + f(1,0,1)x1 x 2 x3 + f(1,1,0) x1 x2 x 3 + f(1,1,1) x1 x2 x3 ED y d ng thiết yếu t c th nh t là d ng t ng c a các tích s nhưng trong m i tích s ch a y những bi n Boole d i d ng th t ho c d ng bù (ngh ch o). B. D ng chính t c 2 (tích c a những t ng s ): ET ng thiết yếu t c 2 là d ng i ng u c a d ng bao gồm t c 1 đề xuất bi u th c t ng quát lác c a d ngchính t c 2 mang đến n bi n c vi t nh sau: 2n −1
f(x1, x2, ..., xn) = ∏ e =0trong ó e là s th p phân t ng ng v i mã nh phân (α1,α2, ...,αn);và: xi n u αi = 1 xi i = xi 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 những t ng s (d ng chính t c 2) c vi tnh sau: f(x1,x2)=Ví d 2.8: Bi u th c c a hàm Boole 3 bi n d ng chủ yếu t c 2: f(x1,x2,x3) = .. .

Xem thêm:

. .. .Bài gi ng NT S 1 Trang 18 y, d ng thiết yếu t c th nhì là d ng tích c a các t ng s nhưng mà trong ó m i t ng s nàych 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(x1,x2) d ng bao gồm t c 1, v i b ng giá tr a hàm c đến nh sau: x1 x2 f(x1,x2) 0 0 0 0 1 1 1 0 1 1 1 1 Vi t d i d ng chủ yếu t 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 T = x 1.x2 + x1. X 2 + x1.x2Nh n xét: • U ng chính t c th nh t, t ng c a các tích s , là d ng li t kê t t c các t h p. Nh ED phân các bi n vào làm sao để cho t ng ng v i nh ng t h p. ó giá chỉ tr c a hàm ra b ng 1 → ch c n li t kê nh ng t h p bi n khiến cho giá tr hàm 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 (xi), n u bi n t ng ng ng 0 c vi t d ng bù ( x i). ETVí d 2.10: Vi t bi u th c bi u di n hàm f(x1,x2,x3) d ng chủ yếu t c 2 v i b ng giá bán tr c a hàm ra c mang đến
nh sau: x3 x2 x1 f(x1,x2,x3) 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 thiết yếu t c 2 (tích những t ng s ): 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 ng 2. I s BOOLE Trang 19 Áp d ng tiên v ph n t trung hòa 0 cùng 1 ta có: x + 1 = 1, x. 1= x x + 0 = x, x. 0= 0 yêu cầu suy ra bi u th c trên bao gồm th vi t g n l i: f(x1,x2,x3) = (x1+x2+x3).(x1+x2+ x 3).(x1+ x 2+x3)Nh n xét: • ng chủ yếu t c th nhì là d ng li t kê t t c những t h phường nh phân những bi n vào làm sao để cho ng ng v i nh ng t h phường ó giá chỉ tr c a hàm ra b ng 0 → ch c n li t kê nh ng t phường bi n khiến cho giá tr hàm 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 (xi), n u bi n t ng ng ng 1 c vi t d ng bù ( x i). Ví d n gi n sau góp SV hi u rõ h n v phương pháp thành l phường b ng giá tr c a hàm, tìm kiếm hàm m chvà thi t k m ch.Ví d 2.11 T Hãy thi t k m ch n làm thế nào 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 ED u tiên, ta qui nh tr ng thái c a các công t c với 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 tế bào t ho t ng c a m ch nh sau: ET Công t c 1 Công t c 2 Tr ng thái èn x1 x2 f(x1,x2) 0 0 0
0 1 1 1 0 1 1 1 1 b ng tr ng thái bao gồm th vi t bi u th c c a hàm f(x1,x2) theo d ng chính t c 1 ho c thiết yếu t c 2. - Theo d ng bao gồm t 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 ng thiết yếu t c 2 ta có: f(x1, x2) = (0+x1+x2) = x1 + x2 T bi u th c tế bào t tr ng thái /t t c a èn f(x1,x2) th y r ng bao gồm th th c hi n m ch b ng ph n ngắn gọn xúc tích HO C bao gồm 2 ngõ vào (c ng OR 2 ngõ vào).Bài t phường áp d ng: M t h i ng giám kh o g m 3 thành viên. M i thành viên tất cả th l a ch n NG Ý ho c KHÔNG NG Ý. K t qu g i là T khi a s những thành viên trong h i nggiám kh o NG Ý, ng c l i là KHÔNG T. Hãy thi t k m ch gi i quy t câu hỏi trên.