Jumat, 01 Februari 2013

Aljabar Boolean

Misalkan terdapat
-          Dua operator biner: + dan ×
-          Sebuah operator uner: ’.
-          B : himpunan yang didefinisikan pada opeartor +, ×, 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.      Komplemen:                (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.


Aljabar Boolean 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:
1)      0 + 1 = 1 + 0 = 1
2)      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).


1.      Komplemen: jelas berlaku karena Tabel 7.3 memperlihatkan bahwa:
1)      a + a‘ = 1, karena 0 + 0’= 0 + 1 = 1 dan 1 + 1’= 1 + 0 = 1
2)      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
c
a + b
a × b
a× (b + c)
a × b’ + a × b × c’ + b’, dan sebagainya

Mengevaluasi Ekspresi Boolean

Contoh:  a× (b + c)
jika a = 0, b = 1, dan c = 0, maka hasil evaluasi ekspresi:
0’× (1 + 0) = 1 × 1 = 1

Dua ekspresi Boolean dikatakan ekivalen (dilambangkan dengan ‘=’) jika keduanya mempunyai nilai yang sama untuk setiap pemberian nilai-nilai kepada n peubah.
Contoh: a × (b + c) = (a . b) + (a × c)

Contoh. Perlihatkan bahwa a + ab = a + b .
Penyelesaian: 


 
 
  • Perjanjian: tanda titik (×) dapat dihilangkan dari penulisan ekspresi Boolean, kecuali jika ada penekanan:
(i)              a(b + c) = ab + ac
(ii)                           a + bc = (a + b) (a + c)
(iii)                         a × 0 , bukan a0
           
Prinsip Dualitas


  • Misalkan S adalah kesamaan (identity) di dalam aljabar Boolean yang melibatkan operator +,  ×, dan komplemen, maka jika pernyataan S* diperoleh dengan cara mengganti
                        ×   dengan  +
            +  dengan  ×
                        0  dengan  1
            1  dengan  0
dan membiarkan operator komplemen tetap apa adanya, maka kesamaan S* juga benar. S* disebut sebagai dual dari S.

Contoh. 
(i)   (a × 1)(0 + a’) = 0  dualnya (a + 0) + (1 × a’) = 1
(ii)  a(a‘ + b) = ab       dualnya a + ab = a + b
Hukum-hukum Aljabar Boolean




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

  • a + ab        = (a + ab) + ab           (Penyerapan)  
  • a + ab        = a + (ab + ab)           (Asosiatif)  
  • a + ab        = a + (a + a’)b             (Distributif) 
  • a + ab        = a + 1 · b                   (Komplemen) 
  • a + ab        = a + b                         (Identitas) 
sifat yang ke dua adalah dual dari sifat di atas





Tidak ada komentar: