Post on 14-Jan-2016
description
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
7/18/2019 boleaan aljabar 6790
http://slidepdf.com/reader/full/boleaan-aljabar-6790 2/83
Rinaldi Munir/IF2151 Mat. Diskrit 2
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"
7/18/2019 boleaan aljabar 6790
http://slidepdf.com/reader/full/boleaan-aljabar-6790 3/83
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% / )
7/18/2019 boleaan aljabar 6790
http://slidepdf.com/reader/full/boleaan-aljabar-6790 4/83
Rinaldi Munir/IF2151 Mat. Diskrit 0
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.
7/18/2019 boleaan aljabar 6790
http://slidepdf.com/reader/full/boleaan-aljabar-6790 5/83
Rinaldi Munir/IF2151 Mat. Diskrit 5
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
7/18/2019 boleaan aljabar 6790
http://slidepdf.com/reader/full/boleaan-aljabar-6790 6/83
Rinaldi Munir/IF2151 Mat. Diskrit
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.
7/18/2019 boleaan aljabar 6790
http://slidepdf.com/reader/full/boleaan-aljabar-6790 7/83
Rinaldi Munir/IF2151 Mat. Diskrit 8
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
7/18/2019 boleaan aljabar 6790
http://slidepdf.com/reader/full/boleaan-aljabar-6790 8/83
Rinaldi Munir/IF2151 Mat. Diskrit 9
+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.
7/18/2019 boleaan aljabar 6790
http://slidepdf.com/reader/full/boleaan-aljabar-6790 9/83
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
7/18/2019 boleaan aljabar 6790
http://slidepdf.com/reader/full/boleaan-aljabar-6790 10/83
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,
7/18/2019 boleaan aljabar 6790
http://slidepdf.com/reader/full/boleaan-aljabar-6790 11/83
Rinaldi Munir/IF2151 Mat. Diskrit 11
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)
7/18/2019 boleaan aljabar 6790
http://slidepdf.com/reader/full/boleaan-aljabar-6790 12/83
Rinaldi Munir/IF2151 Mat. Diskrit 12
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
7/18/2019 boleaan aljabar 6790
http://slidepdf.com/reader/full/boleaan-aljabar-6790 13/83
Rinaldi Munir/IF2151 Mat. Diskrit 1
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% )
7/18/2019 boleaan aljabar 6790
http://slidepdf.com/reader/full/boleaan-aljabar-6790 14/83
Rinaldi Munir/IF2151 Mat. Diskrit 10
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,
7/18/2019 boleaan aljabar 6790
http://slidepdf.com/reader/full/boleaan-aljabar-6790 15/83
Rinaldi Munir/IF2151 Mat. Diskrit 15
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.
7/18/2019 boleaan aljabar 6790
http://slidepdf.com/reader/full/boleaan-aljabar-6790 16/83
Rinaldi Munir/IF2151 Mat. Diskrit 1
• $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 .
7/18/2019 boleaan aljabar 6790
http://slidepdf.com/reader/full/boleaan-aljabar-6790 17/83
Rinaldi Munir/IF2151 Mat. Diskrit 18
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 %.
7/18/2019 boleaan aljabar 6790
http://slidepdf.com/reader/full/boleaan-aljabar-6790 18/83
Rinaldi Munir/IF2151 Mat. Diskrit 19
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
)
7/18/2019 boleaan aljabar 6790
http://slidepdf.com/reader/full/boleaan-aljabar-6790 19/83
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 %,
7/18/2019 boleaan aljabar 6790
http://slidepdf.com/reader/full/boleaan-aljabar-6790 20/83
Rinaldi Munir/IF2151 Mat. Diskrit 2)
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 %,
7/18/2019 boleaan aljabar 6790
http://slidepdf.com/reader/full/boleaan-aljabar-6790 21/83
Rinaldi Munir/IF2151 Mat. Diskrit 21
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
7/18/2019 boleaan aljabar 6790
http://slidepdf.com/reader/full/boleaan-aljabar-6790 22/83
Rinaldi Munir/IF2151 Mat. Diskrit 22
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
7/18/2019 boleaan aljabar 6790
http://slidepdf.com/reader/full/boleaan-aljabar-6790 23/83
Rinaldi Munir/IF2151 Mat. Diskrit 2
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
7/18/2019 boleaan aljabar 6790
http://slidepdf.com/reader/full/boleaan-aljabar-6790 24/83
Rinaldi Munir/IF2151 Mat. Diskrit 20
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
7/18/2019 boleaan aljabar 6790
http://slidepdf.com/reader/full/boleaan-aljabar-6790 25/83
Rinaldi Munir/IF2151 Mat. Diskrit 25
>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,
7/18/2019 boleaan aljabar 6790
http://slidepdf.com/reader/full/boleaan-aljabar-6790 26/83
Rinaldi Munir/IF2151 Mat. Diskrit 2
+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( ,
7/18/2019 boleaan aljabar 6790
http://slidepdf.com/reader/full/boleaan-aljabar-6790 27/83
Rinaldi Munir/IF2151 Mat. Diskrit 28
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,
7/18/2019 boleaan aljabar 6790
http://slidepdf.com/reader/full/boleaan-aljabar-6790 28/83
Rinaldi Munir/IF2151 Mat. Diskrit 29
+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( ,
7/18/2019 boleaan aljabar 6790
http://slidepdf.com/reader/full/boleaan-aljabar-6790 29/83
Rinaldi Munir/IF2151 Mat. Diskrit 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
7/18/2019 boleaan aljabar 6790
http://slidepdf.com/reader/full/boleaan-aljabar-6790 30/83
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,
7/18/2019 boleaan aljabar 6790
http://slidepdf.com/reader/full/boleaan-aljabar-6790 31/83
Rinaldi Munir/IF2151 Mat. Diskrit 1
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 %
7/18/2019 boleaan aljabar 6790
http://slidepdf.com/reader/full/boleaan-aljabar-6790 32/83
Rinaldi Munir/IF2151 Mat. Diskrit 2
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
>$,
7/18/2019 boleaan aljabar 6790
http://slidepdf.com/reader/full/boleaan-aljabar-6790 33/83
Rinaldi Munir/IF2151 Mat. Diskrit
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
7/18/2019 boleaan aljabar 6790
http://slidepdf.com/reader/full/boleaan-aljabar-6790 34/83
Rinaldi Munir/IF2151 Mat. Diskrit 0
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
7/18/2019 boleaan aljabar 6790
http://slidepdf.com/reader/full/boleaan-aljabar-6790 35/83
Rinaldi Munir/IF2151 Mat. Diskrit 5
(. )ankaian *oika
Gerban' ACD Gerban' R Gerban' C* +in!erter ,
y
x xy
y
x x" y x# x
7/18/2019 boleaan aljabar 6790
http://slidepdf.com/reader/full/boleaan-aljabar-6790 36/83
Rinaldi Munir/IF2151 Mat. Diskrit
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
7/18/2019 boleaan aljabar 6790
http://slidepdf.com/reader/full/boleaan-aljabar-6790 37/83
Rinaldi Munir/IF2151 Mat. Diskrit 8
+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
7/18/2019 boleaan aljabar 6790
http://slidepdf.com/reader/full/boleaan-aljabar-6790 38/83
Rinaldi Munir/IF2151 Mat. Diskrit 9
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
7/18/2019 boleaan aljabar 6790
http://slidepdf.com/reader/full/boleaan-aljabar-6790 39/83
Rinaldi Munir/IF2151 Mat. Diskrit <
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
7/18/2019 boleaan aljabar 6790
http://slidepdf.com/reader/full/boleaan-aljabar-6790 40/83
Rinaldi Munir/IF2151 Mat. Diskrit 0)
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,
7/18/2019 boleaan aljabar 6790
http://slidepdf.com/reader/full/boleaan-aljabar-6790 41/83
Rinaldi Munir/IF2151 Mat. Diskrit 01
". 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
7/18/2019 boleaan aljabar 6790
http://slidepdf.com/reader/full/boleaan-aljabar-6790 42/83
Rinaldi Munir/IF2151 Mat. Diskrit 02
(. 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 %
7/18/2019 boleaan aljabar 6790
http://slidepdf.com/reader/full/boleaan-aljabar-6790 43/83
Rinaldi Munir/IF2151 Mat. Diskrit 0
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
7/18/2019 boleaan aljabar 6790
http://slidepdf.com/reader/full/boleaan-aljabar-6790 44/83
Rinaldi Munir/IF2151 Mat. Diskrit 00
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
7/18/2019 boleaan aljabar 6790
http://slidepdf.com/reader/full/boleaan-aljabar-6790 45/83
Rinaldi Munir/IF2151 Mat. Diskrit 05
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) ) ) ) )
7/18/2019 boleaan aljabar 6790
http://slidepdf.com/reader/full/boleaan-aljabar-6790 46/83
Rinaldi Munir/IF2151 Mat. Diskrit 0
$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
7/18/2019 boleaan aljabar 6790
http://slidepdf.com/reader/full/boleaan-aljabar-6790 47/83
Rinaldi Munir/IF2151 Mat. Diskrit 08
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
7/18/2019 boleaan aljabar 6790
http://slidepdf.com/reader/full/boleaan-aljabar-6790 48/83
Rinaldi Munir/IF2151 Mat. Diskrit 09
Bukti se:ara aljabar"
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) ) ) ) )
7/18/2019 boleaan aljabar 6790
http://slidepdf.com/reader/full/boleaan-aljabar-6790 49/83
Rinaldi Munir/IF2151 Mat. Diskrit 0<
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%
7/18/2019 boleaan aljabar 6790
http://slidepdf.com/reader/full/boleaan-aljabar-6790 50/83
Rinaldi Munir/IF2151 Mat. Diskrit 5)
. 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
7/18/2019 boleaan aljabar 6790
http://slidepdf.com/reader/full/boleaan-aljabar-6790 51/83
Rinaldi Munir/IF2151 Mat. Diskrit 51
Bukti se:ara aljabar"
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
7/18/2019 boleaan aljabar 6790
http://slidepdf.com/reader/full/boleaan-aljabar-6790 52/83
Rinaldi Munir/IF2151 Mat. Diskrit 52
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
7/18/2019 boleaan aljabar 6790
http://slidepdf.com/reader/full/boleaan-aljabar-6790 53/83
Rinaldi Munir/IF2151 Mat. Diskrit 5
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
7/18/2019 boleaan aljabar 6790
http://slidepdf.com/reader/full/boleaan-aljabar-6790 54/83
Rinaldi Munir/IF2151 Mat. Diskrit 50
@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,.
7/18/2019 boleaan aljabar 6790
http://slidepdf.com/reader/full/boleaan-aljabar-6790 55/83
Rinaldi Munir/IF2151 Mat. Diskrit 55
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
7/18/2019 boleaan aljabar 6790
http://slidepdf.com/reader/full/boleaan-aljabar-6790 56/83
Rinaldi Munir/IF2151 Mat. Diskrit 5
>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
7/18/2019 boleaan aljabar 6790
http://slidepdf.com/reader/full/boleaan-aljabar-6790 57/83
Rinaldi Munir/IF2151 Mat. Diskrit 58
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 %
7/18/2019 boleaan aljabar 6790
http://slidepdf.com/reader/full/boleaan-aljabar-6790 58/83
Rinaldi Munir/IF2151 Mat. Diskrit 59
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.
7/18/2019 boleaan aljabar 6790
http://slidepdf.com/reader/full/boleaan-aljabar-6790 59/83
Rinaldi Munir/IF2151 Mat. Diskrit 5<
>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
7/18/2019 boleaan aljabar 6790
http://slidepdf.com/reader/full/boleaan-aljabar-6790 60/83
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
7/18/2019 boleaan aljabar 6790
http://slidepdf.com/reader/full/boleaan-aljabar-6790 61/83
Rinaldi Munir/IF2151 Mat. Diskrit 1
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 %
7/18/2019 boleaan aljabar 6790
http://slidepdf.com/reader/full/boleaan-aljabar-6790 62/83
Rinaldi Munir/IF2151 Mat. Diskrit 2
>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
7/18/2019 boleaan aljabar 6790
http://slidepdf.com/reader/full/boleaan-aljabar-6790 63/83
Rinaldi Munir/IF2151 Mat. Diskrit
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
7/18/2019 boleaan aljabar 6790
http://slidepdf.com/reader/full/boleaan-aljabar-6790 64/83
Rinaldi Munir/IF2151 Mat. Diskrit 0
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
7/18/2019 boleaan aljabar 6790
http://slidepdf.com/reader/full/boleaan-aljabar-6790 65/83
Rinaldi Munir/IF2151 Mat. Diskrit 5
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
)
) )
) )
) ) )
7/18/2019 boleaan aljabar 6790
http://slidepdf.com/reader/full/boleaan-aljabar-6790 66/83
Rinaldi Munir/IF2151 Mat. Diskrit
@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
7/18/2019 boleaan aljabar 6790
http://slidepdf.com/reader/full/boleaan-aljabar-6790 67/83
Rinaldi Munir/IF2151 Mat. Diskrit 8
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
7/18/2019 boleaan aljabar 6790
http://slidepdf.com/reader/full/boleaan-aljabar-6790 68/83
Rinaldi Munir/IF2151 Mat. Diskrit 9
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%.
7/18/2019 boleaan aljabar 6790
http://slidepdf.com/reader/full/boleaan-aljabar-6790 69/83
Rinaldi Munir/IF2151 Mat. Diskrit <
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 + ,
7/18/2019 boleaan aljabar 6790
http://slidepdf.com/reader/full/boleaan-aljabar-6790 70/83
Rinaldi Munir/IF2151 Mat. Diskrit 8)
+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,
7/18/2019 boleaan aljabar 6790
http://slidepdf.com/reader/full/boleaan-aljabar-6790 71/83
Rinaldi Munir/IF2151 Mat. Diskrit 81
+:, 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
7/18/2019 boleaan aljabar 6790
http://slidepdf.com/reader/full/boleaan-aljabar-6790 72/83
Rinaldi Munir/IF2151 Mat. Diskrit 82
x y zw
f .
f 0
f 2
f 1
7/18/2019 boleaan aljabar 6790
http://slidepdf.com/reader/full/boleaan-aljabar-6790 73/83
Rinaldi Munir/IF2151 Mat. Diskrit 8
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
7/18/2019 boleaan aljabar 6790
http://slidepdf.com/reader/full/boleaan-aljabar-6790 74/83
Rinaldi Munir/IF2151 Mat. Diskrit 80
>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
7/18/2019 boleaan aljabar 6790
http://slidepdf.com/reader/full/boleaan-aljabar-6790 75/83
Rinaldi Munir/IF2151 Mat. Diskrit 85
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
7/18/2019 boleaan aljabar 6790
http://slidepdf.com/reader/full/boleaan-aljabar-6790 76/83
Rinaldi Munir/IF2151 Mat. Diskrit 8
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 ! √
7/18/2019 boleaan aljabar 6790
http://slidepdf.com/reader/full/boleaan-aljabar-6790 77/83
Rinaldi Munir/IF2151 Mat. Diskrit 88
+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
7/18/2019 boleaan aljabar 6790
http://slidepdf.com/reader/full/boleaan-aljabar-6790 78/83
Rinaldi Munir/IF2151 Mat. Diskrit 89
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 √
7/18/2019 boleaan aljabar 6790
http://slidepdf.com/reader/full/boleaan-aljabar-6790 79/83
Rinaldi Munir/IF2151 Mat. Diskrit 8<
+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.
7/18/2019 boleaan aljabar 6790
http://slidepdf.com/reader/full/boleaan-aljabar-6790 80/83
Rinaldi Munir/IF2151 Mat. Diskrit 9)
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%.
7/18/2019 boleaan aljabar 6790
http://slidepdf.com/reader/full/boleaan-aljabar-6790 81/83
Rinaldi Munir/IF2151 Mat. Diskrit 91
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
7/18/2019 boleaan aljabar 6790
http://slidepdf.com/reader/full/boleaan-aljabar-6790 82/83
Rinaldi Munir/IF2151 Mat. Diskrit 92
. $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,
7/18/2019 boleaan aljabar 6790
http://slidepdf.com/reader/full/boleaan-aljabar-6790 83/83
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,.