boleaan aljabar 6790

7/18/2019 boleaan aljabar 6790

http://slidepdf.com/reader/full/boleaan-aljabar-6790 1/83

Rinaldi Munir/IF2151 Mat. Diskrit 1

Aljabar Boolean

Bahan Kuliah

Matematika Diskrit




Definisi Aljabar Boolean

Misalkan terdaat

! Dua oerator biner" # dan ⋅ ! $ebuah oerator uner" %.

! B " himunan &an' didefinisikan ada oerator #( ⋅( dan %

! ) dan 1 adalah dua elemen &an' berbeda dari B.

*uel

+ B( #( ⋅( %,disebut aljabar Boolean jika untuk setia a( b( c ∈ B berlaku

aksioma!aksioma atau ostulat -untin'ton berikut"



Rinaldi Munir/IF2151 Mat. Diskrit

1. Closure" +i, a # b ∈ B

+ii, a ⋅ b ∈ B

2. Identitas" +i, a # ) / a

+ii, a ⋅ 1 / a

. Komutatif" +i, a # b / b # a

+ii, a ⋅ b / b . a

0. Distributif"+i, a ⋅ +b # c, / +a ⋅ b, # +a ⋅ c,

+ii, a # +b ⋅ c, / +a # b, ⋅ +a # c,

5. Komlemen1" +i, a # a% / 1

+ii, a ⋅ a% / )




ntuk memun&ai sebuah aljabar Boolean(

harus dierlihatkan"

1. lemen!elemen himunan B(2. Kaidah oerasi untuk oerator biner dan

oerator uner(

. Memenuhi ostulat -untin'ton.




Aljabar Boolean Dua-Nilai

Aljabar Boolean dua!nilai"

! B 3)( 14

! oerator biner( # dan ⋅ ! oerator uner( %

! Kaidah untuk oerator biner dan oerator uner"

a b a ⋅ b a b a # b a a%

) ) ) ) ) ) ) 1

) 1 ) ) 1 1 1 )1 ) ) 1 ) 1

1 1 1 1 1 1




6ek aakah memenuhi ostulat -untin'ton"

1. Closure " jelas berlaku

2. Identitas" jelas berlaku karena dari tabel daat kita lihat bah7a"

+i, ) # 1 1 # ) 1+ii, 1 ⋅ ) ) ⋅ 1 )

. Komutatif" jelas berlaku den'an melihat simetri tabel oerator

biner.




0. Distributif" +i, a ⋅ +b # c, +a ⋅ b, # +a ⋅ c, daat ditunjukkan

benar dari tabel oerator biner di atas den'an membentuk tabelkebenaran"

a

b c b # c a ⋅ +b # c, a ⋅ b a ⋅ c +a ⋅ b, # +a ⋅ c,

) ) ) ) ) ) ) )

) ) 1 1 ) ) ) )

) 1 ) 1 ) ) ) )

) 1 1 1 ) ) ) )

1 ) ) ) ) ) ) )1 ) 1 1 1 ) 1 1

1 1 ) 1 1 1 ) 1

1 1 1 1 1 1 1 1




+ii, -ukum distributif a # +b ⋅ c, +a # b, ⋅ +a # c, daat

ditunjukkan benar den'an membuat tabel kebenaran den'an:ara &an' sama seerti +i,.

5. Komlemen" jelas berlaku karena *abel 8. memerlihatkan

bah7a"

+i, a # a; 1( karena ) # )% ) # 1 1 dan 1 # 1% 1 # ) 1+ii, a ⋅ a )( karena ) ⋅ )% ) ⋅ 1 ) dan 1 ⋅ 1% 1 ⋅ ) )

Karena kelima ostulat -untin'ton dienuhi( maka terbukti bah7a

3)( 14 bersama!sama den'an oerator biner # dan ⋅ oerator

komlemen ; meruakan aljabar Boolean.



Rinaldi Munir/IF2151 Mat. Diskrit <

Ekspresi Boolean

• Misalkan + B( #( ⋅( %, adalah sebuah aljabar Boolean. $uatu

eksresi Boolean dalam + B( #( ⋅( %, adalah"

+i, setia elemen di dalam B(+ii, setia eubah(

+iii, jika e1 dan e2 adalah eksresi Boolean( maka e1 # e2( e1 ⋅ e2( e1% adalah eksresi Boolean

6ontoh" )

1

a

b

a # b

a ⋅ b

a%⋅ +b # c,

a ⋅ b% # a ⋅ b ⋅ c% # b%( dan seba'ain&a



Rinaldi Munir/IF2151 Mat. Diskrit 1)

Mengevaluasi Ekspresi Boolean

• 6ontoh" a%⋅ +b # c,

jika a )( b 1( dan c )( maka hasil e=aluasi eksresi"

)%⋅ +1 # ), 1 ⋅ 1 1

• Dua eksresi Boolean dikatakan ekivalen +dilamban'kan

den'an ;%, jika keduan&a memun&ai nilai &an' sama untuksetia emberian nilai!nilai keada n eubah.

6ontoh"a ⋅ +b # c, +a . b, # +a ⋅ c,




Contoh. >erlihatkan bah7a a # a%b a # b .

>en&elesaian"

a b a% a%b a # a%b a # b

) ) 1 ) ) )

) 1 1 1 1 1

