Aljabar Boolean II ( Lanjutan )

Fungsi Boolean (disebut juga fungsi biner) adalah pemetaan dari Bⁿ ke B melalui ekspresi Boolean, kita menuliskannya sebagai

                        f : Bⁿ ® B

yang dalam hal ini Bⁿ adalah himpunan yang beranggotakan pasangan terurut ganda-n (ordered n-tuple) di dalam daerah asal B.

Setiap ekspresi Boolean tidak lain merupakan fungsi Boolean.

Misalkan sebuah fungsi Boolean adalah

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

Fungsi f memetakan nilai-nilai pasangan terurut ganda-3

(x, y, z) ke himpunan {0, 1}. 

Contohnya, (1, 0, 1) yang berarti x = 1, y = 0, dan z = 1 sehingga f(1, 0, 1) = 1 × 0 × 1 + 1’ × 0 + 0’× 1 = 0 + 0 + 1 = 1

Contoh.  Contoh-contoh fungsi Boolean yang lain:

1.      f(x) = x

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

3.      f(x, y) = x’ y’

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

5.      f(x, y, z) = xyz’                                                                                                                   

  

Setiap peubah di dalam fungsi Boolean, termasuk dalam bentuk komplemennya, disebut literal.

Contoh: Fungsi h(x, y, z) = xyz’ pada contoh di atas terdiri dari 3 buah literal, yaitu x, y, dan z’.

Contoh. Diketahui fungsi Booelan f(x, y, z) = xy z’, nyatakan h dalam tabel kebenaran.

Penyelesaian:

Komplemen Fungsi

1.      Cara pertama: menggunakan hukum De Morgan

Hukum De Morgan untuk dua buah peubah, x₁ dan x₂, adalah 

                   

Contoh. Misalkan f(x, y, z) = x(y’z’ + yz), maka

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

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

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

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

2.      Cara kedua: menggunakan prinsip dualitas.

Tentukan dual dari ekspresi Boolean yang merepresentasikan f, lalu komplemenkan setiap literal di dalam dual tersebut.

Contoh. Misalkan f(x, y, z) = x(y’z’ + yz), maka

dual dari  f:                                          x + (y’ + z’) (y + z)

komplemenkan tiap literalnya:            x’ + (y + z) (y’ + z’) = f ’

           

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

Bentuk Kanonik

·         Jadi, 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

 

 

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

     Tabel 7.10

 

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’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.  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 Baku

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)