Algoritma Quine-McCluskey

Quine-McCluskey merupakan salah satu metoda yang digunakan untuk menyederhanakan sebuah persamaan boolean. Fungsinya sama seperti Karnaugh Map (K-Map), hanya saja dengan metode Quine-McCluskey kita dapat menghitung lebih dari 6 variabel. Format tabelnya juga menjadikan lebih efisien untuk digunakan dalam algoritma komputer dan memberikan cara deterministik untuk memeriksa bahwa bentuk minimal sebuah fungsi boolean telah tercapai.
Metode ini secara umum terdiri dari 2 langkah, yaitu mencari semua prime implicant kemudian pilih EPI & sisa PI yang mengcover minterm sehingga didapat fungsi minimum.
Contoh soal:
Sederhanakan fungsi F(A,B,C) = Σm(0,1,2,3,6,7,8,9,14,15)
Jawab:
Langkah 1
Buat tabel semua minterm dari fungsi berdasarkan representasi binernya

Langkah 2
Susun minterm menjadi beberapa grup berdasarkan jumlah 1 dari representasi binernya

Langkah 3
Bandingkan setiap minterm dalam sebuah grup dengan setiap minterm grup di bawahnya. Jika keduanya hanya memiliki satu nilai bit yang berbeda, kombinasikan menjadi sebuah term baru pada list berikutnya dengan tanda (-) pada variabel yang dieliminasi.
Langkah 4
Ulangi langkah diatas untuk semua grup dari minterm dalam list, hasil dalam list baru disusun per grup juga. Pemberian tanda ceklis (v) dilakukan setelah membuat list berikutnya, dengan menceklis minterm yang ada kombinasinya di list selanjutnya.

Langkah 5
Bandingkan lagi grup minterm pada list baru, cari yang berbeda satu bit seperti langkah sebelumnya kemudian susun lagi hasilnya menjadi sebuah list baru. Lakukan terus langkah ini hingga tidak ada list baru yang dapat dibuat. Semua term yang tidak terceklis merupakan Prime Implicant.

Langkah 6
Pilih subset prime implicant paling minimal, yang dapat mengcover semua minterm dari fungsi booleannya.

Dari perhitungan di atas kita kita lihat bahwa PI2 dan PI4 merupakan EPI (Essential Prime Implicant) karena mengcover 8,9 dan 14,15 yang tidak memiliki PI lain yang mengcovernya. Dengan mengambil keduanya otomatis 0,1,6,7 telah tercover. Sisanya untuk mengcover 2,3 ambil dari PI1 atau PI3, sehingga kita dapatkan solusi dari soal ini:
F = PI1 + PI2 + PI4
= A’B’+ B’C’ + BC
Sumber: berkas-berkas catatan kuliah “Perancangan Rangkaian Sekuensial”. Ditemukan juga pada catatan kuliah “Rangkaian Logika & Teknik Digital” dan matakuliah “Matematika Diskrit”