Solution Manual For Discrete Mathematics With Applications, 5th Edition

Preview (16 of 732 Pages)

100%

Solution Manual For Discrete Mathematics With Applications, 5th Edition - Page 1 preview image

Loading page ...

Manual Section 1.11Chapter 1: Speaking MathematicallyMany college and university students have difficulty using and interpreting language involving if-thenstatements and quantification. Section 1.1 is a gentle introduction to the relation between informaland formal ways of expressing such statements. The exercises are intended to start the process ofhelping students improve their ability to interpret mathematical statements and evaluate their truthor falsity.Sections 1.2 - 1.4 are a brief introduction to the language of sets, relations, functions,and graphs. Including Sections 1.2 and 1.3 at the beginning of the course can help students relatediscrete mathematics to the pre-calculus or calculus they have studied previously while enlargingtheir perspective to include a greater proportion of discrete examples.Section 1.4 is designed tobroaden students’ understanding of the way the word graph is used in mathematics and to showthem how graph models can be used to solve some significant problems.Proofs of set properties, such as the distributive laws, and proofs of properties of relations andfunctions, such as transitivity and surjectivity, are considerably more complex than those used inChapter 4 to give students their first practice in constructing mathematical proofs. For this reasonset theory as a theory is left to Chapter 6, properties of functions to Chapter 7, and properties ofrelations to Chapter 8.By making slight changes about exercise choices, instructors could coverSection 1.2 just before starting Chapter 6 and Section 1.3 just before starting Chapter 7.The material in Section 1.4 lays the groundwork for the discussion of the handshake theoremand its applications in Section 4.9. Instructors who wish to offer a self-contained treatment of graphtheory can combine both sections with the material in Chapter 10.College and university mathematics instructors may be surprised by the way students understandthe meaning of the term “real number.” When asked to evaluate the truth or falsity of a statementabout real numbers, it is not unusual for students to think only of integers.Thus an informaldescription of the relationship between real numbers and points on a number line is given in Section1.2 to illustrate that there are many real numbers between any pair of consecutive integers, Examples3.3.5 and 3.3.6 show that while there is a smallest positive integer there is no smallest positive realnumber, and the discussion in Chapter 7, which precedes the proof of the uncountability of the realnumbers between 0 and 1, describes a procedure for approximating the (possibly infinite) decimalexpansion for an arbitrarily chosen point on a number line.Section 1.11.a.x2=−1 (Or: the square ofxis−1)b. a real numberx2.a.a remainder of 2 when it is divided by 5 and a remainder of 3 when it is divided by 6b.an integern;nis divided by 6 the remainder is 33.a.betweenaandbb. distinct real numbersaandb; there is a real numberc4.a.a real number; greater thanrb. real numberr; there is a real numbers5.a.ris positiveb.positive; the reciprocal ofris positive (Or: positive; 1/ris positive)c.is positive; 1/ris positive (Or: is positive; the reciprocal ofris positive)6.a.sis negativeb.negative; the cube root ofsis negative (Or:3√sis negative)c.is negative;3√sis negative (Or: the cube root ofsis negative)

Solution Manual For Discrete Mathematics With Applications, 5th Edition - Page 2 preview image

Loading page ...

Solution Manual For Discrete Mathematics With Applications, 5th Edition - Page 3 preview image

Loading page ...

