Boolean algebra and Karnaugh maps
Diperkenalkan
14:55
RISC, Pipelines & Logika
Dua desainer chip menghadapi masalah yang sama: membuat program berjalan cepat. Satu berkata — bangun instruksi yang kuat, sehingga setiap instruksi melakukan banyak pekerjaan. Yang lain berkata — pertahankan…
Narasi bahasa Inggris · takarir bahasa Inggris dan 中文 yang dapat dipilih
In this lesson
| English | Makna |
|---|---|
| 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/ | Hukum absorpsi |
| 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$.
Match each Boolean law to what it says.
Kesulitan 2/5 · 140 koin + bonus kecil pada penyelesaian pertama hari ini
These laws let you simplify Boolean expressions algebraically before building the circuit.
By the absorption law, A + A·B simplifies to ____.
Kesulitan 1/5 · 100 koin + bonus kecil pada penyelesaian pertama hari ini
If A is true the whole expression is true whatever B is, and if A is false both terms are false. B cannot affect the result.
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 apa pun ditulis ulang menggunakan hanya gerbang NAND atau hanya gerbang NOR, dan chip yang dibangun dari satu gerbang berulang lebih murah diproduksi.

Dua ekspresi, satu tabel kebenaran
Boolean algebra
A·B, A+B, Ā …
Boolean algebra is just these gates written as expressions — compare the truth tables.
By De Morgan's law, $\overline{A \cdot B}$ equals:
Kesulitan 1/5 · 100 koin + bonus kecil pada penyelesaian pertama hari ini
Negate the whole, swap AND→OR, negate each operand: $\overline{A \cdot B} = \overline{A} + \overline{B}$.
Applying De Morgan's law to an expression involves which steps? Select semua that apply.
Kesulitan 2/5 · 140 koin + bonus kecil pada penyelesaian pertama hari ini
Negate the whole, swap the operator, negate each part. Order is irrelevant, since AND and OR are commutative.
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.
Simplify $A\cdot B + A\cdot\overline{B}$.
Kesulitan 1/5 · 100 koin + bonus kecil pada penyelesaian pertama hari ini
Factor out A: $A(B + \overline{B}) = A \cdot 1 = A$.
A·B + A·NOT B needs two ANDs, one NOT and one OR. How many gates does its simplified form need?
Kesulitan 2/5 · 140 koin + bonus kecil pada penyelesaian pertama hari ini
It simplifies to just A, so the output is the input and no gate is needed at all. Four gates saved.
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
A Karnaugh map simplifies a Boolean expression by:
Kesulitan 1/5 · 100 koin + bonus kecil pada penyelesaian pertama hari ini
You group adjacent 1s (in Gray-code order) into power-of-two rectangles; each group becomes a simplified term.
Why are the rows and columns of a Karnaugh map labelled 00, 01, 11, 10 rather than 00, 01, 10, 11?
Kesulitan 1/5 · 100 koin + bonus kecil pada penyelesaian pertama hari ini
Gray code order makes algebraic adjacency into physical adjacency. In counting order the grouping rule would simply not work.
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.
In a Karnaugh map, a larger group of adjacent 1s eliminates more variables, giving a simpler term (a group of 2 drops one variable, a group of 4 drops two).
Kesulitan 1/5 · 100 koin + bonus kecil pada penyelesaian pertama hari ini
You group adjacent 1s into power-of-two rectangles in Gray-code order; the bigger the group, the simpler the term it becomes.
Put the steps of simplifying with a Karnaugh map in order.
Kesulitan 3/5 · 200 koin + bonus kecil pada penyelesaian pertama hari ini
Gray code, ones, biggest groups, drop what changes, OR the terms. Use as few and as large groups as will cover every 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 mudah 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