Table of Contents
III. Theory and Mathematical Background – 40%
C. Discrete structures
3. Discrete probability, recurrence relations, and number theory
a. Definition: Discrete means that it can be separated from other things. Digital clocks are discrete because 9 o’clock is a very specific state. Analog (face) clocks are not discrete because there is a range of states that are considered to be 9 o’clock.
b. Definition: For thousands of years, geeks and nerds all over the world have looked and found patterns in numbers. Before computers, most of these patterns had little value, so we called it number theory.
c. Sets are unordered collections of elements. We need to know how to describe the members of the set and we need to know operators on sets.
d. We list the members of a set B inside of a pair of braces{}. If an element is a member of the set, we write x Î B. If an element is not a member of the set, we write x Ï B. If the elements of a set follow from some sort of function, then we write {x | f(x)} (read this as all x such that f(x). If two sets have the same elements, then B = D. If a set has no elements, then it is the empty set or null set written Æ. If all of the elements in B are also in D, then B is a subset of D written B Í D. If B Í D and there is at least one element in D that is not in B, then B is a proper subset of D written B Ì D. The power set of a given set is the set of all possible subsets of the original set. For example, the power set of {0,1} is [{Æ}, {0}, {1}. {0,1}]. You should note that that the number of elements (which are actually subsets) in the power set with n elements is 2n. When counting the number of elements in a set, we often say it has cardinality of n if there are n elements in the set. We say sets are cardinal, because the order of the elements is not important. If the order of the elements is important, we usually call it an ordered set or a sequence.
e. The compliment of B written 
has all of the elements that are not in B, but are in the set that is made up of B and . The union of two sets S and T, written S È T is a new set that has all of the elements from S and T. The intersection of S and T, written S Ç T is a new set that has only the elements that are in both S and T. The Cartesian product (or cross product) of A and B, written A X B is {(a, b) | a ÎA ^ b Î B}. Meaning the new set has all of the ordered pairs with one element from A and one element from B.
f. Strings are elements in a specific order. Again, we need to know how to express them and operate on them.
g. A string that has no elements is called the empty string written l or Î. Strings are often constructed using summation notation.
h. Two strings S and T are concatenated, written ST, if the elements in S are followed immediately by the elements in T. Sn means that the string S has n elements; also called the length of S. T* creates a new set that includes the empty set and a bunch of new strings made up of elements from T. Each of these new strings is of varying length. We could write T* = { Î + T1 + T2 + T3 + …}. T+ is similar to T* except it does not include the empty set. The reversal of a string B, written BR, is the same elements but in the opposite order.
