Penyederhanaan Aljabar Boolean

BAB I.

Penyederhanaan fungsi logika dengan K-Map

Metode penyederhanaan persamaan Boole, yang paling sering digunakan, melalui metode ini adalah menggunakan Peta Karnaugh Veitch atau yang sering juga disebut sebagai diagram Karnaugh (Karnaugh MAP). Karnaugh Map (disingkat K-map) adalah sebuah peralatan grafis yang digunakan untuk menyederhanakan persamaan logika atau mengkonversikan sebuah Tabel Kebenaran menjadi sebuah rangkaian Logika. AB dan C adalah variabel input, output-output berupa minterm-minterm bernilai 1 diisikan pada sel K-map. Jumlah sel K-map adalah 2 ^{jumlah variabel input} .

Misalnya: jika terdapat dua variabel input pada masukannya maka jumlah kemungkinan variasi adalah 2²= 4 kemungkinan jumlah kotak persegi pada K-Map.

Bila jumlah kotak persegi pada K-Map sudah ditentukan, maka tiap-tiap kotak harus ditandai sendiri-sendiri.

            Penyederhanaan atau minimisasi dilakukan dengan mengelompokkan kotak-kotak yang bertetangga, yang bernilai logika-1, menjadi satu blok yang bergantung dari besarnya digram, dapat terdiri dari 2,4,8 kotak,... dsb. Blok demikian dapat dianggap satu kotak yang ditandai dengan variabel dipinggirnya. Selama pengelompokkan dapat menciptakan blok yang baru, maka pengelompokkan berganda dari suatu kotak selalu membawa penyederhanaan.

Kotak yang tidak termasuk dalam suatu kelompok atau blok akan ditandaioleh variabel berpadanan seperti semula. Persamaan baru yang disederhanakan merupakan “penjumlahan” dari semua blok dari sisa kotak yang berlogika 1.

Contoh 5 : sederhanakan

A	B	T
0 0 1 1	0 1 0 1	1 1 0 0

Solusi :

Salah satu metode penyederhanaan fungsi logika untuk maksimal 4 variabel dapat dilakukan:

