Aljabar Boolean dan peta Karnaugh
| English | Bahasa Indonesia |
|---|---|
| Boolean algebra/ˈbuːlɪən ˈældʒɪbrə/ | Aljabar Boolean |
| De Morgan's laws/də ˈmɔːɡənz lɔːz/ | hukum De Morgan |
| Karnaugh map/ˈkɑːnɔː mæp/ | peta Karnaugh |
| truth table/truːθ ˈteɪbl/ | tabel kebenaran |
| absorption/əbˈsɔːpʃn/ | penyerapan |
| Gray code/ɡreɪ kəʊd/ | kode Gray |
Tesis magister yang membangun era digital
- Pada tahun 1937, seorang mahasiswa berusia 21 tahun bernama Claude Shannon menyadari bahwa relay telepon yang ia pelajari melakukan hal yang sama dengan aljabar yang diciptakan George Boole delapan puluh tahun sebelumnya untuk penalaran tentang benar dan salah.
- Jika sakelar adalah variabel Boolean, maka sirkuit adalah ekspresi, dan penyederhanaan ekspresi tersebut menghapus gerbang dari sirkuit. Gerbang lebih sedikit berarti lebih murah, lebih cepat, dan hemat daya.
- Tesisnya telah disebut sebagai tesis paling penting abad ini. Semua yang ada di halaman ini adalah satu ide itu yang digunakan sebagai alat.
- Pelajaran ini adalah aljabar Boolean, hukum De Morgan, dan peta Karnaugh yang melakukan pekerjaan yang sama secara visual.
Notasi dan hukum-hukumnya
+berarti OR,·berarti AND dan sering kali dibiarkan tersirat, dan garis atas (overbar) berarti NOT. Tabel kebenaran menggambarkan hal yang sama secara menyeluruh.- Identitas: $A + 0 = A$ dan $A \cdot 1 = A$. Null: $A + 1 = 1$ dan $A \cdot 0 = 0$.
- Idempoten: $A + A = A$. Inverse: $A + \overline{A} = 1$ dan $A \cdot \overline{A} = 0$.
- Absorpsi: $A + A\cdot B = A$, karena jika $A$ bernilai benar, seluruh ekspresi bernilai benar terlepas dari $B$.
Cocokkan setiap hukum Boolean dengan artinya.
Hukum-hukum ini memungkinkan Anda menyederhanakan ekspresi Boolean secara aljabar sebelum membuat sirkuit.
Menurut hukum penyerapan, A + A·B disederhanakan menjadi ____.
Jika A benar, seluruh ekspresi akan benar apa pun nilai B, dan jika A salah, kedua suku menjadi salah. B tidak dapat memengaruhi hasil.
Hukum De Morgan
- Hukum De Morgan adalah dua hukum yang akan ditanyakan dalam ujian:
- Resep dalam kata-kata: negasikan keseluruhan, tukar AND dan OR, negasikan setiap operand.
- Mereka penting secara praktis karena memungkinkan任何 ekspresi ditulis ulang menggunakan hanya gerbang NAND atau hanya gerbang NOR, dan chip yang dibangun dari satu jenis gerbang berulang lebih murah diproduksi.
Dua ekspresi, satu tabel kebenaran
Aljabar Boolean
A·B, A+B, Ā …
Aljabar Boolean hanyalah gerbang-gerbang ini yang ditulis sebagai ekspresi — bandingkan tabel kebenarannya.
Menurut hukum De Morgan, $\overline{A \cdot B}$ sama dengan:
Negasikan seluruhnya, tukar AND→OR, negasikan setiap operand: $\overline{A \cdot B} = \overline{A} + \overline{B}$.
Menerapkan hukum De Morgan pada suatu ekspresi melibatkan langkah-langkah mana? Pilih semua yang berlaku.
Negasikan seluruhnya, tukar operator, negasikan setiap bagian. Urutan tidak relevan, karena AND dan OR bersifat komutatif.
Contoh terpecahkan: sederhanakan, dan hitung gerbangnya
- Sederhanakan $Z = A\cdot B + A\cdot\overline{B}$ dan sebutkan penghematannya.
- Keluarkan $A$: $Z = A\cdot(B + \overline{B})$. Berdasarkan hukum invers $B + \overline{B} = 1$, sehingga $Z = A \cdot 1 = A$.
- Ekspresi asli membutuhkan dua gerbang AND, satu NOT, dan satu OR: empat gerbang. Ekspresi yang disederhanakan tidak memerlukan gerbang apa pun, hanya input $A$.
- Selalu akhiri dengan apa yang diperoleh dari penyederhanaan: gerbang lebih sedikit, sehingga sirkuit lebih murah, lebih cepat, dan hemat daya.
Sederhanakan $A\cdot B + A\cdot\overline{B}$.
Faktorkan keluar A: $A(B + \overline{B}) = A \cdot 1 = A$.
A·B + A·NOT B membutuhkan dua gerbang AND, satu NOT, dan satu OR. Berapa banyak gerbang yang dibutuhkan oleh bentuk sederhananya?
Ini disederhanakan menjadi A saja, sehingga output adalah input dan tidak ada gerbang yang diperlukan sama sekali. Empat gerbang terhemat.
Peta Karnaugh
- Peta Karnaugh menyederhanakan ekspresi dengan mengelompokkan angka 1 berdekatan yang diambil dari tabel kebenaran.
- Baris dan kolom diberi label dalam urutan kode Gray,
00, 01, 11, 10, agar sel berdekatan berbeda tepat dalam satu variabel. Itulah trik utamanya: membuat aljabar terlihat sebagai kedekatan. - Tempatkan angka 1 di setiap sel di mana outputnya 1, lalu temukan kelompok persegi panjang dari angka 1 yang sisinya merupakan pangkat dua: 1, 2, 4, 8. Kelompok dapat melingkari tepi-tepinya.
*Semakin besar persegi panjang, semakin sederhana istilahnya
Peta Karnaugh menyederhanakan ekspresi Boolean dengan cara:
Anda mengelompokkan angka 1 yang berdekatan (dalam urutan kode Gray) ke dalam persegi panjang berpangkat dua; setiap kelompok menjadi suku yang disederhanakan.
Mengapa baris dan kolom Peta Karnaugh diberi label 00, 01, 11, 10 alih-alih 00, 01, 10, 11?
Urutan kode Gray mengubah kedekatan aljabar menjadi kedekatan fisik. Dalam urutan penghitungan, aturan pengelompokan tidak akan berfungsi.
Membaca sebuah kelompok
- Di dalam kelompok, variabel yang tetap sama bertahan dalam istilah; variabel yang berubah hilang.
- Jadi, kelompok berisi 2 mengurangi satu variabel, kelompok berisi 4 mengurangi dua, dan kelompok berisi 8 mengurangi tiga. Semakin besar kelompok, semakin sederhana istilahnya.
- Tutupi setiap angka 1 menggunakan jumlah kelompok sedikit mungkin dan ukuran kelompok sebesar mungkin, kemudian gabungkan istilah-istilah kelompok dengan OR. Kelompok boleh tumpang tindih, dan tumpang tindih seringkali memungkinkan pembentukan kelompok yang lebih besar.
Dalam Peta Karnaugh, kelompok angka 1 yang lebih besar menghilangkan lebih banyak variabel, memberikan suku yang lebih sederhana (kelompok 2 mengurangi satu variabel, kelompok 4 mengurangi dua).
Anda mengelompokkan angka 1 yang berdekatan ke dalam persegi panjang berpangkat dua dalam urutan kode Gray; semakin besar kelompoknya, semakin sederhana suku yang terbentuk.
Susunlah langkah-langkah penyederhanaan menggunakan Peta Karnaugh secara berurutan.
Kode Gray, angka satu, kelompok terbesar, hilangkan yang berubah, ATAU istilah-istilah tersebut. Gunakan kelompok sekecil dan sebesar mungkin agar mencakup setiap 1.
Contoh terpecahkan: baca peta dua variabel
- Peta Karnaugh untuk $A$ dan $B$ memiliki angka 1 di sel-sel $\overline{A}B$ dan $AB$. Sederhanakan.
- Kedua angka 1 tersebut berdekatan: mereka berbagi kolom $B = 1$, sehingga mereka berkelompok sebagai persegi panjang berisi 2.
- Di dalam kelompok itu $B$ tetap bernilai 1 sepanjang waktu, sementara $A$ berubah dari 0 menjadi 1. Variabel yang berubah hilang.
- Jadi seluruh ekspresi hanyalah $Z = B$. Bandingkan dengan jumlah produk yang belum disederhanakan, $\overline{A}B + AB$, yang membutuhkan satu NOT, dua AND, dan satu OR.
Metode mana yang harus digunakan
- Aljabar Boolean bersifat presisi dan berlaku untuk berapa pun jumlah variabel, tetapi Anda harus mengenali hukum mana yang berlaku.
- Peta Karnaugh bersifat mekanis dan sulit untuk keliru bagi dua hingga empat variabel, yang merupakan materi ujian, dan peta ini menunjukkan pengelompokan terbesar secara langsung.
- Keduanya memberikan jawaban yang sama. Manfaat dari peta-K adalah bahwa penyederhanaan menjadi proses melihat, bukan mencari hukum.
⟦⟧ Nilai yang sering terlewat
- De Morgan adalah negasikan keseluruhan, tukar operator, negasikan setiap bagian. Mengubah hanya operator adalah jawaban klasik setengah benar.
- Baris peta-K harus dalam urutan kode Gray,
00, 01, 11, 10. Dalam urutan penghitungan biner, kedekatan menjadi salah dan pengelompokan gagal. - Ukuran kelompok adalah pangkat dua dan dapat melingkari tepi. Kelompok berisi tiga bukanlah kelompok yang valid.
- Sebutkan tujuan dari penyederhanaan: gerbang lebih sedikit, sehingga lebih murah, lebih cepat, dan hemat daya.
Anda telah memahaminya
- Aljabar Boolean menulis ulang ekspresi menjadi istilah yang lebih sedikit, sehingga sirkuit membutuhkan gerbang yang lebih sedikit
- De Morgan: $\overline{A + B} = \overline{A} \cdot \overline{B}$ dan $\overline{A \cdot B} = \overline{A} + \overline{B}$; absorpsi: $A + AB = A$; $A\cdot B + A\cdot\overline{B} = A$
- Peta Karnaugh mengelompokkan angka 1 berdekatan dari tabel kebenaran, dengan baris dan kolom dalam urutan kode Gray sehingga tetangga berbeda dalam satu variabel
- Variabel yang berubah di dalam kelompok menghilang, sehingga kelompok yang lebih besar menghasilkan istilah yang lebih sederhana: tutupi setiap angka 1 dengan jumlah kelompok sesedikit mungkin dan ukuran sebesarmungkin