Kuliah Sistem Digital Aljabar Boolean
1
Topik 2 – Aljabar Boolean • Aturan-2 u/ menentukan logika digital, atau `switching algebra’ – Terkait dengan nilai-2 Boolean – 0, 1 – Nilai sinyal dinyatakan dengan variabel-2 – {X, Y, DIN, …}
• Perjanjian logika positif
– Tegangan analog (LOW, HIGH) (0, 1) – logika negatif – jarang digunakan
• Operator-2: { · , + , ‘ , }
• Aksioma-2 dan Teorema-2 …
– Membantu u/ mereduksi logika kompleks menjadi logika lebih sederhana – meningkatkan “area dan kecepatan” dari rangkaian digital
Definisi: Ekspresi Boolean • Literal: sebuah variabel atau komplemennya – X, X, DIN, TK_L
• Ekpresi: literals dikombinasikan dengan AND, OR, tanda kurung, komplementasi – – – –
X+Y PQR A+BC ((DIN Z) + TK_L A B C + Q5) RESET
• Persamaan: variabel = ekspresi
– P = ((DIN Z) + TK_L A B C + Q5) RESET
Aksioma • Aksioma – kumpulan definisi dasar (A1-A5, A1’-A5’) minimal yang diasumsikan benar dan secara menyeluruh mendefinisikan aljabar switching – Dapat digunakan untuk membuktikan teorema-2 aljabar switching lainnya (T1-T15). (A1)
X=0, if X1
(A1’) X=1, if X0
(A2)
If X=0, then X’=1
(A2’) If X=1, then X’=0
(A3)
0·0=0
(A3’) 1 + 1 = 1
(A4)
1·1=1
(A4’) 0 + 0 = 0
(A5)
0·1=1·0=0
(A5’) 1 + 0 = 0 + 1 = 1
Each axiom has a dual
Teorema-2 variabel tunggal (T1-T5)
• Dibuktikan melalui induksi sempurna (perfect induction)
– Karena sebuah variabel switching hanya dapat mempunyai nilai 0 dan 1, kita dapat membuktikan sebuah teorema dengan melibatkan sebuah variabel tunggal X melalui peletakan sederhana: X = 0 atau X =1
• Contoh: (T1) X + 0 = X
– X=0 : 0 + 0 = 0 benar menurut aksioma A4’ – X=1 : 1 + 0 = 1 benar menurut aksioma A5’
Teorema-2 dua dan tiga variabel (T6-T11)
• Dualitas:
– Tes: 0 & 1, AND & OR teorema-2 tetap benar? – Ya!! …kenapa? … setiap aksioma memiliki sebuah dual …
• Hati-2 dengan` urutan operator (operator precedence_’ – penggunaan tanda kurung
Teorema T6, T7 (Commutatif) (T6) X + Y = Y + X (T6’) X · Y = Y · X (Assosiatif) (T7) (X + Y) + Z = X + (Y + Z) (T7’) (X · Y) · Z = X · (Y · Z)
• Mirip dengan hukum-2 commutatif dan assosiatif untuk penjumlahan dan perkalian dari bilangan-2 bulat dan riil
(Distributif)
Teorema T8
(T8) X · Y + X · Z = X · (Y + Z) (T8’) (X + Y) · (X + Z) = X + Y · Z • Jumlah dari perkalian (sum-of-products (SOP)) vs. Perkalian dari jumlah (product-of-sums (POS)) V · W · Y + V · W · Z + V · X · Y + V · X · Z = V · (W + X) · (Y + Z) (bentuk SOP)
(bentuk POS)
(V · W · X) + (Y · Z ) = (V + Y) · (V + Z) · (W + Y) · (W + Z) · (X + Y) · (X + Z)
• Tergantung pd masalah, pilih yang lebih sederhana – Yang mana lebih logis menurut anda?
Teorema T9, T10 (Covering) (T9) X + X · Y = X (T9’) X · (X + Y) = X (Kombinasi) (T10) X · Y + X · Y’ = X (T10’) (X + Y) · (X + Y’) = X • Perguna dalam penyederhanaan fungsi-2 logika
Teorema T11 (konsensus) (T11) X · Y + X’ · Z + Y · Z = X · Y + X’ · Z (T11’) (X + Y) · ( X’ + Z) · (Y + Z) = (X + Y) · (X’ + Z) • Pada T11 term Y·Z disebut konsensus dari term X·Y dan X’·Z: – Jika Y · Z = 0, maka T11 pasti benar – Jika Y · Z = 1, maka X · Y atau X’ · Z harus 1 – Sehingga term Y · Z : redundan dan harus dibuang
• Tugas buktikan (T11’)?
Teorema-2 N-variabel (T12 – T15)
Pembuktian menggunakan induksi terbatas (finite induction) Paling penting: teorema-2 DeMorgan (T13 & T13’)
Contoh Teorema DeMorgan: NAND • (X · Y)’ = (X’ + Y’)
– (X · Y)’ dirujuk umumnya sebagai gerbang NAND pada ekspresi gerbang logika
Contoh Teorema DeMorgan: NOR • (X + Y)’ = (X’ · Y’)
– (X + Y)’ dirujuk sebagai gerbang NOR pada ekspresi gerbang logika
Gerbang-2 NAND & NOR
• Menggunakan jumlah rangk. yang lebih sedikit ketimbang gerbang-2 AND & OR • Fan-in & Fan-out NAND
AND
Extra ciruits
Generalisasi Teorem DeMorgan (T14) [F(X1, X2, . . ., Xn, +, ·)]’ = F(X1’, X2’, . . ., Xn’, · , +) • Diberikan suatu ekspresi logika n-variabel, komplemennya dapat ditemukan melalui “swapping + dan · dan penkomplemenan seluruh variabel • Contoh:
– F(W,X,Y,Z) = (W’ · X) + (X · Y) + (W · (X’ + Z’)) = ((W)’ · X) + (X · Y) + (W · ((X)’ + (Z)’)) – [F(W,X,Y,Z)]’ = ((W’)’ + X’) · (X’ + Y’) · (W’ + ((X’)’ · (Z’)’)) – Gunakan (T4) (X’)’ = X, pers. Diatas dpt disederhanakan menjadi: – [F(W,X,Y,Z)]’ = (W + X’) · (X’ + Y’) · (W’ + (X · Z))
REVISI Dualitas
• Setiap teorema pd aljabar switching tetap benar jika 0 & 1 di-swapped dan · & + di-swapped. • Benar karena seluruh duals dari seluruh aksioma adalah benar, sehingga duals dari seluruh teorema aljabar switching dapt dibuktikan dengan menggunakan duals aksioma-2. • Kita dapat menuliskan kembali teorema DeMorgan sbg [F(X1, X2, …., Xn)]’ = FD(X1’, X2’, …., Xn’) • Catatan … – A·B+CA+B·C (A + B) · C – Duality bukan berarti ekuivalensi !!
Manipulasi ekspresi Boolean • Bagaimana menyatakan (A · B + C)? • Gunakan teorema DeMorgan … – A · B + C = ( ( A · B + C )’ )’ – = ( ( A · B )’ · C’ )’ – = ( ( A’ + B’ ) · C’ )’ ( A · B + C )’ = ( A’ + B’ ) · C’
(A1) (A2) (A3) (A4) (A5)
Aksioma-2 dan Teorema-2 Aljabar Switching
X = 0 if X 1 If X = 0, then X’ = 1 0.0 = 0 1.1 =1 0.1=1.0=0
(A1’) (A2’) (A3’) (A4’) (A5’)
X = 1 if X 0 if X = 1, then, X’ = 0 1+1=1 0+0=0 1+0 =0+1=1
(T1) X + 0 = X (T1’) X . 1 = X (Identities) (T2) X + 1 = 1 (T2’) X . 0 = 0 (Null elements) (T3) X + X = X (T3’) X . X = X (Idempotency) (T4) (X’)’ = X (Involution) (T5) X + X’ = 1 (T5’) X . X’ = 0 (Complements) (T6) X + Y = Y + X (T6’) X . Y = Y . X (Commutativity) (T7) (X + Y) + Z = X + (Y + Z) (T7’) (X . Y) . Z = X . (Y . Z) (Associativity) (T8) X . Y + X . Z = X . (Y + Z) (T8’) (X + Y) . (X + Z) = X + Y . Z (Distributivity) (T9) X + X . Y = X (T9’) X . (X + Y) = X (Covering) (T10) X . Y + X . Y’ = X (T10’) (X + Y) . (X + Y’) = X (Combining) (T11) X . Y + X’. Z + Y . Z = X . Y + X’ . Z (T11’) (X + Y) . ( X’ + Z) . (Y + Z) = (X + Y) . (X’ + Z) (Consensus) (T12) X + X + . . . + X = X (T12’) X . X . . . . . X = X (Generalized idempotency) (T13) (X1 . X2 . . . . . Xn)’ = X1’ + X2’ + . . . + Xn’ (T13’) (X1 + X2 + . . . + Xn)’ = X1’ . X2’ . . . . . Xn’ (DeMorgan’s theorems) (T14) [F(X1, X2, . . ., Xn, +, .)]’ = F(X1’, X2’, . . ., Xn’, . , +) (Generalized DeMorgran’s theorem)
Definisi lanjut – Ekspresi Boolean • Term perkalian:
– Z’, (W · X · Y), (X · Y’ · Z), (W’ · Y’ · Z)
• Term penjumlahan:
– Z’, (W + X + Y), (X + Y’ + Z), (W’ + Y’ + Z)
• Ekspresi sum-of-products (SOP):
– Z’ + (W · X · Y) + (X · Y’ · Z) + (W’ · Y’ · Z)
• Ekspresi product-of-sums (POS) :
– Z’ · (W + X + Y) · (X + Y’ + Z) · (W’ + Y’ + Z)
• Term normal: term perkalian atau penjumlahan di dlmnya tidak ada variabel yang muncul lebih dari sekali Contoh-2 term-2 non-normal: W·X·X·Y’ W+W+X’+Y X·X’·Y Contoh-2 term-2 normal: W·X·Y’ W+X’+Y 0
Minterm dan Maxterm •
Minterm: – Sebuah minterm n-variabel merupkan sebuah term perkalian normal dgn n literals. – Terdapat 2n term perkalian yang demikian. – Contoh-2 minterm 4-variabel: W · X’ · Y’ · Z’ W · X · Y’ · Z W’ · X’ · Y · Z’ – Dapat didefinisikan sebagai sebuah term perkalian yang = 1 pada benar-benar satu baris dari tabel kebenaran
•
Maxterm: – Sebuah maxterm n-variabel merupakan sebuah term penjumlahan normal dengan n literals. – Terdapat 2n term-2 penjumlahan yang demikian. – Contoh-2 maksterm 4-variabel: W’ + X’ + Y + Z’ W + X’ + Y’ + Z W’ + X’ + Y + Z – Dpt didefiniskan sebgaia sebuah term penjumlahan yang = 0 pada benar-2 satu baris dari tabel kebenaran
Minterms/Maxterms u/ sebuah fungsi 3-variabel
Representasi Penjumlahan Kanonis • Minterm i : – Baris i dari tabel kebenaran yang memiliki keluaran 1 1
• Penjumlahan Kanonis (Canonical sum): – Jumlah dari seluruh minterms u/ suatu fungsi yang diberikan (tabel kebenaran)
• Notasi Σ: – Contoh: Σ X,Y,Z (0, 3, 4, 6, 7)
= X’·Y’·Z’ + X’·Y·Z + X·Y’·Z’ + X·Y·Z’ + X·Y·Z
– Representasi ini biasa direalisasi dgn menggunakan rangkaian logika AND-OR 2 level dengan inverter-2 pada masukan-2 gerbang AND, sperti yang diperlukan
Contoh penjumlahan kanonis
• Fungsi direpresenyasikan dengan tabel kebenaran: Row X Y Z 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
F 1 0 0 1 1 0 1 1
mempunyai representasi penjumlahan kanonis sbb:
Daftar Minterm menggunakan notasi Σ
F = Σ X,Y,Z (0, 3, 4, 6, 7) = X’·Y’·Z’ + X’·Y·Z + X·Y’·Z’ + X·Y·Z’ + X·Y·Z Penjumlahan minterms kanonis secara aljabar
Representasi perkalian kanonis • Maxterm i: – baris i dari tabel kebenara yang mempunyai keluaran 0
• Pekalian kanonis: – Perkalian dari maxterms u/ suatu fungsi yang diberikan (tabel kebenaran)
• Notasi Π : – Contoh: Π X,Y,Z (1,2,5)
= (X + Y + Z’) . (X + Y’ + Z) . (X’ + Y + Z’)
– Representasi direalisasi dgn menggunakan rangk. logika OR-AND 2 –levels dengan inverter-2 pada masukan-2 gerbang OR, seperti dibutuhkan
Contoh perkalian kanonis
• Fungsi direpresentasi dengan tabel kebenaran: Row X Y Z 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
F 1 0 0 1 1 0 1 1
memiliki representasi perkalian kanonis: Daftar Maxterm notasi Π F = Π X,Y,Z (1,2,5) = (X + Y + Z’) · (X + Y’ + Z) · (X’ + Y + Z’) Perkalian maxterms kanonis secara aljabar
Konversi antara daftar Minterm/Maxterm • Dapatkan komplemen dari set … • Contoh: Σ X,Y,Z(0,1,2,3) = Π X,Y,Z(4,5,6,7) Σ X,Y(1) = Π X,Y(0,2,3) Σ W,X,Y,Z(0,1,2,3,5,7,11,13) = Π W,X,Y,Z(4,6,8,9,12,14,15)
Latihan • F=X’YZ+X’YZ’+XZ • Ditanyakan:
– Buatlah rangkaian digital persamaan diatas – Sederhanakan persamaan diatas dan buatlah rangkaian digital dari hasil penyederhanaanya – Buatlah Rangkaian dalam bentuk IC dan tentukan type2 IC TTL yang dibutuhkan – Ubahlah Rangkaian yang disederhanakan menjadi rangkaian NAND saja, berapa IC TTL yang dibutuhkan – Ubahlah rangkaian menjadi NOR saja, dan berapa IC TTL yang dibutuhkan
27
• • • •
F=X’YZ+X’YZ’+XZ F=X’Y(Z+Z’)+XZ T8 F=X’Y.1+XZ T5 F=X’Y+XZ
28
