Exam 2012, Discrete Mathematics, questions and answers PDF
| Title | Exam 2012, Discrete Mathematics, questions and answers |
|---|---|
| Course | Discrete Mathematics |
| Institution | University of Queensland |
| Pages | 9 |
| File Size | 300.6 KB |
| File Type | |
| Total Downloads | 71 |
| Total Views | 184 |
Summary
Download Exam 2012, Discrete Mathematics, questions and answers PDF
Description
UQAttic.net[Chat]
MATH10612012Semester1Exam
MATH1061:2012Semester1Exam UQAttic Getmoreoutofyourstudytime.JoinUQAttic'sSemester1,2013revisionchat.
Otherexampapers
Readthispagefirst! Pleasecontributetothesedocuments. Ifyou'relookingforaneffectivewaytofamiliariseyourselfwiththecoursematerial,youcan'tgo pastcollaboratingwithfellowstudents.Wehavelabouredtoputtheseup,andsoattheveryleast pointoutwhereyouthinkwearewrong! You'llgetmoreoutofthecourse,you'lldobetterintheexam,andotherstudentswillbenefitfrom yourinputaswell. Togeteditingpermissions,simplygotothechatroomandprovideuswithyourGoogleAccount address.
Style. Typeanswersinbluebeneatheachquestion. Ifyou'reunsureofyouranswer,highlightyouranswertextthenhitCtrl+Alt+Mtocreateacomment besidethetext.Onceyou'resatisfiedwiththeanswer,clickthe"Resolve"buttononthecomment. Ifyouwantsomeextraexplanationfromsomeoneelseontheiranswer,highlighttheotherperson's answerandrepeattheprocedureabove.
Communicate. Headovertouqattic.netandclick"ChatNow!".You'llfindachatroomfullofstudentsjustlikeyou. Talkaboutarevisiondocument(likethisone)orswappreptips. IfyouhaveyourownIRCclient,pointittoirc.uqattic.net,port6667,channel#attic.
UQAttic.net[Chat]
MATH10612012Semester1Exam
Q1:(a)Constructatruthtableforthefollowingstatementform: p ⋁ (q ⋀ ( ~ p)) ↔ ((~ q) → p) p
q
p ⋁ (q ⋀ (~ p))
((~ q) → p)
p ⋁ (q ⋀ ( ~ p)) ↔ ((~ q) → p)
T
T
T
T
T
T
F
T
T
T
F
T
T
T
T
F
F
F
F
T
Thisstatementformisatautology. (b)Writedownthenegationofthefollowingstatement: ∀x ∈ ℝ, ∃y ∈ ℤ suchthat (x + y) ≥ 0 .Is theoriginalstatementtrueorfalse?Explainyouranswerbriefly. ∃x ∈ ℝ suchthat ∀y ∈ ℤ, (x + y) < 0 . Theoriginalstatementistrue;forallrealnumbers x,anyinteger y > |x| satisfies x + y ≥ 0 . Q2:Sets P , Q , R, Saregivenby P = { a, b}, Q = {a, ∅}, R = { ∅}, S = {P , ∅} .Completethe following. P ⋃ Q = {a, b, ∅} Q ⋂ R = {∅} P ⋂S = ∅ P − Q = {b}
P (Q) = {∅, {a}, {∅}, {a, ∅}} P (R) = {∅, {∅}} P × S = {(a, P ), (a, ∅), (b, P ), (b, ∅)} |P × R | = 2 Q3:(a)Writethefollowingstatementsintheform“If...then...” (i)ItisnecessaryforAlicetocounttoteninorderforhertoremaincalm. IfAliceremainscalm,thenshecountedtoten. (ii)ItissufficientforBobtotakeanumbrellainordertokeeptherainaway. IfBobtakesanumbrella,thentherainiskeptaway.
MATH10612012Semester1Exam
UQAttic.net[Chat]
(Thetensei.e.whetheryouusedpasttense,presenttense,futuretensedoesn’treallymatter) (b)If risrationaland sisirrational,provethat 2r + s isirrational. Weprovetheresultbycontradiction.Suppose risrational, sisirrational,and 2r + s isrational. Then, r = aband 2r + s = dc forsome a, b, c, d ∈ ℤ with b, d =/ 0. Then, / 0, itfollowsthat s isrational,a s = (2r + s) − 2r = dc − 2ab = cb−2ad bd .Since cb − 2ad, bd ∈ ℤ ,and bd = contradiction.Thereforetheoriginalclaimistrue.∎ Q4: (a)If adivides b(thatis,if a|b),where a, bareintegers,then b = a × k forsomeinteger k. (b)If a, b, careintegerssuchthat a|b, b|c ,provethat a|(b + 2c) . Supposethat a, b, careintegerssuchthat a|b, b|c .Then, b = ak, c = bm forsomeintegers k, m.Then, b + 2c = b + 2bm = ak + 2akm = (k + 2km)a.Since k + 2km ∈ ℤ,itfollowsthat a|(b + 2c) .∎ (c)Provethatif nisanyoddinteger,then n2 − 5isdivisibleby4butneverby8. Supposethat nisanoddinteger.Then, n = 2k + 1 forsomeinteger k .Then, n2 − 5 = (2k + 1)2 − 5 = 4k2 + 4k − 4 = 4(k2 + k − 1).Since k2 + k − 1isaninteger, n2 − 5 isdivisible by4. Moreover,if kiseventhen k2isevenandso k2 + k − 1isodd;if kisoddthen k2isoddandso k2 + k − 1isodd.Ineachcase, k2 + k − 1 = 2m + 1 forsomeinteger m .Then, 4(k2 + k − 1) = 8m + 4,whichisnotdivisibleby8(sincethereisaremainderof4afterdivision).∎ Q5:(a)Proveorgiveacounterexample:“If gcd(a, b) = d and gcd(b, c) = 1 ,then gcd(a, c) = 1 ” Acounterexampleis a = 6 , b = 3, c = 2, d = 3 : gcd(6, 3) = 3 and gcd(3, 2) = 1 ,but gcd(6, 2) = 2 . (b)Leta,b,cbepositiveintegersandletpbeaprime.Statewhetherthefollowingaretrueor false. (i)If a|band b|cthen a|c 2.True.(ifb=ka,c=mb,then c2 = m2k2a ∙ a ) (ii)If p|ab,then pdoesn’tdivide aorelsepdoesn’tdivideb.False.(Counterex.:p=a=b=2) (iii)If p|athengcd(a,p)=a.False.(Counterexample:p=2,a=4,thengcd(a,p)=2) (iv)Ifa|b,b|candc|a,thena;b;careequaltosomeprime.False.(Counterex.:a=b=c=4) (c)Calculatethefollowing,giveanswersbetween0and5: (i)31div6=5 (ii)31mod6≡1 (iii)31!mod6≡0
MATH10612012Semester1Exam
UQAttic.net[Chat]
(iv) 100131mod6≡5(since1001≡1,and ( − 1)31 =− 1≡5 ) Q6:(a)Foreachofthefollowinglistsofnumbers,eitherexplainwhynosimplegraphwithseven verticesandthegivennumbersasdegreescanexist,orelsedrawasimplegraphwithseven verticeshavingthegivendegrees. (i)6,5,4,3,2,2,1. Nosuchgraphexists,sincethetotaldegreeisodd. (ii)6,4,2,2,2,1,1.
(b)(i)Atreewith9verticeshas8edges. (ii)Aparticulartreewith9verticeshaspreciselyfiveverticesofdegree1,andpreciselytwo verticesofdegree2.Theremainingtwoverticeshavedegreesaandb.Findaandb,giventhat a ≤ b . Thetotaldegreeofthetreeis16=1+1+1+1+1+2+2+a+b.So,a+b=7.Sincea,bcan’tbe1or2, theonlysolutionisa=3,b=4. Q7:UsethegraphGshownhereforthisquestion(seetheexampaper). (a)WritedownanEulercircuitoranEulerpathinG,ifeitherispossible;otherwiseexplainwhy anEulercircuitoranEulerpathisnotpossible. Ghastwoverticesofodddegree,namelyf,g.So,ithasanEulerpath.Onesuchpathis f,b,a,c,d,b,e,a,g,c,h,e,f,h,d,g. (b)DoesGcontainaHamiltoncycle?Ifso,writeonedown. Yes.OneHamiltoncycleisa,b,e,f,h,d,g,c. Q8:(a)Findthecoefficientof x9y5intheexpansionof (2x − y)14.Writeyouranswerasapositive ornegativeproductofprimepowers. 5 9 Therequiredcoefficientis (14 9 )∙ 2 ∙ ( − 1 ) = − 1 025024.Asaproductofprimes, 14∙13∙12∙11∙10 5∙4∙3∙2∙1
∙ (− 1) ∙ 29 = 14 ∙ 13 ∙ 11 ∙ (− 1) ∙ 29 = (− 1) ∙ 210 ∙ 7 ∙ 11 ∙ 13 .
MATH10612012Semester1Exam
UQAttic.net[Chat]
n (b)Provethat (r−1 )+ (nr) = (n+1 ,wherenandrarepositiveintegers. r ) −r+1) n n! n!∙r n! Ifn,rarepositiveintegers,then (r−1 )= (n−r+1)!∙( ,and(nr ) = (n−r)!∙r! .So, = (nn−!(rn+1)!∙ r! r−1)! = (n−r+1)!∙r! n!(n−r+1) n!(n+1) (n+1)! n (r−1 ) + (nr) =n!∙r+ .∎ = (n−r+1)!∙r! =(n+1−r)!∙r! = ( n+1 r ) (n−r+1)!∙r!
Q9:Acommitteeoffiveistobechosenfromacollectionof4womenand8men.(a)Howmany differentcommitteesoffivepeoplecanbeformed? (125 ) = 7 92 . (b)Howmanydifferentcommitteesoffivecanbeformed,ifatleasttwomenandatleasttwo womenaretobeonthecommitteeoffive? Eitherthereare3menand2women,ofwhichthereare (83 )× (42) = 3 36 options,or2menand3 women,ofwhichthereare 82( )× ( 43) = 1 12options,foratotalof336 + 112 = 448 options. (c)Whatistheprobabilitythatthereareexactly3womenand2menchosen,giventhatthe constraintsinpart(b)hold? 112 = 1 . 448 4 Q10:(a)Usemathematicalinductiontoprovethat 4n + 7 < 5n forallintegers n ≥ 2 . LetP(n)bethestatement 4n + 7 < 5n,weaimtoshow P (n)istrueforall n ≥ 2 .Inthecasethat n = 2,itholdsthat 42 + 7 = 23 < 25 = 52 ,so P (2) istrue. If P (n)istrueforsome n ≥ 2 ,then 4n + 7 < 5n ,so 4n+1 + 7 = 4 ∙ 4n + 7 < 4(4n + 7) < 4 ∙ 5n < 5 ∙ 5n = 5n+1 ,so P (n + 1) istrue. Bytheprincipleofmathematicalinduction, P (n) holdsforall n ≥ 2 .∎ (b)Explainwhetherthefollowingsetsatisesthewellorderingprinciplefortheintegers:Theset ofallnonnegativeintegersoftheform 43 − 6k ,where k ∈ Z . Yes,thissatisfiesthewellorderingprincipleasithasaleastelement,being1sinceitisalsothe smallestnonnegativeinteger(wherethelargestpossibleelementbeingk=7). Q11:Functionsfandg,bothfromZtoZ,aredefinedby: f (x) = |2 − x| and g(x) = ceiling(2x ) .
MATH10612012Semester1Exam
UQAttic.net[Chat]
(a)Whatistherangeoff? Forany y ∈ ℤ,if y ≥ 0then y = f (y + 2),andif y < 0,wecannothave |2 − x| = y forany x ,since |2 − x| ≥ 0 .So,therangeof f is {y ∈ ℤ|y ≥ 0} . (b)Whatistherangeofg? Forany y ∈ ℤ,itholdsthat g(2y) = y,sotherangeof g is ℤ . (c)Isf11?Verifyyouranswer. No,since f (1) = 1 = f (3) ,but 1 =/ 3 . (d)IsgontoZ?Verifyyouranswer. Yes,sincetherangeis ℤ ,bypart(b). (e)Find (g ° f )(3) . First, f (3) = |2 − 3| = 1 .Then, (g ° f)(3) = g(f(3)) = g(1) = ceiling(12) = 1 . (f)Find (f ° g)(3) . First, g(3) = ceiling(32) = 2 .Then, (f ° g)(3) = f(g(3)) = f (2) = |2 − 2| = 0 . (g)Is (g ° f ) ontoZ?Verifyyouranswer. ≥ 0 ,so ceiling(|2−x| No. |2 − x| ≥ 0,so |2−x| 2 ) ≥ 0 .Thus,− 1 ∈ ℤ isnotintherangeofg ° f . 2 Q12:Binaryrelationsρandτaredefinedonthesetofintegers,Z,asfollows: mρnifandonlyifmisamultipleofn; mτnifandonlyif m2 − n2 isdivisibleby3. (a)Indicatewhichpropertiesthesebinaryrelationshave.
ρ
τ
Reflexive
✓
✓
Symmetric
✗
✓
Antisymmetric
✗E ✗
Transitive
✓E ✓
PartialOrder
✗
✗
(b)Explainyouranswersforthetwoboxesmarked(E) Antisymmetryofρ:Consider m = 1 , n =− 1.Then, misamultipleof n and n isamultipleof m , but m =/ n . Transitivityofρ:Ifm,n,kareintegerssuchthatmρnandnρk,then m = xn and n = yk for someintegers x, y.Then, m = (xy)k,so misamultipleof k,thatis,mρk. (c)ONEofρ,τisanequivalencerelation.Forthatbinaryrelation,giveitsequivalenceclasses.
MATH10612012Semester1Exam
UQAttic.net[Chat]
Theequivalencerelationisτ.Theequivalenceclassesare [ 0] = { ∙ ∙ ∙ − 6 ,− 3 , 0 , 3, 6, ∙ ∙ ∙} = { 3x|x ∈ ℤ} and [ 1] = { ∙∙ ∙ − 5 ,− 4 ,− 2 ,− 1 , 1, 2, 4, 5, ∙ ∙ ∙} = {3x + 1, 3x + 2|x ∈ ℤ} . Q13:Let X = { x, y}.DefineabinaryrelationσonP(X)(thepowersetofX),byAσBifandonlyif A ⊆ B . (a)Writedown X × X .
X × X = { (x,x ),( x,y ), ( y, x ), ( y, y )} .
(b) |P (X)| = 4 (c)HowmanydifferentbinaryrelationscanbedefinedonthesetX? AbinaryrelationonXisasubsetof X × X .Thenumberofrelationsisthen |P (X × X )| = 24 = 16 . (d)Isσreflexive? (e)Isσantisymmetric?
Yes,itisclearthat A ⊆ A forany A ⊆ X . Yes,sinceif A ⊆ B ⊆ A,then A = B(bydefinitionofsetequality).
(f)Isσtransitive? Yes,sinceif A ⊆ B ⊆ C ,thenitisclearthat A ⊆ C . (g)Isσapartialorderrelation? Yes,sinceitisreflexive,antisymmetricandtransitive. (h)Isσatotalorderrelation? No,sinceneither {x} ⊆ {y} nor {y} ⊆ {x} hold. Q14:Binaryoperations●and⭑aredenedonthesetofintegersℤby a ∙ b = a + b − 3 , a ★ b = a + 2b + ab . (a)Is●associative? Yes,forany a, b, c ∈ ℤ , (a ∙ b) ∙ c = (a + b − 3) + c − 3 = a + b + c − 6 and a ∙ (b ∙ c) = a + (b + c − 3 ) − 3 = a + b + c − 6 = ( a ∙ b ) ∙ c . (b)Is⭑associative? No,consider a = 1, b = 1, c = 2 .Then, a ★ (b ★ c) = 1 ★ (1 + 4 + 2) = 1 ★ 7 = 1 + 14 + 7 = 22 ,and (a ★ b) ★ c = (1 + 2 + 1) ★ 2 = 4 ★ 2 = 4 + 4 + 8 = 16 =/ a ★ (b ★ c), sothisisacounterexample. (c)Isthereanidentityelementfor●? Yes,3,since 3 ∙ a = 3 + a − 3 = a and a ∙ 3 = a + 3 − 3 = a . (d)Isthereanidentityelementfor⭑? No.Iftherewereanidentity e,thenitwouldsatisfy,forall a ∈ ℤ , a = a ★ e = a + 2e + ae ,so 0 = 2e + ae.Theonlysolutionisclearly e = 0,so0istheonlycandidateforanidentityelement. However, 0 ★ 1 = 2,so0isnotanidentity. (e)Isℤagroupwithrespecttoeither●or⭑? Yes,with●. Itisclearthat●isclosed(thatis,if a, b ∈ ℤ then a + b − 3 ∈ ℤ ). Byparts(a)and(c),●isassociativeandhasidentity. Foranyinteger a ∈ ℤ,theinverseof awithrespectto●is 6 − a ,since (6 − a ) ∙ a = 6 − a + a − 3 = 3 ,and a ∙ (6 − a) = a + 6 − a − 3 = 3 .
UQAttic.net[Chat]
MATH10612012Semester1Exam
ℤisnotagroupwithrespectto⭑,sincetheoperationisnotassociativeandhasnoidentity. Q15:(a)Youaretoldthat {a, b , c, d, e} formsanabeliangroupoforder5,withthegroup operationgivenbythefollowingCayleytable.However,thetableisincomplete.Pleasecomplete thetablesothatthisdoesindeedformanabeliangroup. First,wecanrecognisethateachgroupelementmustoccurpreciselyonceineachrowand column,andstandardsudokustyletrickscanfillinmostofthetable.Sincethegroupisabelian, thetablewillbesymmetricaboutthemaindiagonalaswell. Then,noticethat a1 = a, a2 = a ∙ a = c , a3 = a ∙ a ∙ a = a ∙ c = d, a4 = b, a5 = e.So, b ∙ c = a4 ∙ a2 = a6 = a1 = aand c ∙ c = a2 ∙ a2 = a4 = b.Thiswillallowtherestofthetabletobe filledin.(Ifyoudidn’tgetthesudokustyletrick,thenyoucouldhavealsodonethepowersofa trickoneveryemptycelltoendupfillingoutthetable). °
e
a
b
c
d
e
e
a
b
c
d
a
a
c
e
d
b
b
b
e
d
a
c
c
c
d
a
b
e
d
d
b
c
e
a
(b)Let G = {1, 2, 4, 5, 7, 8}andlet °denotemultiplicationmodulo9.Verifythat (G,°) isa group.Hint:startingwithaCayleytablewillhelp. ACayleytableis: °
1
2
4
5
7
8
1
1
2
4
5
7
8
2
2
4
8
1
5
7
4
4
8
7
2
1
5
5
5
1
2
7
8
4
7
7
5
1
8
4
2
8
8
7
5
4
2
1
MATH10612012Semester1Exam
UQAttic.net[Chat]
SinceeveryentryinthetableisinG,theoperationisclosed.Itisalsoeasytoseefromthetable thatGhasanidentity1,andsince1occursineveryrowandcolumn,everyelementhasan inverse. Associativityfollowsfromassociativityofmultiplicationintheintegers. (c)Theabovegroup (G,°)frompart(b)hasorder6.Ifpossible,giveanexampleofasubgroup of (G,°)oforder(i)2;(ii)3;(iii)4.Ifnosuchsubgroupexists,giveabriefreasonwhy(refer,by name,toanytheoremused). (i)Theset {1, 8} formsasubgroupoforder2. (ii)Theset {1, 4, 7} formsasubgroupoforder3. (iii)NosuchsubgroupexistsbyLagrange’sTheorem,since4doesnotdivide6....
Similar Free PDFs
Exam 2012, questions and answers
- 17 Pages
Exam 2012, questions and answers
- 15 Pages
Exam 2012, questions and answers
- 6 Pages
Exam 2012, Questions and answers
- 7 Pages
Exam 2012, questions and answers
- 12 Pages
Popular Institutions
- Tinajero National High School - Annex
- Politeknik Caltex Riau
- Yokohama City University
- SGT University
- University of Al-Qadisiyah
- Divine Word College of Vigan
- Techniek College Rotterdam
- Universidade de Santiago
- Universiti Teknologi MARA Cawangan Johor Kampus Pasir Gudang
- Poltekkes Kemenkes Yogyakarta
- Baguio City National High School
- Colegio san marcos
- preparatoria uno
- Centro de Bachillerato Tecnológico Industrial y de Servicios No. 107
- Dalian Maritime University
- Quang Trung Secondary School
- Colegio Tecnológico en Informática
- Corporación Regional de Educación Superior
- Grupo CEDVA
- Dar Al Uloom University
- Centro de Estudios Preuniversitarios de la Universidad Nacional de Ingeniería
- 上智大学
- Aakash International School, Nuna Majara
- San Felipe Neri Catholic School
- Kang Chiao International School - New Taipei City
- Misamis Occidental National High School
- Institución Educativa Escuela Normal Juan Ladrilleros
- Kolehiyo ng Pantukan
- Batanes State College
- Instituto Continental
- Sekolah Menengah Kejuruan Kesehatan Kaltara (Tarakan)
- Colegio de La Inmaculada Concepcion - Cebu