# CIS 160 Midterm 1

 .remove_background_ad { border: 1px solid #555555; padding: .75em; margin: .75em; background-color: #e7e7e7; } .rmbg_image { max-height: 80px; } What is a statement that is either true or false proposition Negation Conjunction Disjunction Exclusive OR Implication Biconditional Negation (¬p): not pConjunction (p⋀q): p and qDisjunction (p⋁q): p or qExclusive OR (p⊕q): p exclusive or qImplication (p→q): p implies qBiconditional (p↔q): p if and only if q Truth Table p is a sufficient condition for q means p → q 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) p is a necessary and sufficient condition for q means p iff q (p↔q) Universal Quantifier (for all) ∀ statement is true for all elements in the domain of x Existential quantifier (There exists) ∃ means that there is an element in the domain of x for which the predicate is true 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. 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. 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. The number of elements in the Power set of set S, with n elements can be given by The number of permutations of set S where S has n elements can be given by n! 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. The intersection of sets A and B A∩B is the set that contains those elements that are in both A and B. Two sets are called ____ if their intersection is an empty set disjoint A collection of sets is a partition of a set A iff and only if 1. A = union of all sets in the partition2. all the sets in the partition are mutually disjoint The difference of sets A and B A \ B is the set containing those elements that are in A but not in B. The complement of set A U \ A or ¬A is the set of elements not in A. 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. Let A and B be sets. Then A = B if and only if A ⊆ BB ⊆ A A - (B ∪ C) =  A - (B ∩ C) = A - (B ∪ C) = (A-B)∩(A-C)A - (B ∩ C) = (A-B)∪(A-C) 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) =  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) An r-combination of a set of n elements means an unordered selection of r of the n elements of S.  is the value of Fundamental Theorem of Arithmetic Given any integer n > 1, there exist a positive integer k, distinct prime numbersp1, p2, . . . , pk, and positive integers e1, e2, . . . , ek such thatn = p1^e1 p2^e2 p3^e3...pk^ekand 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. The elements of a multiset are ____ however, the elements of each element are _____. distinguishableindistinguishable The permutations of a multiset S with nk elements of n total objects is 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  or  Steps for an Induction Proof 1. Assert what you want to prove2. Base Case3. Induction Hypothosis4. Induction Step Steps for a combinatorial proof 1. Ask a question2. Show that LHS answers the question3. Show RHS answers the question4. Conclude they are equal Pascal's Formula If n and k are positive ints with n >= k then The Binomial Theorem For any real numbers a and b and non-negative integer n The Pigeonhole Principle If k + 1 or more objects are distributed among k bins then there is at least one bin that hastwo or more objects. For example, the pigeon hole principle can be used to conclude thatin any group of thirteen people there are at least two who are born in the same month. .remove_background_ad { border: 1px solid #555555; padding: .75em; margin: .75em; background-color: #e7e7e7; } .rmbg_image { max-height: 80px; } AuthorHenri93 ID324065 Card SetCIS 160 Midterm 1 DescriptionCIS 160 MIDTERM 1 Updated2016-10-05T00:40:19Z Show Answers