1 ) ) ) 1 1

1 1 ) ) 1 1

• >erjanjian" tanda titik +⋅, daat dihilan'kan dari enulisan

eksresi Boolean( ke:uali jika ada enekanan"

+i, a+b # c, ab # ac +ii, a # bc +a # b, +a # c,

+iii, a ⋅ ) ( bukan a)




Prinsip Dualitas

• Misalkan S adalah kesamaan +identity, di dalam aljabar

Boolean &an' melibatkan oerator #( ⋅( dan komlemen(

maka jika ern&ataan S ? dieroleh den'an :ara men''anti

⋅ den'an #

# den'an ⋅ ) den'an 1

1 den'an )

dan membiarkan oerator komlemen teta aa adan&a(

maka kesamaan S ? ju'a benar. S ? disebut seba'ai dual dariS .

Contoh.

+i, +a ⋅ 1,+) # a%, ) dualn&a +a # ), # +1 ⋅ a%, 1

+ii, a+a; # b, ab dualn&a a # a;b a # b




Hukum-hukum Aljabar Boolean1. -ukum identitas"

+i, a # ) a

+ii, a ⋅ 1 a

2. -ukum idemoten"

+i, a # a a

+ii, a ⋅ a a

. -ukum komlemen"

+i, a # a% 1+ii, aa% )

0. -ukum dominansi"

+i, a ⋅ ) )

+ii, a # 1 1

5. -ukum in=olusi"

+i, +a%,% a

. -ukum en&eraan"

+i, a # ab a

+ii, a+a # b, a

8. -ukum komutatif"

+i, a # b b # a

+ii, ab ba

9. -ukum asosiatif"

+i, a # +b # c, +a # b, # c

+ii, a +b c, +a b, c

<. -ukum distributif"+i, a # +b c, +a # b, +a # c,

+ii, a +b # c, a b # a c

1). -ukum De Mor'an"+i, +a # b,% a%b%

+ii, +ab,% a% # b%

11. -ukum )/1

+i, )% 1

+ii, 1% )




Contoh 7.3. Buktikan +i, a # a%b / a # b dan +ii, a+a% # b, / ab

>en&elesaian"

+i, a # a%b / +a # ab, # a%b +>en&eraan,

/ a # +ab # a%b, +Asosiatif,/ a # +a # a%,b +Distributif,

/ a # 1 • b +Komlemen,

/ a # b +Identitas,

+ii, adalah dual dari +i,




Funsi Boolean

• Funsi Boolean +disebut ju'a fun'si biner, adalah emetaan

dari Bn ke B melalui eksresi Boolean( kita menuliskann&a

seba'ai

f " Bn → B

&an' dalam hal ini Bn adalah himunan &an' beran''otakan

asan'an terurut 'anda!n +ordered n-tuple, di dalam daerah

asal B.




• $etia eksresi Boolean tidak lain meruakan fun'si

Boolean.

• Misalkan sebuah fun'si Boolean adalah

f + x( y( z , / xyz # x% y # y% z

Fun'si f memetakan nilai!nilai asan'an terurut 'anda!

+ x( y( z , ke himunan 3)( 14.

6ontohn&a( +1( )( 1, &an' berarti x / 1( y / )( dan z / 1

sehin''a f+1( )( 1, / 1 ⋅ ) ⋅ 1 # 1% ⋅ ) # )%⋅ 1 / ) # ) # 1 / 1 .




Contoh. 6ontoh!:ontoh fun'si Boolean &an' lain"

1. f + x, x

2. f + x( y, x% y # xy%# y%

. f + x( y, x% y%

0. f + x( y, + x # y,%

5. f + x( y( z , xyz %

• $etia eubah di dalam fun'si Boolean( termasuk dalam

bentuk komlemenn&a( disebut literal.

6ontoh" Fun'si h+ x( y( z , xyz % ada :ontoh di atas terdiridari buah literal( &aitu x( &( dan z %.




Contoh. Diketahui fun'si Booelan f + x( y( z , xy z %( n&atakan h

dalam tabel kebenaran.

>en&elesaian"

x y z f + x( y( z , xy z %

)

))

)

1

1

1

1

)

)1

1

)

)

1

1

)

1)

1

)

1

)

1

)

))

)

)

)

1

)



Rinaldi Munir/IF2151 Mat. Diskrit 1<