a)          Berdasarkan tabel kebenaran diatas, maka persamaan Aljabarnya adalah T=(`A.`B)+(`A.B)...... standart disjunctif.

b)         Selanjutnya dibuat diagram K-Map dengan mengalihkan persamaan kedalam kotak-kotak berpadanan.

c)          Selanjutnya menyusul pengelompokan kotak-kotak bertetangga yang bernilai logika-1. Diagram diatas memungkinkan pembentukan 1 blok berkotak-kotak secara khas yang ditandai dengan huruf pinggir `A. Tidak ada kotak yang bernilai logika-1 yang tersisa. Sehingga hasil penyederhanaannya adalah : T = `A.

Aturan Dasar Untuk Melakukan Penyederhanaan Dengan Menggunakan K-Map

a)            Peta digambar sedemikan rupa sehingga kotak-kotak yang bersebelahan hanya berbeda “satu” variabel.

b)            Suku-suku dari persamaan yang akan disederhanakan dimasukkan kedalam kotak yang besesuaian  dengan cara memberi logika-1 didalamnya.

c)            Bila pada kotak persegi yang bersebelahan terdapat logika-1, maka variabel yang berbeda pada kedua kotak tersebut dihilangkan (Hukum komplementasi). Sehingga pada suku tersebut hanya “Variabel yang sama” yang merupakan bagian dari hasil akhir dari hasil penyederhanaan.

d)           Jika semua suku telah disederhanakan, persamaan akhir diperoleh dengan menuliskan semua suku-suku yang telah disederhanakan itu dalam bentuk standar disjunctif.

Selanjutnya aturan pembentukan Loop  dapat kita perluas untuk banyak variabel masukan (input).

Penyelesaian logika dari tabel kebenaran dengan menggunakan metode SOP dan POS

Merupakan ekspresi fungsi AND atau metode SOP:

-  Rangkaian kombinasi logika

- Kondisi output ditentukan oleh kombinasi input

– inputnya

 Penyelesaian logika dari tabel kebenaran dengan menggunakan metode SOP dan POS dan implementasi pada rancangan rangkaian logikanya. Jika diberikan suatu tabel kebenaran dari suatu kasus maka kita bisa menggunakan metode SOP atau POS untuk merancang suatu rangkaian kombinasionalnya. Untuk menentukan suatu rancangan kita menghendaki suatu rancangan yang paling efisien. Dengan adanya tabel kebenaran kita dapat menentukan mana diantara metode yang paling efisien untuk diimplementasikan. Untuk menentukan metode mana yang paling efisien, kita lihat bagian output pada tabel kebenaran tersebut. Jika jumlah output yang mempunyai nilai 1 lebih sedikit dari jumlah output yang mempunyai nilai 0, maka kita bisa menentukan bahwa metode SOP yang lebih efisien. Jika jumlah output yang mempunyai nilai 0 lebih sedikit dari jumlah output yang mempunyai nilai 1, maka kita bisa menentukan metode POS yang lebih efisien. Kadangkala suatu hasil dari tabel disajikan dalam bentuk fungsi. Dan kita akan mengenal symbol "Σ" melambangkan operasi SOP sehingga yang ditampilkan adalah output yang mempunyai nilai 1 dan symbol "Π" melambangkan operasi POS sehingga yang ditampilkan adalah ouput yang mempunyai nilai 0.

1.1.Variabel Input Data  2.

Sebuah rangkaian logika yang mempunyai 2 buah input, maka akan mempunyai 4 buah variabel input (sesuai dengan rumus 2ⁿ = 2² = 4). Variabel input data ada 2, maka ada 4 kotak yang ditandai dengan A,`A, B dan`B. Urutan penandaan diatur sedemikan rupa sehingga pada peralihan dari satu kotak kekotak disebelahnya hanya boleh berbeda satu variabel (satu nilai logika) saja. Untuk lebih jelasnya perhatikan gambar berikut :

						B      A	`A	A
`A.`B	A.`B		00	10	Atau	`B
`A.B	A.B		01	11		B

1.2.Variabel Input Data  3.

Dalam sebuah rangkaian logika yang mempunyai tiga buah input, akan mempunyai 8 buah kombinasi variabel input ( 2³ ). Jadi sebuah Peta Karnaugh dari sebuah rangkaian logika dengan 3 buah input akan memiliki 8 buah kotak. Bentuk Peta Karnaughnya adalah :

Gambar. Peta Karnaugh dengan Tiga variabel

Bila kita perhatikan, penempatan nilai 11 ada dikolom ketiga dari Peta Karnaugh tiga variabel. Prinsip yang dipergunakan adalah perubahan antara kolom yang satu dengan yang lainnya harus memiliki satu nilai perubahan saja. Demikian juga dengan Peta Karnaugh diatas, kolom ke-2 = 01maka pada kolom berikutnya (ke-3) harus 00 atau 11, karena pada kolom pertama 00 sudah didefinisikan, maka kolom ke-3 diisi dengan nilai 11.

Sebagai contoh untuk variable 3 Input-an:

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

Maksud dari fungsi diatas adalah fungsi tersebut mempunyai 3 variabel input dan output yang mempunyai nilai 1 adalah 0, 3, 5, dan 7 (tanda Σ melambangkan SOP). Jika fungsi yang disajikan adalah:

F( A, B, C ) = Π ( 0, 3, 5, 7 )

Maksudnya adalah fungsi tersebut mempunyai 3 variabel input dan output yang mempunyai nilai 0 adalah 0, 3, 5, dan 7 (tanda Π melambangkan POS). Rangkaian kombinasional untuk mengimplementasikan tabel kebenaran berikut :

A	B	C	OUTPUT
0	0	0	0
0	0	1	0
0	1	0	1
0	1	1	1
1	0	0	0
1	0	1	0
1	1	0	0
1	1	1	1

Karena output dengan nilai 1 lebih sedikit maka kita gunakan metode SOP. Dan untuk teknik penyederhanaannya kita langsung gunakan K-Map (karena masih 3 variabel). Sehingga K-Map akan berbentuk:

                                               

Ekspresi fungsi logikanya dari hasil K-Map tersebut adalah:

                                                           

Karena bentuk fungsi logikanya adalah SOP kita dapat merancang rangkaian kombinasionalnya dari gerbang NAND saja, yaitu dengan cara member double bar pada fungsi tersebut kemudian operasikan bar yang terbawah. Fungsi akan menjadi:

                                                           

 Sehingga rangkaian kombinasionalnya menjadi:

                                   

Contoh :

Rangkaian kombinasional untuk mengimplementasikan tabel kebenaran berikut ini :

           

A	B	C	OUTPUT
0	0	0	0
0	0	1	0
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	1
1	1	0	1
1	1	1	1

Karena output dengan nilai 0 lebih banyak maka kita gunakan metode POS. Sehingga K-Map akan terbentuk :

                       

Ekspresi fungsi logikanya dari hasil K-Map tersebut adalah:

                       

Dari fungsi logika tersebut kita dapat merancang rangkaian kombinasionalnya dari gerbang NOR saja dengan cara memberi double bar kemudian bar terbawah dioperasikan sehingga:

                                   

Dan rangkaian kombinasionalnya:

1.3.Variabel Input Data 4.

Apabila sebuah rangkaian logika mempunyai empat buah variabel input, maka akan dihasilkan sebanyak 16 buah kombinasi variabel input. Untuk menggambarkan Peta Karnaugh dengan 4 buah input, maka harus dibuatkan 16 buah kotak.

                              Gambar. Peta Karnaugh dengan Empat Variabel

Misalkan suku A.B.`C.D dari sebuah fungsi mempunyai 4 variabel input, maka suku ini harus dimasukkan kedalam peta karnaugh  sebagai nilai satu  pada kotak yang berpadanan. Pada tabel kebenaran suku-suku ini diwakili oleh kode input 1101 yaitu logika-1 untuk input D, logika1-0 untuk input C logika-1 untuk input B dan logika-1 untuk input A. Serta bila suku A.B.`C.D muncul dalam persamaan (fungsi), maka niali fungsi (suku A.B.`C.D) ini diberi logika-1. Hal ini berarti bahwa bila logika-1 muncul pada lajur fungsi dari kolom fungsi maka pada kotak yang berpadanan dari peta karnaugh juga diberi logika-1.

