Karnaugh Map (K-Map): Pengertian, Cara Menyederhanakan Fungsi Boolean dan Contohnya

Karnaugh Map (K-Map) adalah metode grafis yang digunakan untuk menyederhanakan fungsi Boolean dalam rangkaian logika digital. Metode ini membantu menentukan bentuk ekspresi Boolean yang lebih sederhana tanpa harus melakukan manipulasi aljabar Boolean secara berulang. Dalam dunia elektronika digital, penyederhanaan fungsi Boolean sangat penting untuk merancang rangkaian logika yang efisien. 

Dengan menggunakan Karnaugh Map, jumlah gerbang logika yang dibutuhkan dapat dikurangi sehingga rangkaian menjadi lebih sederhana, hemat komponen, dan lebih mudah dianalisis. Artikel ini membahas pengertian Karnaugh Map, fungsi dan manfaatnya, susunan tabel K-Map, aturan pengelompokan, serta contoh penyederhanaan fungsi Boolean menggunakan K-Map dua variabel, tiga variabel, dan empat variabel.

Karnaugh Map, yang sering disingkat menjadi K-Map, adalah metode penyederhanaan fungsi Boolean menggunakan tabel berbentuk kisi atau kotak-kotak yang mewakili seluruh kemungkinan kombinasi input biner. Metode ini diperkenalkan oleh Maurice Karnaugh pada tahun 1953 dan menjadi salah satu teknik yang banyak dipelajari dalam perancangan rangkaian logika digital. Setiap kotak pada Karnaugh Map mewakili satu kombinasi nilai variabel input. 

Nilai keluaran fungsi Boolean kemudian dimasukkan ke dalam kotak yang sesuai. Kotak-kotak yang memiliki nilai logika 1 dapat dikelompokkan berdasarkan aturan tertentu untuk memperoleh ekspresi Boolean yang lebih sederhana.

Sebagai contoh, sebuah fungsi Boolean dengan dua variabel input, yaitu A dan B, memiliki empat kemungkinan kombinasi input:

- A = 0 dan B = 0.

- A = 0 dan B = 1.

- A = 1 dan B = 0.

- A = 1 dan B = 1.

Keempat kombinasi tersebut dapat disusun dalam Karnaugh Map berukuran 2 × 2. Berbeda dengan penyederhanaan menggunakan aljabar Boolean yang mengandalkan identitas dan hukum-hukum logika, K-Map memanfaatkan pola visual untuk menemukan variabel yang dapat dihilangkan dari ekspresi Boolean.

Karnaugh Map memiliki peranan penting dalam analisis dan perancangan rangkaian logika kombinasional. Beberapa fungsi dan manfaatnya adalah sebagai berikut:

1. Menyederhanakan Ekspresi Boolean

Fungsi utama Karnaugh Map adalah menyederhanakan ekspresi Boolean yang diperoleh dari tabel kebenaran atau persamaan logika. Ekspresi yang awalnya memiliki banyak suku dapat diubah menjadi bentuk yang lebih ringkas. Penyederhanaan ini membantu mengurangi kompleksitas rangkaian digital.

2. Mengurangi Jumlah Gerbang Logika

Ekspresi Boolean yang lebih sederhana umumnya membutuhkan lebih sedikit gerbang logika, seperti AND, OR, dan NOT. Sebagai contoh, ekspresi Boolean:

Y = A·B + A·B̅

dapat disederhanakan menjadi:

Y = A

Dengan demikian, rangkaian yang semula membutuhkan beberapa gerbang logika dapat digantikan dengan hubungan langsung dari input A ke output Y, jika tidak ada persyaratan rangkaian lain yang harus dipenuhi.

3. Mempermudah Perancangan Rangkaian Logika

K-Map membantu perancang memahami hubungan antara kombinasi input dan output suatu rangkaian. Metode ini dapat digunakan dalam perancangan berbagai rangkaian logika kombinasional, seperti encoder, decoder, multiplexer, comparator digital, dan rangkaian pengendali sederhana.

4. Mengurangi Kompleksitas Rangkaian

Selain mengurangi jumlah gerbang logika, penyederhanaan fungsi Boolean juga dapat mengurangi jumlah koneksi dan tingkat kompleksitas rangkaian.

Namun, pengurangan jumlah gerbang tidak selalu menjamin konsumsi daya atau waktu tunda paling rendah. Hasil akhirnya tetap bergantung pada jenis gerbang logika, teknologi IC, serta kebutuhan perancangan.