!omplemen Funsi

1. 6ara ertama" men''unakan hukum De Mor'an

-ukum De Mor'an untuk dua buah eubah( x1 dan x2( adalah

Contoh. Misalkan f + x( y( z , / x+ y% z % # yz ,( maka f %+ x( y( z , / + x+ y% z % # yz ,,%

/ x% # + y% z % # yz ,%

/ x% # + y% z %,% + yz ,%

/ x% # + y # z , + y% # z %,




2. 6ara kedua" men''unakan rinsi dualitas.

*entukan dual dari eksresi Boolean &an' mereresentasikan f (lalu komlemenkan setia literal di dalam dual tersebut.

Contoh. Misalkan f + x( y( z , x+ y% z % # yz ,( maka

dual dari f " x # + y% # z %, + y # z ,

komlemenkan tia literaln&a" x% # + y # z , + y% # z %, f %

@adi( f ;+ x( y( z , x% # + y # z ,+ y% # z %,




Bentuk !anonik

• Ada dua ma:am bentuk kanonik"

1. >enjumlahan dari hasil kali + sum-of-product atau $>,2. >erkalian dari hasil jumlah + product-of-sum atau >$,

6ontoh" 1. f + x( y( z , x% y% z # xy% z % # xyz $>

$etia suku +term, disebut minterm

2. g + x( y( z , + x # y # z ,+ x # y% # z ,+ x # y% # z %,

+ x% # y # z %,+ x% # y% # z ,

>$

$etia suku +term, disebut maxterm

• $etia minterm/maxterm men'andun' literal len'ka




Minterm Maxterm

x y $uku amban' $uku amban'

))

1

1

)1

)

1

x% y% x% y

xy%

x y

m) m1

m2

m

x # y x # y%

x% # y

x% # y%

M ) M 1

M 2 M




Minterm Maxterm

x y z $uku amban' $uku amban'

)

)

)

)1

1

11

)

)

1

1)

)

11

)

1

)

1)

1

)1

x% y% z %

x% y% z

x; y z %

x% y z x y% z %

x y% z

x y z % x y z

m)

m1

m2

m

m0

m5

m m8

x # y # z

x # y # z %

x # y%# z

x # y%# z % x%# y # z

x%# y # z %

x%# y%# z x%# y%# z %

M )

M 1

M 2 M M 0

M 5

M M 8




Contoh 7."#. C&atakan tabel kebenaran di ba7ah ini dalam bentuk

kanonik $> dan >$.

$abel 7."#

x y z f + x( y( z ,

)

))

)

1

1

11

)

)1

1

)

)

11

)

1)

1

)

1

)1

)

1)

)

1

)

)1




>en&elesaian"

+a, $>Kombinasi nilai!nilai eubah &an' men'hasilkan nilai fun'si

sama den'an 1 adalah ))1( 1))( dan 111( maka fun'si

Booleann&a dalam bentuk kanonik $> adalah

