Minggu, 13 Mei 2018

Matematika Diskrit

ALJABAR BOOLEAN

 
“Education is the most powerful weapon which you can use to change the world.” 
— Nelson Mandela


Aljabar boolean merupakan aljabar yang berhubungan dengan variabel-variabel biner dan operasi-operasi logik. Variabel-variabel diperlihatkan dengan huruf-huruf alfabet, dan tiga operasi dasar dengan AND, OR dan NOT (komplemen). Fungsi boolean terdiri dari variabel-variabel biner yang menunjukkan fungsi, suatu tanda sama dengan, dan suatu ekspresi aljabar yang dibentuk dengan menggunakan variabel-variabel biner, konstanta-konstanta 0 dan 1, simbol-simbol operasi logik, dan tanda kurung.
          Suatu fungsi boolean bisa dinyatakan dalam tabel kebenaran. Suatu tabel kebenaran untuk fungsi boolean merupakan daftar semua kombinasi angka-angka biner 0 dan 1 yang diberikan ke variabel-variabel biner dan daftar yang memperlihatkan nilai fungsi untuk masing-masing kombinasi biner.
          Aljabar boolean mempunyai 2 fungsi berbeda yang saling berhubungan. Dalam arti luas, aljabar boolean berarti suatu jenis simbol-simbol yang ditemukan oleh George Boole untuk memanipulasi nilai-nilai kebenaran logika secara aljabar. Dalam hal ini aljabar boolean cocok untuk diaplikasikan dalam komputer. Disisi lain, aljabar boolean juga merupakan suatu struktur aljabar yang operasi-operasinya memenuhi aturan tertentu.


DALIL BOOLEAN ;
1.     X=0 ATAU X=1
2.    0 . 0 = 0
3.    1 + 1 = 1
4.    0 + 0 = 0
5.    1 . 1 =  1
6.    1 . 0 = 0 . 1 = 0
7.    1 + 0 = 0 + 1 = 0

TEOREMA BOOLEAN
1. HK. KOMUTATIF
A + B = B + A
A .  B = B  . A
6. HK. IDENTITAS
A + A = A
A  . A = A
2. HK. ASSOSIATIF
(A+B)+C = A+(B+C)
(A.B) . C = A . (B.C)
7.
0 + A = A ----- 1. A = A
1 + A = 1 ----- 0 . A = 0
3. HK. DISTRIBUTIF
A . (B+C) = A.B + A.C
A + (B.C) = (A+B) . (A+C)
8.
A’ + A = 1
A’ .  A  =0
4. HK. NEGASI
( A’ ) = A’
(A’)’  = A
9.
A + A’ . B = A + B
A . (A + B)= A . B
5. HK. ABRSORPSI
A+ A.B  = A
A.(A+B) = A
10. DE MORGAN’S
( A+ B )’  = A’ . B’
( A . B )’  = A’ + B’

CONTOH :
A  + A . B’ + A’ .  B       =  A . ( 1 + B’ ) + A’ . B
          =  A . 1 + A’ . B
          =  A + A’ . B
          =  A + B



·         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

Contoh : Buktikan (i) a + ab = a + b   dan   (ii) a(a’ + b) = ab
Penyelesaian:
            (i)         a + ab   = (a + ab) + ab              (Penyerapan)
                                    = a + (ab + ab)              (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 Bn ke B melalui ekspresi Boolean, kita menuliskannya sebagai
                        f : Bn ® B
yang dalam hal ini Bn 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 + xy + yz
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) = xy + 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, x1 dan x2, adalah 
                   
Contoh. Misalkan f(x, y, z) = x(yz’ + yz), maka
    f ’(x, y, z)  = (x(yz’ + yz))’
                           =  x’ + (yz’ + yz)’
                            =  x’ + (yz’)’ (yz)’
                       =  x’ + (y + z) (y’ + z’)


Tidak ada komentar:

Posting Komentar

RANGKAIAN LISTRIK (TUGAS INDIVIDU)

TUGAS INDIVIDU RANGKAIAN LISRIK 1. Soal mengenai Rangkaian Listrik Kompleks Hitung besar arus I yang mengalir pada rangkai...