Matdis โ Bab 8
Aljabar Boolean
Sistem aljabar biner untuk logika digital โ fondasi desain rangkaian, penyederhanaan ekspresi, dan peta Karnaugh.
Ref: Rinaldi Munir, Matematika Diskrit, Edisi 7 (2020), Bab 8. โ Rosen, Discrete Mathematics, 8th ed., Ch. 12. โ Mano & Ciletti, Digital Design, 6th ed., Pearson.
Mengapa Aljabar Boolean Penting?
Aljabar Boolean adalah bahasa matematika komputer. Setiap instruksi CPU, setiap bit data, setiap keputusan dalam program diimplementasikan dengan gerbang logika yang bekerja atas prinsip Boolean. George Boole (1854) menciptakan aljabar ini; Claude Shannon (1937) membuktikan bahwa ia dapat memodelkan rangkaian listrik digital.
Contoh paling kasat mata: Peta Karnaugh. Menyederhanakan ekspresi dari 12 gerbang menjadi 4 gerbang berarti chip lebih kecil, lebih murah, dan lebih hemat daya โ dampak yang langsung terasa pada perangkat yang diproduksi jutaan unit.
1. Definisi dan Operasi Dasar
Definisi (Aljabar Boolean)
Aljabar Boolean adalah struktur aljabar (B, +, ยท, ', 0, 1) dengan himpunan B, dua operasi biner (+ untuk OR, ยท untuk AND), satu operasi unar (' untuk NOT), dan dua elemen khusus 0 dan 1, yang memenuhi aksioma Huntington.
AND (ยท) โ Konjungsi
0ยท0=0, 0ยท1=0
1ยท0=0, 1ยท1=1
OR (+) โ Disjungsi
0+0=0, 0+1=1
1+0=1, 1+1=1
NOT (') โ Negasi
0' = 1
1' = 0
Analogi: Saklar Listrik
Bayangkan saklar listrik: ON = 1, OFF = 0. AND = dua saklar seri (keduanya harus ON agar arus mengalir). OR = dua saklar paralel (cukup satu ON). NOT = inverter. Setiap fungsi Boolean dapat diwujudkan sebagai jaringan saklar โ inilah yang ada di dalam chip CPU modern dengan miliaran transistor CMOS.
2. Tabel Kebenaran
Eksplorasi Interaktif: Evaluasi Ekspresi Boolean
A AND B
0
A OR B
1
NOT A
0
A XOR B
1
A' + B
0
A NAND B
1
A NOR B
0
A AND B AND C
0
A OR B OR C
1
Tabel Kebenaran Lengkap: Pilih Gerbang
| A | B | AND(A,B) |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
3. Hukum-Hukum Aljabar Boolean
Hukum Identitas, Dominasi, Idempoten, Komplemen
| Hukum | AND | OR |
|---|---|---|
| Identitas | Aยท1 = A | A+0 = A |
| Dominasi | Aยท0 = 0 | A+1 = 1 |
| Idempoten | AยทA = A | A+A = A |
| Komplemen | AยทA'= 0 | A+A'= 1 |
| Involusi | (A')' = A | |
Hukum Distributif, Absorpsi, De Morgan
| Distributif 1 | A(B+C)=AB+AC |
| Distributif 2 | A+BC=(A+B)(A+C) |
| Absorpsi 1 | A+AB = A |
| Absorpsi 2 | A(A+B) = A |
| De Morgan 1 | (AB)'=A'+B' |
| De Morgan 2 | (A+B)'=A'B' |
Hukum De Morgan โ Sangat Penting dalam Desain Chip!
De Morgan adalah jembatan antara AND dan OR. Dalam desain chip CMOS, gerbang NAND jauh lebih efisien dari AND (memerlukan lebih sedikit transistor). Sehingga semua fungsi Boolean biasanya diimplementasikan menggunakan NAND (atau NOR) saja โ keduanya disebut gerbang universal.
NOT(AND) = OR of NOTs
NOT(OR) = AND of NOTs
4. Bentuk Kanonik: SOP dan POS
Sum of Products (SOP) โ Minterm
OR dari suku-suku AND. Setiap suku AND = minterm (semua variabel muncul sekali, bisa dengan atau tanpa komplemen). Contoh:
F = ฮฃm(1,3,5,7) = A'B'C + A'BC + AB'C + ABC
Disederhanakan: F = C (karena C=1 di semua minterm)
Product of Sums (POS) โ Maxterm
AND dari suku-suku OR. Setiap suku OR = maxterm. Dibentuk dari baris tabel kebenaran dengan F = 0. Contoh:
F = ฮ M(0,2,4,6) = (A+B+C)(A+B'+C)...(etc)
Disederhanakan: F = C (setara dengan SOP di atas)
5. Peta Karnaugh (K-Map)
Tujuan K-Map
Penyederhanaan fungsi Boolean secara visual. Sel-sel bertetangga berbeda hanya 1 bit (Gray code). Kelompokkan sel bernilai 1 dalam kelompok 2แต (1, 2, 4, 8, 16) untuk mendapatkan ekspresi SOP minimal.
Aturan kunci: (1) ambil kelompok sebesar mungkin; (2) wrap-around diperbolehkan (kolom/baris ujung bertetangga); (3) setiap sel 1 harus masuk minimal 1 kelompok; (4) don't care (X) bisa dimasukkan untuk memperbesar kelompok.
K-Map 3 Variabel: F(A,B,C) = ฮฃm(0,1,3,5,7)
K-Map 3 variabel. Grup biru โ A'B', grup kuning โ BC. Hasil: F = A'B' + BC
6. Gerbang Logika Digital
Simbol Standar Gerbang Logika (IEEE/ANSI)
Fungsi Setiap Gerbang Logika
Ubah masukan A dan B โ setiap kartu memperlihatkan simbol fungsi (persamaan Boolean) dan keluarannya secara langsung.
Keluaran 1 hanya jika SEMUA masukan 1 (perkalian logika).
Keluaran 1 jika SALAH SATU masukan 1 (penjumlahan logika).
Pembalik (inverter): 0โ1, 1โ0. Hanya satu masukan.
Keluaran 1 jika masukan BERBEDA. Dasar penjumlahan biner & enkripsi (one-time pad).
AND yang dibalik. Gerbang UNIVERSAL โ semua fungsi dapat dibangun hanya dari NAND.
OR yang dibalik. Juga gerbang UNIVERSAL.
XOR dibalik: keluaran 1 jika masukan SAMA (pembanding kesetaraan).
๐ก Lihat penerapan langsung pada Pembahasan Contoh Soal (Soal 2 โ simulator rangkaian NOT/OR/NAND).
7. Sintesis Rangkaian Logika
Proses desain rangkaian logika: (1) Spesifikasi masalah โ (2) Tabel kebenaran โ (3) Ekspresi SOP/POS โ (4) Penyederhanaan K-Map atau Quine-McCluskey โ (5) Jaringan gerbang logika โ (6) Implementasi CMOS/FPGA.
# Contoh: Full Adder (A, B, Cin)
Sum S = A XOR B XOR Cin
Cout = AB + ACin + BCin
# Implementasi: 2 XOR + 3 AND + 1 OR gate (total 6 gates)
# Implementasi NAND-only: NAND(NAND(A,B), NAND(A,Cin), NAND(B,Cin)) untuk Cout
8. Aplikasi: Dari Ekspresi Boolean ke Rangkaian
Aljabar Boolean โ Gerbang Logika โ Silikon
Penjumlah Biner (Adder): Rangkaian penjumlah 1-bit adalah dua fungsi Boolean murni: Sum = A โ B โ Cin dan Carry = AB + Cin(A โ B). Merangkai 64 salinannya menghasilkan ALU yang menjumlahkan bilangan 64-bit di dalam prosesor.
Multiplexer & Dekoder: MUX 4-ke-1 diekspresikan sebagai F = SโโฒSโโฒIโ + SโโฒSโIโ + SโSโโฒIโ + SโSโIโ. Bentuk SOP ini diterjemahkan langsung menjadi gerbang โ dasar dari pemilihan jalur data di dalam CPU.
Minimisasi = Hemat Silikon: Peta Karnaugh dan algoritma Quine-McCluskey mencari bentuk dengan literal paling sedikit. Setiap gerbang yang dihemat berarti luas chip, konsumsi daya, dan penundaan propagasi yang lebih kecil โ dikalikan jutaan unit produksi.
9. Contoh Soal & Pembahasan
Soal 1: Penyederhanaan Aljabar
Sederhanakan: F = ABC + ABC' + AB'C
Soal 2: De Morgan dan Komplemen
Temukan komplemen dari F = AB' + A'C menggunakan teorema De Morgan.
Soal 3: Minterm dan Maxterm
Nyatakan F(A,B,C) = ฮฃm(1,3,5,7) dalam bentuk SOP kanonik, kemudian sederhanakan.
Soal 4: K-Map 4 Variabel
Sederhanakan F(A,B,C,D) = ฮฃm(0,1,4,5,8,9,12,13).
Soal 5: Full Adder
Turunkan ekspresi boolean untuk Sum (S) dan Carry-out (Cout) dari Full Adder (A, B, Cin).
Soal 6: Implementasi NAND Universal
Implementasikan F = AB + C hanya dengan gerbang NAND.
Bank Soal Multi-Kompleksitas & Kasus Terintegrasi
Referensi: Munir, R. (2020). Matematika Diskrit, Edisi 7, Bab 8 โ Aljabar Boolean & Gerbang Logika.
MUDAH Soal Dasar Gerbang Logika
B-M1: Tabel Kebenaran AND/OR/NOT
Buat tabel kebenaran untuk F = (A AND B) OR (NOT C). Berapa baris yang menghasilkan F=1?
B-M2: Hukum De Morgan
Sederhanakan NOT(A OR B) menggunakan De Morgan. Verifikasi dengan A=1, B=0.
B-M3: XOR Gate
Tentukan output XOR untuk semua kombinasi 2-input. Apa hubungan XOR dengan penjumlahan modulo 2?
B-M4: NAND Universal Gate
Implementasikan NOT(A) menggunakan hanya gerbang NAND. Kemudian implementasikan AND(A,B) dari NAND.
SEDANG Minimisasi & Penyederhanaan
B-S1: SOP dari Tabel Kebenaran
F(A,B,C) = 1 untuk minterm {1,3,5,7} (SOP minterms). Tulis ekspresi canonical SOP, lalu sederhanakan.
B-S2: Karnaugh Map 3 Variabel
Sederhanakan F menggunakan K-Map untuk minterm {0,1,4,5} dari 3 variabel (A,B,C).
B-S3: Half Adder Circuit
Rancang Half Adder: 2 input (A,B) โ 2 output (Sum, Carry). Tulis ekspresi Boolean dan gambar circuit-nya.
B-S4: Dual Expression (POS โ SOP)
Ubah F = AB + AC + BC ke POS (Product of Sums). Gunakan De Morgan ganda.
SULIT Minimisasi Kompleks
B-H1: Quine-McCluskey Method
Minimisasi F(A,B,C,D) dengan minterms {0,1,2,5,6,7,8,9,10,14} menggunakan metode Quine-McCluskey. Identifikasi prime implicants.
B-H2: Hazard Detection & Elimination
F = AB + A'C. Identifikasi static hazard ketika A berubah dengan B=C=1. Bagaimana mengeliminasi hazard tersebut?
B-H3: Implementasi dengan NOR Only
Implementasikan F = A + BC menggunakan HANYA gerbang NOR. Berapa minimum NOR gate yang diperlukan?
TERINTEGRASI Boolean + Minimisasi Rangkaian + Peta Karnaugh
B-T1: Boolean + Minimisasi โ Mux Implementation
Implementasikan 2-to-1 MUX: F = S'ยทA + SยทB. Minimisasi dengan K-Map 3 variabel (S,A,B). Implementasikan dengan 2 NAND gates + 1 NAND.
B-T2: Boolean + Rangkaian โ Full Adder
Rancang full adder 1-bit: masukan A, B, dan Cin; keluaran Sum dan Cout. Buat tabel kebenaran, turunkan ekspresi SOP, lalu sederhanakan dengan peta Karnaugh.
B-T3: Boolean + Peluang โ Probabilistic Circuit Failure
Sebuah circuit AND memiliki 3 gerbang seri (G1,G2,G3). Tiap gerbang gagal dengan probabilitas p=0.01 secara independen. Hitung P(circuit gagal) dan P(circuit benar). Berapa redundansi (parallel gates) untuk P(gagal)<10โปโถ?