Contoh : penyederhanaan tabel kebenaran dibawah ini :

D	C	B	A	T(Output)
0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1	0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1	0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1	0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1	0 1 0 0 1 1 1 1 0 1 0 0 1 1 1 1

Solusi :

Berdasarkan hasil pembentukan loop pada K-map maka diperoleh hasil penyederhanaan

Sebagai berikut :

T = (A.`B) + C

1.4.Variabel Input Data 5.

Apabila sebuah rangkaian logika mempunyai lima buah variabel input, maka akan dihasilkan sebanyak 32 buah kombinasi variabel input. Untuk menggambarkan Peta Karnaugh dengan 5 buah input, maka harus dibuatkan 32 buah kotak.

                 

Peta Karnaugh dengan Lima variabel

Berdasarkan hasil pembentukan loop pada K-map maka diperoleh hasil penyederhanaan

Sebagai berikut :

T=

1.5.Penggunaan Peta Karnaugh

Penggunaan Peta Karnaugh dapat dijelaskan dengan contoh persamaan seperti dibawah ini berdasarkan tabel kebenaran dari AND GATE.

F = ABC + ABC + ABC + ABC+ ABC      

Dengan tabel kebenaran :

A	B	C	F
0	0	0	0	A’B’C A’B C A B’C A B C’ A B C
0	0	1	1
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	1

            Dari tabel kebenaran diatas, pada kolom F terdapat angka logika 0 dan 1 yang akan disederhanakan adalah mempunyai hasil 1 dan selanjutnya dikonversikan kedalam Peta Karnaugh seperti dibawah ini :

Gambar. Hasil Konversi

Didalam kotak-kotak tersusun angka logika 1 dan logika 0, dimana angka logika 1 letaknya bisa berdekatan / berdampingan dan bisa juga berjauhan tergantung bentuk soal yang mempunyai nilai 1.

Berdasarkan letak angka 1 maka akan didapat beberapa kemungkinan yang akan terjadi, yaitu sebagai berikut :

1.      PAIR, apabila ada dua angka logika 1 yang berdampingan.

2.      QUAD, apabila ada empat angka logika 1 berdampingan.

3.      OKTET, apabila ada delapan angka logika 1 berdampingan.

4.      ROLLING (melingkar), apabila nilai logika 1 yang terdapat pada kolom sebelah kiri dengan nilai logika 1 pada kolom sebelah kanan, atau nilai logika 1 pada baris paling atas dengan logika 1 pada baris paling bawah.

5.      OVERLAPPING, apabila pembacaan logika 1 yang digunakan lebih dari 1 (satu) kali.

      Pasangan yang terbentuk dari angka 1 yang berdampingan seperti pada contoh penyederhanaan diatas adalah sebuah pair dan sebuah quad.

      Langkah-langkah penyederhanaan rangkaian logika dengan menggunakan Peta Karnaugh bila secara singkat adalah sebagai berikut : .

1.      Masukkan angka-angka 1 ke dalam Peta Karnaugh untuk setiap hasil kali fundamental yang bersesuaian dengan kelaran 1 dalam tabel logika.

Tulislah angka-angka 0 ditempat-tempat yang tersisa

2.      Lingkarilah pair, quad, oktet, dan pasangan yang ada pada peta. Jangan lupa melakukan proses pengulangan dan penandaan kelompok-kelompok tumpang tindih untuk memperoleh kelompok yang sebesar mungkin.

3.      Lingkarilah sisa-sisa angka 1 yang terisolasi.

4.      Hapuslah kelompok-kelompok kelebihan bilamana ada.

5.      Tulislah persamaan boolean dalam pernyataan operasi OR dari hasil kali yang bersesuaian dengan kelompok-kelompok yang dilingkari dalam Peta Karnaugh.

6.      Gambarlah rangkaian logika ekivalennya.

BAB. II

Metode Quine Mc.Cluskey

      Metode lain yang digunakan untuk menyederhanakan fungsi boolean adalah dengan menggunakan metode Quine-McCluskey atau biasa disebut metode tabulasi. Jika jumlah variabel yang terlibat pada suatu fungsi lebih dari enam variabel maka penggunaan Peta Karnaugh menjadi semakin rumit. Untuk itu digunakan metode Quine-McCluskey atau tabulasi ini. Dasar hukum yang digunkan metode ini adalah aksioma distribusi.

Metode Quine-McCluskey ini terdiri dari dua bagian, yaitu :

1.      Menentukan term-term sebagai kandidat (Prime Implicant).

2.      Memilih prime implicant untuk mendapatkan ekspresi dengan jumlah literal paling sedikit.

                                                2.1. Menentukan Prime Implicant

Langkah-langkah penyelesaian dalam menentukan prime implicant (kandidat-kandidat) adalah dengan cara :

a.       Kelompokkan representasi biner untuk minterm menurut jumlah digit 1-nya.

Tabel  Konversi Biner

Desimal	Biner
0	0000
1	0001
2	0010
8	1000
10	1010
11	1011
14	1110
15	1111

Berdasarkan tabel diatas, pisahkan menurut jumlah digit 1-nya menjadi :

Tabel. Tabel Menurut Jumlah Digit

Jumlah Digit 1	Desimal
0	0
1	1,2,8
2	10
3	11,14
4	15

Jika dibuat kedalam bentuk tabel kelompok, menjadi :

Tabel. Tabel Kelompok

Desimal	w	x	Y	z
0	0	0	0	0
1 2 8	0 0 1	0 0 0	0 1 0	1 0 0
10	1	0	1	0
11 14	1 1	0 1	1 1	1 0
15	1	1	1	1

b.      Dari dua minterm yang berbeda nilai digit 1-nya dapat dikombinasikan dengan angka 0 untuk menghilangkan minterm dari suatu bagian lainnya jika mempunyai nilai bit yang sama dalam semua posisi kecuali satu posisi. Satu posisi yang berbeda tersebut dapat diganti dengan tanda ‘-‘, misalnya :

                        0000

                                                            000-                 0001

sehingga jika contoh diatas diselesaikan, menjadi :

Tabel. Tabel Penyederhanaan (1)

( 1 )						( 2 )
Desimal	w	X	Y	z		Reduksi	w	x	y	z
0	0	0	0	0	√	0,1	0	0	0	-
1	0	0	0	1	√	0,2	0	0	-	0	√
2	0	0	1	0	√	0,8	-	0	0	0	√
8	1	0	0	0	√	2,10	-	0	1	0	√
10	1	0	1	0	√	8,10	1	0	-	0	√
11	1	0	1	1	√	10,11	1	0	1	-	√
14	1	1	1	0	√	10,14	1	-	1	0	√
15	1	1	1	1	√	11,15	1	-	1	1	√
						14,15	1	1	1	-	√

Keterangan :

            √ : Bilangan yang bisa dikerjakan lagi pada proses berikutnya.

a.       Kelompokkan hasil minterm tahap b seperti tahap a.

b.       Ulangi tahap b dan c sampai minterm dari setiap bagian tidak dapat saling menghilangkan.

                                                2.2. Memilih Prime-Implicant

            Dari tabel 2.13 di atas, terlihat hasil dari tahap penentuan prime-implicant pada kolom 1, 2, dan 3. pada kolom 3 (sudah tidak dapat dihilangkan), terlihat pada bagian pertama mencakup desimal 0,2,8,10, dan bagian kedua meliputi desimal 10,11,14,15. Hal ini berarti dari fungsi boolean F = ∑ (0,1,2,8,10,11,14,15); desimal yang belum ada pada kolom 3 adalah desimal 1. Hal ini berarti calon prime implicant-nya adalah :

            √  : 0,1                         (0 0 0 -) ditandai dengan A

            √  : 0,2,8,10                 (- 0 - 0) ditandai dengan B

            √  : 10,11,14,15           (1 - 1 -) ditandai dengan C

Jika dibuat dalam bentuk tabel, adalah sebagai berikut :

Tabel  Tabel Prime Implicant

	0	1	2	8	10	11	14	15
A	X	@
B	X		@	@	X
C					X	@	@

Keterangan :

            Tanda @ adalah yang harus dipilih.

            Jadi bentuk sederhana setelah menggunakan metode Quine-McCluskey dari fungsi boolean F = ∑ (0,1,2,8,10,11,14,15) adalah:

            F = A + B + C

               =  W’X’Y’ + X’Z’ + WZ

            Metode peta Karnaugh diperlukan ketelitian yang cukup tinggi didalam proses penyederhanaannya, karena setelah persamaan yang akan disederhanakan dikonversikan kedalam peta karnaugh, ada banyak kemungkinan yang terbentuk antara angka 1 yang berhubungan. {Dalam 1 quad bisa terdiri dari 2 pair, dalam 1 oktet bisa terdiri dari 2 buah quad dan 4 buah pair, dan lain-lain}. Sedangkan untuk metode fungsi aljabar dan metode Quine-McCluskey hasil akhirnya pasti.

                        2.3.Contoh Metode Quine-McCluskey

            Berikut ini contoh kasus dengan menggunakan metode Quine McCluskey yang akan dibahas :

Contoh 1 : Fungsi Boolean dengan lima variabel

F (v,w,x,y,z) = ∑ m( 0, 2, 4, 5, 11, 12, 15, 18, 21, 22, 23, 24, 25, 26, 29, 30, 31 )

Contoh 2 : Fungsi Boolean dengan delapan variabel

F (s,t,u,v,w,x,y,z) = ∑ m(18, 20, 27, 32, 44, 48, 49, 52, 53, 64, 79, 80, 84, 95, 100, 104, 105, 106, 107, 108, 142, 143, 148, 154, 158, 160 )

                                    Penyelesaian Contoh Metode Quine McCluskey

            Dalam menyederhanakan persamaan dalam metode Quine-McCluskey, tahapan yang harus dilakukan adalah :

1.       Menyatakan variabel komplemen dengan 0, dan variabel yang bukan komplemen dengan 1.

2.       Kelompokkan suku-suku berdasarkan jumlah 1.

3.       Kombinasikan suku-suku tersebut dengan kelompok lain yang jumlah 1 nya berbeda satu, sehingga diperoleh bentuk prima yang sederhana.

Setelah tahap tersebut selesai dilakukan, maka tahap selanjutnya adalah :

1.       Mencari Prime implicant : term yang menjadi calon term yang akan terdapat dalam fungsi sederhana.

2.       Memilih Prime implicant yang memiliki jumlah literal paling sedikit.

Dalam melakukan proses tersebut, digunakan tabel reduksi Quine-McCluskey dan tabel reduksi Prime implicant.

Penyelesaian contoh 1 :

Tabel Reduksi Quine-Mccluskey

Kemudian pemilihan Prime implicant berikutnya dengan cara memperhatikan Prime implicant mana yang memiliki tanda ‘X’ terbanyak maka didapatkan K.

Sehingga di dapatkan hasil A+B+C+D+E+F+G+K.

Jadi ekspresi sederhana yang dihasilkan adalah :

F(v,w,x,y,z) = v’w’y’z’ + w’x’yz’ + v’xy’z’ + w’xy’z + vwx’z’ + v’wyz + vwy’z + vxy.

Penyelesaian contoh 2 :

F (s,t,u,v,w,x,y,z) = ∑ m(18, 20, 27, 32, 44, 48, 49, 52, 53, 64, 79, 80, 84, 95, 100, 104, 105, 106, 107, 108, 142, 143, 148, 154, 158, 160 )

Tabel Reduksi Quine-Mccluskey

  

berdasarkan tabel prime implicants diatas, didapatkan label-label prime implicant terpilih, yaitu : A + B + C + D + E + F + G + H + J + L + M + N + O

ekspresi sederhananya adalah :

F(s,t,u,v,w,x,y,z) = s’t’u’vw’x’yz’ + s’t’u’vwx’yz + t’uv’w’x’y’z’ + s’tu’w’x’y’z’ +t’u’vw’xy’z’ + s’tu’vw’y’z’ + s’uv’wxy’z’ + s’tuv’xy’z’ + st’u’v’wxy + st’u’vwyz’ + s’tu’wxyz + s’t’uvw’y’ + s’tuv’wx’.