f + x( y( z , x% y% z # xy% z % # xyz

atau +den'an men''unakan lamban' minterm,(

+ x( y( z , m1 # m0 # m8 ∑ +1( 0( 8,




+b, >$Kombinasi nilai!nilai eubah &an' men'hasilkan nilai fun'si

sama den'an ) adalah )))( )1)( )11( 1)1( dan 11)( maka

fun'si Booleann&a dalam bentuk kanonik >$ adalah

f + x( y( z , / + x # y # z ,+ x # y%# z ,+ x # y%# z %,+ x%# y # z %,+ x%# y%# z ,

atau dalam bentuk lain(

+ x( y( z , / M ) M

2 M

M

5 M

/ ∏+)( 2( ( 5( ,




Contoh 7."". C&atakan fun'si Boolean f + x( y( z , x # y% z dalam

bentuk kanonik $> dan >$.

>en&elesaian"

+a, $>

x x+ y # y%,

xy # xy%

xy + z # z %, # xy%+ z # z %,

xyz # xyz % # xy% z # xy% z %

y% z y% z + x # x%,

&%E # %&%E

@adi 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 # m0 # m5 # m # m8 Σ +1(0(5((8,




+b, >$

f + 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 ,

@adi( 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 , M ) M 2 M ∏+)( 2( ,




!onversi Antar Bentuk !anonik

Misalkan f + x( y( E, Σ +1( 0( 5( ( 8,

dan f %adalah fun'si komlemen dari f (

f %+ x( y( z , Σ +)( 2( , m)# m2 # m

Den'an men''unakan hukum De Mor'an( kita daat memeroleh

fun'si f dalam bentuk >$"

f %+ x( y( z , + f %+ x( y( z ,,% +m) # m2 # m,%

m)% . m2% . m%

+ x% y% z %,% + x% y z’ ,% + x% y z ,%

+ x # y # z , + x # y% # z , + x # y% # E%, M ) M 2 M

∏ +)(2(,

@adi( f + x( y( E, Σ +1( 0( 5( ( 8, ∏ +)(2(,.

Kesimulan" m j% M j



Rinaldi Munir/IF2151 Mat. Diskrit )

Contoh. C&atakan

f + x( y( z , ∏ +)( 2( 0( 5, dan g +w( x( &( E, Σ+1( 2( 5( ( 1)( 15,

dalam bentuk $>.

>en&elesaian" f + x( y( E, Σ +1( ( ( 8,

g +w( x( y( z , ∏ +)( ( 0( 8( 9( <( 11( 12( 1( 10,




Contoh. 6arilah bentuk kanonik $> dan >$ dari f + x( y( z , y% #

y # x%&E%>en&elesaian"

+a, $>

f + x( y( E, y% # xy # x% yz % y% + x # x%, + z # z %, # xy + z # z %, # x% yz %

+ xy% # x% y%, + z # z %, # xyz # xyz % # x% yz % xy% z # xy% z % # x% y% z # x% y% z % # xyz # xyz % # x% yz %

atau f + x( y( E, m)# m1 # m2# m0# m5# m# m8

+b, >$ f + x( y( E, M x # y% # z %




Bentuk Baku

*idak harus men'andun' literal &an' len'ka.

6ontohn&a(

f + x( y( z , y% # xy # x% yz +bentuk baku $>

f + x( y( z , x+ y% # z ,+ x% # y # z %, +bentuk baku

>$,




Aplikasi Aljabar Boolean

". %arinan Pensaklaran & Switching Network '

$aklar" objek &an' memun&ai dua buah keadaan" buka dan tutu.

*i'a bentuk 'erban' alin' sederhana"

1. a x b

Output b han&a ada jika dan han&a jika x dibuka ⇒ x

2. a x y b

Output b han&a ada jika dan han&a jika x dan y dibuka ⇒ xy

. a x

c

b y

Output c han&a ada jika dan han&a jika x atau y dibuka ⇒ x # y




6ontoh ran'kaian ensaklaran ada ran'kaian listrik"

1. $aklar dalam hubun'an $RI" lo'ika ACD

amu

B

∞ $umber te'an'an

2. $aklar dalam hubun'an >ARA" lo'ika R

amu

B

∞ $umber *e'an'an




(. )ankaian *oika

Gerban' ACD Gerban' R Gerban' C* +in!erter ,

y

x xy

y

x x" y x# x




Contoh. C&atakan fun'si f + x( y( z , xy # x% y ke dalam ran'kaianlo'ika.

@a7ab" +a, 6ara ertama

x#

x

y xy

x

y x#y

xy"x#y




+b, 6ara kedua

+:, 6ara keti'a

x#

xy

x y

x#y

xy"x #y

x H

x y x

y

x H y

x y"x H y




Gerban' turunan

Gerban' CACD Gerban' R

Gerban' CR Gerban' CR

x

y+ xy ,H

x

y+ x"y ,H

x

y# x y

x

y#+ x y ,H




x H

y H x H y H

eki=alen den'an x

y + x"y ,H

x H

y H

x H # y H eki=alen den'an

x

y+ x y ,H

x

y+ x # y ,H eki=alen den'an

x

y+ x # y ,H

x # y




Pen+e,erhanaan Funsi Boolean

Contoh. f + x( y, x% y # xy% # y%

disederhanakan menjadi

f + x( y, x% # y%

>en&ederhanaan fun'si Boolean daat dilakukan den'an :ara"

1. $e:ara aljabar

2. Men''unakan >eta Karnau'h

. Men''unakan metode Juine M: 6luske& +metode *abulasi,




". Pen+e,erhanaan eara Aljabar

Contoh"

1. f + x( y, x # x% y

+ x # x%,+ x # y,

1 ⋅ + x # y ,

x # y

2. 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




(. Peta !arnauh

a. $eta %arnaugh dengan dua peubah y

) 1

m) m1 x ) x% y% x% y

m2 m 1 xy% xy

b. $eta dengan tiga peubah

yz)) )1 11 1)

m) m1 m m2 x ) x% y% z % x% y% z x% yz x% yz %

m0 m5 m8 m 1 xy% z % xy% z xyz xyz %




Contoh. Diberikan tabel kebenaran( 'ambarkan >eta Karnau'h.

x y z f + x( y( z ,

) ) ) )

) ) 1 )

) 1 ) 1

) 1 1 )

1 ) ) )

1 ) 1 )

1 1 ) 1

1 1 1 1

yz)) )1 11 1)

x ) ) ) ) 1

1 ) ) 1 1




b. $eta dengan empat peubah

yz)) )1 11 1)

m) m1 m m2 wx )) w% x% y% z % w% x% y% z w% x% yz w% x% yz %

m0 m5 m8 m )1 w% xy% z % w% xy% z w% xyz w% xyz %

m12 m1 m15 m10 11 wxy% z % wxy% z wxyz wxyz %

m9 m< m11 m1) 1) wx% y% z % wx% y% z wx% yz wx% yz %

C h Dib ik b l k b b k > K h




Contoh. Diberikan tabel kebenaran( 'ambarkan >eta Karnau'h.

w x y z f +w( x( y( z ,

) ) ) ) )) ) ) 1 1

) ) 1 ) )

) ) 1 1 )) 1 ) ) )) 1 ) 1 )

) 1 1 ) 1) 1 1 1 1

1 ) ) ) )1 ) ) 1 )1 ) 1 ) )

