lanjutan boolean

Hukum-hukum Aljabar Boolean

1.  Hukum identitas: (i)    a + 0 = a (ii)  a × 1 = a	2.  Hukum idempoten: (i)   a + a = a (ii)  a × a = a
3.  Hukum komplemen: (i)    a + a’ = 1 (ii)  aa’ = 0	4.  Hukum dominansi: (i)    a × 0  = 0 (ii)   a + 1 = 1
5.  Hukum involusi: (i) (a’)’ = a	6.  Hukum penyerapan: (i)    a + ab = a (ii)  a(a + b) = a
7.  Hukum komutatif: (i)    a + b = b + a (ii)   ab = ba	8.  Hukum asosiatif: (i)    a + (b + c) = (a + b) + c (ii)   a (b c) = (a b) c
9.  Hukum distributif: (i) a + (b c) = (a + b) (a + c) (ii) a (b + c) = a b + a c	10.    Hukum De Morgan: (i) (a + b)’ = a’b’ (ii) (ab)’ = a’ + b’
11.           Hukum 0/1   (i)   0’ = 1        (ii)  1’ = 0

Contoh 7.3. Buktikan (i) a + a’b = a + b   dan   (ii) a(a’ + b) = ab

Penyelesaian:

          (i)      a + a’b       = (a + ab) + a’b           (Penyerapan)

                             = a + (ab + a’b)           (Asosiatif)

                             = a + (a + a’)b             (Distributif)

                             = a + 1 · b                    (Komplemen)

                             = a + b                          (Identitas)

(ii) adalah dual dari (i)

Fungsi Boolean

·       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:

      

x	y	z	f(x, y, z) = xy 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 0 0 0 0 0 1 0

                                                         

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

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

  

Baca selengkapnya »