2Manual: Chapter 17.a.There are real numbers whose sum is less than their difference.True.For example,1 + (−1) = 0,1−(−1) = 1 + 1 = 2, and 0<2.b.There is a real number whose square is less than itself. True. For example, (1/2)2= 1/4<1/2 .c.The square of each positive integer is greater than or equal to the integer.True. Ifnis any positive integer, thenn≥1. Multiplying both sides by the positive numberndoes not change the direction of the inequality (see Appendix A, T20), and son2≥n.d.The absolute value of the sum of any two numbers is less than or equal to the sum of theirabsolute values.True. This is known as the triangle inequality. It is discussed in Section 4.4.8.a.have four sidesb.has four sidesc.has four sidesd.is a square; has four sidese.Jhas four sides9.a.have at most two real solutionsb.has at most two real solutionsc.has at most tworeal solutionsd.is a quadratic equation; has at most two real solutionse.Ehas at mosttwo real solutions10.a.have reciprocalsb.a reciprocalc.sis a reciprocal forr11.a.have positive square rootsb.a positive square rootc.ris a square root fore12.a.real number; product with every number leaves the number unchangedb.a positive square rootc.rs=s13.a.real number; product with every real number equals zerob.with every number leaves the number unchangedc.ab= 0Section 1.21.A=CandB=D2.a.The set of all positive real numbersxsuch that 0 is less thanxandxis less than 1b.The set of all real numbersxsuch thatxis less than or equal to zero orxis greater thanor equal to 1c.The set of all integersnsuch thatnis a factor of 6d.The set of all positive integersnsuch thatnis a factor of 63.a.No,{4}is a set with one element, namely 4, whereas 4 is just a symbol that represents thenumber 4b.Three: the elements of the set are 3, 4, and 5.c.Three: the elements are the symbol 1, the set{1}, and the set{1,{1}}4.a.Yes:{2}is the set whose only element is 2.b.One: 2 is the only element in this setc.Two: The two elements are 0 and{0}d.Yes:{0}is one of the elements listed in the set.e.No: The only elements listed in the set are{0}and{1}, and 0 is not equal to either ofthese.

Solution Manual For Discrete Mathematics With Applications, 5th Edition - Page 4 preview image

Loading page ...

Manual Section 1.235. The only sets that are equal to each other areAandD.Acontains the integers 0, 1, and 2 and nothing else.Bcontains all the real numbers that are greater than or equal to−1 and less than 3.Ccontains all the real numbers that are greater than−1 and less than 3. Thus−1 is inBbut not inC.Dcontains all the integers greater than−1 and less than 3. ThusDcontains the integers 0,1, and 2 and nothing else, and soD={0,1,2}=A.Econtains all the positive integers greater than−1 and less than 3.HenceEcontains theintegers 1 and 2 and nothing else, that is,E={1,2}.6.T2andT−3each have two elements, andT0andT1each have one element.Justification:T2={2,22}={2,4},T−3={−3,(−3)2}={−3,9},T1={1,12}={1,1}={1}, andT0={0,02}={0,0}={0}.7.a.{1,−1}b.T={m∈Z|m= 1+(−1)kfor some integerk}={0,2}.Exercises in Chapter 4 explore thefact that (−1)k=−1 whenkis odd and (−1)k= 1 whenkis even. So 1+(−1)k= 1+(−1) = 0whenkis odd, and 1 + (−1)k= 1 + 1 = 2 whenkis even.c.the set has no elementsd. Z(every integer is in the set)e.There are no elements inWbecause there are no integers that are both greater than 1 andless than−3.f.X=Zbecause every integerusatisfies at least one of the conditionsu≤4 oru≥1.8.a.No,B*Abecausej∈Bandj /∈Ab.Yes, because every element inCis inA.c.Yes, because every element inCis inC.c.. Yes, because it is true that every element inCis inC.d.Yes,Cis a proper subset ofA. Both elements ofCare inA, butAcontains elements(namelycandf) that are not inC.9.a.Yesb.No, the number 1 is not a set and so it cannot be a subset.c.No: The only elements in{1,2}are 1 and 2,and{2}is not equal to either of these.d.Yes:{3}is one of the elements listed in{1,{2},{3}}.e.Yes:{1}is the set whose only element is 1.f.No, the only element in{2}is the number 2 and the number 2 is not one of the threeelements in{1,{2},{3}}.g.Yes: The only element in{1}is 1, and 1 is an element in{1,2}.h.No: The only elements in{{1},2}are{1}and 2, and 1 is not equal to either of these.i.Yes, the only element in{1}is the number 1, which is an element in{1,{2}}.j.Yes: The only element in{1}is 1, which is is an element in{1}. So every element in{1}isin{1}.10.a.No. Observe that (−2)2= (−2)(−2) = 4, whereas−22=−(22) =−4. So ((−2)2,−22) =(4,−4), whereas (−22,(−2)2) = (−4,4). And (4,−4)̸= (−4,4) because−4̸= 4.b.No: For two ordered pairs to be equal, the elements in each pair must occur in the sameorder. In this case the first element of the first pair is 5, whereas the first element of the second

