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) = x’
y’ dan g (x, y) = (x + y)’ adalah dua buah fungsi yang
sama.
Contoh lain,
f (x, y, z) = x’ y’ z +
xy’ z’ + 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 x’ y’ z , xy’ z’ , 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) = x’ y’ z + xy’ z’ +
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’
= (x’ y’ z’ )’
(x’ y z’ )’ (x’ y 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 + x’ yz
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) = x’ y’
z + x’ y z + x y’
= x’ z (y’ + y) + x y’
= x’ z . 1 + x y’
4. f (x, y, z) = x y + x’ z
+ y z
= x y + x’ z + y z ( x + x’
)
= x y + x’ z + x y z + x’ y
z
= x y ( 1 + z ) + x’ z ( 1 +
y )
= x y + x’ z
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.
Sekian terima kasih dan semoga bermanfaat.