Aljabar Boolean

Aljabar Boolean

Dalam bab aljabar Boolean ini akan dibahas beberapa materi mengenai SOP, POS dan Peta Karnough. 

Definisi Aljabar Boolean adalah struktur aljabar yang "mencakup intisari" operasi logika AND, OR dan NOR dan juga teori himpunan untuk operasi union, interseksi dan komplemen. Boolean adalah suatu tipe data yang hanya mempunyai dua nilai. Yaitu true atau false (benar atau salah). Simbol yang digunakan pada aljabar Boolean itu sendiri adalah  (.) untuk AND, (+) untuk OR dan ( ) untuk NOR.
Hukum-hukum Aljabar Boolean



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/maxtermmengandung literal lengkap





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


                   Tabel 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) =  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 M5 M6 = Õ(0, 2, 3, 5, 6)           

Contoh 2. 
Nyatakan fungsi Boolean f(x, y, z) = x + y’z dalam 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)   = m1 + m4 + m5 + m6 + m7 = 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) = M0M2M3 = Õ(0, 2, 3)  
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’
                     = (x’y’z’)’ (x’y z’)’ (x’y 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 3.
  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 4.
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) = m0+ m1 + m2+ m4+ m5+ m6+ m7        
(b) POS
            f(x, y, z)  = M3 = x + y’ + z’    



BentukBaku        
             
•           Tidak harus mengandung literal yang lengkap.
•           Contohnya,  

 f(x, y, z) = y’ + xy + x’yz                                          (bentuk baku SOP)
  f(x, y, z) = x(y’ + z)(x’ + y + z’)                           (bentuk baku  POS)




Peta Karnaugh

a.  Peta Karnaugh dengan dua peubah



b. Peta dengan tiga peubah



Contoh. Diberikan tabel kebenaran, gambarkan Peta Karnaugh.





b. Peta dengan empat peubah



Contoh. Diberikan tabel kebenaran, gambarkan Peta Karnaugh.






Teknik Minimisasi Fungsi Boolean dengan PetaKarnaugh


1. Pasangan: dua buah 1 yang bertetangga



Sebelum disederhanakan: f(w, x, y, z) = wxyz + wxyz’
Hasil Penyederhanaan:     f(w, x, y, z) = wxy
Bukti secara aljabar:

                        f(w, x, y, z) = wxyz + wxyz’
                                            = wxy(z + z’)
                                            = wxy(1)
                                            = wxy

2. Kuad: empat buah 1 yang bertetangga



Sebelum disederhanakan: f(w, x, y, z) = wxy’z’ + wxy’z + wxyz + wxyz’
Hasil penyederhanaan:  f(w, x, y, z) = wx
Bukti secara aljabar:

                        f(w, x, y, z) = wxy’ + wxy
                                            = wx(z’ + z)
                                            = wx(1)
                                            = wx

  




Peta Karnaugh untuk lima peubah




Contoh. 
  (Contoh penggunaan Peta 5 peubah) Carilah fungsi sederhana dari  f(v, w, x, y, z) = S (0, 2, 4, 6, 9, 11, 13, 15, 17, 21, 25, 27, 29, 31)
Jawab:

            Peta Karnaugh dari fungsi tersebut adalah:




Jadi  f(v, w, x, y, z)  =  wz + v’w’z’ + vy’z



KondisiDon’t care
Tabel



Contoh  Diberikan Tabel  Minimisasi fungsi f sesederhana mungkin.

       Tabel


Jawab: Peta Karnaugh dari fungsi tersebut adalah:
 

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

Contoh.
Minimisasi fungsi Boolean berikut (hasil penyederhanaan dalam bentuk baku SOP dan bentuk baku POS):

 f(w, x, y, z) = S (1, 3, 7, 11, 15)

dengan kondisi don’t care adalah d(w, x, y, z) = S (0, 2, 5)

Penyelesaian:

Peta Karnaugh dari fungsi tersebut adalah:


Hasil penyederhanaan dalam bentuk SOP

            f(w, x, y, z) = yz + w’z  (SOP)  (garis penuh)

dan bentuk baku POS adalah             

            f(w, x, y, z) = z (w’ + y)            (POS)  (garis putus2)
Sumber : http://sulistiawan03.blogspot.co.id/2012/10/aljabar-boolean_22.html