Sebelum menggunakan K-Map, ada beberapa konsep dasar yang perlu dipahami, yaitu variabel Boolean, tabel kebenaran, minterm, dan hubungan antar-kotak pada peta Karnaugh.

1. Variabel Boolean

Variabel Boolean adalah variabel yang hanya memiliki dua kemungkinan nilai, yaitu 0 dan 1. Dalam rangkaian logika digital, nilai tersebut umumnya mewakili kondisi logika LOW dan HIGH. Contoh variabel Boolean adalah A, B, C, dan D. Operasi dasar Boolean meliputi:

- AND (·): menghasilkan 1 jika semua input bernilai 1.

- OR (+): menghasilkan 1 jika minimal satu input bernilai 1.

- NOT (garis di atas variabel): membalik nilai logika input.

Sebagai contoh, A̅ menunjukkan komplemen dari A. Jika A = 0, maka A̅ = 1. Sebaliknya, jika A = 1, maka A̅ = 0.

2. Tabel Kebenaran

Tabel kebenaran adalah tabel yang menunjukkan keluaran suatu fungsi logika untuk setiap kemungkinan kombinasi input. Jumlah kombinasi input untuk fungsi Boolean dengan n variabel adalah:

Jumlah kombinasi = 2ⁿ

Keterangan:

- n adalah jumlah variabel input.

- 2ⁿ adalah jumlah kombinasi input yang mungkin.

Sebagai contoh, fungsi dengan dua variabel memiliki 2² = 4 kombinasi. Fungsi dengan tiga variabel memiliki 2³ = 8 kombinasi, sedangkan fungsi dengan empat variabel memiliki 2⁴ = 16 kombinasi.

Tabel kebenaran menjadi salah satu sumber utama untuk mengisi nilai pada Karnaugh Map.

3. Minterm

Minterm adalah suku Boolean yang memuat seluruh variabel input, masing-masing dalam bentuk asli atau komplemennya, dan bernilai 1 hanya untuk satu kombinasi input tertentu. Untuk fungsi dengan dua variabel, contoh minterm adalah:

- m₀ = A̅·B̅

- m₁ = A̅·B

- m₂ = A·B̅

- m₃ = A·B

Penulisan fungsi Boolean dalam bentuk penjumlahan minterm atau Sum of Products (SOP) sering digunakan sebagai dasar pengisian K-Map. Sebagai contoh:

F(A,B) = Σm(1,3)

Artinya, fungsi F memiliki nilai 1 pada minterm nomor 1 dan 3.

4. Urutan Gray Code pada Karnaugh Map

Salah satu ciri penting Karnaugh Map adalah penggunaan Gray Code untuk mengatur urutan kombinasi variabel. Pada Gray Code, dua kombinasi yang bersebelahan hanya berbeda pada satu bit. Sebagai contoh, urutan dua bit pada K-Map adalah 00, 01, 11, 10. Urutan tersebut berbeda dari urutan biner biasa, yaitu 00, 01, 10, 11. Penggunaan Gray Code memastikan bahwa setiap kotak yang bersebelahan mewakili kombinasi input yang hanya berbeda pada satu variabel. Perbedaan satu variabel inilah yang memungkinkan penyederhanaan ekspresi Boolean.

Ukuran Karnaugh Map bergantung pada jumlah variabel input yang digunakan. Semakin banyak variabel, semakin banyak pula kotak yang diperlukan.

1. Karnaugh Map Dua Variabel

K-Map dua variabel digunakan untuk menyederhanakan fungsi Boolean dengan dua input, yaitu A dan B. Peta ini memiliki empat kotak yang mewakili kombinasi 00, 01, 11, dan 10. Susunannya adalah sebagai berikut.

Setiap kotak mewakili satu minterm. Sebagai contoh, kotak m₀ mewakili A = 0 dan B = 0, sedangkan kotak m₃ mewakili A = 1 dan B = 1.

2. Karnaugh Map Tiga Variabel

K-Map tiga variabel digunakan untuk fungsi Boolean dengan input A, B, dan C. Peta ini memiliki delapan kotak. Dua variabel ditempatkan pada kolom, sedangkan satu variabel lainnya ditempatkan pada baris.

Urutan kolom mengikuti Gray Code, yaitu 00, 01, 11, dan 10. Perhatikan bahwa m₂ berada di sebelah m₃, bukan di sebelah m₁. Hal ini terjadi karena susunan K-Map harus mempertahankan hubungan satu bit berbeda antara setiap kotak yang bersebelahan.

3. Karnaugh Map Empat Variabel

