Penyederhanaan Fungsi Boolean

Ada tiga metode yang dapat digunakan untuk menyederhanakan fungsi Boolean :

1. Secara aljabar
2. Metode peta Karnaugh
3. Metode Tabulasi (Quine-Mc.Cluskey)

1. Secara aljabar, menggunakan hukum-hukum aljabar Boolean,

Contoh : sederhanakanlah fungsi Boolean f(x, y, z) = xz’ + y’z + xyz’

Penyelesaian :
f(x, y, z) = xz’ + y’z + xyz’
= xz’ • 1 + y’z + xyz’---> (Hukum identitas)
= xz’ (1 + y) + y’z    --->  (Hukum distributif)
= xz’ • 1 + y’z          --->  (Hukum dominansi)
= xz’  +  y’z             --->  (Hukum identitas)

Pada soal diatas fungsi Boolean diminimumkan dengan trik manipulasi aljabar dengan prosedur yang cut-and-try yang memanfaatkan postulat, hukum-hukum dasar, dan metode manipulasi lain yang sudah dikenal. Untuk tiga variabel saja hukum yang dipakai sudah tiga.

Bagaimana untuk enam varibel ke atas? Terlebih lagi tidak ada aturan khusus yang harus diikuti yang akan menjamin menuju ke jawaban akhir. Maka metode aljabar hanya cocok untuk menyederhanakan fungsi Boolean yang jumlah variabelnya kecil misalnya 4 variabel dan akan sangat sulit bila variabelnya lebih dari 4.

2. Metode peta Karnaugh

Contoh : carilah fungsi sederhana dari f(v, w, x, y, z) = (0, 2, 4, 6, 9, 11, 13, 15, 17, 21, 25, 27, 29, 31).
Penyelesaian :
Peta Karnaugh dari fungsi tersebut adalah :

Fungsi minimasi: f(v, w, x, y, z) = wz + v’w’z’ + vy’z

Pada soal diatas peta Karnaugh untuk lima variabel dibuat dengan anggapan ada dua buah peta empat variabel yang disambungkan, demikian juga untuk enam variabel. Untuk fungsi Boolean 6 variabel pengerjaan penyederhanaan dengan peta Karnaugh sudah mulai rumit.

Bagaimana untuk variabel 6 ke atas ? Maka akan semakin rumit, sebab ukuran peta bertambah besar. Selain itu, metode peta Karnaugh lebih sulit diprogram dengan komputer karena diperlukan pengamatan visual untuk mengidentifikasi minterm-minterm yang akan dikelompokkan.

Untuk itu diperlukan metode penyerderhanaan yang lain yang dapat diprogram dan dapat digunakan untuk fungsi Boolean dengan sembarang jumlah peubah. Metode alternatif tersebut adalah metode Quine-McCluskey.

3. Metode Tabulasi (Quine-Mc.Cluskey)   

Dengan metoda Peta Karnaugh, penyelesaian persamaan dengan lebih dari enam variabel adalah kompleks. Metoda Quine-Mc Cluskey atau metode tabulasi membantu penyelesaian tersebut.

Metode tabulasi ini terdiri atas dua bagian, yaitu :

1. Menentukan term-term sebagai kandidat (prime-implicant)
2. Memilih prime-implicant untuk mendapatkan ekpresi dengan jumlah literal sedikit.

Langkah-Langkah Metode Quine-Mccluskey Untuk Menyederhanakan Ekspresi Boolean Dalam Bentuk SOP

Metode Quine-McCluskey memiliki langkah-langkah untuk meyelesaikannya. Langkah-langkah tersebut adalah sebagai berikut:

1. Nyatakan tiap minterm dalam n peubah menjadi string bit yang panjangnya n, yang dalam hal ini peubah komplemen dinyatakan dengan  ‘0’, peubah yang bukan komplemen dengan  ‘1’.
2. Kelompokkan tiap minterm berdasarkan jumlah ‘1’ yang dimilikinya.
3. Kombinasikan minterm dengan n peubah dengan kelompok lain yang jumlah ‘1’nya berbeda satu, sehingga diperoleh bentuk prima (prime implicant) yang terdiri dari n-1 peubah.  Minterm yang dikombinasikan diberi tanda “v”.
4. Kombinasikan minterm dalam n-1 peubah dengan kelompok lain yang jumlah ‘1’-nya berbeda satu, sehingga diperoleh bentuk prima yang terdiri dari n-2 peubah.
5. Teruskan langkah 4 sampai diperoleh bentuk prima yang sesederhana mungkin.
6. Ambil semua bentuk prima yang tidak bertanda “v”.  Buatah tabel baru yang memperlihatkan mintrem dari ekspresi Boolean semula yang dicakup oleh bentuk prima tersebut (tandai dengan “x”).  Setiap minterm harus dicakup oleh paling sedikit satu buah bentuk prima.
7. Pilih bentuk prima yang memiliki jumlah literal paling sedikit namun mencakup sebanyak mungkin minterm dari ekspresi Boolean semula.  

