Peta Karnaugh, Tabel Kebenaran, dan Ekspresi Boolean

Siapa yang Mengembangkan Peta Karnaugh?

Maurice Karnaugh, seorang insinyur telekomunikasi, mengembangkan peta Karnaugh di Bell Labs pada tahun 1953 saat merancang sirkuit switching telepon berbasis logika digital.

Penggunaan Peta Karnaugh

Sekarang kita telah mengembangkan peta Karnaugh dengan bantuan diagram Venn, mari kita gunakan. Peta Karnaugh mengurangi fungsi logika lebih cepat dan mudah dibandingkan dengan aljabar Boolean. Dengan mengurangi yang kami maksud menyederhanakan, mengurangi jumlah gerbang dan input.

Kami ingin menyederhanakan logika ke biaya terendah bentuk untuk menghemat biaya dengan penghapusan komponen. Kami mendefinisikan biaya terendah sebagai jumlah gerbang terendah dengan jumlah input per gerbang terendah.

Diberi pilihan, sebagian besar siswa melakukan penyederhanaan logika dengan peta Karnaugh daripada aljabar Boolean setelah mereka mempelajari alat ini.

Kami menunjukkan lima item individual di atas, yang hanya merupakan cara berbeda untuk merepresentasikan hal yang sama:fungsi logika digital 2-input arbitrer. Pertama adalah logika relay tangga, kemudian gerbang logika, tabel kebenaran, peta Karnaugh, dan persamaan Boolean.

Intinya adalah bahwa semua ini setara. Dua masukan A dan B dapat mengambil nilai 0 atau 1 , tinggi atau rendah, terbuka atau tertutup, Benar atau Salah, tergantung kasusnya. Ada 2 ² =4 kombinasi input menghasilkan output. Ini berlaku untuk kelima contoh.

Keempat keluaran ini dapat diamati pada lampu dalam logika tangga relai, pada probe logika pada diagram gerbang. Keluaran ini dapat dicatat dalam tabel kebenaran, atau di peta Karnaugh. Lihatlah peta Karnaugh sebagai tabel kebenaran yang disusun ulang.

Output dari persamaan Boolean dapat dihitung dengan hukum aljabar Boolean dan ditransfer ke tabel kebenaran atau peta Karnaugh.

Manakah dari lima deskripsi logika yang setara yang harus kita gunakan? Yang paling berguna untuk menyelesaikan tugas.

Keluaran dari tabel kebenaran sesuai dengan basis satu-ke-satu dengan entri peta Karnaugh. Mulai dari bagian atas tabel kebenaran, input A=0, B=0 menghasilkan output .

Perhatikan bahwa keluaran yang sama ini ditemukan di peta Karnaugh di alamat sel A=0, B=0, sudut kiri atas peta-K di mana baris A=0 dan kolom B=0 berpotongan. Output tabel kebenaran lainnya , , dari input AB=01, 10, 11 ditemukan di lokasi K-map yang sesuai.

Di bawah ini, kami menunjukkan daerah 2-sel yang berdekatan di peta-K 2-variabel dengan bantuan diagram Venn persegi panjang sebelumnya seperti daerah Boolean.

Sel dan berdekatan di K-map sebagai elips di paling kiri K-map di bawah. Merujuk pada tabel kebenaran sebelumnya, tidak demikian. Ada entri tabel kebenaran lain (β) di antara mereka. Yang membawa kita ke inti dari pengorganisasian K-map ke dalam array persegi, sel dengan variabel Boolean yang sama harus dekat satu sama lain untuk menghadirkan pola yang melompat ke arah kita.

Untuk sel dan mereka memiliki variabel Boolean B’ bersama. Kami mengetahui ini karena B=0 (sama seperti B’ ) untuk kolom di atas sel dan . Bandingkan ini dengan diagram Venn persegi di atas K-map.

Baris penalaran yang sama menunjukkan bahwa dan memiliki Boolean B (B=1) persamaan. Kemudian, dan memiliki Boolean A’ (A=0) yang sama. Akhirnya, dan memiliki Boolean A (A=1) sama. Bandingkan dua peta terakhir dengan diagram Venn persegi tengah.

Untuk meringkas, kami mencari kesamaan variabel Boolean di antara sel. Peta Karnaugh diatur sehingga kita dapat melihat kesamaan itu. Mari kita coba beberapa contoh.

Contoh

Contoh:

Pindahkan isi tabel kebenaran ke peta Karnaugh di atas.

Solusi:

Tabel kebenaran berisi dua 1 S. K-map harus memiliki keduanya. temukan 1 first pertama pada baris ke-2 tabel kebenaran di atas.

• perhatikan tabel kebenaran alamat AB
• menemukan sel di K-map yang memiliki alamat yang sama
• menempatkan 1 di sel itu

Ulangi proses untuk 1 di baris terakhir tabel kebenaran.

Contoh:

Untuk peta Karnaugh pada soal di atas, tuliskan ekspresi Boolean. Solusi ada di bawah.

Solusi:

Cari sel yang berdekatan, yaitu di atas atau di samping sel. Sel diagonal tidak berdekatan. Sel yang berdekatan akan memiliki satu atau lebih variabel Boolean yang sama.