K-Map empat variabel digunakan untuk fungsi Boolean dengan input A, B, C, dan D. Peta ini memiliki 16 kotak yang disusun dalam empat baris dan empat kolom.

Baris dan kolom sama-sama mengikuti Gray Code. Dengan susunan tersebut, kotak yang bersebelahan secara horizontal maupun vertikal hanya berbeda pada satu variabel. Perlu diperhatikan bahwa kotak di sisi paling kiri dan paling kanan saling bersebelahan, demikian juga kotak di baris paling atas dan paling bawah. Sifat ini disebut adjacency wrap-around dan menjadi salah satu aturan penting dalam pengelompokan K-Map.

Pengelompokan merupakan tahap utama dalam penyederhanaan fungsi Boolean menggunakan Karnaugh Map. Tujuannya adalah menemukan variabel yang dapat dihilangkan dari setiap kelompok.

1. Kelompok Harus Berjumlah Pangkat Dua

Jumlah kotak dalam setiap kelompok harus berupa pangkat dua, yaitu:

- 1 kotak.

- 2 kotak.

- 4 kotak.

- 8 kotak.

- 16 kotak, jika seluruh kotak pada K-Map empat variabel dapat dikelompokkan.

Kelompok yang terdiri dari tiga, lima, enam, atau tujuh kotak tidak diperbolehkan sebagai satu kelompok.

2. Kelompokkan Kotak yang Berisi Nilai 1

Untuk menyederhanakan fungsi Boolean dalam bentuk SOP, kotak yang berisi nilai 1 dikelompokkan berdasarkan aturan K-Map. Kelompok dapat berbentuk horizontal atau vertikal. Pengelompokan juga dapat melintasi tepi peta karena sisi yang berlawanan dianggap saling bersebelahan. Kotak yang hanya bersentuhan secara diagonal tidak dianggap bersebelahan.

3. Utamakan Kelompok yang Lebih Besar

Semakin besar kelompok, semakin banyak variabel yang dapat dihilangkan. Sebagai contoh:

- Kelompok 2 kotak dapat menghilangkan satu variabel.

- Kelompok 4 kotak dapat menghilangkan dua variabel.

- Kelompok 8 kotak dapat menghilangkan tiga variabel.

Oleh karena itu, kelompokkan kotak sebanyak mungkin selama aturan K-Map tetap terpenuhi.

4. Semua Nilai 1 Harus Terwakili

Setiap kotak bernilai 1 harus tercakup dalam setidaknya satu kelompok. Satu kotak boleh menjadi bagian dari lebih dari satu kelompok jika diperlukan untuk menghasilkan ekspresi yang lebih sederhana. Namun, pengelompokan berlebihan yang tidak membantu menyederhanakan fungsi sebaiknya dihindari.

5. Gunakan Don't Care Jika Tersedia

Dalam beberapa rangkaian, terdapat kombinasi input yang tidak pernah digunakan atau keluarannya tidak dipedulikan. Kondisi tersebut dapat dinyatakan sebagai don't care dan biasanya ditandai dengan X. Nilai X boleh dianggap sebagai 1 atau 0 sesuai kebutuhan penyederhanaan. Penggunaan don't care bersifat opsional. Jika memasukkan X ke dalam kelompok tidak menghasilkan penyederhanaan yang lebih baik, nilai tersebut dapat diabaikan.

Untuk mendapatkan hasil yang benar, penyederhanaan fungsi Boolean sebaiknya dilakukan secara berurutan.

1. Menentukan Fungsi Boolean

Langkah pertama adalah menentukan fungsi Boolean yang akan disederhanakan. Fungsi dapat diperoleh dari persamaan Boolean, tabel kebenaran, atau daftar minterm. Sebagai contoh:

F(A,B,C) = Σm(1,3,5,7)

Fungsi tersebut memiliki keluaran 1 pada minterm 1, 3, 5, dan 7.

2. Membuat Tabel Karnaugh Map

Karena fungsi memiliki tiga variabel, gunakan K-Map tiga variabel yang terdiri dari delapan kotak. Masukkan nilai 1 ke dalam kotak m₁, m₃, m₅, dan m₇. Kotak lainnya diisi dengan nilai 0.

3. Mengelompokkan Kotak Bernilai 1

Selanjutnya, kelompokkan empat kotak bernilai 1 menjadi satu kelompok.

Kotak m₁ dan m₃ berada pada baris A = 0, sedangkan m₅ dan m₇ berada pada baris A = 1. Keempat kotak tersebut membentuk satu kelompok vertikal yang mencakup semua baris dan kolom BC bernilai 01 serta 11. Dengan kata lain, kelompok tersebut mencakup seluruh kombinasi ketika C = 1.