Solution Manual For Discrete Mathematics With Applications, 5th Edition - Page 5 preview image

Loading page ...

4Manual: Chapter 1pair is−5, and the second element of the first pair is−5 whereas the second element of thesecond pair is 5.c.Yes. Note that 8−9 =−1 and3√−1 =−1, and so (8−9,3√−1) = (−1,−1).d.Yes The first elements of both pairs equal12, and the second elements of both pairs equal−8.11.a.{(w, a),(w, b),(x, a),(x, b),(y, a),(y, b),(z, a),(z, b)}A×Bhas 4·2 = 8 elements.b.{(a, w),(b, w),(a, x),(b, x),(a, y),(b, y),(a, z),(b, z)}B×Ahas 4·2 = 8 elements.c.{(w, w),(w, x),(w, y),(w, z),(x, w),(x, x),(x, y),(x, z),(y, w),(y, x),(y, y),(y, z),(z, w),(z, x),(z, y),(z, z)}A×Ahas 4·4 = 16 elements.d.{(a, a),(a, b),(b, a),(b, b)}B×Bhas 2·2 = 4 elements.12. All four sets have nine elements.a.S×T={(2,1),(2,3),(2,5),(4,1),(4,3),(4,5),(6,1),(6,3),(6,5)}b.T×S={(1,2),(3,2),(5,2),(1,4),(3,4),(5,4),(1,6),(3,6),(5,6)}c.S×S={(2,2),(2,4),(2,6),(4,2),(4,4),(4,6),(6,2),(6,4),(6,6)}d.T×T={(1,1),(1,3),(1,5),(3,1),(3,3),(3,5),(5,1),(5,3),(5,5)}13.a.A×(B×C) ={(1,(u, m)),(1,(u, n)),(2,(u, m)),(2,(u, n)),(3,(u, m)),(3,(u, n))}b.(A×B)×C={((1, u), m),((1, u), n),((2, u), m),((2, u), n),((3, u), m),((3, u), n)}c.A×B×C={(1, u, m),(1, u, n),(2, u, m),(2, u, n),(3, u, m),(3, u, n)}14.a.R×(S×T) ={(a,(x, p)),(a,(x, q)),(a,(x, r)),(a,(y, p)),(a,(y, q)),(a,(y, r))}b.(R×S)×T={((a, x), p),((a, x), q),((a, x), r),((a, y), p),((a, y), q),((a, y), r)}c.R×S×T={(a, x, p),(a, x, q),(a, x, r),(a, y, p),(a, y, q),(a, y, r)}15. 0000, 0001, 0010, 0100, 100016.yxxxx, xyxxx,xxyxx,xxxyx,xxxxySection 1.31.a.No. Yes. No. Yes.b.R={(2,6),(2,8),(2,10),(3,6),(4,8)}c.Domain ofR=A={2,3,4}, co-domain ofR=B={6,8,10}d.R68102342.a.2S2 because12−12= 0, which is an integer.−1S−1 because1−1−1−1= 0, which is an integer.3S3 because13−13= 0, which is an integer.3/S−3 because13−1−3=23, which is not an integer.

Solution Manual For Discrete Mathematics With Applications, 5th Edition - Page 6 preview image

Loading page ...

