THOUSANDS OF FREE BLOGGER TEMPLATES

Jumat, 06 Desember 2013

BILANGAN BOOLEAN SOP POS

Aljabar Boolean dapat didefinisikan dalam beberapa cara. Cara yang paling umum adalah dengan menspesifikasikan unsur – unsur pembentuknya dan operasi – operasi yang menyertainya.
Misalkan B adalah himpunan yang didefinisikan pada dua operator biner, + dan ., dan sebuah operator uner,’. Misalkan 0 dan 1 adalah dua elemen yang berbeda dari B. Maka, tupel <B, +, ., ‘, 0, 1> disebut aljabar Boolean jika untuk setiap a, b, c 0 B berlaku aksioma berikut :
1. Identitas
(i) a + 0 = a
(ii) a . 1 = a
2. Komutatif
(i) a + b = b + a
(ii) a . b = b . a
3. Distributif
(i) a . (b + c) = (a . b) + (a . c)
(ii) a + (b . c) = (a + b) . (a + c)
4. Komplemen
Untuk setiap a 0 B terdapat elemen unik a’ 0 B sehingga
(i) a + a’ = 1
(ii) a . a’ = 0
5. Closure: (i)  a + b E B    (ii) a × b E B     
Angka 0 dan 1 adalah dua elemen yang berada di dalam B. 0 disebut
elemen terkecil dan 1 disebut elemen terbesar. Tanda (+) disebut operator penjumlahan,( .) disebut operator perkalian, dan ( ‘) disebut operator komplemen.
Ada perbedaan antara aljabar Boolean dengan aljabar biasa untuk aritmetika bilangan riil :
1. Hukum distributif yang pertama, a . (b + c) = (a . b) + (a . c) sudah dikenal di dalam aljabar biasa, tetapi hukum distributif yang kedua, a + (b . c) = (a + b) . (a + c)
2. Aljabar Boolean tidak memiliki kebalikan perkalian dan kebalikan penjumlahan; karena itu, tidak ada operasi pembagian dan pengurangan di dalam aljabar Boolean.
         
          3. Aljabar biasa memperlakukan himpunan bilangan riil dengan elemen yang tidak berhingga banyaknya.
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



Buktikan apakah memenuhi postulat Huntington:
1.     Closure :  berlaku
2.     Identitas: berlaku karena dari tabel dapat di lihat bahwa:
(i)  0 + 1 = 1 + 0 = 1
(ii) 1 × 0  = 0 × 1 = 0
3.     Komutatif: 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
5.     Komplemen: jelas berlaku karena 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 
Kesimpulannya: Karena kelima postulat Huntington dipenuhi, maka terbukti bahwa B = {0, 1} 
Ekspresi Boolean
- Semisal (B, +, ×, ’) sebuah aljabar Boolean.
- Suatu ekspresi Boolean dalam (B, +, ×, ’) dapat berbentuk:
(1)   elemen di dalam B, ex : 0 dan 1
(2)  peubah/ literal/ variable, ex : a, b, c
    (3) jika e1 dan e2 adalah ekspresi Boolean, maka e1 + e2,
e1 × e2, e1’ adalah ekspresi Boolean
Prinsip Dualitas
Semisal S kesamaan di dalam aljabar Boolean yang menggunakan operator +,  ×, dan komplemen, maka jika pernyataan S* diperoleh dengan cara mengganti
                   ×   dengan  +
     +  dengan  ×
                   0  dengan  1
     1  dengan  0
dan biarkan operator komplemen tetap apa adanya, maka kesamaan S* juga benar.
Contoh. 
(1)   (a × 1)(0 + a’) = 0  dualnya (a + 0) + (1 × a’) = 1
(2)  a(a‘ + b) = ab       dualnya a + ab = a + b


1.     Cara pertama: menggunakan hukum De Morgan
Hukum De Morgan untuk dua buah peubah, x1 dan x2, adalah 
Contoh. Semisal  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’)                                
2.     Cara kedua: menggunakan prinsip dualitas.
Tentukan dual dari ekspresi Boolean yang merepresentasikan f, lalu komplemenkan setiap literal di dalam dual tersebut.
Bentuk Kanonik
·        Jadi, 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) = xyz + xyz’ + 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
Minterm
Maxterm
x
y
Suku
Lambang
Suku
Lambang
0
0
1
1
0
1
0
1
xy
xy
xy
x y
m0
m1
m2
m3
x + y
x + y
x’ + y
x’ + y
M0
M1
M2
M3



Contoh.
buatlah tabel kebenaran di bawah ini dalam bentuk kanonik SOP dan POS.
        Tabel
