Outline of COT 3100 material for first examI. Counting A. Sum Rule B. Product Rule C. Subtraction Idea D. Permutations E. Combinations F. Combinations with repetitionII. Logic A. Symbols(,, and ) B. Truth Tables C. Logic Laws D. Methods of showing equality of logical expressions E. Implication Rules F. Contrapositive of a stmt.III. Sets A. Symbols(, , , , , , and ) B. Counting with sets C. Set Laws D. Membership Table E. Proof Techniques for if-then statements i. direct proof ii. proof of contrapositive iii. proof by contradiction F. How to Disprove an if-then statement G. Inclusion-Exclusion PrincipleReading in texbook: 1.1 – 1.4, 2.1 – 2.3, 3.1 – 3.31) Find the number of permutations of letters of the English alphabet (i.e. strings of length 26 using each letter exactly once) that contain none of the strings math, bio or housing.Total number of permutations = 26!Permutations with math = 23!Permutations with bio = 24!Permutations with housing = 20!Permutations with both math and bio = 21!Permutations with both math and housing = 17!Permutations with both bio and housing = 0Permutations with math, bio and housing = 0Total = 26! – (23! + 24! + 20! – (21! + 17!) + 0) = 26! – 24! – 23! – 20! + 21! + 17! 2) In how many ways can 3 blue, 4 white and 2 red balls be distributed into 4 distinct boxes?Distributing each the blues balls is independent of distributing the white ones and the red ones. Using the technique in section 1.4 we know we can distribute 3 blues balls amongst 4 distinguishable boxes in 4-1+3C3 = 20 ways. Similarly, we can distribute the white balls in 4-1+4C4 = 35 ways and the red balls in 4-1+2C2 = 10 ways. Using the product rule, we can distribute the balls in 20x35x10 = 7000 ways.3). In a language survey of students it is found that 80 students know English, 60 know French, 50 know German, 30 know English and French, 20 know French and German, 15 know English and German and 10 students know all three languages. How many students know a) at least one language? b) English only? c) French and one but not both out of English and German?d) at least two languages?Use the inclusion-exclusion principle to handle each of these questions.|A B C| = |A| + |B| + |C| – |A B| – |B C| – |A C| + |A B C|.Let A = students who speak English, B = students who speak French, and C = students that speak German|A B C| = 80 + 60 + 50 – 30 – 20 – 15 + 10 = 135 total students that know at least one language.Now, let’s count the number of students that know English andat least one other language, using the inclusion exclusion principle.|A B| + |A C| - |A B C| = 30 + 15 – 10 = 35. Thus, the number of students that just speak English is simply 80 – 35 = 45.Total that speak French and another language is equal to|A B| + |B C| - |A B C| = 30 + 20 – 10 = 40.Of these students, 10 of them speak 2 different languages. You want to subtract these out also, so there is a total 30 that speak French and exactly one other language.The number of people that speak at least 2 languages is simply|A B| + |B C| + |A C| - 2|A B C| = 30+20+15–20 = 45. We must subtract out the intersection of all three language speakers since we include them 3 times in our initial count.4) Show that the following expression is a tautology:( (p r) ( (q r) p) ) ( ((p q) ) p ) ( (p r) ( (q r) p) ) ( ((p q) ) p ) ( (p r) ( (q r) p) ) ( p q) p (De Morgans) ( (p r) ( (q r) p) ) ( p q) p(Double Negation)(p p) ( (p r) (q r) (p q)) (Comm/Assoc or)T ( (p r) (q r) (p q)) (Inverse Law)T (Domination Law)5) Given the following premises:pp q(q r) sShow that s is true. 1. p (Premise) 2. p q (Premise) 3. q (1+2+Modus Ponens) 4. q r (3+Disjunctive Amplification) 5. q r s (Premise) 6. s (4+5+Modus Ponens)6) Use set laws to prove that (C(AB))((AB)C) = AB.(C(AB))((AB)C) = (AB)( CC) Distributive= (AB)U Inverse Law= AB Identity LawProve or disprove the following:7) Power(A) = Power(A). Disprove. Consider the Universe of positive integers. Let A = {1,2}. Then we have the set {1,3}Power(A) because clearly we have {1,3} Power(A). But we also have that {1,3}Power(A) because 1A. Thus the sets can not be equalin this example since we have found an element that is in one ofthe sets that is not in the other set.8) If A B C, then AC BC.Disprove. Let A= {1} B={2} and C=A B = C, but AC and BC. 9) (AC)(CB)=We must show that the set (AC)(CB) contains no elements. Assume to the contrary, that there exists an x(AC)(CB).We have that x AC and x CB, by the definition of intersection. Then we can conclude that xA, xC, xC, andxB. But this is a contradiction, thus, our assumption is incorrect and the set (AC)(CB)=.10) (AB)C = (AC) (BC)We can prove using membership table method.A B C AB AC BC (AB)C (AC) (BC)1 1 1 0 0 0 0 01 1 0 0 1 1 0 01 0 1 1 0 0 0 01 0 0 1 1 0 1 10 1 1 0 0 0 0 00 1 0 0 0 1 0 00 0 1 0 0 0 0 00 0 0 0 0 0 0 0The identity of the last two columns proves the equivalence.11) A (BC) = (A B)(A C)A (BC) = (A B)(A C)A (BC) = {x | xA x(BC)}, by the dfn of -= {x | xA x[(BC)]}, by the defn of = {x | xA x(BC)}, by DeMorgan’s law={x | xA [x(B) x (C)]}, by the defn of intersection={x | xA (xBxC)}, by the defn on set complement={x | xA xB xC}, by associative law={x | xA xA xB xC }, by idempotent law={x | (xA xB )(xA xC )}, by comm. & assoc.={x | (xAB )(xAC )}, by the defn of set difference={x | x(AB )(AC )}, by the defn of =
View Full Document