Manual Section 1.35b.S={(−3,−3),(−2,−2),(−1,−1),(1,1),(2,2),(3,3),(1,−1),(−1,1),(2,−2),(−2,2)}c.The domain and co-domain ofSare both{−3,−2,−1,1,2,3}.d.S–3–2–1123–3–2–1123CD3.a.3T0 because3−03=33= 1, which is an integer.1̸T(−1) because1−(−1)3=23, which is not an integer.(2,−1)∈Tbecause2−(−1)3=33= 1, which is an integer.(3,−2)/∈Tbecause3−(−2)3=53, which is not an integer.b.T={(1,−2),(2,−1),(3,0)}c.Domain ofT=E={1,2,3}, co-domain ofT=F={−2,−1,0}d.T–2–101234.a.2V6 because2−64=−44=−1, which is an integer.1̸V(−1) because(−2)−84=−64, which is not an integer.(−2)̸V8 because(−2)−84=−64, which is not an integer.0̸V6 because0−64=−64, which is not an integer.2̸V4 because2−44=−24, which is not an integer.b.V={(−2,6),(0,4),(0,8),(2,6)}c.Domain ofV={−2,0,2}, co-domain ofV={4,6,8}d.S–202468GH5.a.(2,1)∈Sbecause 2≥1. (2,2)∈Sbecause 2≥2.2̸S3 because 23. (−1)S(−2) because−1≥ −2.

Solution Manual For Discrete Mathematics With Applications, 5th Edition - Page 7 preview image

Loading page ...

6Manual: Chapter 1b.x1x$yin shaded regiongraph ofS6.a.(2,4)∈Rbecause 4 = 22.(4,2)/∈Rbecause 2̸= 42.(−3,9)∈Rbecause 9 = (−3)2.(9,−3)/∈Rbecause−3̸= 92.b.123456-6-5-4-3-2-1654321-1-2789yy = x2x7.a.R567456AB456567STAB456567b.Ris not a function because it satisfies neither property (1) nor property (2) of the definition.It fails property (1) because (4, y)/∈R, for anyyinB. It fails property (2) because (6,5)∈Rand (6,6)∈Rand 5̸= 6.Sis not a function because (5, 5)∈Sand (5,7)∈Sand 5̸= 7. SoSdoes not satisfy property(2) of the definition of function.Tis not a function both because (5, x)/∈Tfor anyxinBand because (6,5)∈Tand(6,7)∈Tand 5̸= 7. SoTdoes not satisfy either property (1) or property (2) of the definitionof function.

Solution Manual For Discrete Mathematics With Applications, 5th Edition - Page 8 preview image

Loading page ...

Manual Section 1.378.a.U24135ABV135ABW135AB2424b.None ofU,V, orWare functions.Uis not a function because (4, y) is not inUfor anyyinB, and soUdoes not satisfy property(1) of the definition of function.Vis not a function because (2, y) is not inVfor anyyinB, and soVdoes not satisfy property(1) of the definition of function.Wis not a function because both (2,3) and (2,5) are inWand 3̸= 5, and soWdoes notsatisfy property (2) of the definition of function.9.a.There is only one:{(0,1),(1,1)}b.{(0,1)},{(1,1)}10. The following sets are relations from{a, b}to{x, y}that are not functions:{(a, x)},{(a, y)},{(b, x)},{(b, y)},{(a, x),(a, y)},{(b, x),(b, y)},{(a, x),(a, y),(b, x)},{(a, x),(a, y),(b, y)},{(b, x),(b, y),(a, x)},{(b, x),(b, y),(a, y)},{(a, x),(a, y),(b, x),(b, y)}.11.L(0201) = 4, L(12) = 212.C(x) =yx, C(yyxyx) =yyyxyx13.a.Domain =A={−1,0,1},co-domain =B={t, u, v, w}b.F(−1) =u, F(0) =w, F(1) =u14.a.Domain ofG={1,2,3,4},co-domain ofG={a, b, c, d}b.G(1) =G(2) =G(3) =G(4) =c15.a.This diagram does not determine a function because 2 is related to both 2 and 6.b.This diagram does not determine a function because 5 is in the domain but it is not relatedto any element in the co-domain.c.This diagram does not determine a function because 4 is related to both 1 and 2, whichviolates property (2) of the definition of function.d.This diagram defines a function; both properties (1) and (2) are satisfied.e.This diagram does not determine a function because 2 is in the domain but it is not relatedto any element in the co-domain.16.f(−1) = (−1)2= 1, f(0) = 02= 0, f(12)=(12)2=14.17.g(−1000) =−999,g(0) = 1,g(999) = 100018.h(−125) =h(01) =h(917) = 219. For eachx∈R,g(x) = 2x3+ 2xx2+ 1= 2x(x2+ 1)x2+ 1= 2x=f(x).Therefore, by definition ofequality of functions,f=g.

