Materi MatDis (Matematika Diskrit) : Aljabar Boolean

1. Definisi Aljabar Boolean
    Yang disebut aljabar boolean adalah <B, +, ., ',  0, 1>

• Identitas

         (i) a + 0 = a
         (ii) a + 1 = a

• Komutatif

          (i) a + b = b + a
          (ii) a . b = b . a

• Distributif

          (i) a . (b +c) = (a . b) + (a . c)
          (ii) a + (b . c) = (a + b) . (a + c)

• Komplemen

          (i) a + a' = 1
          (ii) a . a' = 0


2. Prinsip Dualitas
    Misalkan S adalah kesamaan (identify) di dalam aljabar boolean yang melibatkan operator +, ., dan komplemen, maka jika pernyataan S* diperoleh dari S 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


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 Soal :
1. Bentuk baku SOP dan POS dari f (x, y, z) = xy + x'z

    SOP:
    xy = xy(z + z')
         = xyz + xyz'
    dan
    x'z = x'z (y +y')
          = x'yz + x'y'z
    Jadi f(x, y, z) = xy + x'z
                          = xyz + xyz' + x'yz + x'y'z
   Atau f(x, y, z) = m7 + m6 + m3 + m1
                          = (1, 3, 6, 7)

    POS:
    f(x, y, z) = xy +x'z
                   = (xy + x')(xy + z)
                  = (x + x')(y + x')(x + z)(y + z)
                   = (x' + y)(x + z)(y + z)
   
     x' + y = x' + y + zz' = (x' + y + z)(x' + y + z')
     x + z  = x + z + yy'  = (x + y + z)(x + y' + z)
     y + z   = xx' + y + z  = (x + y +z)(x' + y + z)

     Jadi f(x, y, z) = (x + y + z)(x + y' + z)(x' + y + z)(x' + y + z')

     Atau f(x, y, z) = M0 M2 M4 M5
                            = (0, 2, 4, 5)

2. Bentuk Baku SOP dan POS dari f(x, y, z) = x + yz'
   
     SOP:
     x = x(y + y')
        = xy + xy'
        = xy (z + z') + xy' (z + z')
        = xyz + xyz' + xy'z + xy'z'
    dan
    yz' = yz' (x + x')
          = yz'x + yz'x' = xyz' + x'yz'
 
     Jadi f(x, y, z) = x + yz'
                           = xyz + xyz' + xy'z + xy'z' + x'yz'
                           = x'yz' + xy'z' + xy'z + xyz' + xyz
     
     Atau f(x, y, z) = m2 + m4 + m5 + m6 + m7
                            = (2, 4, 5, 6, 7)


    POS:
    f(x, y, z) = x + yz'
                   = (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) = M0 M1 M3
                          = (0, 1, 3)