x
y
z
f(x, y, 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
1
0
0
1
0
0
1
Jwab:
(a)    SOP
Perpaduan nilai-nilai peubah yang menghasilkan nilai fungsi sama dengan 1 adalah 001, 100, dan 111, maka fungsi Booleannya dalam bentuk kanonik SOP:
f(x, y, z) =  xyz + xyz’ + xyz
atau bisa (dengan menggunakan lambang minterm),              
f(x, y, z) =  m1 + m4 + m7 (1, 4, 7)

    (b) POS
Kombinasi nilai-nilai peubah yang menghasilkan nilai fungsi sama dengan 0 adalah 000, 010,  011, 101, dan 110, maka fungsi Booleannya dalam bentuk kanonik POS adalah
 f(x, y, z)  =  (x + y + z)(x + y’+ z)(x + y’+ z’)
   (x’+ y + z’)(x’+ y’+ z)
                            atau dalam bentuk lain,           
f(x, y, z) =  M0 M2 M3 M5 M6(0, 2, 3, 5, 6)
 

PETA KARNAUGH (K-MAP)
 Peta Karnaugh adalah suatu cara lain untuk mempermudah penyederhanaan fungsi Boolean. Cara ini lebih mudah dari pada cara penyederhanaan aljabar terutama dengan 3 atau 4 Variabel akan tetap, jika peubahnya lebih dari 6, akan lebih sulit.
Definisi Peta Karnaugh yaitu:
Setiap peta karnaugh boleh mengubah wujud dalam suatu rangkap Boolean
atau jadual benar
Setiap petak menunjukkan nilai ‘minterm’ (bagi SOP) atau ‘maxterm’ (bagi POS) setiap pembolehubah. Kemudian hanya merangkumi 2 atau 3 atau 4 pembolehubah/input saja. Pemudahan bagi rangkap Boolean lebih besar daripada 4. Bilangan petak (2ⁿ) akan ditentukan oleh bilangan input          




             a.  Peta Karnaugh dua peubah
                                              y
                                            0          1
m0
m1
x   0
xy
xy
m2
m3
1 
xy
xy
             b. Peta dengan tiga peubah
         Yz
00
 01
 11
 10
m0
m1
m3
m2
    
x 0
xyz
xyz
xyz
xyz
m4
m5
m7
m6
1 
xyz
xyz
xyz
xyz



c.  Peta dengan empat peubah
yz
00
01
11
10
m0
m1
m3
m2
                               wx  00
wxyz
wxyz
wxyz
wxyz
m4
m5
m7
m6
                   01  
wxyz
wxyz
wxyz
wxyz
m12
m13
m15
m14
11
wxyz
wxyz
wxyz
wxyz
m8
m9
m11
m10
10
wxyz
wxyz
wxyz
wxyz

Teknik Minimisasi Fungsi Boolean dengan Peta Karnaugh

1. Pasangan: dua buah 1 yang bertetangga
yz
00
01
11
10
wx   00
0
0
0
0
01
0
0
0
0
11
0
0
1
1
10
0
0
0
0
Sebelum disederhanakan: f(w, x, y, z) = wxyz + wxyz
Hasil Penyederhanaan:     f(w, x, y, z) = wxy
 
2. Kuad: empat buah 1 yang bertetangga
yz
00
01
11
10
ab   00
0
0
0
0
01
0
0
0
0
11
1
1
1
1
10
0
0
0
0
Sebelum disederhanakan: f(b,a, y, z) = bayz’ + bayz + bayz + bayz
Hasil penyederhanaan:  f(b, a, y, z) = ba
3.  Oktet: delapan buah 1 yang bertetangga
yz
00
01
11
10
ws   00
0
0
0
0
01
0
0
0
0
11
1
1
1
1
10
1
1
1
1
    
Sebelum disederhanakan: f(a, b, c, d) = wsyz’ + wsyz + wsyz + wsyz’ +
             wsyz’ + wsyz + wsyz + wsyz
Hasil penyederhanaan: f(w, s, y, z) = w

Peta Karnaugh untuk lima peubah

 000      001    011    010     110     111    101     100
00
m0
m1
m3
m2
m6
m7
m5
m4
01
m8
m9
m11
m10
m14
m15
m13
m12
11
m24
m25
m27
m26
m30
m31
m29
m28
10
m16
m17
m19
m18
m22
m23
m21
m20
Garis pencerminan
Keadaan Don’t Care
w
x
y
z
desimal
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
2
3
4
5
6
7
8
9
don’t care
don’t care
don’t care
don’t care
don’t care
don’t care