Solution Manual For Discrete Mathematics With Applications, 5th Edition - Page 9 preview image

Loading page ...

8Manual: Chapter 120. For allx∈R,K(x) = (x−1)(x−3) + 1 = (x2−4x+ 3) + 1 =x2+ 4x+ 4 = (x−2)2=H(x).Therefore, by definition of equality of functions,H=K.Section 1.41.V(G) ={v1, v2, v3, v4}, E(G) ={e1, e2, e3}Edge-endpoint function:EdgeEndpointse1{v1,v2}e2{v1,v3}e3{v3}2.V(G) ={v1, v2, v3, v4},E(G) ={e1, e2, e3, e4, e5}Edge-endpoint function:EdgeEndpointse1{v1, v2}e2{v2, v3}e3{v2, v3}e4{v2, v4}e5{v4}3.1e1e22453e3e44.1v4v3v2v1v5eeee4235. Imagine that the edges are strings and the vertices are knots. You can pick up the left-handfigure and lay it down again to form the right-hand figure as shown below.526134e6e5e7e4e3e2e1

Solution Manual For Discrete Mathematics With Applications, 5th Edition - Page 10 preview image

Loading page ...

Manual Section 1.496.v4v3v2v1e3e4e21e7.or123456789v4v3v2v1v5v6v7eeeeeeeee123456789v4v3v2v1v5v6v7eeeeeeeee8. (i)e1,e2,e7are incident onv1.(ii)v1,v2, andv3are adjacent tov3.(iii)e2,e8,e9, ande3are adjacent toe1.(iv) Loops aree6ande7.(v)e8ande9are parallel;e4ande5are parallel.(vi)v6is an isolated vertex.(vii) degree ofv3= 59. (i)e1,e2,e7are incident onv1.(ii)v1andv2are adjacent tov3.(iii)e2ande7are adjacent toe1.(iv)e1ande3are loops.(v)e4ande5are parallel.(vi)v4is an isolated vertex.(vii) degree ofv3= 210.a.Yes. According to the graph,Sports Illustratedis an instance of a sports magazine, a sportsmagazine is a periodical, and a periodical contains printed writing.b.Yes. According to the graph,Poetry Magazineis an instance of a Literary journal which isa Scholarly journal and, therefore, contains Long words.11.(vvccB/)→(vc/Bvc)→(vvcB/c)→(c/Bvvc)→(vcB/vc)→(/Bvvcc)(vvccB/)→(vv/Bcc)→(vvcB/c)→(c/Bvvc)→(vcB/vc)→(/Bvvcc)(vvccB/)→(vv/Bcc)→(vvcB/c)→(c/Bvvc)→(ccB/vv)→(/Bvvcc)

Solution Manual For Discrete Mathematics With Applications, 5th Edition - Page 11 preview image

Loading page ...

10Manual: Chapter 112. To solve this puzzle using a graph, introduce a notation in which, for example,wc/fgmeansthat the wolf and the cabbage are on the left bank of the river and the ferryman and the goatare on the right bank. Then draw those arrangements of wolf, cabbage, goat, and ferrymanthat can be reached from the initial arrangement (wgcf/) and that are not arrangements to beavoided (such as (wg/fc)). At each stage ask yourself, “Where can I go from here?” and drawlines or arrows pointing to those arrangements. This method gives the graph shown below.Examining the diagram reveals the solutions(wgcf/)→(wc/gf)→(wcf/g)→(w/gcf)→(wgf/c)→(g/wcf)→(gf/wc)→(/wgcf)and(wgcf/)→(wc/gf)→(wcf/g)→(c/wgf)→(gcf/w)→(g/wcf)→(gf/wc)→(/wgcf)13.vvvcccB/vvvc/Bccvvcc/Bvcvvvcc/BcvvvccB/cvvv/BcccvvvcB/ccvc/BvvccvvccB/vccccB/vvvc/BvvvccvcB/vvcc/BvvvcccccB/vvvcccB/vvvcThe diagram shows several solutions. Among them is (vvvcccB/)→(vvcc/Bvc)→(vvvccB/c)→(vvv/Bccc)→(vvvcB/cc)→(vc/Bvvcc)→(vvccB/vc)→(cc/Bvvvc)→(cccB/vvv)→(c/Bvvvcc)→(vcB/vvcc)→(/Bvvvccc), or one can end with (c/Bvvvcc)→(ccB/vvvc)→(/Bvvvccc), or one can start with (vvvcccB/)→(vvvc/Bcc)→(vvvccB/c).14. Represent possible amounts of water in jugsAandBby ordered pairs with, say, the orderedpair (1,3) indicating that there is one quart of water in jugAand three quarts in jugB.Starting with (0,0), draw an edge from one ordered pair to another if it is possible to go fromthe situation represented by the one pair to that represented by the other and back by either

