Bài giảng Kỹ thuật số - Chương 2: Đại số Boole

Nội dung chương 2: Đại số Boole thuộc bài giảng Kỹ thuật số trình bày về các tiên đề và định lý đại số boole, hàm boole và các phương pháp biểu diễn, tối thiểu hàm boole. Tài liệu này dành cho các sinh viên và giảng viên, mời các bạn tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng Kỹ thuật số - Chương 2: Đại số BooleBaìi giaíng Kyî Thuáût Säú Trang 12 Chæång 2 ÂAÛI SÄÚ BOOLE2.1. CAÏC TIÃN ÂÃÖ VAÌ ÂËNH LYÏ ÂAÛI SÄÚ BOOLE2.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áûpthaì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 bố ∀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æí kh, 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änthoía maîn: x+ x =0Chæå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ìnhcáú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åïinhau nãúu trong mãûnh âãö naìy ngæåìi ta thay pheïp toaïn cäüng thaình pheïptoaïn nhán vaì ngæåüc laûi,thay 0 bàòng 1 vaì ngæåüc laûi thç seî suy ra âæåücmãûnh âãö kia. Khi hai mãûnh âãö âäúi ngáùu våïi nhau, nãúu 1 trong 2 mãûnh âãö âæåücchæï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 = 02.2. HAÌM BOOLE VAÌ CAÏC PHÆÅNG PHAÏP BIÃØU DIÃÙN2.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æïclaì ∀x, y ∈ B âæåüc goüi laì biãún Boole thç haìm Boole, kyï hiãûu laì f, âæåüchç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ïchaìm Boole bàòng caïc pheïp toaïn + (cäüng logic), x (nhán logic) hoàûcnghë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 nbiãún. Vê duû: Xeït haìm f(x1, x2 ) = x1 + x2 Xeït B = B* ={0,1} x1 x2 f(x1, x2) Nãúu x1 = x2 =0 ⇒ f(0,0) = 0 0 0 0 Nãúu x1 = 0, x2 = 1 ⇒ f(0,1) = 1 0 1 1 Nãúu x ...