Tuesday, January 24, 2012

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   wxy
                0, 2, 8, 10              yang bersesuaian dengan term   xz
                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) = wxy’ + xz’ + 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 + cd’ + cd
 

Penyederhanaan Fungsi Boolean

Contoh.     f(x, y) = xy + 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 + xy

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

 = 1 × (x + y )

 = x+ y



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

 = xz(y’ + y) + xy

 = xz + xz



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

   = xy+ xz + xyz + xyz

   = xy(1 + z) + xz(1 + y) = xy+ xz

2.  Peta Karnaugh
a.  Peta Karnaugh dengan dua peubah
                                                            y
                                                         0          1

m0
m1
x   0
xy
xy

m2
m3
xy
xy


b. Peta dengan tiga peubah








yz
00

01

11

10

m0
m1
m3
m2

x   0                     
xyz
xyz
xyz
xyz

m4
m5
m7
m6

1                    
xyz
xyz
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)  = m0+ m2 + m3



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



    f ’(x, y, z)  = (f ’(x, y, z))’ = (m0 + m2 + m3)’

                       = m0’ . m2’ . m3

                     = (xyz’)’ (xy z’)’ (xy z)’

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

            = M0 M2 M3

            = Õ (0,2,3)



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


Kesimpulan: mj’ = Mj


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 + xyz

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

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

                       = xyz + xyz’ + xyz+ xyz’ + xyz + xyz’ + xyz


atau f(x, y, z) = m0+ m1 + m2+ m4+ m5+ m6+ m7        



(b) POS

          f(x, y, z)  = M3= 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) = xyz + xyz’ + 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
xy
xy
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
xyz
xyz
xy z
xy z
x yz
x yz
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) =  xyz+ xyz’ + xyz



atau (dengan menggunakan lambang minterm),           



f(x, y, z) =  m1 + m4 + m7 = å (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) =  M0 M2 M3 M5M6 = Õ(0, 2, 3, 5, 6)         

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

Penyelesaian:

     (a) SOP

     x  = x(y + y’)

         = xy + xy

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

         = xyz + xyz’ + xyz+ xyz





     yz = yz (x+ x’)

           = xy’z + x’y’z



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

                                  = xyz + xyz’ + xyz + xyz’ + xyz + xyz

                                  = xyz + xyz’ + xyz + xyz’ + xyz

                       

       atau  f(x, y, z)   = m1 + m4 + m5 + m6 + m7 = S (1,4,5,6,7)

(b) POS

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

                        = (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) = M0M2M3= Õ(0, 2, 3)