Outline of COT 3100 material for first exam I Counting A Sum Rule B Product Rule C Subtraction Idea D Permutations E Combinations F Combinations with repetition II 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 Principle Reading in texbook 1 1 1 4 2 1 2 3 3 1 3 3 1 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 0 Permutations with math bio and housing 0 Total 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 and at 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 Domination Law T 5 Given the following premises p p q q r s Show 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 A B A B C A B C A B A B C A B C C Distributive A B U Inverse Law A B Identity Law Prove 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 1 A Thus the sets can not be equal in this example since we have found an element that is in one of the sets that is not in the other set 8 If A B C then A C B C Disprove Let A 1 B 2 and C A B C but A C and B C 9 A C C B We must show that the set A C C B contains no elements Assume to the contrary that there exists an x A C C B We have that x A C and x C B by the definition of intersection Then we can conclude that x A x C x C and x B But this is a contradiction thus our assumption is incorrect and the set A C C B 10 A B C A C B C We can prove using membership table method A B C A B A C B C A B C A C B C 1 1 1 0 0 0 0 0 1 1 0 0 1 1 0 0 1 0 1 1 0 0 0 0 1 0 0 1 1 0 1 1 0 1 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 The identity of the last two columns proves the equivalence 11 A B C A B A C A B C A B A C A B C x x A x B C by the dfn of x x A x B C by the defn of x x A x B C by DeMorgan s law x x A x B x C by the defn of intersection x x A x B x C by the defn on set complement x x A x B x C by associative law x x A x A x B x C by idempotent law x x A x B x A x C by comm assoc x x A B x A C by the defn of set difference x x A B A C by the defn of A B A C
View Full Document
Unlocking...