Metode Quine-McCluskey

• Metode Peat Karnaugh tidak mangkus untuk jumlah peubah > 6 (ukuran peta semakin besar).

• Metode peta Karnaugh lebih sulit diprogram dengan komputer karena diperlukan pengamatan visual

  untuk mengidentifikasi minterm-minterm yang akan dikelompokkan.

• Metode alternatif adalah metode Quine-McCluskey . Metode ini mudah diprogram.

Contoh 7.46

Sederhanakan fungsi Boolean f(w, x, y, z) = S (0, 1, 2, 8, 10, 11, 14, 15).

Penyelesaian:

(i)       Langkah 1 sampai 5:

Langkah 6 dan 7:

Bentuk prima yang terpilih adalah:

                0,1                          yang bersesuaian dengan term   w’x’y

                0, 2, 8, 10              yang bersesuaian dengan term   x’z’

                10, 11, 14, 15       yang bersesuaian dengan term   wy

Semua bentuk prima di atas sudah mencakup semua mintermdari fungsi Boolean semula. Dengan demikian

fungsi Boolean hasil penyederhanaan  adalah  f(w, x, y, z) = w’x’y’ + x’z’ + wy.  

Kondisi Don’t care

Tabel 5.16

w	x	y	z	desimal
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 2 3 4 5 6 7 8 9 don’t care don’t care don’t care don’t care don’t care don’t care

Contoh 5.25. Diberikan Tabel 5.17. Minimisasi fungsi f sesederhana mungkin.

       Tabel 5.17

a	b	c	d	f(a, b, c, d)
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	1 0 0 1 1 1 0 1 X X X X X X X X

 Jawab: Peta Karnaugh dari fungsi tersebut adalah:

             Hasil penyederhanaan:  f(a, b, c, d) = bd + c’d’ + cd

 

Penyederhanaan Fungsi Boolean

Contoh.     f(x, y) = x’y + xy’ + y’

disederhanakan menjadi

f(x, y) = x’ + y’

Penyederhanaan fungsi Boolean dapat dilakukan dengan 3 cara:

1.    Secara aljabar

2.    Menggunakan Peta Karnaugh

3.  Menggunakan metode Quine Mc Cluskey (metode Tabulasi)

1. Penyederhanaan Secara Aljabar

Contoh:

1.    f(x, y) = x + x’y

      = (x+ x’)(x + y)

 = 1 × (x + y )

 = x+ y

2.    f(x, y, z) = x’y’z + x’yz + xy’

 = x’z(y’ + y) + xy’

 = x’z + xz’

3.    f(x, y, z) = xy + x’z + yz  = xy+ x’z + yz(x + x’)

   = xy+ x’z + xyz + x’yz

   = xy(1 + z) + x’z(1 + y) = xy+ x’z

2.  Peta Karnaugh

a.  Peta Karnaugh dengan dua peubah

                                                            y

                                                         0          1

	m0	m1	x   0	x’y’	x’y
	m2	m3	1	xy’	xy

b. Peta dengan tiga peubah

							yz 00	01	11	10
	m0	m1	m3	m2		x   0	x’y’z’	x’y’z	x’yz	x’yz’
	m4	m5	m7	m6		1	xy’z’	xy’z	xyz	xyz’

Konversi Antar Bentuk Kanonik

Misalkan

f(x, y, z)      = S (1, 4, 5, 6, 7)

dan f’adalah fungsi komplemen dari f,

f’(x, y, z) = S (0, 2, 3)  = m₀+ m₂ + m₃

Dengan menggunakan hukum De Morgan, kita dapat memperoleh fungsi f dalam bentuk POS:

    f ’(x, y, z)  = (f ’(x, y, z))’ = (m₀ + m₂ + m₃)’

                       = m₀’ . m₂’ . m₃’

                     = (x’y’z’)’ (x’y z’)’ (x’y z)’

            = (x + y + z) (x+ y’ + z) (x + y’ + z’)

            = M₀ M₂ M₃

            = Õ (0,2,3)

Jadi,  f(x, y, z) = S (1, 4, 5, 6, 7) = Õ (0,2,3).

Kesimpulan: m_j’ = M_j

Contoh.  Nyatakan

 f(x, y, z)= Õ (0, 2, 4, 5) dan

g(w, x, y, z) = S(1, 2, 5, 6, 10, 15)

dalam bentuk SOP.

Penyelesaian:

          f(x, y, z)      = S (1, 3, 6, 7)             

        g(w, x, y, z)= Õ (0, 3, 4, 7, 8, 9, 11, 12, 13, 14) 

Contoh. Carilah bentuk kanonik SOP dan POS dari f(x, y, z) = y’ + xy + x’yz’

Penyelesaian:

(a) SOP