Solution Manual For Discrete Mathematics With Applications, 5th Edition - Page 12 preview image

Loading page ...

Manual Section 1.411filling a jug from the tap, emptying a jug into the drain, or transferring water from one jugto another.Except for (0,0), only draw edges from states that have edges incident on them(since these are the only states that can be reached). The resulting graph is shown as follows:(0,3)(1,3)(2,3)(3,3)(0,2)(1,2)(2,2)(3,2)(0,1)(1,1)(2,1)(3,1)(0,0)(1,0)(2,0)(3,0)(0,5)(1,5)(2,5)(3,5)(0,4)(1,4)(2,4)(3,4)It is clear from the graph that one solution is (0,0)→(3,0)→(0,3)→(3,3)→(1,5)→(1,0)and another solution is (0,0)→(0,5)→(3,2)→(0,2)→(2,0)→(2,5)→(3,4)→(0,4)→(3,1)→(0,1).Note that it would be possible to add arrows to the above graph from each reachable stateto each other state that could be obtained from it either by filling one of the jugs to the topor by emptying the entire contents of one of the jugs. For instance, one could draw an arrowfrom (0,3) to (0,5) or from (0,3) to (0,0).Because the graph is connected, all such arrowswould point to states already reachable by other means, so that it is not necessary to addsuch additional arrows to find solutions to the problem (and it makes the diagram look morecomplicated).However, if the problem were to find all possible solutions, the arrows wouldhave to be added.15.bcedgfa1323231Vertexehas maximal degree, so color it with color #1. Vertexadoes not share an edge withe,and so color #1 may also be used for it. From the remaining uncolored vertices, all ofd, g, andfhave maximal degree. Choose any one of them—say,d—and use color #2 for it. Observethat verticescandfdo not share an edge withd, but they do share an edge with each other,which means that color #2 may be used for one but not the other.Choose to colorfwithcolor #2 because the degree offis greater than the degree ofc.The remaining uncoloredvertices,b, c,andg, are unconnected, and so color #3 may be used for all three.

Solution Manual For Discrete Mathematics With Applications, 5th Edition - Page 13 preview image

Loading page ...

12Manual: Chapter 116. Represent each committee name by a vertex, labeled with the first letter of the name of thecommittee, and join vertices if, and only if, the corresponding committees have a member incommon. Figure (a) shows one way to color the graphs. VertexHhas maximum degree, souse color #1 for it.VertexLdoes not share an edge withH, and so color #1 may also beused for it.From the remaining uncolored vertices, each ofP,U, andGis adjacent to three other vertices.Choose any one of them, sayP, and use color #2 for it. VerticesUandCdo not share anedge withPor with each other, and so color #2 may also be used for them.Color #3 can then be used for the remaining vertex,G, at which point all vertices will becolored.Note that the same result is obtained ifUis chosen instead ofPin step 2. However, ifGischosen instead ofPin step 2, the result is the coloring indicated in Figure (b).UGHPLC221132(b)(a)UGHPLC331122To use the results of Figure (a) to schedule the meetings, let colorncorrespond to meetingtimen. ThenTime 1: hiring, libraryTime 2: personnel, undergraduate education, colloquiumTime 3: graduate educationUsing the results of Figure (b) to schedule the meetings produces this result:Time 1: hiring, libraryTime 2: graduate education, colloquiumTime 3: personnel, undergraduate education17. In the following graph each course number is represented as a vertex. Vertices are joined if,and only if, the corresponding courses have a student in common.1101201301351001242433102101Vertex 135 has maximum degree, so use color #1 for it. All vertices share edges with vertex135, and so color #1 cannot be used on any other vertex.From the remaining uncolored vertices, only vertex 120 has maximum degree. So use color #2for it. Because vertex 100 does not share an edge with vertex 120, color #2 may also be usedfor it.From the remaining uncolored vertices, all of101, 102, 110, and 130 have maximum degree.Choose any one of them, say vertex 101, and use color #3 for it.Neither vertex 102 nor