4. Menentukan Variabel yang Tetap

Setelah pengelompokan, perhatikan nilai setiap variabel dalam kelompok. Variabel yang berubah dari 0 menjadi 1 atau sebaliknya dapat dihilangkan. Variabel yang tetap dipertahankan dalam ekspresi hasil penyederhanaan. Pada kelompok m₁, m₃, m₅, dan m₇:

- Variabel A berubah dari 0 menjadi 1.

- Variabel B berubah dari 0 menjadi 1.

- Variabel C selalu bernilai 1.

Dengan demikian, variabel A dan B dihilangkan, sedangkan C tetap dipertahankan.

5. Menuliskan Hasil Penyederhanaan

Berdasarkan hasil pengelompokan, fungsi Boolean yang semula memiliki empat minterm dapat disederhanakan menjadi:

F = C

Hasil tersebut menunjukkan bahwa fungsi hanya bergantung pada variabel C. Nilai A dan B tidak lagi memengaruhi keluaran setelah penyederhanaan.

Untuk memahami penerapan K-Map secara lebih sederhana, perhatikan contoh di bawah ini. 

Diketahui fungsi Boolean:

F(A,B) = Σm(1,2,3)

Fungsi tersebut memiliki keluaran 1 pada minterm 1, 2, dan 3.

1. Membuat K-Map

Masukkan nilai minterm ke dalam tabel berikut.

Kotak m₁, m₂, dan m₃ bernilai 1.

2. Melakukan Pengelompokan

Tiga kotak bernilai 1 tidak boleh digabungkan menjadi satu kelompok karena jumlah kotaknya bukan pangkat dua. Oleh sebab itu, gunakan dua kelompok yang masing-masing berisi dua kotak:

- Kelompok pertama terdiri dari m₁ dan m₃ pada kolom B = 1.

- Kelompok kedua terdiri dari m₂ dan m₃ pada baris A = 1.

Minterm m₃ digunakan dalam kedua kelompok. Pengulangan tersebut diperbolehkan selama membantu mencakup seluruh kotak bernilai 1.

3. Menentukan Persamaan Boolean

Pada kelompok pertama, nilai B tetap 1, sedangkan A berubah. Hasil kelompok pertama adalah B. Pada kelompok kedua, nilai A tetap 1, sedangkan B berubah. Hasil kelompok kedua adalah A. Kedua hasil kelompok digabungkan menggunakan operasi OR. Dengan demikian, fungsi Boolean yang telah disederhanakan adalah:

F = A + B

Artinya, keluaran F akan bernilai 1 jika A atau B bernilai 1, atau jika keduanya bernilai 1.

Selanjutnya, perhatikan contoh fungsi Boolean dengan tiga variabel.

Diketahui:

F(A,B,C) = Σm(0,2,4,6)

Fungsi tersebut memiliki keluaran 1 pada minterm 0, 2, 4, dan 6.

1. Mengisi K-Map Tiga Variabel

Masukkan nilai 1 ke dalam kotak sesuai nomor minterm.

Kotak m₀ dan m₂ berada pada baris A = 0, sedangkan m₄ dan m₆ berada pada baris A = 1.

2. Mengelompokkan Empat Kotak

Keempat kotak bernilai 1 membentuk kelompok empat kotak melalui sisi kiri dan kanan K-Map. Kelompok ini sah karena sisi paling kiri dan paling kanan dianggap bersebelahan.

3. Menentukan Variabel yang Tetap

Pada keempat kotak tersebut:

- Variabel A berubah dari 0 menjadi 1.

- Variabel B berubah dari 0 menjadi 1.

- Variabel C selalu bernilai 0.

Variabel A dan B dihilangkan karena berubah. Variabel C dipertahankan dalam bentuk komplemen karena selalu bernilai 0. Hasil penyederhanaannya adalah F = C̅. Contoh ini menunjukkan bahwa pengelompokan K-Map tidak hanya dilakukan pada kotak yang terlihat berdampingan di tengah peta, tetapi juga dapat memanfaatkan hubungan antar-tepi.

K-Map empat variabel memiliki 16 kotak sehingga pengelompokannya lebih kompleks dibandingkan K-Map dua atau tiga variabel. Perhatikan fungsi Boolean berikut:

F(A,B,C,D) = Σm(0,1,2,3,8,9,10,11)

1. Mengisi K-Map Empat Variabel

Masukkan nilai 1 pada minterm yang tercantum dalam fungsi.

