ALJABAR BOOLEAN II

SISTEM DIGITALSISTEM DIGITAL

TEKNIK INFORMATIKATEKNIK INFORMATIKA

UNIVERSITASUNIVERSITAS TRUNOJOYOTRUNOJOYORahmadyRahmady LiyantantoLiyantanto, S.kom, S.kom

liyantanto@gmail.comliyantanto@gmail.com

10/25/201110/25/2011 22

PembahasanPembahasannn FungsiFungsi BooleanBooleannn KomplemenKomplemen FungsiFungsinn BentukBentuk KanonikKanonik

àà SOPSOPàà POSPOS

nn AplikasiAplikasi AljabarAljabar BooleanBoolean

10/25/201110/25/2011 33

Fungsi BooleanFungsi Booleannn Fungsi BooleanFungsi Boolean (disebut juga fungsi biner)(disebut juga fungsi biner)

adalah pemetaan dariadalah pemetaan dari BnBn keke BB melalui ekspresimelalui ekspresiBoolean, kita menuliskannya sebagaiBoolean, kita menuliskannya sebagai

ff :: BnBn ®® BByang dalam hal iniyang dalam hal ini BnBn adalah himpunan yangadalah himpunan yangberanggotakan pasangan terurut gandaberanggotakan pasangan terurut ganda--nn((ordered nordered n--tupletuple) di dalam daerah asal) di dalam daerah asal BB..

nn Setiap ekspresi Boolean tidak lain merupakanSetiap ekspresi Boolean tidak lain merupakanfungsi Boolean.fungsi Boolean.

10/25/201110/25/2011 44

nn Misalkan sebuah fungsi Boolean adalahMisalkan sebuah fungsi Boolean adalahff((xx,, yy,, zz) =) = xyzxyz ++ xx’’yy ++ yy’’zz

FungsiFungsi ff memetakan nilaimemetakan nilai--nilai pasangan terurutnilai pasangan terurutgandaganda--3 (3 (xx,, yy,, zz) ke himpunan {0, 1}.) ke himpunan {0, 1}.Contohnya, (1, 0, 1) yang berartiContohnya, (1, 0, 1) yang berarti xx = 1,= 1, yy = 0, dan= 0, danzz = 1= 1sehingga f(1, 0, 1) = 1sehingga f(1, 0, 1) = 1 ×× 00 ×× 1 + 1’1 + 1’ ×× 0 + 0’0 + 0’×× 1 = 0 +1 = 0 +0 + 1 = 1 .0 + 1 = 1 .

10/25/201110/25/2011 55

nn ff((xx) =) = xxnn ff((xx,, yy) =) = xx ’’yy ++ xyxy ’+’+ yy ’’nn ff((xx,, yy) =) = xx ’’ yy ’’nn ff((xx,, yy) = () = (xx ++ yy)’)’nn ff((xx,, yy,, zz) =) = xyzxyz ’’

ContohContoh--contoh fungsi Boolean yang lain:contoh fungsi Boolean yang lain:

10/25/201110/25/2011 66

nn Setiap peubah di dalam fungsi Boolean,Setiap peubah di dalam fungsi Boolean,termasuk dalam bentuk komplemennya,termasuk dalam bentuk komplemennya,disebutdisebut literalliteral..

nn Contoh: FungsiContoh: Fungsi hh((xx,, yy,, zz) =) = xyzxyz’ pada’ padacontoh di atas terdiri dari 3 buah literal,contoh di atas terdiri dari 3 buah literal,yaituyaitu xx, y, dan, y, dan zz’.’.

10/25/201110/25/2011 77

Diketahui fungsi Booelan f(x, y, z) = xy z’,nyatakan h dalam tabel kebenaran.

Contoh.

Penyelesaian: x y z f(x, y, z) = xy z’00001111

00110011

01010101

00000010

10/25/201110/25/2011 88

nn Cara pertama: menggunakan hukum DeCara pertama: menggunakan hukum DeMorganMorganHukum De Morgan untuk dua buah peubah,Hukum De Morgan untuk dua buah peubah,xx1 dan1 dan xx2, adalah2, adalah

Komplemen Fungsi

10/25/201110/25/2011 99

nn MisalkanMisalkan ff((xx,, yy,, zz) =) = xx((yy’’zz’ +’ + yzyz), maka), makaff ’(’(xx,, yy,, zz) = () = (xx((yy’’zz’ +’ + yzyz))’))’

== xx’ + (’ + (yy’’zz’ +’ + yzyz)’)’== xx’ + (’ + (yy’’zz’)’ (’)’ (yzyz)’)’== xx’ + (’ + (yy ++ zz) () (yy’ +’ + zz’)’)

Contoh.

10/25/201110/25/2011 1010

nn CaraCara keduakedua:: menggunakanmenggunakan prinsipprinsip dualitasdualitas..TentukanTentukan dualdual daridari ekspresiekspresi BooleanBoolean yangyangmerepresentasikanmerepresentasikan ff,, lalulalu komplemenkankomplemenkansetiapsetiap literalliteral didi dalamdalam dualdual tersebuttersebut..