Solution Manual For Discrete Mathematics With Applications, 5th Edition - Page 14 preview image

Loading page ...

Manual Section 1.413vertex 110 shares an edge with vertex 101, but they do share an edge with each other.Socolor #3 may be used for only one of them. If color #3 is used for vertex 110, then, since theremaining vertices 130 and 102 are connected, two additional colors would be needed for themto have different colors. On the other hand, if color #3 is used for vertex 102, then, since theremaining vertices, 110 and 130, are not connected to each other, color 4 may be used for both.Therefore, to minimize the number of colors, color #3 should be used for vertex 102 and color#4 for vertices 110 and 130. The result is indicated in the annotations on the graph.To use the results for scheduling exams, let colorncorrespond to exam timen. ThenTime 1: MCS135Time 2: MCS 100 and MCS120Time 3: MCS101 and MCS102Time 4: MCS110 and MCS130Note that because, for example, MSC135, MSC102, MSC110, and MSC 120 are all connectedto each other, they must all be given different colors, and so the schedule for the seven examsmust use at least four time periods.

Solution Manual For Discrete Mathematics With Applications, 5th Edition - Page 15 preview image

Loading page ...

Manual: Chapter 21Chapter 2: The Logic of Compound StatementsThe ability to reason using the principles of logic is essential for solving problems in abstract math-ematics and computer science and for understanding the reasoning used in mathematical proof anddisproof. Because a significant number of students who come to college have had limited opportu-nity to develop this ability, a primary aim of Chapters 2 and 3 is to help students develop an innervoice that speaks with logical precision. Consequently, the various rules used in logical reasoning aredeveloped both symbolically and in the context of their somewhat limited but very important usein everyday language. Exercise sets for Sections 2.1–2.3 and 3.1–3.4 contain sentences for studentsto negate, write the contrapositive for, and so forth. Virtually all students benefit from doing theseexercises. Another aim of Chapters 2 and 3 is to teach students the rudiments of symbolic logic asa foundation for a variety of upper-division courses.Symbolic logic is used in, among others, thestudy of digital logic circuits, relational databases, artificial intelligence, and program verification.Suggestions1.In Section 2.1 a surprising number of students apply De Morgan’s law to write the negation of,for example, “1< x≤3” as “1≥x >3.” You may find that it takes some effort to teach them toavoid making this mistake.2.In Sections 2.1 and 2.4, students have more difficulty than you might expect simplifying statementforms and circuits. Only through trial and error can you learn the extent to which this is the caseat your institution. If it is, you might either assign only the easier exercises or build in extra time toteach students how to do the more complicated ones. Discussion of simplification techniques occursagain in Chapter 6 in the context of set theory. At this later point in the course most students areable to deal with it successfully.3.In ordinary English, the phrase “only if” is often used as a synonym for “if and only if.” But itis possible to find informal sentences for which the intuitive interpretation is the same as the logicaldefinition. It is helpful to give examples of such statements when you introduce the logical definition.For instance, it is not hard to get students to agree that “The team will win the championship onlyif it wins the semifinal game” means the same as “If the team does not win the semifinal game thenit will not win the championship.” Once students see this, you can suggest that they remember thisexample when they encounter more abstract “only if”statements.Through guided discussion, students also come to agree that the statement “Winning the semi-final game is a necessary condition for winning the championship” translates to “If the team doesnot win the semifinal game then it will not win the championship.” They can be encouraged to usethis (or a similar statement) as a reference to help develop intuition for general statements of theform “Ais a necessary condition forB.”With students who have weaker backgrounds, you may find yourself tying up excessive amountsof class time discussing “only if” and “necessary and sufficient conditions.” You might just assignthe easier exercises, or you might assign exercises on these topics to be done for extra credit (puttingcorresponding extra credit problems on exams) and use the results to help distinguish A from Bstudents. It is probably best not to omit these topics altogether, though, because the language of“only if” and “necessary and sufficient conditions” is a standard part of the technical vocabulary oftextbooks used in upper-division courses, as well as occurring regularly in non-mathematical writing.4.In Section 2.3, many students mistakenly conclude that an argument is valid if, when theycompute the truth table, they find a single row in which both the premises and the conclusion aretrue. The source of students’ difficulty appears to be their tendency to ignore quantification and tomisinterpret if-then statements as “and” statements. Since the definition of validity includes botha universal quantifier and if-then, it is helpful to go back over the definition and the procedures fortesting for validity and invalidity after discussing the general topic of universal conditional statements

