Menu

Week 1

0 Comment

Individual Selected Textbook Exercises Directions Use the e book to see examples, ebook user is salvatore2 amp. password is salvatore80 Ch. 1of Discrete and Combinatorial Mathematics Supplementary Exercises1. In the manufacture of a certain type of automobile, fourkinds of major defects and seven kinds of minor defects canoccur. For those situations in which defects do occur, in howmany ways can there be twice as many minor defects as thereare major ones?Answer: For the ratio of 1:2 to occur, there are a total of 3 situations as follows:a. 1 major defect : 2 minor defect For 1 major defect: 4!/(4-1)! = 4For 2 minor defect: 7!/(7-2)! = 7×6 =42 Hence: 4 x 42 = 168b. 2 major defect : 4 minor defect For 2 major defect: 4!/(4-2)! = 4 x 3 = 12For 4 minor defect: 7!/(7-4)! = 7x6x5x4 =840 Hence: 12 x 840 = 10,080 c. 3 major defect : 6 minor defect For 3 major defect: 4!/(4-3)! = 4 x 3 x 2 = 24For 6 minor defect: 7!/(7-6)! = 7x6x5x4x3x2 =5040 Hence: 24 x 5040 = 120,960 Totally: 168 + 10,080 + 120,960 = 131,208 2. A machine has nine different dials, each with five settingslabeled 0, 1, 2, 3, and 4.a) In how many ways can all the dials on the machine beset? Answer: 59 = 1,953,125b) If the nine dials are arranged in a line at the top of themachine, how many of the machine settings have no twoadjacent dials with the same setting? Answer: 1st place = 5 possibilities 2nd,3rd to 9th = 4 possibilities each place Hence: 5 x 48 = 327,680 3. How many of the 9000 four-digit integers 1000, 1001,1002, . . . , 9998, 9999 have four distinct digits that are eitherincreasing (as in 1347 and 6789) or decreasing (as in6421 and 8653)? Answer: For increasing, note that there are important points to be considered such as the digit 9 can only be found in the last place, the digit 0 is unusable hence our effective digits is nine in total (1,2,3,4,5,6,7,8 and 9) and that order and distinction is very important. In this method used, the tens place is used as reference:A. Digit in the tens placeB. Combinations221315410566371Note that digit 1 is not possible to put in the tens place as the resulting number lt. 1000 which is the leftmost boundary.To proceed, we note how many digits can be placed in the units place considering the digit in the tens place. Here we are restricted to the digits 1,2,3,4,5 and 6 since the digit 7,8,9 will compromise the whole restriction of increasing order when use it in the units position:A. Digit in the tens placeC. Possible Number of Digits in Units PlaceD. Total combination = (B*C)21213230433054246515766Total=126For decreasing, note that there are important points to be considered such as the digit 9 can only be placed in the units position and that the digit 0 can be used but only placed in the thousands position. In this method used, the tens place is used as reference:E. Digit in the tens placeF. Combinations828721615510463321Note that digit 1 is not possible to put in the tens place as the resulting number would violate the restriction of decreasing and distinct numbers.To proceed, we note how many digits can be placed in the units place considering the digit in the tens place. Here we are restricted to the digits 1,2,3,4,5 and 6 since the digit 7,8,9 will compromise the whole restriction of increasing order when use in the units position:B. Digit in the tens placeG. Possible Number of Digits in Units PlaceH. Total combination = (B*C)812872426345544045303618277Total=2104. Mr. and Mrs. Richardson want to name their new daughterso that her initials (first, middle, and last) will be in alphabeticalorder with no repeated initial. How many such triples of initialscan occur under these circumstances?Answer: Grouping the alphabets by 3 in succession such as ABC,BCD,EFG and limiting it with three distinct initials and alphabetical in order means that we can end only on the combination XYZ. Hence, on the 26 alphabets, only 24 combinations can be used given the restriction.Ch. 2 of Discrete and Combinatorial Mathematics 5. Let p, q be primitive statements for which the implicationp→q is false. Determine the truth values for each of the following.a) p ∧ q p=1, q=0. hence truth value =0 (false) b) ¬p ∨ q p=0, q=0. hence truth value =0 (false)c) q →p q=0, p=1. hence truth value =1 (true)d) ¬q →¬p q=1, p=0. hence truth value =0 (false)6. Use the substitution rules to verify that each of the followingis a tautology. (Here p, q, and r are primitive statements.)a) [p ∨ (q ∧ r)] ∨ ¬[p ∨ (q ∧ r)]Let m = [p ∨ (q ∧ r)], hence: m ∨ ¬mTo illustrateM¬mm ∨ ¬m011101Hence: [p ∨ (q ∧ r)] ∨ ¬[p ∨ (q ∧ r)] is a tautology since all components have truth values=1b) [(p ∨ q)→r] ↔ [¬r →¬(p ∨ q)]Let s = (p ∨ q) hence: [s→r] ↔ [¬r →¬s]sRs→r¬r¬s¬r →¬s001111011011100100111001Since truth values for components of s→r corresponds to ¬r →¬s, then [s→r] ↔ [¬r →¬s] is a tautology.7. For any statements p, q, prove thata) ¬(p ↓ q)⇐⇒(¬p ↑¬q)using Tautology:pq(p ↓ q)¬(p ↓ q)¬p¬q(¬p ↑¬q)0001111011010010100101110000Since the values correspond and the conditions of tautology exists, then ¬(p ↓ q)⇐⇒(¬p ↑¬q) which is De Morgan’s Lawb) ¬(p ↑ q)⇐⇒(¬p ↓¬q)using Tautology:pq(p ↑ q)¬(p ↑ q)¬p¬q(¬p ↓¬q)0001111010110110010111110000Since the values correspond and the conditions of tautology exists, then ¬(p ↑ q)⇐⇒(¬p ↓¬q)8. The following are three valid arguments. Establish the validityof each by means of a truth table. In each case, determinewhich rows of the table are crucial for assessing the validity ofthe argument and which rows can be ignored.a) [p ∧ (p→q) ∧ r] → [(p ∨ q)→r]pqr(p→q)p ∧ (p→q)p ∧ (p→q) ∧ rp ∨ q(p ∨ q)→r[p ∧ (p→q) ∧ r] → [(p ∨ q)→r]00010001100110 0011010100101011100111100000101101000111110110101111111111Green shade : necessaryBlue shade : unnecessarySince the indicator → indicates that the truth value can only be false (=0) when the statement on the left side is true, then there was no need to investigate further the rows shaded blue. b) [[(p ∧ q)→r] ∧ ¬q ∧ (p→¬r)]→(¬p ∨¬q)pqr(p ∧ q)(p ∧ q)→r¬p¬q¬r[(p ∧ q)→r] ∧ ¬qp→¬r[[(p ∧ q)→r] ∧ ¬q ∧ (p→¬r)]¬p ∨¬q[[(p ∧ q)→r] ∧ ¬q ∧ (p→¬r)]→(¬p ∨¬q)00001111111110010111011111010011010101101101100010111000101111111101010101001111011001010011111100000001Green shade : necessaryBlue shade : unnecessarySince the indicator → indicates that the truth value can only be false (=0) when the statement on the left side [[(p ∧ q)→r] ∧ ¬q ∧ (p→¬r)] is true (1), there was no need to investigate those with values =0. c) [[p ∨ (q ∨ r)] ∧ ¬q]→(p ∨ r)pQr(q ∨ r)[p ∨ (q ∨ r)]¬q[[p ∨ (q ∨ r)] ∧ ¬q](p ∨ r)[[p ∨ (q ∨ r)] ∧ ¬q]→(p ∨ r)000001001001111111010110001011110011100011111101111111110110011111110011Green shade : necessaryBlue shade : unnecessarySince the indicator → indicates that the truth value can only be false (=0) when the statement on the left side [[p ∨ (q ∨ r)] ∧ ¬q] is true (1), there was no need to investigate those with values =0. Ch. 3 of Discrete and Combinatorial Mathematics9. a) Determine the sets A, B where A − B _ {1, 3, 7, 11}, B − A _ {2, 6, 8}, and A ∩ B _ {4, 9}. From A ∩ B € {4, 9}, we have a preliminary A € {4, 9} and B € {4, 9} We add to set A the values of A − B € {1, 3, 7, 11} then A € {1, 3,4, 7, 9,11} We add to set B the values of B − A € {2, 6, 8} then B € {2,4,6,8,9} b) Determine the sets C, D where C − D €{1, 2, 4}, D − C € {7, 8}, and C ∪ D € {1, 2, 4, 5, 7, 8, 9} From C − D €{1, 2, 4}, we have a preliminary C €{1, 2, 4} From D − C € {7, 8}, we have a preliminary D € {7, 8} Considering C ∪ D € {1, 2, 4, 5, 7, 8, 9} to be the entirety of the sets, then Answer: the set C must be {1, 2, 4, 5, 9}the set D must be {5,7,8, 9}10. UsingVenn diagrams, investigate the truth or falsity of each of the following, for sets A, B, C ⊆ _.a) A (B ∩ C) = (A B) ∩ (A C) Venn Diagram for A (B ∩ C): Venn Diagram for (A B) ∩ (A C): Hence the statement is false.b) A − (B ∪ C) = (A − B) ∩ (A − C) Venn Diagram for A − (B ∪ C): Venn Diagram for (A − B) ∩ (A − C): From the diagram, we can see that the statement is true.c) A (B C) = (A B) C Venn Diagram for A (B C): Venn Diagram for (A B) C: From the diagram, we can see that the statement is true.11. During freshman orientation at a small liberal arts college, two showings of the latest James Bond movie were presented. Among the 600 freshmen, 80 attended the first showing and 125attended the second showing, while 450 didn’t make it to either showing. How many of the 600 freshmen attended twice? The possible Venn Diagram is shown in the following: The intersection represents the number of students that attended twice. Hence, the answer is that 55 students attended twice.12. A manufacturer of 2000 automobile batteries is concerned about defective terminals and defective plates. If 1920 of her batteries have neither defect, 60 have defective plates, and 20have both defects, how many batteries have defective terminals?The possible Venn Diagram is shown in the following: From the resulting Venn Diagram, one can verify that 60 automobiles have defective plates and 20 have both defects thus satisfying the given. 2000 – 1920 – 60 = 20 which is the number of automobiles which has defective terminals only. Therefore, the number of automobiles with defective batteries is 20 + 20 = 40. Answer is 40.