Sabtu, 15 Oktober 2011

Aljabar Boolean

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:

A
b
a × b

a
b
a + b

a
a
0
0
0

0
0
0

0
1
0
1
0

0
1
1

1
0
1
0
0

1
0
1



1
1
1

1
1
1
 


 
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:

a
b
c
b + c
a × (b + c)
a × b
a × c
(a × b) + (a × c)
0
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
1
0
1
0
0
0
0
0
1
1
1
0
0
0
0
1
0
0
0
0
0
0
0
1
0
1
1
1
0
1
1
1
1
0
1
1
1
0
1
1
1
1
1
1
1
1
1


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

 

a
b
a
ab
a + ab
a + b
0
0
1
0
0
0
0
1
1
1
1
1
1
0
0
0
1
1
1
1
0
0
1
1

·       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

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)’ = ab
(ii) (ab)’ = a’ + b

11.           Hukum 0/1
  (i)   0’ = 1
       (ii)  1’ = 0







Tidak ada komentar:

Posting Komentar