Solution Manual For Discrete Mathematics With Applications, 5th Edition - Page 16 preview image

Loading page ...

2Solutions for Exercises: The Logic of Compound Statementsin Section 3.1. As a practical measure to help students assess validity and invalidity correctly, thefirst example in Section 2.3 is of an invalid argument whose truth table has eight rows, severalof which have true premises and a true conclusion.To further focus students’ attention on thesituations where all the premises are true, the truth values for the conclusions of arguments areomitted when at least one premise is false.5.In Section 2.3, you might suggest that students just familiarize themselves with, but not memorize,the various forms of valid arguments covered in Section 2.3. It is wise, however, to have them learnthe terms modus ponens and modus tollens (because these are used in some upper-division computerscience courses) and converse and inverse errors (because these errors are so common).Section 2.11. Common form:Ifpthenq.pTherefore,q(a+ 2b)(a2−b) can be written in prefix notation. All algebraic expressions can be written inprefix notation.2. Common form:Ifpthenq.∼qTherefore,∼pAll prime numbers are odd. 2 is odd3. Common form:p∨q∼pTherefore,qMy mind is shot. Logic is confusing.4. Common form:Ifpthenq.Ifqthenr.Therefore,Ifpthenr.Has 4 vertices and 6 edges. Is complete; Any two of its vertices can be joined by a path5.a.It is a statement because it is a true sentence. 1,024 is a perfect square because 1,024 = 322,and the next smaller perfect square is 312= 961, which has fewer than four digits.b.The truth or falsity of this sentence depends on the reference for the pronoun “she.”Considered on its own, the sentence cannot be said to be either true or false, and so it is nota statement.c.This sentence is false; hence it is a statement.d.This is not a statement because its truth or falsity depends on the value ofx.6.a. s∧ib.∼s∧ ∼i7.m∧ ∼c8.a.(h∧w)∧ ∼sb.∼w∧(h∧s)c.∼w∧ ∼h∧ ∼sd.(∼w∧ ∼s)∧he. w∧ ∼(h∧s) (w∧(∼h∨ ∼s) is also acceptable)9.a. p∨qb.r∧pc.r∧(p∨q)10.a. p∧q∧rb.p∧ ∼qc.p∧(∼q∨ ∼r)d.(∼p∧q)∧ ∼re.∼p∨(q∧r)

Preview Mode

This document has 732 pages. Sign in to access the full document!

Report

Study Now!

Document Details

Related Documents

Test Bank For Discrete Mathematics With Applications, 5th Edition

Precalculus - Polynomial and Rational Functions

Precalculus - Functions

Precalculus - Exponential and Logarithmic Functions

Math Word Problems - Translating Expressions

Math Word Problems - Equations

Algebra II – Word Problems

Algebra II – Sequences and Series

Algebra II - Segments Lines and Inequalities

Algebra II - Relations and Functions

Company

Explore

Study Tools