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.