1 ) 1 1 )

1 1 ) ) )1 1 ) 1 )

1 1 1 ) 11 1 1 1 )

yz)) )1 11 1)

wx )) ) 1 ) 1

)1 ) ) 1 1

11 ) ) ) 1

1) ) ) ) )




$eknik /inimisasi Funsi Boolean ,enan Peta !arnauh

1. $asangan" dua buah 1 &an' bertetan''a

yz)) )1 "1 ")

wx )) ) ) ) )

)1 ) ) ) )

"" ) ) 1 1

1) ) ) ) )

Sebelum disederhana&an" f +w( x( y( z , wxyz # wxyz %

'asil $enyederhanaan" f +w( x( y( z , wxy

Bukti se:ara aljabar"

f +w( x( y( z , wxyz # wxyz %

wxy+ z # z %,

wxy+1,

wxy




2. %uad " emat buah 1 &an' bertetan''a

yz)) )1 11 1)

wx )) ) ) ) )

)1 ) ) ) )

"" 1 1 1 1

1) ) ) ) )

Sebelum disederhana&an" f +w( x( y( z , wxy% z % # wxy% z # wxyz # wxyz %

'asil penyederhanaan" f +w( x( y( z , wx





f +w( x( y( z , wxy% # wxy wx+ z % # z ,

wx+1,

wx

yz

)) )1 11 1)

wx )) ) ) ) )

)1 ) ) ) )

11 1 1 1 1

1) ) ) ) )




6ontoh lain"

yz#) #1 11 1)

wx )) ) ) ) )

)1 ) ) ) )

"1 1 1 ) )

") 1 1 ) )

$ebelum disederhanakan" f +w( x( y( z , wxy% z % # wxy% z # wx% y% z % # wx% y%E

'asil penyederhanaan" f +w( x( y( z , wy%




. O&tet " delaan buah 1 &an' bertetan''a

yz

)) )1 11 1)wx ))

) ) ) )

)1) ) ) )

"11 1 1 1

") 1 1 1 1

Sebelum disederhana&an" f +a( b( c( d , wxy% z % # wxy% z # wxyz # wxyz % #

wx% y% z % # wx% y% z # wx% yz # wx% yz %

'asil penyederhanaan" f +w( x( y( z , w





f +w( x( y( z , wy% # wy

w+ y% # y, w

yz)) )1 11 1)

wx )) ) ) ) )

)1 ) ) ) )

11 1 1 1 1

1) 1 1 1 1




Contoh 0."(. Andaikan suatu tabel kebenaran telah diterjemahkan ke dalam

>eta Karnau'h. $ederhanakan fun'si Boolean &an' bersesuaian sesederhana

mun'kin.

yz

)) )1 11 1)

wx )) ) 1 1 1

)1 ) ) ) 1

11 1 1 ) 1

1) 1 1 ) 1

@a7ab" +lihat >eta Karnau'h, f +w( x( y( z , wy% # yz % # w% x% z




Contoh 0."3. Minimisasi fun'si Boolean &an' bersesuaian den'an >eta

Karnau'h di ba7ah ini.

yz)) )1 11 1)

wx )) ) ) ) )

)1 ) 1 ) )

11 1 1 1 1

1) 1 1 1 1

@a7ab" +lihat >eta Karnau'h, f +w( x( y( z , w # xy% z




@ika en&elesaian 6ontoh 5.1 adalah seerti di ba7ah ini"

yz)) )1 11 1)

wx )) ) ) ) )

)1 ) 1 ) )

11 1 1 1 1

1) 1 1 1 1

maka fun'si Boolean hasil en&ederhanaan adalah

f +w( x( y( z , / w # w% xy% z +jumlah literal / 5,

&an' tern&ata masih belum sederhana dibandin'kan f +w( x( y( z , / w # xy% z

+jumlah literal / 0,.




Contoh 0."1. +>en''ulun'an/rolling , $ederhanakan fun'si Boolean &an'

bersesuaian den'an >eta Karnau'h di ba7ah ini.

yz)) )1 11 1)

wx )) ) ) ) )

)1 1 ) ) 1