Hal ini dapat dilakukan dengan cara berikut:

• Tandai kolom-kolom yang mempunyai satu tanda “x” dengan tanda “*”, lalu beri tanda “v” di sebelah kiri bentuk prima yang berasosiasi dengan tanda “*” tersebut.  Bentuk prima ini telah dipilih untuk fungsi Boolean sederhana.
• Untuk setiap bentuk prima yang ditandai dengan “v”, beri tanda minterm yang dicakup oleh bentuk prima tersebut dnegan tanda “v” (di baris bawah setelah “*”).
• Periksa apakah masih ada minterm yang belum dicakup oleh bentuk prima terpilih.  Jika ada, pilih dari bentuk prima yang tersisa yang mencakup sebanyak mungkin minterm tersebut.  Beri tanda “v” bentuk prima yang dipilih itu serta minterm yang dicakupnya.
• Ulangi langkah c sampai seluruh minterm sudah dicakup oleh semua bentuk prima.

Contoh Penerapan Metode Quine-Mc.Cluskey

Diketahui fungsi Boolean berikut ini : F = (0,1,2,8,10,11,14,15)

l. Menentukan Prime-Implican
langkah-langkah penyelesaian :

1. Kelompokkan representasi biner untuk tiap minterm menurut jumlah difit ’ 1 ’ : (desimal : 0 s/d 15; berarti nilai maks. 15, banyaknya digit biner m = 4, 24 = 16).

tabel konversi :

Dari tabel konversi tersebut dapat dilihat bahwa jumlah digit 1 adalah :











Jadi, tabel kelompoknya adalah :

2. Dari dua minterm yang berbeda digit ‘1’dapat dikombinasikan dengan saling menghilangkan. Minterm dari satu bagian dengan bagian lainnya jika mempunyai nilai bit yang samadalam semua posisi yang berbeda tersebut diganti dengan tanda ‘-’.


Misalnya
bagian I    : 0000
bagian II   : 0001
Hasil        : 000-
Sehingga tabel 3.2.3 menjadi :

Ad* ) keterangan : tanda v berarti minterm tersebut dipilih untuk tahap selanjutnyad caption

3. Kelompokkan hail minterm tahap 2) seperti tahap 1)
4. Ulangi tahap 2) dan tahap 3) sampai minterm dari setiap bagian tidak dapat saling menghilangkan.

Dari keempat langkah tersebut dihasilkan tabel berikut ini :

II. Memilih Prime-Implicant

Dari tabel 3.2.3 terlihat bhasil dari tahap penentuan prime implicant pada i kolom a, b, c. Pada kolom c ( sudah tidak dapat saling dihilangkan ), terlihat pada bagian pertama mencakup desimal 10, 11, 14, 15. Hal ini berarti dari fungsi boolean F = (0,1,2,8,10,11,14,15); desimalyang belum ada pada kolom c adalah desimal ‘1’.

Hal yang berarti calon prime-implicant adalah :
- 1                      (0 0 0 1)    ditandai dengan A
- 0, 2, 8, 10         (- 0 - 0)    ditandai dengan B
- 10,11,14,15       (1 - 1 -)    ditandai dengan C   

Tanda v : berarti yang harus dipilih

Jadi bentuk sederhana dari fungsi Boolean F = ? (0,1,2,8,10,11,14,15) adalah F = A + B + C= w’x’y’z + x’z’ + wy

Jika jumlah peubah yang terlibat pada suatu fungsi Boolean lebih banyak labih dari 6 peubah, maka penggunaan Peta Karnaugh menjadi semakin rumit. Untuk itu digunakan metode Quine Mc Clusky. Metode ini juga disebut metode tabulasi