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) =  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 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)   = 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) 

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 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) = m₀+ m₁ + m₂+ m₄+ m₅+ m₆+ m₇        

(b) POS

            f(x, y, z)  = M₃ = 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)

 Untuk donload, silakan Klik Disini