Misalkan f(x, y, z) = x(y’z’ + yz), makadual dari f: x + (y’ + z’) (y + z)komplemenkan tiap literalnya: x’ + (y + z) (y’ + z’) = f ’

Jadi, f ‘(x, y, z) = x’ + (y + z)(y’ + z’)

10/25/201110/25/2011 1111

BentukBentuk KanonikKanonik

Jadi, ada dua macam bentuk kanonik:Penjumlahan dari hasil kali (sum-of-product atau SOP)Perkalian dari hasil jumlah (product-of-sum atau POS)

10/25/201110/25/2011 1212

Contoh :Contoh :

1. f(x, y, z) = x’y’z + xy’z’ + xyz à SOPSetiap 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 literallengkap

10/25/201110/25/2011 1313

Minterm Maxterm

x y Suku Lambang Suku Lambang

0011

0101

x’y’x’yxy’x y

m0m1m2m3

x + yx + y’x’ + yx’ + y’

M0M1M2M3

10/25/201110/25/2011 1414

Minterm Maxterm

x y z Suku Lambang Suku Lambang00001111

00110011

01010101

x’y’z’x’y’zx‘y z’x’y zx y’z’x y’zx y z’x y z

m0m1m2m3m4m5m6m7

x + y + zx + y + z’x + y’+zx + y’+z’x’+ y + zx’+ y + z’x’+ y’+ zx’+ y’+ z’

M0M1M2M3M4M5M6M7

10/25/201110/25/2011 1515

Contoh Soal:Contoh Soal:nn NyatakanNyatakan tabeltabel kebenarankebenaran didi bawahbawah iniini dalamdalam

bentukbentuk kanonikkanonik SOPSOP dandan POSPOS..

x y z f(x, y, z)00001111

00110011

01010101

01001001

10/25/201110/25/2011 1616

nn PenyelesaianPenyelesaian::SOPSOPKombinasiKombinasi nilainilai--nilainilai peubahpeubah yangyang menghasilkanmenghasilkannilainilai fungsifungsi samasama dengandengan 11 adalahadalah 001001,, 100100,, dandan111111,, makamaka fungsifungsi BooleannyaBooleannya dalamdalam bentukbentukkanonikkanonik SOPSOP adalahadalah

ff((xx,, yy,, zz)) == xx’’yy’’zz ++ xyxy’’zz’’ ++ xyzxyzatauatau (dengan(dengan menggunakanmenggunakan lambanglambang mintermminterm),),

ff((xx,, yy,, zz)) == mm11 ++ mm44 ++ mm77 == åå ((11,, 44,, 77))

10/25/201110/25/2011 1717

Contoh:Nyatakan fungsi Boolean f(x, y, z) = x + y’z dalambentuk kanonik SOP dan POS.Penyelesaian:(a) SOPx = x(y + y’)

= xy + xy’= xy (z + z’) + xy’(z + z’)= xyz + xyz’ + xy’z + xy’z’

y’z = y’z (x + x’)= xy’z + x’y’z

Jadi f(x, y, z) = x + y’z= xyz + xyz’ + xy’z + xy’z’ + xy’z + x’y’z= x’y’z + xy’z’ + xy’z + xyz’ + xyz

atau f(x, y, z) = m1 + m4 + m5 + m6 + m7 = S (1,4,5,6,7)

10/25/201110/25/2011 1818

(b) POSf(x, y, z) = x + y’z

= (x + y’)(x + z)x + y’ = x + y’ + zz’

= (x + y’ + z)(x + y’ + z’)x + z = x + z + yy’

= (x + y + z)(x + y’ + z)Jadi, f(x, y, z) = (x + y’ + z)(x + y’ + z’)(x + y + z)(x + y’ + z)

= (x + y + z)(x + y’ + z)(x + y’ + z’)atau f(x, y, z) = M0M2M3 = Õ(0, 2, 3)

10/25/201110/25/2011 1919

Aplikasi Aljabar BooleanAplikasi Aljabar BooleanNyatakan fungsiNyatakan fungsi ff((xx,, yy,, zz) =) = xyxy ++ xx’’yy ke dalamke dalamrangkaian logika.rangkaian logika.

Jawab: (a) Cara pertama

x'

x

yxy

x

yx'y

xy+x'y

10/25/201110/25/2011 2020

(b) Cara kedua

x'

xyxy

x'y

xy+x'y

10/25/201110/25/2011 2121

x'

xy

x y

x'y

xy+x'y

(c) Cara ketiga

10/25/201110/25/2011 2222

Penyederhanaan Fungsi BooleanPenyederhanaan Fungsi Boolean

nn Penyederhanaan Secara AljabarPenyederhanaan Secara AljabarContoh:

f(x, y) = x + x’y= (x + x’)(x + y)= 1 × (x + y )= x + y

10/25/201110/25/2011 2323

f(x, y, z) = x’y’z + x’yz + xy’= x’z(y’ + y) + xy’

= x’z + xz’

f(x,y,z) = xy + x’z + yz = xy + x’z + yz(x +x’)

= xy + x’z + xyz + x’yz= xy(1 + z) + x’z(1 + y) = xy + x’z