11 1 ) ) 1

1) ) ) ) )

@a7ab" f +w( x( y( z , xy% z % # xyz % belum sederhana




>en&elesaian &an' lebih minimal"

yz)# )1 11 1#

wx )) ) ) ) )

)" 1 ) ) 1

1" 1 ) ) 1

1) ) ) ) )

f +w( x( y( z , / xz % ///K lebih sederhana




Contoh 0."". $ederhanakan fun'si Boolean f + x( y( z , x% yz # xy% z % # xyz #

xyz %.

@a7ab"

>eta Karnau'h untuk fun'si tersebut adalah"

yz)) )1 11 1)

x ) 1

1 1 1 1

-asil en&ederhanaan" f + x( y( z , yz # xz %




Contoh 0."0" +Kelomok berlebihan, $ederhanakan fun'si Boolean &an'

bersesuaian den'an >eta Karnau'h di ba7ah ini.

yz

)) )1 11 1)

wx )) ) ) ) )

)1 ) 1 ) )

11 ) 1 1 )

1) ) ) 1 )

@a7ab" f +w( x( y( z , xy% z # wxz # wyz → masih belum sederhana.




>en&elesaian &an' lebih minimal"

yz)) )1 11 1)

wx )) ) ) ) )

)1 ) 1 ) )

11 ) 1 1 )

1) ) ) 1 )

f +w( x( y( z , xy% z # wyz lebih sederhana



Rinaldi Munir/IF2151 Mat. Diskrit )

Contoh 0."2. $ederhanakan fun'si Boolean &an' bersesuaian den'an >eta

Karnau'h di ba7ah ini.

cd)) )1 11 1)

ab )) ) ) ) )

)1 ) ) 1 )

11 1 1 1 1

1) ) 1 1 1

@a7ab" +lihat >eta Karnau'h di atas, f +a( b( c( d , ab # ad # ac # bcd




Contoh 0."7. Minimisasi fun'si Boolean f + x( y( z , x% z # x% y # xy% z # yz

@a7ab"

x’z x% z + y # y%, x% yz # x% y% z

x% y x% y+ z # z %, x% yz # x% yz % yz yz + x # x%, xyz # x% yz

f + x( y( z , x% z # x% y # xy% z # yz

x% yz # x% y% z # x% yz # x% yz % # xy% z # xyz # x% yz

x% yz # x% y% z # x% yz % # xyz # xy% z

>eta Karnau'h untuk fun'si tersebut adalah"

yz)) )1 11 1)

x ) ) 1 1 1

1 ) 1 1 )

-asil en&ederhanaan" f + x( y( z , z # x% yz %




>eta Karnau'h untuk lima eubah

))) ))1 )11 )1) 11) 111 1)1 1))

)) m) m1 m m2 m m8 m5 m0

)1 m9 m< m11 m1) m10 m15 m1 m12

11 m20 m25 m28 m2 m) m1 m2< m29

1) m1 m18 m1< m19 m22 m2 m21 m2)

Garis en:erminan




Contoh 0.(". +6ontoh en''unaan >eta 5 eubah, 6arilah fun'si sederhana

dari f +!( w( x( y( z , / Σ +)( 2( 0( ( <( 11( 1( 15( 18( 21( 25( 28( 2<( 1,

@a7ab"

>eta Karnau'h dari fun'si tersebut adalah"

xyz

))

)

))

1

)1

1

)1

)

11

)

11

1

1)

1

1)

)

!w

))

1 1 1 1

)1 1 1 1 1

11 1 1 1 1

1) 1 1

@adi f +!( w( x( y( z , / wz # !%w% z % # !y% z




Kondisi (on’t care

$abel 0."2

w x y z desimal

))

))

)

)

)

)1

1

1

1

11

1

1

))

))

1

1

1

1)

)

)

)

11

1

1

))

11

)

)

1

1)

)

1

1

))

1

1

)1

)1

)

1

)

1)

1

)

1

)1

)

1

)1

2

0

5

89

<

don’t care

don’t care

don’t caredon’t care

don’t care

don’t care

C t h 0 (0 Dib ik * b l 5 18 Mi i i i f i f d h




Contoh 0.(0. Diberikan *abel 5.18. Minimisasi fun'si f sesederhana

mun'kin.

$abel 0."7

a b c d f +a( b( c( d ,))

))

))

))1

111

1

11

1

))

))

11

11)

)))

1

11

1

))

11

))

11)

)11

)

)1

1

)1

)1

)1

)1)

1)1

)

1)

1

1)

)1

11

)1

)

) )

) )

) ) )




@a7ab" >eta Karnau'h dari fun'si tersebut adalah"

cd)) )1 11 1)

ab

))

1 ) 1 )

)1 1 1 1 )

11 ) ) ) )

1) ) ) ) )

