Minggu, 14 Oktober 2012

aljabar boolean


Ekpresi Aljabar

1.Bentuk Kanonik
Beberapa fungsi Boolean mungkin mempunyai ekspresi aljabar
yang berbeda , tetapi sebenarnya nilai fungsinya sama.
Sebagai contoh, f (x,y) = xydan g (x, y) = (x + y)adalah dua buah fungsi yang sama.
Contoh lain,
 f (x, y, z) = xyz + xyz+ xyz dan g(x, y, z) = (x + y + z) (x + y+ z) (x + y+ z‟) (x+ y +z) (x+ y+ z) adalah dua buah fungsi yang sama. Fungsi pertama, f, tampil dalam bentuk penjumlahan dari hasil kali, sedangkan fungsi yang kedua, g, muncul sebagai bentuk perkalian dari hasil penjumlahan.
Setiap suku (term) mengandung literal yang lengkap, x, y, z. Fungsi boolean yang dinyatakan sebagai jumlah dari hasil kali dan hasil kali dari jumlah, dengan setiap sukunya mengandung literal lengkap, disebut dalam bentuk kanonik.
Ada dua macam bentuk kanonik :
1. Minterm atau sum-of- product (SOP)
2. Maxterm atau product-of-sum (POS)
Minterm dan Maxterm dari dua peubah biner ditunjukkan pada tabel 1.1 berikut :
Tabel 1.1
Minterm dan Maxterm dari tiga peubah biner ditunjukkan pada
tabel 1.2 berikut :
Tabel 1.2
Suatu fungsi boolean dapat dibentuk secara aljabar dari tabel kebenaran yang diketahui dengan membentuk minterm dari setiap kombinasinya.
Untuk membentuk minterm, tinjau kombinasi peubah – peubah yang menghasilkan nilai 1. Kombinasi 001, 100 dan 111 ditulis sebagai xyz , xyz, dan xyz. Untuk membentuk maxterm, tinjau kombinasi peubah – peubah yang menghasilkan nilai 0. Kombinasi 000, 010, 101 dan 110 ditulissebagai (x + y + z) , (x + y+ z) , (x+ y + z) dan (x+ y+ z)

Contoh :
Tinjau fungsi Boolean yang diekspresikan dalam tabel 1.3 berikut ini. Nyatakan fungsi tersebut dalam bentuk Kanonik SOP dan POS.
Tabel 1.3
Jawab :
1. SOP : tinjau kombinasi peubah yang menghasilkan nilai 1
f (x, y, z) = xyz + xyz+ xyz
atau dalam bentuk lain,
f (x, y, z) = m1 + m4 + m7 = (1, 4, 7)
2. POS : tinjau kombinasi peubah yang menghasilkan nilai 0
f (x, y, z) = (x + y + z) (x + y+ z) (x + y+ z‟) (x
+ y + z) (x+ y+ z)f
atau dalam bentuk lain,
f (x, y, z) = M0 M2 M3 M5 M6 = (0, 2, 3, 5, 6)
Notasi dan berguna untuk menyingkat penulisan ekspresi
bentuk SOP dan POS.

2. Konversi Antar Bentuk Kanonik
Misal f adalah fungsi Boolean dalam bentuk SOP :
f (x,y,z) = (1, 4, 5, 6, 7)
dan f ‘ adalah komplemen dari f.
f ‘ (x, y, z) = (0, 2, 3) = m0 + m2 + m3
Dengan menggunakan hukum de Morgan, kita dapat memperoleh
fungsi f dalam bentuk POS :
f ‘ (x, y, z) = (f ‘ (x, y, z))= (m0 + m2 + m3)
= m0. m2. m3
= (xyz)(xy z)(xy z)
= (x + y + z) (x + y+ z) (x + y+ z)
= M0 M2 M3
= (0, 2, 3)
Jadi mj = M j


3. Bentuk Baku
Dua bentuk kanonik adalah bentuk dasar yang diperoleh dengan membaca fungsi dari tabel kebenaran. Bentuk ini umumnya sangat jarang muncul, karena setiap suku di dalam bentuk kanonik harus mengandung literal atau peubah yang lengkap, baik dalam bentuk normal (x) atau dalam bentuk komplemennya x’.
Cara lain untuk mengekspresikan fungsi Boolean adalah bentuk baku (standard) . Pada bentuk ini, suku – suku yang membentuk fungsi dapat mengandung satu, dua, atau sejumlah literal. Dua tipe bentuk baku adalah bentuk baku SOP dan bentuk baku POS.
Contoh :
f (x,y,z) = y+ xy + xyz
f (x,y,z) = x(y+ z) (x+ y + z)