• Kelompokkan (lingkari) keduanya 1 s di kolom
• Temukan variabel atas dan/atau sisi yang sama untuk grup, Tulis ini sebagai hasil Boolean. Ini adalah B dalam kasus kami.
• Abaikan variabel yang tidak sama untuk grup sel. Dalam kasus kami, A bervariasi, apakah 1 dan 0, abaikan Boolean A.
• Abaikan variabel apa pun yang tidak terkait dengan sel yang berisi 1s. B’ tidak memiliki orang di bawahnya. Abaikan B'
• Hasil Keluar =B

Ini mungkin lebih mudah dilihat dengan membandingkan diagram Venn di sebelah kanan, khususnya B kolom.

Contoh:

Tulis ekspresi Boolean untuk peta Karnaugh di bawah ini.

Solusi: (atas)

• Kelompokkan (lingkari) dua 1 di baris
• Temukan variabel yang sama untuk grup, Keluar =A’

Contoh:

Untuk tabel Kebenaran di bawah ini, transfer output ke Karnaugh, lalu tulis ekspresi Boolean untuk hasilnya.

Solusi:

Transfer 1 s dari lokasi di tabel Kebenaran ke lokasi yang sesuai di K-map.

• Kelompokkan (lingkari) dua angka 1 di kolom di bawah B=1
• Kelompokkan (lingkari) dua angka 1 di kanan baris A=1
• Tulis istilah produk untuk grup pertama =B
• Tulis istilah produk untuk grup kedua =A
• Tuliskan Jumlah Produk dari dua suku di atas Output =A+B

Solusi K-map di tengah adalah solusi biaya paling sederhana atau terendah. Solusi yang kurang diinginkan ada di paling kanan. Setelah mengelompokkan keduanya 1 s, kami membuat kesalahan dengan membentuk grup 1-sel. Alasan mengapa ini tidak diinginkan adalah karena:

• Sel tunggal memiliki suku produk AB’
• Solusi yang sesuai adalah Keluaran =AB’ + B
• Ini bukan solusi paling sederhana

Cara mengambil single ini 1 adalah membentuk kelompok yang terdiri dari dua orang dengan 1 di sebelah kanannya seperti yang ditunjukkan pada garis bawah peta-K tengah, meskipun 1 ini telah disertakan dalam grup kolom (B ). Kami diizinkan untuk menggunakan kembali sel untuk membentuk kelompok yang lebih besar. Sebenarnya, ini diinginkan karena mengarah pada hasil yang lebih sederhana.

Kita perlu menunjukkan bahwa salah satu dari solusi di atas, Output atau Output Salah, secara logis benar. Kedua sirkuit menghasilkan output yang sama. Ini adalah masalah sirkuit sebelumnya menjadi solusi biaya terendah.

Contoh:

Isi peta Karnaugh untuk ekspresi Boolean di bawah ini, lalu tulis ekspresi Boolean untuk hasilnya.

Solusi: (atas)

Ekspresi Boolean memiliki tiga suku produk. Akan ada 1 dimasukkan untuk setiap istilah produk. Padahal, secara umum, jumlah 1 s per istilah produk bervariasi dengan jumlah variabel dalam istilah produk dibandingkan dengan ukuran K-map.

Istilah produk adalah alamat sel tempat 1 dimasukkan. Istilah produk pertama, A'B , sesuai dengan 01 sel di peta. Sebuah 1 dimasukkan ke dalam sel ini. Dua istilah P lainnya dimasukkan dengan total tiga 1

Selanjutnya, lanjutkan dengan mengelompokkan dan mengekstrak hasil yang disederhanakan seperti pada soal tabel kebenaran sebelumnya.

Contoh:

Sederhanakan diagram logika di bawah ini.

Solusi: (Gambar di bawah)

• Tuliskan ekspresi Boolean untuk diagram logika asli seperti yang ditunjukkan di bawah ini
• Transfer istilah produk ke peta Karnaugh
• Bentuk kelompok sel seperti pada contoh sebelumnya
• Tulis ekspresi Boolean untuk grup seperti pada contoh sebelumnya
• Gambarlah diagram logika yang disederhanakan

Contoh: Sederhanakan diagram logika di bawah ini.

Solusi:

• Tuliskan ekspresi Boolean untuk diagram logika asli yang ditunjukkan di atas
• Transfer istilah produk ke peta Karnaugh.
• Tidak mungkin membentuk kelompok.
• Tidak ada penyederhanaan yang mungkin; biarkan apa adanya.

Tidak ada penyederhanaan logika yang mungkin untuk diagram di atas. Ini terkadang terjadi. Baik metode peta Karnaugh maupun aljabar Boolean tidak dapat menyederhanakan logika ini lebih jauh.

Kami menunjukkan simbol skema Eksklusif-ATAU di atas; Namun, ini bukan penyederhanaan logis. Itu hanya membuat diagram skematik terlihat lebih bagus.

Karena logika Exclusive-OR tidak dapat disederhanakan dan digunakan secara luas, logika ini disediakan oleh pabrikan sebagai sirkuit terpadu dasar (7486).

LEMBAR KERJA TERKAIT:

• Lembar Kerja Pemetaan Karnaugh
• Lembar Kerja Aljabar Boolean
• Lembar Kerja Gerbang Logika Dasar