CIS 160 Midterm 1

  1. What is a statement that is either true or false
  2. Negation
    Exclusive OR
    • Negation (¬p): not p
    • Conjunction (p⋀q): p and q
    • Disjunction (p⋁q): p or q
    • Exclusive OR (p⊕q): p exclusive or q
    • Implication (p→q): p implies q
    • Biconditional (p↔q): p if and only if q
  3. Truth Table
    Image Upload 1
  4. p is a sufficient condition for q means
    p → q
  5. p is a necessary condition for q means that
    • ¬p → ¬q or equivalently q → p
    • (p ∧ q is not the correct answer because p could still be true but q may be false, q still may happen without p)
  6. p is a necessary and sufficient condition for q means
    p iff q (p↔q)
  7. Universal Quantifier (for all)
    ∀ statement is true for all elements in the domain of x
  8. Existential quantifier (There exists)
    ∃ means that there is an element in the domain of x for which the predicate is true
  9. When is an integer prime?
    An integer n is prime iff n > 1 and for all positive integers r and s, if n = r x s, then r = 1 or s = 1. Otherwise n is composite.
  10. For any set S, the empty set
    ∅⊆S and S⊆S.
    If A⊆B and A≠B then we say that A is a proper subset of B (A⊂B). A is a proper subset of B if A is a subset of B and there is an element in B that does not belong to A.
  11. Theorem of Number of Numbers between numbers
    If m and n are integers and m ≤ n then there are n-m+1 integers from m to n inclusive.
  12. The number of elements in the Power set of set S, with n elements can be given by
  13. The number of permutations of set S where S has n elements can be given by
  14. The union of sets A and B
    A∪B is the set that contains those elements that are in A or in B or in both.
  15. The intersection of sets A and B
    A∩B is the set that contains those elements that are in both A and B.
  16. Two sets are called ____ if their intersection is an empty set
  17. A collection of sets is a partition of a set A iff and only if
    • 1. A = union of all sets in the partition
    • 2. all the sets in the partition are mutually disjoint
  18. The difference of sets A and B
    A \ B is the set containing those elements that are in A but not in B.
  19. The complement of set A
    U \ A or ¬A is the set of elements not in A.
  20. The cartesian product of A and B
    A x B is the set of all ordered pairs formed by taking an element from A together with an element from B in all possible ways.
  21. Let A and B be sets. Then A = B if and only if
    • A ⊆ B
    • B ⊆ A
  22. A - (B ∪ C) = 
    A - (B ∩ C) =
    • A - (B ∪ C) = (A-B)∩(A-C)
    • A - (B ∩ C) = (A-B)∪(A-C)
  23. Let P(n,r) denote the number of r-permutations of a set of n elements. What is the value of P(n,r)?
    P(n,r) = chart?chf=bg,s,00000000&cht=tx&chl=%5Cfrac%7Bn!%7D%7B(n-r)!%7D&chs=96x78
  24. The Inclusion-Exclusion Formula

    If A, B, and C are any finite sets, then
    |A∪B∪C| =
    • |A| + |B| + |C| - |A∩B| - |A∩C| - |B∩C| + |A∩B∩C|
    • Observe that if the sets are mutually disjoint then |A∪B∪C| = |A| + |B| + |C| (Sum Rule)
  25. An r-combination of a set of n elements means an unordered selection of r of the n elements of S. chart?chf=bg,s,00000000&cht=tx&chl=(%5Cfrac%7Bn%7D%7Br%7D)&chs=50x52 is the value of
  26. Fundamental Theorem of Arithmetic

    • Given any integer n > 1, there exist a positive integer k, distinct prime numbers
    • p1, p2, . . . , pk, and positive integers e1, e2, . . . , ek such that
    • n = p1^e1 p2^e2 p3^^ek
    • and any other expression of n as a product of primes is identical to this except,
    • perhaps, for the order in which the factors are written.
  27. The elements of a multiset are ____ however, the elements of each element are _____.
    • distinguishable
    • indistinguishable
  28. The permutations of a multiset S with nk elements of n total objects is
  29. r-combinations with repetition allowed
    n: n-1 sticks
    r: n crosses
    The total number of possible ways to choose multisets of size r from a multiset of n objects with repetition of each object is
    chart?chf=bg,s,00000000&cht=tx&chl=(%5Cfrac%7Bn%2Br-1%7D%7Br%7D)&chs=138x60 or chart?chf=bg,s,00000000&cht=tx&chl=%5Cfrac%7B(n%2Br-1)!%7D%7B(n-1)!r!%7D&chs=140x86
  30. Steps for an Induction Proof
    • 1. Assert what you want to prove
    • 2. Base Case
    • 3. Induction Hypothosis
    • 4. Induction Step
  31. Steps for a combinatorial proof
    • 1. Ask a question
    • 2. Show that LHS answers the question
    • 3. Show RHS answers the question
    • 4. Conclude they are equal
  32. Pascal's Formula
    • If n and k are positive ints with n >= k then
    • chart?chf=bg,s,00000000&cht=tx&chl=(%5Cfrac%7Bn%7D%7Bk%7D)%20%3D%20(%5Cfrac%7Bn-1%7D%7Bk-1%7D)%2B(%5Cfrac%7Bn-1%7D%7Bk%7D)&chs=304x66
  33. The Binomial Theorem
    • For any real numbers a and b and non-negative integer n
    • chart?chf=bg,s,00000000&cht=tx&chl=(a%2Bb)%5En%20%3D%20%5Csum_%7Bk%3D0%7D%5En%20(%5Cfrac%7Bn%7D%7Bk%7D)%20%5Ctimes%20a%5E%7Bn-k%7D%20b%5Ek&chs=442x60
  34. The Pigeonhole Principle
    • If k + 1 or more objects are distributed among k bins then there is at least one bin that has
    • two or more objects. For example, the pigeon hole principle can be used to conclude that
    • in any group of thirteen people there are at least two who are born in the same month.
Card Set
CIS 160 Midterm 1