4. Penyederhanaan Fungsi Boolean (Minimasi fungsi)
Fungsi boolean dapat disederhanakan dalam 3 cara :
1. Secara aljabar, dengan menggunakan rumus atau
aksioma yang berlaku pada fungsi boolean
2. Menggunakan Peta Karnaugh
3. Menggunakan metode Quine Mc Cluskey (metode Tabulasi)

4.1 Secara Aljabar
Contoh :
1. f (x, y) = x + x‟ y
= (x + x) (x + y)
= 1 . (x + y)
= x + y
2. f (x, y) = x (x+ y)
= x x+ x y
= 0 + x y
= x y
3. f (x, y, z) = xyz + xy z + x y
= xz (y+ y) + x y
= xz . 1 + x y
4. f (x, y, z) = x y + xz + y z
= x y + xz + y z ( x + x)
= x y + xz + x y z + xy z
= x y ( 1 + z ) + xz ( 1 + y )
= x y + xz

5. Metode Peta Karnaugh (K-Map)
Metode Karnaugh Map (K-Map) adalah penjelasan tentang fungsi tabel kebenaran Boolean dalam bentuk gambar. Salah satu tujuan dari K-Map untuk menyederhanakan fungsi Boolean sampai enam variabel.
K-Map adalah diagram/peta yang terdiri dari beberapa kotak yang bersisian, setiap bujursangkar merepresentasikan sebuah minterm. Jumlah kotak tergantung pada jumlah variabel. Peta Karnaugh untuk dua variabel, akan berisi 4 bujursangkar. Untuk 3 variabel terdiri dari 8 bujursangkar, 4 variabel terdiri dari 16 bujursangkar, untuk 5 variabel terdiri dari 32 bujursangkar dan untuk 6 variabel terdiri dari 64 bujursangkar. Di halaman ini akan dijelaskan K-Map 2 variabel, 3 variabel, 4 variabel, 5 variabel dan 6 variabel.

5.1 Peta Karnaugh untuk 2 Variabel
Gambar 3 K-Map 2 variabel
Pada K-Map 2 variabel dimisalkan dua peubah di dalam fungsi Boolean adalah x dan y. Baris pada K-Map untuk peubah x dan kolom untuk peubah y. Setiap kotak merepresentasikan minterm dari kombinasi baris dan kolom yang bersesuaian. Dua kotak yang bersisian berbeda hanya satu literal.

5.2 Peta Karnaugh untuk 3 Variabel
 
Gambar 4 K-Map 3 Variabel
Pada K-Map 3 variabel (misalkan x, y dan z), jumlah kotak di dalam K-Map meningkat menjadi 23 = 8. Baris pada K-Map untuk peubah x dan kolom untuk peubah yz. Antara satu kolom dengan kolom yang lain hanya berbeda 1 literal. Setiap kotak merepresentasikan minterm dari kombinasi baris dan kolom yang bersesuaian.

5.3 Peta Karnaugh untuk 4 Variabel
 
Gambar 5 K-Map 4 Variabel
Misalkan empat peubah di dalam fungsi Boolean adalah w, x, y dan z. Jumlah kotak didalam K-Map menjadi 24 = 16. Baris pada K-Map untuk peubah wx dan kolom untuk peubah yz. Antara satu kolom dengan kolom berikutnya hanya berbeda satu literal. Setiap kotak merepresentasikan minterm dari kombinasi baris dan kolom yang bersesuaian.

5.4 Peta Karnaugh untuk 5 Variabel
 
Gambar 6 K-Map 5 Variabel
Pendefinisian K-Map 5 variabel yaitu hanya terjadi satu buah perubahan ke baris/ke kolom sebelum dan sesudahnya sama seperti pada K-Map 4 variabel. Namun harus diperhatikan terdapat garis pembatas antara 010 dan 110. Penentu kelompok dapat dilakukan dengan memperlakukan sistem cermin terhadap garis pembatas tersebut. Terdapat 32 bentuk minterm didalamnya.


5.5 Peta Karnaugh untuk 6 Variabel
 
Gambar 7 K-Map 6 Variabel
Pada K-Map 6 variabel terdapat 36 bentuk minterm di masing-masing bujur sangkar. Pendefinisiannya sama seperti bentuk K-Map sebelumnya yaitu hanya terdapat satu kali perubahan. Penentu kelompok didapatkan dengan melakukan sistem cermin terhadap garis pembatas yang terdapat diantara 010 dan 110.

Tidak ada komentar:

Poskan Komentar