Chapter 2
 Persamaan Boolean
2008, Pearson Education, Inc
Overview
Bagian 1 – Rangkaian Gerbang dan Persamaan Boolean Logika Biner dan Gerbang
!l"abar Boolean
#tandard Forms
%anipulasi Peta
Bagian * – Gerbang$ tamba+an dan rangkaian ,ipe$ gerbang -ang lain
Operator '.clusive)OR dan Gerbang
Operator Logika 2 Beroperasi pada nilai biner dan variabel biner
Dasar operator logika adala+ merupakan 3ungsi logika !4D5 OR and 4O,
Gerbang Logika mengimplementasikan 3ungsi logika
 
,rue6False
On6O33 
7es64o
168 Digunakan 1 dan 8 untuk men-atakan $ nilai Conto+ariable identi3ier 2
!5 B5 -5 95 or :1 
R'#',5 #,!R,;0,5 atau !DD1 &-ad(
 
OR 
4O,
!4D din-atakan dengan titik &<(
OR din-atakan dengan tamba+ &=(
 
  dibaca 9 adala+ 2 . OR -
  dibaca : adala+ 2 4O, !
  tidak sama dengan 2
= B!7   ⋅
-.9   +
 
 Operasi penerapan untuk nilai   E8E and E1E untuk masing$ operator 2
!4D  
81
18
,rut+ ,ables6,abel ebenaran
Truth table − #uatu da3tar tabular dari nilai suatu 3ungsi untuk semua kemungkinan kombinasi
Conto+2 ,rut+ tables untuk operasi dasar 2
111
881
818
888
:<77:
logic 1 is switc+ closed logic 8 is switc+ open
Hntuk outputs2 logic 1 is lig+t on logic 8 is lig+t o33
4O, menggunakan switc+
  seperti2 logic 1 is switc+ open logic 8 is switc+ closed
0mplementasi Fungsi Logika
C
Conto+2 Logic Hsing #witc+es 
Lampu n-ala &L 1( untuk2
'(), *, C, +  ' (), *, C, + ) ((* C / +
) * C / ) +
Dan bila tidak5 mati &L 8( %odel -ang berguna untuk rangk rela- dan
untuk rangk gerbang C%O# 5 merupakan dasar dari teknologi logika digital saat ini
0mplementasi Fungsi Logika (Continued
Gerbang Logika&Logic Gates(
Pada awal komputer5 switc+es terbuka dan tertutup menggunakan medan magnit -ang di+asilkan ole+ energi dari koil pada relays #witc+es secara bergantian membuka dan menutup "alan arus
emudian5 vacuum tubes membuka dan menutup "alan arus secara elektronik5 menggantikan rela-s
#aat ini5 transistors dipakai sebagai electronic switc+es -ang membuka dan menutup "alann-a arus
Optional2 C+apter J – Part 12 ,+e Design #pace
 
X 0 0 1 1
 Y 0 1 0 1
X   · Y(AND) 0 0 0 1
X 1 Y(OR) 0 1 1 1
(NOT) X 1 1 0 0
(a) Graphic symbols
AND gate
X   ! X
#imbol Gerbang Logika dan perilakun-a Gerbang Logika mempun-ai simbol k+usus5
!nd wave3orm be+avior in time as 3ollows2
 
=
 
Dela- pada Gerbang
#ecara aktual5 p+-sical gates5 bila satu atau lebi+ input beruba+ men-ebabkan output beruba+5 peruba+an tersebut tidak ter"adi secara instan
Dela- antara peruba+an input dan peruba+an +asil output adala+ gate delay din-atakan 2 t G
tG tG
Diagram Logika dan 'kspresi)n-a
Persamaan Boolean5 tabel kebenaran dan Diagram Logika menta-akan Fungsi -ang samaK
:
'valuasi Fungsi Boolean
9. -. FM .9-.9-.F*
1.
!l"abar Boolean #truktur !l"abar dide3inisikan pada satu set atau minimum $
elemen5 !5 B5 dengan tiga operator biner &denoted =5 < and ( -ang dirumuskan secara mendasar sbb2
10.
12.
1".
1$.
 X &Y + Z (  XY XZ =
 X + Y X Y 
 X Y X = Y 
#-$ 6Idempotence
Beberapa properti dari identitas dan !l"abar
Dual dari ekspresi suatu ekspresi al"abar didapat dengan menggantikan = and < dan menggantikan 8Ns dan 1Ns
Hnless it +appens to be sel3)dual5 t+e dual o3 an e.pression does not e?ual t+e e.pression itsel3
'.ample2 F &! = C( < B = 8
  dual F &! < C = B( < 1 ! < C = B
'.ample2 G : < 7 = & = (
  dual / () / *() / C(* / C. 9sin4 the *oolean identities,
  () /*C (*/C )* / )C / *C. :o ; is sel-dual.
 
Chapter 2 - Part 1 18
emungkinan dapat lebi+ dari $ elemen in B5 -aitu elemen selain1 and 8 Hmumn-a disebut apa !l"abar Boolean dengan lebi+ dari $ elemen
Bila B terdiri +an-a 1 dan 85 maka B disebut switc+ing algebra -ang merupakan al"abar -ang sering digunakan
Beberapa properti dari identitas dan !l"abar (Continued
!lgebra o3 #ets
 
Operator Boolean
1. Parentheses<=urun4 2. > !. )>+ ". R  
 
! = !<B ! &!bsorption ,+eorem(
  ! = !<B
! < 1  1 = : 1
!lasan melakukan pembuktian untuk mempela"ari2 Ber)+ati$ dan secara e3isien menggunakan rumus dan teorema
!l"abar Boolean
 
!B = !C = BC !B = !C &Consensus ,+eorem(
Proo3 #teps Qusti3ication &identit- or t+eorem(
  !B = !C = BC
 
 
  &lan"utkanK(
7:(7:&   +
. --
 
 
 
 
 
Pembuktian dengan pen-eder+anaan
  +
-. . - -. ⋅ -. +
 
'valuasi Fungsi Boolean
9. -. FM .9-.9-.F*
Pen-eder+anan 'kspresi
#uatu Penerapan !l"abar Boolean
#eder+anakan agar didapat "umla+ literal terkecil &variabel complemen dan tidak complemen(2
 !B = !BCD = ! C D = ! C D = ! B D
!B = !B&CD( = ! C &D = D( = ! B D
!B = ! C = ! B D B&! = !D( =!C
B &! = D( = ! C literals
Fungsi Complemen
Gunakan ,eorema De%organ@s untuk mengkomplemen)kan 3ungsi2 1 #aling ditukar operators !4D dan OR 
$omplemen)kan masing$ nilai konstan
  F &. = - = 9(&. = - = 9( Conto+2omplemen)kan G &a = bc(d = e
G  ((a (3 / c/ d e (a (3 / c / d e
. 9-9-.
Overview Bentuk Fungsi anonik 
!pa itu Bentuk anonik
Representasi #um)o3)%interm &#O%(
Representasi Product)o3)%a.term &PO%(
Bentuk anonik 
#angat berguna untuk menspeci3- Fungsi Boolean dalam bentuk seperti2 !llows comparison 3or e?ualit-
/as a correspondence to t+e trut+ tables
 Bentuk anonik -ang umum digunakan 2 #um o3 %interms &#O%( #um o3 Product
&#OP(
 
%interms
%interms adala+ !4D terms dengan adan-a setiap variabel baik itu StrueN atau bentuk komplemen 3orm
Diketa+ui masing$ variabel biner adala+ normal &eg5 .( atau komplemen &eg5 (5 maka ada $n  minterms untuk n variable
Conto+2 Dua variable &: and 7( akan didapat   $ . $ M kombinasi2
  &bot+ normal(
7: :7
7: 7:
%a.terms
%a.terms adala+ OR terms dengan setiap variable StrueN atau bentuk complemen
Diketa+ui masing$ variabel biner adala+ normal &eg5 .( atau komplemen &eg5 .(5 maka ada $n ma.terms untuk n variable
Conto+2 Dua variable &: and 7( meng+asilkan $ . $ M kombinasi2
  &bot+ normal(
  &. normal5 - complemented(
  &. complemented5 - normal(
  &bot+ complemented(
Conto+2 Dua variable minterms dan ma.terms
0ndeks diatas sangat penting untuk menentukan variabel -ang mana dalam terms tersebut StrueN dan -ang mana komplemen
%a.terms and %interms
0nde. %interm %a.term
Hrutan #tandard
%interms dan ma.terms didisain dengan subscript #ubscript adala+ angka 5 tergantung pada binar- pattern)n-a Bit pada pattern men-atakan komplemen atau kondisi
normal untuk masing$ variable -ang ditulis dalam urutan standard
#emua variabel akan ada dalam minterm atau ma.term dan akan ditulis dalam urutan -ang sama &umumn-a alp+abeticall-(
Conto+2 Hntuk variable a5 b5 c2
%a.terms2 &a = b = c(5 &a = b = c(
,erms2 &b = a = c(5 a c b5 dan &c = b = a( ,0D! dalam urutan standard
%interms2 a b c5 a b c5 a b c
 
,u"uan dari 0nde.
0nde. untuk minterm atau ma.term5 men-atakan sebagai bil biner5 -ang dipakai untuk menentukan apaka+ variable -ang ada bentuk StrueN atau bentuk komplemen
Hntuk %interms2 1 berarti var ini Bukan komplemen dan
8 berarti var ini omplemen
Hntuk %a.terms2 8 berarti var ini Bukan komplemen dan
1 berarti var ini omplemen
 
%isalkan ariabel tersebut adala+ 2 :5 75 and
Hrutan standard)n-a adala+ 2 :5 t+en 75 t+en
0nde. 8 &basis 18( 888 &basis $( untuk tiga variables( etiga var tersebut adala+ komplemen
utk minterm 8 & ( dan tidak ada var -ang komplemen untuk %a.term 8 &:575(
%interm 85 disebut m8   
 Minterm 6 ?
 Maxterm 6 ?
%engulangi2 De%organ@s ,+eorem   and Conto+ Dua ariabel2   dan
Qadi %$ adala+ komplemen dari m$ dan
sebalikn-a Bila De%organ@s ,+eorem terdiri dari n variabel5
maka term diatas "uga terdiri dari n variabel
Bila 2 dan  
/ubungan %interm and %a.term
  $ variabel $ variabel
%asing$ kolom pada tabel 3ungsi ma.term adala+ komplemen dari kolom tabel 3ungsi minterm5 maka %i adala+ komplemen dari mi
. - m8  m1  m$  m* 
. - %8  %1  %$  %* 
 
Observasi
Pada ,abel 3ungsi2 %asing$ minterm mempun-ai satu dan +an-a satu5 1 berada
pada $n  terms & minimum dari 1s( #elain itu adala+ 8
%asing$ ma.term mempun-ai satu dan +an-a satu5 8 berada pada $n terms & ma.imum o3 8s( #elain itu adala+ 1
ita dapat mengimplementasikan dengan EORingE minterms dengan memasukkan E1E kedalam tabel 3ungsi 0ni disebut Fungsi dari minterm
ita dapat mengimplementasikan dengan E!4DingE ma.terms dengan memasukkan E8E kedalam tabel 3ungsi 0ni disebut Fungsi dari ma.term
Qadi ada dua bentuk kanonik2 #um o3 %interms &#O%( – Qumla+ sukumin
Product o3 %a.terms &PO%( – /asil kali sukuma.
  untuk men-atakan Fungsi Boolean
. - 9 inde. m1   = mM   = mT   F1  
8 8 8 8 8 = 8 = 8 8
8 8 1 1 1 = 8 = 8 1
8 1 8 $ 8 = 8 = 8 8
8 1 1 * 8 = 8 = 8 8
1 8 8 M 8 = 1 = 8 1
1 8 1 8 = 8 = 8 8
1 1 8 J 8 = 8 = 8 8
1 1 1 T 8 = 8 = 1 1
Conto+ Fungsi %interm
F1 . - 9 = . - 9 = . - 9
Conto+ Fungsi %interm
 F&!5 B5 C5 D5 '( )5*5C5+E5 /
)5*C5+5E / )*5C5+5E / )*5C+E
 
  F1  %8  < %$  < %*  < %R  < %J
. - 9 i %8 ⋅ %$ ⋅ %* ⋅ % ⋅ %J F1
⋅
⋅
⋅
⋅
⋅
⋅
⋅
1 ⋅
/ * / C5 / +5 ()5 / *5 / C5 / +
  1M 11 V*  %%%%(D5C5B5!&F   ⋅=
 
Chapter 2 - Part 1 "#
anonikal Qumla+ dari %interms
#etiap 3ungsi Boolean dapat din-atakan dalam 2 #um o3 %interms For t+e 3unction table5 t+e minterms used are t+e
terms corresponding to t+e 1@s
For e.pressions5 e.pand all terms 3irst to e.plicitl- list all minterms Do t+is b- !4Ding an- term missing a variable v wit+ a term & (
'.ample2 0mplement as a sum o3 minterms
First e.pand terms2
,+en distribute terms2
-..3    +
-.(--&.3    +
-.-..-3    +
vv +
Chapter 2 - Part 1 "$
!not+er #O% '.ample
'.ample2 ,+ere are t+ree variables5 !5 B5 and C w+ic+ we
take to be t+e standard order '.panding t+e terms wit+ missing variables2
Collect terms &removing all but one o3 duplicate terms(2
'.press as #O%2 
e ended up wit+2
F m1=mM=mR=mJ=mT
,+is can be denoted in t+e 3ormal s+ort+and2
4ote t+at we e.plicitl- s+ow t+e standard variables in order and drop t+e m designators
(T5J55M51&(C5B5!&F m
CB!F   +
Canonical Product o3 %a.terms
!n- Boolean Function can be e.pressed as a Product o3 %a.terms &PO%( For t+e 3unction table5 t+e ma.terms used are t+e terms
corresponding to t+e 8@s
For an e.pression5 e.pand all terms 3irst to e.plicitl- list all ma.terms Do t+is b- 3irst appl-ing t+e second distributive law 5 ORing terms missing variable v wit+ a term e?ual to and t+en appl-ing t+e distributive law again
'.ample2 Convert to product o3 ma.terms2
  !ppl- t+e distributive law2
!dd missing variable 92
-..(95-5.&3    +
Hse . = - 9 &.=-(<&.=9( wit+ 5 and to get2
,+en use to get2
Rearrange to standard order5
Function Complements
,+e complement o3 a 3unction e.pressed as a sum o3 minterms is constructed b- selecting t+e minterms missing in t+e sum)o3)minterms canonical 3orms
!lternativel-5 t+e complement o3 a 3unction e.pressed b- a #um o3 %interms 3orm is simpl- t+e Product o3 %a.terms wit+ t+e same indices
'.ample2 Given (T55*51&(95-5.&F m
(J5M5$58&(95-5.&F m
 
Conversion Between Forms
,o convert between sum)o3)minterms and product)o3) ma.terms 3orm &or vice)versa( we 3ollow t+ese steps2 Find t+e 3unction complement b- swapping terms in t+e list
wit+ terms not in t+e list
C+ange 3rom products to sums5 or vice versa
'.ample2Given F as be3ore2
Form t+e Complement2
,+en use t+e ot+er 3orm wit+ t+e same indices – t+is 3orms t+e complement again5 giving t+e ot+er 3orm o3 t+e original 3unction2
(T5R5*51&(95-5.&F m
(J5M5$58&(95-5.&F m
Chapter 2 - Part 1 #2
#tandard #um)o3)Products &#OP( 3orm2 e?uations are written as an OR o3 !4D terms
#tandard Product)o3)#ums &PO#( 3orm2 e?uations are written as an !4D o3 OR terms
'.amples2 #OP2
PO#2 
 
#tandard #um)o3)Products &#OP(
! sum o3 minterms 3orm 3or n variables can be written down directl- 3rom a trut+ table 0mplementation o3 t+is 3orm is a two)level
network o3 gates suc+ t+at2
,+e 3irst level consists o3 n)input !4D gates5 and
,+e second level is a single OR gate &wit+ 3ewer t+an $n inputs(
 
  F ! B C = ! B C = ! B C = !BC = !BC #impli3-ing2
  F
#impli3ied F contains * literals compared to 1 in minterm F
#tandard #um)o3)Products &#OP(
(T5J5R5M51&m(C5B5!&F  
Chapter 2 - Part 1 ##
!4D6OR ,wo)level 0mplementation o3 #OP '.pression ,+e two implementations 3or F are s+own
below – it is ?uite apparent w+ic+ is simplerK
F
B
C
A
Chapter 2 - Part 1 #$
#OP and PO# Observations
,+e previous e.amples s+ow t+at2 Canonical Forms &#um)o3)minterms5 Product)o3)
%a.terms(5 or ot+er standard 3orms &#OP5 PO#( di33er in comple.it-
Boolean algebra can be used to manipulate e?uations into simpler 3orms
#impler e?uations lead to simpler two)level implementations 
Wuestions2 /ow can we attain a simplest e.pression
0s t+ere onl- one minimum cost circuit 
,+e ne.t part will deal wit+ t+ese issues
 
,erms o3 Hse
!ll &or portions( o3 t+is material X $88V b- Pearson 'ducation5 0nc
Permission is given to incorporate t+is material or adaptations t+ereo3 into classroom presentations and +andouts to instructors in courses adopting t+e latest edition o3 Logic and Computer Design Fundamentals as t+e course te.tbook
,+ese materials or adaptations t+ereo3 are not to be sold or ot+erwise o33ered 3or consideration
 
Chapter 2
 Persamaan Boolean
2008, Pearson Education, Inc
Chapter 1
2008, Pearson Education, Inc