-asil en&ederhanaan" f +a( b( c( d , bd # c%d % # cd




Contoh 0.(2. Minimisasi fun'si Boolean f + x( y( z , x% yz # x% yz % # xy% z % #

y% z . Gambarkan ran'kaian lo'ikan&a.

@a7ab" Ran'kaian lo'ika fun'si f + x( y( z , sebelum diminimisasikan adalahseerti di ba7ah ini"

x y z

x H yz

x H yz H

xy H z H

xy H z




Minimisasi den'an >eta Karnau'h adalah seba'ai berikut"

yz)) )1 11 1)

x ) ) ) 1 1

1 1 1 ) )

-asil minimisasi adalah f + x( y( z , x% y # xy%.




Contoh 0.(. Berba'ai sistem di'ital men''unakan kode binary coded

decimal +B6D,. Diberikan *abel 5.1< untuk kon=ersi B6D ke kode *xcess!

seba'ai berikut"

$abel 0."4

Masukan B6D Keluaran kode *xcess!

w x y z f 1+w( x( y( z , f 2+w( x( y( z , f +w( x( y( z , f 0+w( x( y( z ,

)

12

0

5

8

9<

)

))

)

)

)

)

)

11

)

))

)

1

1

1

1

))

)

)1

1

)

)

1

1

))

)

1)

1

)

1

)

1

)1

)

))

)

)

1

1

1

11

)

11

1

1

)

)

)

)1

1

))

1

1

)

)

1

1)

1

)1

)

1

)

1

)

1)

+ , f + ,




+a, f 1+w( x( y( z , yz)) )1 11 1)

wx ))

)1 1 1 1

11 ) ) ) )

1) 1 1 ) )

f 1+w( x( y( z , w # xz # xy w # x+ y # z ,

+b, f 2+w( x( y( z , yz)) )1 11 1)

wx )) 1 1 1

)1 1

11 ) ) ) )

1) 1 ) )

f 2+w( x( y( z , xy% z % # x% z # x% y xy% z % # x%+ y # z ,

+:, f+w x y z,




+:, f +w( x( y( z , yz)) )1 11 1)

wx )) 1 1

)1 1 1

11 ) ) ) )

1) 1 ) )

f +w( x( y( z , y% z % # yz

+d, f 0+w( x( y( z ,

yz)) )1 11 1)

wx )) 1 1

)1 1 1

11 ) ) )

1) 1 ) )

f 0+w( x( y( z , z %

x y zw




x y zw

f .

f 0

f 2

f 1




Contoh 7.13

Minimisasi fun'si Boolean berikut +hasil en&ederhanaan

dalam bentuk baku $> dan bentuk baku >$,"

f +w( x( y( z , Σ +1( ( 8( 11( 15,

den'an kondisi don’t care adalah d +w( x( y( z , Σ +)( 2( 5,

> l i




>en&elesaian"

>eta Karnau'h dari fun'si tersebut adalah"

) ) ) 1 1 1 1 )

) )

) 1

1 1

1 )

) 1 1 )

) ) 1 )

) ) 1

) ) 1 )

)

y z

w x

-asil en&ederhanaan dalam bentuk $>

f +w( x( y( z , yz # w% z +$>, +'aris enuh,

dan bentuk baku >$ adalah

f +w( x( y( z , z +w% # y, +>$, +'aris utus2,

M t d Q i




Metode Quine-

McCluskey Metode >eat Karnau'h tidak man'kus untuk

jumlah eubah +ukuran eta semakin besar,.

Metode eta Karnau'h lebih sulit diro'ram

den'an komuter karena dierlukan en'amatan=isual untuk men'identifikasi minterm-minterm

&an' akan dikelomokkan.

Metode alternatif adalah metode Juine!M:6luske& . Metode ini mudah diro'ram.

Contoh 7 12




Contoh 7.12

$ederhanakan fun'si Boolean f +w( x( y( z , Σ +)( 1( 2( 9( 1)( 11( 10( 15,.

>en&elesaian"+i, an'kah 1 samai 5"

+a, +b, +:,

term w x y z term w x y z term w x y z

) ) ) ) ) √ )(1 ) ) ) ! )(2(9(1) ! ) ! )

)(2 ) ) ! ) √ )(9(2(1) ! ) ! )

1 ) ) ) 1 √ )(9 ! ) ) ) √

2 ) ) 1 ) √ 1)(11(10(15 1 ! 1 !

9 1 ) ) ) √ 2(1) ! ) 1 ) √ 1)(10(11(15 1 ! 1 !

9(1) 1 ) ! ) √

1) 1 ) 1 ) √

1)(11 1 ) 1 ! √

11 1 ) 1 1 √ 1)(10 1 ! 1 ) √

10 1 1 1 ) √

