GIÁO TRÌNH LÝ THUYẾT & BÀI TẬP KỸ THUẬT SỐ

Chia sẻ: Nguyen Nhi | Ngày: | Loại File: PDF | Số trang:163

Thêm vào BST

Báo xấu

241
lượt xem 82
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Hệ đếm là tập hợp các phương pháp gọi và biểu diễn các con số bằng các kí hiệu có giá trị số lượng xác định gọi là chữ số. 1.1.1.2. Phân loại Chia làm hai loại: a. Hệ đếm theo vị trí: Là hệ đếm mà trong đó giá trị số lượng của chữ số còn phụ thuộc vào vị trí của nó đứng trong con số. Ví du: 1991 (Hệ thập phân) 1111 (Hệ nhị phân)

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: GIÁO TRÌNH LÝ THUYẾT & BÀI TẬP KỸ THUẬT SỐ

Chæång 1. Hãû thäúng säú âãúm vaì khaïi niãûm vãö maî Trang 1 Chæång 1 HÃÛ THÄÚNG SÄÚ ÂÃÚM VAÌ KHAÏI NIÃÛM VÃÖ MAÎ 1.1. HÃÛ THÄÚNG SÄÚ ÂÃÚM 1.1.1. Hãû âãúm 1.1.1.1. Khaïi niãûm Hãû âãúm laì táûp håüp caïc phæång phaïp goüi vaì biãøu diãùn caïc con säú bàòng caïc kê hiãûu coï giaï trë säú læåüng xaïc âënh goüi laì chæî säú. 1.1.1.2. Phán loaûi Chia laìm hai loaûi: a. Hãû âãúm theo vë trê: Laì hãû âãúm maì trong âoï giaï trë säú læåüng cuía chæî säú coìn phuû thuäüc vaìo vë trê cuía noï âæïng trong con säú. Vê duû: 1991 (Hãû tháûp phán) 1111 (Hãû nhë phán) b. Hãû âãúm khäng theo vë trê: Laì hãû âãúm maì trong âoï giaï trë säú læåüng cuía chæî säú khäng phuû thuäüc vaìo vë trê cuía noï tæång æïng (âæïng) trong con säú. Vê duû: Hãû âãúm La maî I, II, III . . . . . 1.1.2. Cå säú cuía hãû âãúm Mäüt säú A báút kyì coï thãø biãøu diãùn bàòng daîy sau: A= am-1am-2. . . . .a0a-1 . . . . . . . . .a-n Trong âoï: ai ( i = − n ÷ m − 1 ) laì caïc chæî säú; i: caïc haìng säú, i nhoí: haìng treí, i låïn: haìng giaì. Giaï trë säú læåüng cuía caïc chæî säú ai seî nháûn mäüt giaï trë naìo âoï cuía con säú N sao cho thoía maîn báút âàóng thæïc sau: 0 ≤ ai ≤ N −1 Vaì ai nguyãn, thç N âæåüc goüi laì cå säú cuía hãû âãúm.
Baìi giaíng Kyî Thuáût Säú Trang 2 Vê duû: N =10 ⇒ ai = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. N =8 ⇒ ai = 0, 1, 2, 3, 4, 5, 6, 7. N =16 ⇒ ai = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C,D, E, F. N =2 ⇒ ai = 0, 1. Khi âaî xuáút hiãûn cå säú N, ta coï thãø biãøu diãùn säú A dæåïi daûng mäüt âa thæïc theo cå säú N, kyï hiãûu laì A(N) : A(N) = am-1 .Nm-1 + am-2 .Nm-2 +. . ..+ a0 .N0 + a-1 .N-1 + . . + a-n .N-n Hay: m −1 A (N) = ∑ a i N i i =−n Våïi N=10: A(10) = am-1 .10m-1 + am-1 .10m-1 +. . . . .+ a0 .100 +. . .+ a-n .10-n 1999,999 =1.103 +9.102 +9.101 +9.10-1 +9.10-2 +9.10-3 Vê duû: Våïi N=2: A(2) =am-1.2m-1 + . . .+a-n2-n Vê duû: 1111.110 = 1.23 +1.22 + 1.21 + 1.20 + 1.2-1 + 1.2-2 + 0.2-3 Våïi N=16: A(16) = am-1.16m-1 + am-216m-2 +. . .+ a0.160 +..+a-116-1 +. . .+ a-n16-n Vê duû: 3FFH = 3.162 + 15.161 + 15.160 1.1.3. Âäøi cå säú 1.1.3.1. Âäøi tæì cå säú d sang cå säú 10 Vãö phæång phaïp, ngæåìi ta khai triãøn con säú trong cå säú d dæåïi daûng âa thæïc theo cå säú cuía noï. Vê duû: A(2) = 1101, âäøi sang tháûp phán laì: 1101(2) = 1.23 + 1.22 + 0.21 + 1.20 =13(10) 1.1.3.2. Âäøi cå säú 10 sang cå säú d Vãö nguyãn tàõc, ngæåìi ta láúy con säú trong cå säú chia liãn tiãúp cho cå säú d âãún khi thæång säú bàòng khäng thç thäi.
Chæång 1. Hãû thäúng säú âãúm vaì khaïi niãûm vãö maî Trang 3 Vê duû: 13 2 1023 16 2 1 6 15 63 16 3 2 0 15 3 16 2 1 1 30 0 1 A(10)=13 → A(2)=1101 A(10)=1023 → A(16)=3FFH Kãút luáûn: Goüi d1, d2, . . . . ..,dn láön læåüt laì dæ säú cuía pheïp chia säú tháûp phán cho cå säú d láön thæï 1, 2, 3, 4, . . . . ., n thç kãút quaí seî laì dndn-1dn-2 .. d1, nghéa laì dæ säú sau cuìng laì bêt coï troüng säú cao nháút (MSB), coìn dæ säú âáöu tiãn laì bêt coï troüng säú nhoí nháút (LSB). 1.2. HÃÛ ÂÃÚM NHË PHÁN VAÌ KHAÏI NIÃÛM VÃÖ MAÎ 1.2.1. Hãû âãúm nhë phán 1.2.1.1. Khaïi niãûm Hãû âãúm nhë phán coìn goüi laì hãû âãúm cå säú 2 laì hãû âãúm maì trong âoï ngæåìi ta chè sæí duûng hai kê hiãûu 0 vaì 1 âãø biãøu diãùn táút caí caïc säú. Hai kyï hiãûu âoï goüi chung laì bit hoàûc digit vaì noï âàûc træng cho maûch âiãûn tæí coï hai traûng thaïi äøn âënh hay coìn goüi laì 2 traûng thaïi bãön FLIP- FLOP (kyï hiãûu laì FF). Mäüt nhoïm 4 bêt goüi laì nibble. Mäüt nhoïm 8 bêt goüi laì byte. Nhoïm nhiãöu bytes goüi laì tæì (word). Xeït säú nhë phán 4 bêt: a3 a2a1a0. Biãøu diãùn dæåïi daûng âa thæïc theo cå säú cuía noï laì: a3 a2a1a0 = a3.23 + a2 . 22 + a1.21 + a0.20 Trong âoï: - 20, 21, 22, 23 (hay 1, 2, 4, 8) âæåüc goüi laì caïc troüng säú. - a0 âæåüc goüi laì bit coï troüng säú nhoí nháút, hay coìn goüi bit coï yï nghéa nhoí nháút (LSB: Least Significant Bit) .
Baìi giaíng Kyî Thuáût Säú Trang 4 - a3 âæåüc goüi laì bit coï troüng säú låïn nháút, hay coìn goüi laì bêt coï yï nghéa låïn nháút (MSB: Most Significant Bit). Nhæ váûy, våïi säú nhë phán 4 bit a3 a2a1a0 maì trong âoï mäùi chæî säú ai chè nháûn âæåüc hai giaï trë {0,1}, luïc âoï ta coï 24 = 16 täø håüp nhë phán. Säú tháûp phán a3 a2a1a0 Säú tháûp luûc phán 0 0000 0 1 0001 1 2 0010 2 3 0011 3 4 0100 4 5 0101 5 6 0110 6 7 0111 7 8 1000 8 9 1001 9 10 1010 A 11 1011 B 12 1100 C 13 1101 D 14 1110 E 15 1111 F Chuï yï: Khi biãøu diãùn säú nhë phán nhiãöu bit trãn maïy tênh thç thæåìng âãø traïnh sai soït, ngæåìi ta thæåìng biãøu diãùn thäng qua säú tháûp phán hoàûc tháûp luûc phán, baït phán. Vê duû: 3 7 7 6 3 1 1011111011111110 B E F E Coï thãø biãøu diãùn : 137376( 8 ) hoàûc 0BEFE(H).
Chæång 1. Hãû thäúng säú âãúm vaì khaïi niãûm vãö maî Trang 5 1.2.1.2. Caïc pheïp tênh trãn säú nhë phán a. Pheïp cäüng Âãø cäüng hai 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åï 1 3→ Vê duû: 0011 + + 2→ 0010 5→ 0101 b. Pheïp træì 0 - 0 = 0 mæåün 0 0 - 1 = 1 mæån 1 1 - 0 = 1 mæåün 0 1 - 1 = 0 mæåün 0 → 0111 Vê duû: 7 - - → 0101 5 2 1 0 → 0010 = 1.2 + 0.2 + 1.2 = 2 2 c. Pheïp nhán 0.0 = 0 0.1 = 0 1.0 = 0 1.1 = 1 → Vê duû: 7 0111 x x → 5 0101 35 0111 0000 0111 0000 0100011 = 1.25 + 1.21 + 1.20 = 35
Baìi giaíng Kyî Thuáût Säú Trang 6 d. Pheïp chia 0: 0 = 0 1: 1 = 1 → Vê duû: 10 5 1010 101 2 101 10 = 2 00 0 ÆÏng duûng thanh ghi dëch thæûc hiãûn pheïp toaïn nhán hai, chia hai: Thanh ghi ban âáöu Dëch traïi (nhán hai) 000000111 000001110 Dëch phaíi (chia hai) dæ 00000011 1 Thanh ghi sau khi nhán 2 Thanh ghi sau khi chia 2 1.2.2. Khaïi niãûm vãö maî 1.2.2.1. Âaûi cæång Trong âåìi säúng haìng ngaìy, con ngæåìi giao tiãúp våïi nhau thäng qua mäüt hãû thäúng ngän ngæî qui æåïc, nhæng trong maïy tênh chè xæí lyï caïc dæî liãûu nhë phán. Do âoï, mäüt váún âãö âàût ra laì laìm thãú naìo taûo ra mäüt giao diãûn dãù daìng giæîa ngæåìi vaì maïy tênh, nghéa laì maïy tênh thæûc hiãûn âæåüc nhæîng baìi toaïn do con ngæåìi âàût ra. Âãø thæûc hiãûn âiãöu âoï, ngæåìi ta âàût ra váún âãö vãö maî hoïa dæî liãûu. Nhæ váûy, maî hoïa laì quaï trçnh biãún âäøi nhæîng kyï hiãûu quen thuäüc cuía con ngæåìi sang nhæîng kyï hiãûu quen thuäüc våïi maïy tênh. Caïc lénh væûc maî hoïa gäöm : - Säú tháûp phán - Kyï tæû - Táp lãûnh û - Tiãúng noïi - Hçnh aính - ..v..v..
Chæång 1. Hãû thäúng säú âãúm vaì khaïi niãûm vãö maî Trang 7 1.2.2.2. Maî hoïa säú tháûp phán a. Khaïi niãûm Trong thæûc tãú âãø maî hoïa säú tháûp phán, ngæåìi ta sæí duûng caïc säú nhë phán 4 bit. Vê duû: 0 0000 ; 5 0101 1 0001 ; 6 0110 2 0010 ; 7 0101 3 0011 ; 8 1000 4 0100 ; 9 1001 Viãûc sæí duûng caïc säú nhë phán âãø maî hoïa caïc säú tháûp phán goüi laì caïc säú BCD (Binary Code Decimal: Säú tháûp phán âæåüc maî hoïa bàòìng säú nhë phán). b. Phán loaûi Khi sæí duûng säú nhë phán 4 bit âãø maî hoïa caïc säú tháûp phán tæång æïng våïi 24 = 16 täø håüp maî nhë phán phán biãût. Do viãûc choün 10 täø håüp trong 16 täø håüp âãø maî hoïa caïc kyï hiãûu tháûp phán tæì 0 âãún 9 maì trong thæûc tãú xuáút hiãûn nhiãöu loaûi maî BCD khaïc nhau. Màûc duì täön taûi nhiãöu loaûi maî BCD khaïc nhau, nhæng trong thæûc tãú ngæåìi ta chia laìm hai loaûi chênh: BCD coï troüng säú vaì BCD khäng coï troüng säú. b1. Maî BCD coï troüng säú: gäöm coï maî BCD tæû nhiãn, maî BCD säú hoüc. Maî BCD tæû nhiãn âoï laì loaûi maî maì trong âoï caïc troüng säú thæåìng âæåüc sàõp xãúp theo thæï tæû tàng dáön. Vê duû: Maî BCD 8421 , maî BCD 5421 Maî BCD säú hoüc laì loaûi maî maì trong âoï coï täøng caïc troüng säú luän luän bàòng 9. Vê duû: Loaûi maî: BCD 2421, BCD 5121, BCD 8 4-2-1 Suy ra maî BCD säú hoüc coï âàûc træng: Âãø tçm tæì maî tháûp phán cuía mäüt säú tháûp phán naìo âoï ta láúy buì (âaío) tæì maî nhë phán cuía säú buì 9 tæång æïng.
Baìi giaíng Kyî Thuáût Säú Trang 8 3 → 0011 Vê duû: Maì säú 6 laì buì 9 cuía 3: 6 → 1100 Láúy nghëch âaío ta coï: 0011 = 3 Váûy, âàûc træng cuía maî BCD säú hoüc laì coï tênh cháút âäúi xæïng qua mäüt âæåìng trung gian. b2. Maî BCD khäng coï troüng säú: laì loaûi maî khäng cho pheïp phán têch thaình âa thæïc theo cå säú cuía noï. Vê duû: Maî Gray, Maî Gray thæìa 3. Âàûc træng cuía maî Gray laì loaûi bäü maî maì trong âoï hai tæì maî nhë phán âæïng kãú tiãúp nhau bao giåì cuîng chè khaïc nhau 1 bit. Vê duû: Maî Gray: 2 → 0011 Coìn âäúi våïi maî BCD 8421: 3 → 0011 3 → 0010 4 → 0100 4 → 0110 Caïc baíng dæåïi âáy trçnh baìy mäüt säú loaûi maî thäng duûng: Baíng 1: Caïc maî BCD tæû nhiãn. Säú tháûp BCD 8421 BCD 5421 BCD quaï 3 phán a3 a2 a1 a0 b3 b2 b1 b0 c3 c2 c1 c0 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
Chæång 1. Hãû thäúng säú âãúm vaì khaïi niãûm vãö maî Trang 9 Baíng 2: Caïc maî BCD säú hoüc Säú tháûp BCD 2421 BCD 5121 BCD 84-2-1 phán a3 a2 a1 a0 b3 B2 b1 b0 c3 c2 c1 c0 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 0 0 0 1 0 0 4 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 Baíng 3: BCD tæû nhiãn vaì maî Gray. Säú tháûp BCD 8421 BCD quaï 3 Maî Gray Gray quaï 3 phán g3 g2 g1 g0 a3 a2 a1 a0 c3 c2 c1 c0 G3 G2 G1 G0 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 9 Chuï yï: Maî Gray âæåüc suy ra tæì maî BCD 8421 bàòng caïch: caïc bit 0,1 âæïng sau bit 0 (åí maî BCD 8421) khi chuyãøn sang maî Gray thç âæåüc giæî nguyãn, coìn caïc bit 0,1 âæïng sau bit 1 (åí maî BCD 8421) khi chuyãøn sang maî Gray thç âæåüc âäøi ngæåüc laûi, nghéa laì tæì bit 1 thaình bit 0 vaì bit 0 thaình bit 1.
Baìi giaíng Kyî Thuáût Säú Trang 10 1.2.2.3. Maûch nháûn daûng säú BCD 8421 : a3 y Maûch nháûn a2 daûng säú BCD a1 + y = 1 → a3 a2 a1 a0 khäng phaíi säú BCD 8421 + y = 0 → a3 a2 a1 a0 laì säú BCD 8421 Suy ra âãø nháûn daûng mäüt säú nhë phán 4 bit khäng phaíi laì mäüt säú BCD 8421 thç ngoî ra y = 1, nghéa laì: bit a3 luän luän bàòng 1 vaì bit a1 hoàûc a2 bàòng 1. Phæång trçnh logic : y = a3 (a1 + a2 ) = a3a1 + a3 a2 Så âäö logic: a1 a2 y a3 Do viãûc xuáút hiãûn säú BCD nãn coï hai caïch nháûp dæî liãûu vaìo maïy tênh: nháûp säú nhë phán, nháûp bàòng maî BCD. Âãø nháûp säú BCD tháûp phán hai chæî säú thç maïy tênh chia säú tháûp phán thaình caïc âãöcaïc vaì mäùi âãöcaïc âæåüc biãøu diãùn bàòng säú BCD tæång æïng. Vê duû: 11 (tháûp phán) coï thãø âæåüc nháûp vaìo maïy tênh theo 2 caïch: - Säú nhë phán: 1011 - Maî BCD : 0001 0001 1.2.2.4. Caïc pheïp tênh trãn säú BCD a. Pheïp cäüng Säú tháûp phán laì 128 thç: - Säú nhë phán laì: 10000000 - Säú BCD laì: 0001 0010 1000 Do säú BCD chè coï tæì 0 âãún 9 nãn âäúi våïi nhæîng säú tháûp phán låïn hån, noï chia säú tháûp phán thaình nhiãöu âãöcaïc, mäùi âãöcaïc âæåüc biãøu diãùn bàòng säú BCD tæång æïng.
Chæång 1. Hãû thäúng säú âãúm vaì khaïi niãûm vãö maî Trang 11 → 7→ 5 0101 0111 + + + + → 5→ 3 0011 0101 8 1000 12 1100 + Säú hiãûu chènh 0110 0001 0010 1 2 b. b. Pheïp træì A-B =A+ B → 0111 7 0111 - - + Buì 1 cuía 5 → 0101 5 1010 2 0010 10001 + 1 Buì 2 cuía 5 0010 Buì 1 laì bit 0 thaình 1, bit 1 thaình 0. Buì 2 laì buì 1 cäüng thãm 1. Xeït caïc træåìng håüp måí räüng: - Thæûc hiãûn træì 2 säú BCD 1 âãöcaïc maì säú bë træì nhoí hån säú træì. - Måí räüng cho cäüng vaì træì 2 säú BCD nhiãöu âãöcaïc.
"Don't study, don't know - Studying you will know!" NGUYEN TRUNG HOA
Baìi giaíng Kyî Thuáût Säú Trang 12 Chæång 2 ÂAÛI SÄÚ BOOLE 2.1. CAÏC TIÃN ÂÃÖ VAÌ ÂËNH LYÏ ÂAÛI SÄÚ BOOLE 2.1.1. Caïc tiãn âãö Cho mäüt táûp håüp B hæîu haûn trong âoï ngæåìi ta trang bë caïc pheïp toaïn + (cäüng logic), x (nhán logic), - (buì logic ) vaì hai pháön tæí 0 vaì 1 láûp thaình mäüt cáúu truïc âaûi säú Boole. ∀x,y ∈ B thç: x + y ∈ B, x*y ∈ B thoía maîn 5 tiãn âãö sau: 2.1.1.1. Tiãn âãö giao hoaïn ∀x,y ∈ B: x + y = y + x 2.1.1.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 2.1.1.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) 2.1.1.4. Tiãn âãö vãö pháön tæí trung hoìa Trong táûp B täön taûi hai pháön tæí trung hoìa âoï laì pháön tæí âån vë vaì pháön tæí 0, pháön tæí âån vë kyï hiãûu laì 1, pháön tæí 0 kyï hiãûu laì 0. ∀ x ∈ B: x+1= 1 x. 1= x x+0= x x. 0= 0 2.1.1.5. Tiãn âãö vãö pháön tæí buì ∀x ∈ B, bao giåì cuîng täön taûi pháön tæí buì tæång æïng sao cho luän thoía maîn: x+ x =0
Chæång 2. Âaûi säú BOOLE Trang 13 x. x = 0 Nãúu B = B* = {0, 1} vaì thoía maîn 5 tiãn âãö trãn thç cuîng láûp thaình cáúu truïc âaûi säú Boole nhæng laì cáúu truïc âaûi säú Boole nhoí nháút. 2.1.2. Caïc âënh lyï 2.1.2.1 Váún âãö âäúi ngáùu trong âaûi säú Boole Hai mãûnh âãö (hai biãøu thæïc, hai âënh lyï) âæåüc goüi laì âäúi ngáùu våïi nhau nãúu trong mãûnh âãö naìy ngæåìi ta thay pheïp toaïn cäüng thaình pheïp toaïn nhán vaì ngæåüc laûi,thay 0 bàòng 1 vaì ngæåüc laûi thç seî 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 laì âuïng thç mãûnh âãö coìn laûi laì âuïng. Vê duû: x.(y + z ) = ( x. y) + ( x. z ) x + (y. z ) = ( x + y )( x + z ) Vê duû: x+ x =1 x. x = 0 2.1.2.2. Caïc âënh lyï a. Âënh lyï vãö pháön tæí buì laì duy nháút ∀x, y ∈ B: x + y = 1⎫ ⎬⇒ y=x x.y = 0 ⎭ ∀x ∈ B: x + x +. . . . . + x = x x. x. x. . . . . . x = x b. Âënh lyï De Morgan ∀x, y, z ∈ B, ta coï: x + y + z = x. y.z x.y.z = x + y + z ∀x ∈ B, ta coï: x =x ∀x, y, z ∈ B, ta coï:
Baìi giaíng Kyî Thuáût Säú Trang 14 x + y + z = x + y + z = x.y.z x. y. z = x.y.z = x + y + z ∀x, y ∈ B, ta coï: x. ( x + y) = x.y x + ( x . y) = x + y ∀x, y ∈ B, ta coï: x + x. y = x x.(x + y) = x Våïi 0, 1 ∈ B, ta coï: 0 = 1 vaì 1 = 0 2.2. HAÌM BOOLE VAÌ CAÏC PHÆÅNG PHAÏP BIÃØU DIÃÙN 2.2.1. Haìm Boole 2.2.1.1. Âënh nghéa Haìm Boole laì mäüt aïnh xaû Boole tæì âaûi säú Boole vaìo chênh noï. Tæïc laì ∀x, y ∈ B âæåüc goüi laì biãún Boole thç haìm Boole, kyï hiãûu laì f, âæåüc hçnh thaình trãn cå såí liãn kãút caïc biãún Boole bàòng caïc pheïp toaïn + (cäüng logic ), x (nhán logic ), hoàûc nghëch âaío logic (-). Haìm Boole âån giaín nháút laì haìm Boole theo 1 biãún Boole. Kyï hiãûu: f(x) = x f(x) = x f(x) = α (α: laì hàòng säú ) Trong træåìng håüp täøng quaït, ta coï haìm Boole theo n biãún Boole âæåüc kyï hiãûu nhæ sau: f(x1, x2,. . . . . ., xn ) 2.2.1.2. Caïc tênh cháút cuía haìm Boole Nãúu f(x1, x2, ..., xn) laì mäüt haìm Boole thç: + α.f(x1, x2, ..., xn) cuîng laì mäüt haìm Boole. + f (x1, x2, ..., xn) cuîng laì mäüt haìm Boole. Nãúu f1(x1, x2, ..., xn) vaì f2(x1, x2, ..., xn) laì nhæîng haìm Boole thç: + f1(x1, x2, ..., xn) + f2(x1, x2, ..., xn) cuîng laì mäüt haìm Boole. + f1(x1, x2, ..., xn).f2(x1, x2, ..., xn) cuîng laì mäüt haìm Boole.
Chæång 2. Âaûi säú BOOLE Trang 15 Váûy, mäüt haìm Boole f cuîng âæåüc hçnh thaình trãn cå såí liãn kãút caïc haìm Boole bàòng caïc pheïp toaïn + (cäüng logic), x (nhán logic) hoàûc nghëch âaío logic (-). 2.2.1.3. Giaï trë cuía haìm Boole Goüi f (x1, x2, ..., xn) laì mäüt haìm Boole theo biãún Boole. Trong f ngæåìi ta thay caïc biãún xi bàòng caïc giaï trë cuû thãø αi (i = 1, n ) thç haìm f (α1, α2, α3,..., αn) âæåüc goüi laì giaï trë cuía haìm Boole theo n biãún. Vê duû: Xeït haìm f(x1, x2 ) = x1 + x2 Xeït B = B* ={0,1} x1 x2 f(x1, x2) ⇒ f(0,0) = 0 Nãúu x1 = x2 =0 0 0 0 Nãúu x1 = 0, x2 = 1 ⇒ f(0,1) = 1 0 1 1 Nãúu x1 = 1, x2 = 0 ⇒ f(1,0) = 1 1 0 1 Nãúu x1 = 1, x2 = 1 ⇒ f(1,1) = 1 1 1 1 Ta láûp âæåüc baíng giaï trë cuía haìm trãn. Vê duû: f (x1, x2, x3 ) = x1 + x2.x3 Xeït B = B* = {0,1 } Baíng giaï trë cuía haìm: f (x1, x2, x3) x1 x2 x3 000 0 001 0 010 0 011 1 100 1 101 1 110 1 111 1
Baìi giaíng Kyî Thuáût Säú Trang 16 2.2.2. Caïc phæång phaïp biãøu diãùn haìm Boole 2.2.2.1. Phæång phaïp baíng 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: x =0. x + 1. x Ta coï: màût khaïc: ⎧f (1) = 1 f (x ) = x ⇒ ⎨ ⎩f (0 ) = 0 suy ra f(x) = x coï thãø biãøu diãùn: f(x) = x = f(0). x + f (1).x trong âoï: f (0), f (1) âæåüc goüi laì giaï trë cuía haìm Boole theo mäüt biãún. Xeït f(x) = x : x = 1. x + 0. x Ta coï: Màût khaïc: ⎧f (1) = 0 f (x ) = x ⇒ ⎨ ⎩f (0 ) = 1 Suy ra: f(x) = x coï thãø biãøu diãùn: f(x) = x = f(0). x + f(1).x
Chæång 2. Âaûi säú BOOLE Trang 17 Xeït f(x) = α: Ta coï: α = α.1 = α(x + x ) = x .α + α.x Màût khaïc: ⎧f (1) = α f (x ) = α ⇒ ⎨ ⎩f (0) = α 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 Váûy f(x) = f(0). x + f(1).x trong âoï f (0), f (1) âæåüc goüi laì giaï trë cuía haìm Boole theo mäüt biãún, âæåüc goüi laì daûng chênh tàõc thæï nháút (daûng täøng cuía caïc têch) theo mäüt biãún. Trong træåìng håüp hai biãún f(x1, x2) thç caïch biãøu diãùn cuîng hoaìn toaìn dæûa trãn caïch biãøu diãùn cuía daûng chênh tàõc thæï nháút theo 1 biãún (trong âoï xem mäüt biãún laì hàòng säú). Ta coï: f(x1, x2 ) = f(0, x2). x 1 + f(1,x2).x1 f(0, x2) = f(0,0 ). x 2 + f(0,1).x2 maì: f(1, x2) = f(1,0). x 2 + f(1,1). x2 vaì: 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 2 2 −1 α2 f ( x1, x 2) = ∑ f(α1 , α 2 )x1α x 2 1 Váûy: e=0 trong âoï e laì säú tháûp phán tæång æïng våïi maî (α1, α2) vaì: x1 nãúu α1 = 1 α x1 1 = x 1 nãúu α1 = 0 x2 nãúu α2 = 1 α x2 2 = x 2 nãúu α2 = 0
Baìi giaíng Kyî Thuáût Säú Trang 18 Täøng quaït cho n biãún: 2n −1 α f(x1, x2, ..., xn) = ∑ f(α1 , α 2 ,...., α n )x 1α1 x 2 2 ...x n α n e =0 trong âoï e laì säú tháûp phán tæång æïng våïi maî nhë phán (α1, α2, ...., αn); xi nãúu αi = 1 vaì: α xi i = x i nãúu αi = 0 Vê duû: 2 3 −1 f(x1, x2, x3) = ∑ f (α1, α2, α3). x1α1. x2α2. x3α3 e=0 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 + f(1,0,1)x1 x 2 x3 + f(1,1,0) x1 x2 x 3 + f(1,1,1) x1 x2 x3 Váûy daûng chênh tàõc thæï nháút laì daûng täøng cuía caïc têch maì trong mäùi têch säú chæïa âáöy âuí caïc biãún Boole dæåïi daûng tháût hoàûc daûng buì (nghëch âaío). b. Daûng chênh tàõc 2 (têch cuía caïc täøng): Âáy laì daûng âäúi ngáùu cuía daûng chênh tàõc 1 nãn biãøu thæïc täøng quaït cuía daûng chênh tàõc thæï hai cho n biãún laì: 2n −1 f(x1, x2, ..., xn) = ∏ [f(α1, α2, α3) + x1α1 + x2α2+ ...+ xnαn)] e =0 trong âoï e laì säú tháûp phán tæång æïng cuía maî nhë phán (α1, α2, ...., αn); vaì: x i nãúu αi = 1 α xi i = xi nãúu αi = 0 Vê duû: 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]
Chæång 2. Âaûi säú BOOLE Trang 19 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] Váûy, daûng chênh tàõc thæï hai laì daûng têch cuía caïc täøng säú maì trong âoï mäùi täøng säú naìy chæïa âáöy âuí caïc biãún Boole dæåïi daûng tháût hoàûc daûng buì. Chuï yï: Xeït vê duû 1: f(x1, x2) = x1 + x2 , Viãút dæåïi daûng chênh tàõc 1: f(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 Tæì vê duû trãn ta tháúy: Daûng chênh tàõc thæï nháút laì daûng liãût kã táút caí caïc täø håüp nhë phán caïc biãún vaìo sao cho tæång æïng våïi nhæîng täø håüp âoï giaï trë cuía haìm ra bàòng 1. Khi liãût kã nãúu biãún tæång æïng bàòng 1 âæåüc viãút åí daûng tháût (x), vaì biãún tæång æïng bàòng 0 âæåüc viãút åí daûng buì ( x ). Xeït vê duû 2: f(x1, x2, x3) = x1 + x2.x3 Viãút dæåïi daûng chênh tàõc 2: 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] Hay: f(x1, x2, x3) = x1 + x2.x3 = [x1+x2+x3].[x1+x2+ x 3].[x1+ x 2+x3] Váûy, daûng chênh tàõc thæï hai laì daûng liãût kã táút caí caïc täø håüp nhë phán caïc biãún vaìo sao cho tæång æïng våïi nhæîng täø håüp âoï giaï trë cuía haìm ra bàòng 0. Khi liãût kã nãúu biãún tæång æïng bàòng 0 âæåüc viãút åí daûng tháût (x), vaì biãún tæång æïng bàòng 1 âæåüc viãút åí daûng buì ( x ). Xeït vê duû âån giaín sau âãø hiãøu roî hån vãö caïch thaình láûp baíng giaï trë cuía haìm, tçm haìm maûch vaì thiãút kãú maûch: Haîy thiãút kãú maûch âiãûn sao