DOC PREVIEW
UCF COT 3100 - COT 3100 Lecture Notes

This preview shows page 1-2 out of 6 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 6 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 6 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 6 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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(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 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 1A. 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 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, andx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 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  (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 =


View Full Document

UCF COT 3100 - COT 3100 Lecture Notes

Documents in this Course
Lab 1

Lab 1

11 pages

Functions

Functions

10 pages

Load more
Download COT 3100 Lecture Notes
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view COT 3100 Lecture Notes and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view COT 3100 Lecture Notes 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?