11(15 1 ! 1 1 √ 15 1 1 1 1 √ 10(15 1 1 1 ! √




+i, an'kah dan 8"

minterm

Bentuk rima ) 1 2 9 1) 11 10 15

√ )(1 × ×

√ )(2(9(1) × × × ×

√ 1)(11(10(15 × × × ×

? ? ? ? ? ?

√ √ √ √ √ √ √ √

Bentuk rima &an' terilih adalah"

)(1 &an' bersesuaian den'an term w% x% y

)( 2( 9( 1) &an' bersesuaian den'an term x% z %

1)( 11( 10( 15 &an' bersesuaian den'an term wy

$emua bentuk rima di atas sudah men:aku semua minterm dari fun'si Boolean semula. Den'an

demikian( fun'si Boolean hasil en&ederhanaan adalah f +w( x( y( z , w% x% y% # x% z % # wy.

Contoh 7 17




Contoh 7.17

$ederhanakan fun'si Boolean f +w( x( y( z , Σ +1(0((8(9(<(1)(11(15,

>en&elesaian"

+i, an'kah 1 samai 5"

+a, +b, +:,

term w x y z term w x y z term w x y z

1 ) ) ) 1 √ 1(< ! ) ) 1 9(<(1)(11 1 ) ! !

0 ) 1 ) ) √ 0( ) 1 ! ) 9(1)(<(11 1 ) ! !

9 1 ) ) ) √ 9(< 1 ) ) ! √ 9(1) 1 ) ! ) √

) 1 1 ) √

< 1 ) ) 1 √ (8 ) 1 1 !

1) 1 ) 1 ) √ <(11 1 ) ! 1 √

1)(1 1 1 ) 1 ! √

8 ) 1 1 1 √

11 1 ) 1 1 √ 8(15 ! 1 1 1

11(15 1 ! 1 115 1 1 1 1 √




+i, an'kah dan 8

minterm

Bentuk rima 1 0 8 9 < 1) 11 15

√ 1(< × ×

√ 0( × ×

(8 × ×

8(15 × ×

11(15 × ×

√ 9(<(1)(11 × × × ×

? ? ? ?

√ √ √ √ √ √ √

$amai taha ini( masih ada dua minterm &an' belum ter:aku dalam bentuk rima terilih( &aitu 8 dan 15.

Bentuk rima &an' tersisa +tidak terilih, adalah +(8,( +8(15,( dan +11( 15,. Dari keti'a kandidat ini( kita ilih bentuk rima +8(15, karena bentuk rima ini men:akuminterm 8 dan 15 sekali'us.




minterm

Bentuk rima 1 0 8 9 < 1) 11 15

√ 1(< × ×

√ 0( × ×

(8 × ×

√ 8(15 × ×

11(15 × ×

√ 9(<(1)(11 × × × ×

? ? ? ?

√ √ √ √ √ √ √ √ √

$ekaran'( semua minterm sudah ter:aku dalam bentuk rima terilih. Bentuk rima &an' terilih adalah"

1(< &an' bersesuaian den'an term x% y% z

0( &an' bersesuaian den'an term w% xz %8(15 &an' bersesuaian den'an term xyz

9(<(1)(11 &an' bersesuaian den'an term wx%

Den'an demikian( fun'si Boolean hasil en&ederhanaan adalah f +w( x( y( z , x% y% z # w% xz % # xyz # wx%.




atihan soal

1. Imlementasikan fun'si f + x( y( z , Σ +)( , dan

han&a den'an 'erban' CACD saja.

2. Gunakan >eta Karnau'h untuk meran:an'

ran'kaian lo'ika &an' daat menentukanaakah sebuah an'ka desimal &an'

direresentasikan dalam bit biner meruakan

bilan'an 'ena atau bukan +&aitu( memberikan

nilai 1 jika 'ena dan ) jika tidak,.

$ebuah instruksi dalam sebuah ro'ram adalah




. $ebuah instruksi dalam sebuah ro'ram adalah

if A > B then writeln(A) else

writeln(B);

Cilai dan B &an' dibandin'kan masin'!masin'

anjan'n&a dua bit +misalkan a1a2 dan b1b2,.+a, Buatlah ran'kaian lo'ika +&an' sudah disederhanakan

tentun&a, &an' men'hasilkan keluaran 1 jika B atau

) jika tidak.

+b, Gambarkan kembali ran'kaian lo'ikan&a jika han&amen''unakan 'erban' ++( saja +etunjuk" 'unakan

hukum de Mor'an,



5. Buatlah ran'kaian lo'ika &an' menerima

masukan dua!bit dan men'hasilkan

keluaran berua kudrat dari masukan.

$eba'ai :ontoh( jika masukann&a 11 +

dalam sistem desimal,( maka keluarann&a

adalah 1))1 +< dalam sistem desimal,.

boleaan aljabar 6790

Documents