ALJABAR BOOLEAN

Definisi Aljabar Boolean

Misalkan terdapat - Dua operator biner: + dan ⋅ - Sebuah operator uner: ’. - B : himpunan yang didefinisikan pada operator +, ⋅, dan ’ - 0 dan 1 adalah dua elemen yang berbeda dari B. 

Tupel   ( B, +, ⋅, ’) disebut aljabar Boolean jika untuk setiap a, b, c ∈ B berlaku aksioma-aksioma atau postulat Huntington berikut:

1.    Closure: (i)  a + b ∈ B       

 (ii) a ⋅ b ∈ B      

 2. Identitas:        (i)  a + 0 = a   

                (ii) a ⋅ 1 = a    

3. Komutatif:        (i)  a + b = b + a    

  (ii)  a ⋅ b = b . a

 4. Distributif:        (i)   a ⋅ (b + c) = (a ⋅ b) + (a ⋅ c)   

   (ii)  a + (b ⋅ c) = (a + b) ⋅ (a + c)    

5. Komplemen1:   (i)  a + a’ = 1      

    (ii)  a ⋅ a’ = 0

Untuk mempunyai sebuah Aljabar Boolean, harus diperlihatkan:

1. Elemen-elemen himpunan B

2. Kaidah operasi untuk operator biner dan operator uner

3. Memenuhi postulat Huntington

Aljaba rBoolean Dua-Nilai

Aljabar Boolean dua-nilai:

- B = {0, 1}

- operator biner, + dan 

- operator uner, ’

- Kaidah untuk operator biner dan operator uner: 

Cek apakah memenuhi postulat Huntington:

1. Closure :  jelas berlaku

2. Identitas: jelas berlaku karena dari tabel dapat kita lihat bahwa:

(i)  0 + 1 = 1 + 0 = 1 

(ii) 1 ⋅ 0  = 0 ⋅ 1 = 0

3. Komutatif:  jelas berlaku dengan melihat simetri tabel operator biner.

4. Distributif: (i) a ⋅ (b + c) = (a ⋅ b) + (a ⋅ c) dapat ditunjukkan benar dari tabel operator biner di atas  dengan membentuk tabel kebenaran:  

  (ii) Hukum distributif a + (b ⋅ c) = (a + b) ⋅ (a + c) dapat ditunjukkan benar dengan membuat tabel kebenaran dengan cara yang sama seperti (i).

 5. Komplemen: jelas berlaku karena Tabel 7.3 memperlihatkan bahwa:    

(i)  a + a‘ = 1, karena 0 + 0’= 0 + 1 = 1 dan 1 + 1’= 1 + 0 = 1    

(ii) a ⋅ a = 0, karena 0 ⋅ 0’= 0 ⋅ 1 = 0 dan 1 ⋅ 1’ = 1 ⋅ 0 = 0  

 Karena kelima postulat Huntington dipenuhi, maka terbukti bahwa B = {0, 1} bersama-sama dengan operator biner + dan ⋅operator komplemen ‘ merupakan aljabar Boolean. 

Ekspresi Boolean

Misalkan (B, +, ⋅, ’) adalah sebuah aljabar Boolean. Suatu ekspresi Boolean dalam (B, +, ⋅, ’) adalah:   

(i)                  setiap elemen di dalam B

(ii)                setiap peubah

(iii)               jika e1 dan e2 adalah ekspresi Boolean, maka e1 + e2, e1 ⋅ e2, e1’ adalah ekspresi Boolean

Contoh:  0  

  1  

  a  

  b  

  a + b  

  a ⋅ b  

   a’⋅ (b + c)  

   a ⋅ b’ + a ⋅ b ⋅ c’ + b’

   dan sebagainya

Hukum-hukum Aljabar Boolean:

Contoh:

Buktikan (i) a + a’b = a + b  

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)

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

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/maxterm mengandung literal lengkap

Contoh:

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