2. Membentuk Kelompok Delapan Kotak

Delapan kotak bernilai 1 pada baris AB = 00 dan AB = 10 dapat dikelompokkan menjadi satu kelompok berukuran delapan. Baris AB = 00 dan AB = 10 saling bersebelahan karena peta menggunakan Gray Code dan memiliki hubungan melingkar pada sisi atas dan bawah.

3. Menentukan Ekspresi Boolean

Dalam kelompok tersebut, variabel A berubah dari 0 menjadi 1. Variabel B selalu bernilai 0, sedangkan C dan D berubah-ubah. Dengan demikian:

- A dihilangkan karena berubah.

- B dipertahankan sebagai B̅ karena selalu 0.

- C dihilangkan karena berubah.

- D dihilangkan karena berubah.

Hasil penyederhanaannya adalah:

F = B̅

Fungsi yang semula terdiri dari delapan minterm dapat disederhanakan menjadi satu variabel komplemen saja.

Meskipun Karnaugh Map mempermudah penyederhanaan fungsi Boolean, beberapa kesalahan masih sering terjadi, terutama ketika menentukan posisi minterm dan membentuk kelompok.

1. Menggunakan Urutan Biner Biasa

Kesalahan yang sering ditemukan adalah menempatkan kombinasi kolom dalam urutan 00, 01, 10, 11. Susunan tersebut tidak sesuai dengan aturan Gray Code pada K-Map. Urutan yang benar adalah 00, 01, 11, 10 agar kotak-kotak yang bersebelahan hanya berbeda satu bit.

2. Membentuk Kelompok dengan Jumlah Kotak yang Tidak Sesuai

Kelompok berisi tiga atau lima kotak tidak diperbolehkan. Jumlah kotak dalam satu kelompok harus berupa pangkat dua, seperti 1, 2, 4, atau 8.

3. Mengabaikan Hubungan Antar-Tepi

Kotak pada sisi kiri dan kanan serta sisi atas dan bawah dapat saling bersebelahan. Jika hubungan ini diabaikan, hasil penyederhanaan mungkin menjadi kurang optimal.

4. Mempertahankan Variabel yang Berubah

Hanya variabel yang memiliki nilai tetap di seluruh kotak dalam suatu kelompok yang dipertahankan. Variabel yang berubah antara 0 dan 1 harus dihilangkan dari suku Boolean kelompok tersebut.

5. Tidak Mencakup Semua Kotak Bernilai 1

Setiap kotak bernilai 1 harus tercakup setidaknya satu kali. Jika ada kotak bernilai 1 yang tidak masuk ke kelompok mana pun, ekspresi hasil penyederhanaan tidak akan mewakili fungsi Boolean awal secara lengkap.

Karnaugh Map dan aljabar Boolean sama-sama digunakan untuk menyederhanakan fungsi logika digital, tetapi keduanya memiliki pendekatan yang berbeda.

Untuk fungsi dengan dua hingga empat variabel, K-Map sering menjadi pilihan yang praktis karena pola penyederhanaannya mudah dilihat.

Sementara itu, aljabar Boolean tetap berguna untuk memeriksa hasil K-Map, menyederhanakan persamaan secara simbolis, dan menangani fungsi yang memiliki banyak variabel.

Karnaugh Map tidak hanya digunakan dalam pembelajaran teori digital, tetapi juga membantu proses perancangan rangkaian nyata.

1. Rangkaian Logika Kombinasional

K-Map dapat digunakan untuk menyederhanakan fungsi keluaran rangkaian kombinasional, yaitu rangkaian yang keluarannya bergantung pada kombinasi input saat itu. Contohnya meliputi rangkaian encoder, decoder, multiplexer, dan comparator digital.

2. Rangkaian Pengendali

Pada rangkaian pengendali, beberapa kondisi input dapat menentukan apakah suatu keluaran harus aktif atau tidak. Fungsi Boolean dari kondisi tersebut dapat disederhanakan menggunakan K-Map agar implementasi logikanya lebih ringkas.

3. Perancangan Menggunakan Gerbang Logika

Hasil penyederhanaan K-Map dapat diimplementasikan menggunakan gerbang AND, OR, dan NOT, maupun menggunakan kombinasi gerbang NAND atau NOR.

Pemilihan jenis gerbang bergantung pada kebutuhan rangkaian, ketersediaan IC, dan karakteristik implementasi yang diinginkan.

Baca juga: Comparator Digital: Pengertian, Cara Kerja, Jenis dan Contoh Rangkaian Pembanding Biner