f(x, y, z) = y’ + xy + x’yz’

                       = y’ (x + x’) (z+ z’) + xy (z + z’) + x’yz’

             = (xy’ + x’y’) (z+ z’) + xyz + xyz’ + x’yz’

                       = xy’z + xy’z’ + x’y’z+ x’y’z’ + xyz + xyz’ + x’yz’

atau f(x, y, z) = m₀+ m₁ + m₂+ m₄+ m₅+ m₆+ m₇        

(b) POS

          f(x, y, z)  = M₃= x + y’ + z’                                        

                 

Bentuk Kanonik

·       Ada dua macam bentuk kanonik:

1.    Penjumlahan dari hasil kali (sum-of-product atau SOP)

2.    Perkalian dari hasil jumlah (product-of-sum atau POS)

Contoh: 1.  f(x, y, z) = x’y’z + xy’z’ + xyz  à SOP

          Setiap suku (term) disebut minterm

     2. g(x, y, z) = (x + y + z)(x+ y’ + z)(x + y’ + z’)

         (x’ + y + z’)(x’ + y’ + z)  à POS

Setiap suku (term) disebut maxterm

·       Setiap minterm/maxterm mengandung literal lengkap

			Minterm		Maxterm
x	y		Suku	Lambang	Suku	Lambang
0 0 1 1		0 1 0 1	x’y’ x’y xy’ x y	m0 m1 m2 m3	x + y x + y’ x’ + y x’ + y’	M0 M1 M2 M3

 

			Minterm		Maxterm
x	y	z	Suku	Lambang	Suku	Lambang
0 0 0 0 1 1 1 1	0 0 1 1 0 0 1 1	0 1 0 1 0 1 0 1	x’y’z’ x’y’z x‘y z’ x’y z x y’z’ x y’z x y z’ x y z	m0 m1 m2 m3 m4 m5 m6 m7	x + y + z  x + y + z’ x + y’+z x + y’+z’ x’+ y + z x’+ y + z’ x’+ y’+ z x’+ y’+ z’	M0 M1 M2 M3 M4 M5 M6 M7

Contoh 7.10. Nyatakan tabel kebenaran di bawah ini dalam bentuk kanonik SOP dan POS.

     Tabel 7.10

x	y	z	f(x, y, z)
0 0 0 0 1 1 1 1	0 0 1 1 0 0 1 1	0 1 0 1 0 1 0 1	0 1 0 0 1 0 0 1

 

Penyelesaian:

(a)   SOP

Kombinasi nilai-nilai peubah yang menghasilkan nilai fungsi sama dengan 1 adalah 001, 100, dan 111, maka fungsi Booleannya dalam bentuk kanonik SOP adalah

f(x, y, z) =  x’y’z+ xy’z’ + xyz

atau (dengan menggunakan lambang minterm),           

f(x, y, z) =  m₁ + m₄ + m₇ = å (1, 4, 7)

(b) POS

Kombinasi nilai-nilai peubah yang menghasilkan nilai fungsi sama dengan 0 adalah 000, 010,  011, 101, dan 110, maka fungsi Booleannya dalam bentuk kanonik POS adalah

 f(x, y, z)  =  (x + y + z)(x+ y’+ z)(x + y’+ z’)

   (x’+ y + z’)(x’+ y’+ z)

                                  

      atau dalam bentuk lain,                

f(x, y, z) =  M₀ M₂ M₃ M₅M₆ = Õ(0, 2, 3, 5, 6)         

Contoh 7.11. Nyatakan fungsi Boolean f(x, y, z) = x + y’zdalam bentuk kanonik SOP dan POS.

Penyelesaian:

     (a) SOP

     x  = x(y + y’)

         = xy + xy’

         = xy (z + z’) + xy’(z + z’)

         = xyz + xyz’ + xy’z+ xy’z’

     y’z = y’z (x+ x’)

           = xy’z + x’y’z

     Jadi  f(x, y, z)   = x+ y’z

                                  = xyz + xyz’ + xy’z + xy’z’ + xy’z + x’y’z

                                  = x’y’z + xy’z’ + xy’z + xyz’ + xyz

                       

       atau  f(x, y, z)   = m₁ + m₄ + m₅ + m₆ + m₇ = S (1,4,5,6,7)

(b) POS

          f(x, y, z) = x + y’z

                        = (x + y’)(x + z)

          x + y’ = x+ y’ + zz’

                    = (x + y’ + z)(x+ y’ + z’)

          x + z= x + z + yy’        

                  = (x+ y + z)(x + y’ + z)

          Jadi, f(x, y, z) = (x + y’ + z)(x + y’ + z’)(x + y + z)(x + y’ + z)

                            = (x + y  + z)(x + y’ + z)(x + y’ + z’)

          atau f(x, y, z) = M₀M₂M₃= Õ(0, 2, 3)