D. J. Bernstein
More mathematics

MCS 261, Discrete Mathematics, Fall 2005

22 August 2005

The lecture was scheduled for 13:00-13:50 MWF in 118 Douglas Hall but will move to 427 SEO starting Friday 26 August.

Call number for registration: 12339. Prerequisites: Grade of C or better in Math 180, and grade of C or better in MCS 260 (or CS 102).

My office hours will be 15:10-16:00 Monday, 16:10-17:00 Monday, 17:10-18:00 Monday in 410 SEO.

Course grades will be based entirely on examinations. Homework assignments will consist of textbook readings (see below) and practice exams.

The textbook for this course is changing. The old textbook was ``Discrete mathematics with graph theory'' by Goodaire and Parmenter. There are two new textbooks: ``A short course in discrete mathematics'' by Bender and Williamson, and ``Mathematics for algorithm and systems analysis'' by Bender and Williamson.

The new textbooks are available for free online from http://www.math.ucsd.edu/~ebender. Here are the chapters of ``A short course in discrete mathematics'':

  1. Table of Contents
  2. Unit SF: Sets and Functions
  3. Unit BF: Boolean Functions and Computer Arithmetic
  4. Unit Lo: Logic
  5. Unit NT: Number Theory and Cryptography
  6. Unit IS: Induction, Sequences and Series
  7. Solutions
  8. Index
Here are the chapters of ``Mathematics for algorithm and systems analysis'':
  1. Table of Contents
  2. Unit CL: Basic Counting and Listing
  3. Unit Fn: Functions
  4. Unit DT: Decision Trees and Recursion
  5. Unit GT: Basic Concepts in Graph Theory
  6. Solutions
  7. Index
I want to make sure that each concept covered is thoroughly understood, so I plan to focus on the following sections:
  1. SF Section 1: sets
  2. SF Section 2: functions
  3. BF Section 1: Boolean functions
  4. Lo Section 1: propositional logic
  5. Lo Section 2: predicate logic
  6. NT Section 1: basic facts about numbers
  7. NT Section 2: cryptography
  8. IS Section 1: induction
  9. CL Section 1: counting lists with repetitions
  10. CL Section 2: counting lists without repetition
  11. CL Section 3: counting sets
  12. Fn Section 1: more on functions
  13. Fn Section 2: permutations
  14. DT Section 4: recursive equations
  15. GT Section 1: graphs
You should start reading SF Section 1 immediately. (You may find it helpful to also read CL Section 1; the contrast between sets and lists is helpful in clarifying the concept of a set.) As the course progresses, you should continue reading to keep up with the lectures.

Today's class material: The brace notation for a set with specified elements: e.g., {3,5} is the set that has 3 as an element, has 5 as an element, and doesn't have anything else as an element. A set can have more than two elements: e.g., {3,5,7}. A set can have one element: e.g., {3}. A set can have zero elements: {}. A set can have infinitely many elements: e.g., {0,1,2,3,...}, the set of natural numbers. Warning: some people define ``natural number'' to exclude 0. Equality of sets: S = T means that S and T have the same elements. In other words: if S = T then every element of S is an element of T and every element of T is an element of S; if every element of S is an element of T, and every element of T is an element of S, then S = T. Examples: {3,5} = {5,3}; {3,5} = {3,5,3,3}; {3,5} != {3,5,7}. Sets don't care about order or repetition. In contrast, multisets care about repetition, and lists (strings) care about both order and repetition. S <= T (with curved <) means that S is a subset of T, i.e., that every element of S is an element of T. S < T (with curved <) means that S is a proper subset of T, i.e., that S <= T and S != T. Warning: some people write S < T to mean that S is a subset of T, and write S <!= T to mean that S is a proper subset of T; beware the ambiguity of S < T.

25 August 2005

Yesterday's class material: Subset examples: {2,7,1} <= {2,7,1,8}; {2} <= {2,7,1,8}; {1,2,7,8} <= {2,7,1,8}; {} <= {2,7,1,8}. Proper-subset examples: {2,3+4,1} < {2,7,1,8}; {1,2,7,8} !< {2,7,1,8}; {} < {2,7,1,8}. A statement saying ``each element of {} is ...'' is true (``vacuously true''). ``Iff'' means if and only if. Set union: if x is in S union T then If x is not in S union T then x is not in S and x is not in T. Set intersection: if x is in S intersect T then x is in S and x is in T. If x is not in S intersect T then Examples of subset-union-intersection facts: S intersect (S union T) = S. S <= S union T. S intersect T <= S. {} <= S. S <= S. Distributive law: S intersect (T union X) = (S intersect T) union (S intersect X). Proof of the distributive law. Picture of a Venn diagram.

28 August 2005

Class material from Friday: View of set definitions as proof strategies. To prove that S is a subset of T: list elements of S and prove, for each element x of S, that x is an element of T. To prove that S is not a subset of T: find an element x of S that's not an element of T, and prove it! Example: strategy to prove that S intersect T is a subset of S. To prove that two sets S, T are equal: prove that S is a subset of T, and prove that T is a subset of S. To list the elements of S union T, list the elements of S, and list the elements of T. To prove that x is in S union T, prove that x is in S, or prove that x is in T. To prove that x is not in S union T, prove that x is not in S, and prove that x is not in T. Example: proof that S is a subset of S union T. How to list the elements of S intersect T. How to prove that x is in S intersect T. How to prove that x is not in S intersect T. Set difference: x is in S - T means that x is in S and x is not in T. Example: {3,1,4} - {2,7,1} = {3,4}. To prove that x is not in S - T, prove that x is not in S, or prove that x is in T.

Practice exam, due Friday 2 September: For each of the following five statements, use the definitions of union, intersection, etc. to prove the statement for all sets, or disprove the statement by writing down particular sets where the statement is not true. (1) (A union B) intersect C = A union (B intersect C). (2) If A is a subset of B and C is a subset of U-B then A intersect C = {}. (3) (A - B) union C = A - (B union C). (4) (A intersect B) intersect C = A intersect (B intersect C). (5) (A xor B) intersect C = A xor (B intersect C). Here S xor T means (S-T) union (T-S).

Note that a statement about sets A,B,C,... is implicitly a statement about _all_ sets A,B,C,..., unless it explicitly says something different. To prove the statement, you have to prove it for all possible choices of A,B,C,...; to disprove the statement, you have to disprove it for at least one choice of A,B,C,...

Sample question: ``Prove or disprove that, if A is a subset of B, and B is a subset of C, then A is a subset of C.'' Overly short answer, not spelling out enough details: ``Proof: Each element of A is an element of C. Therefore, A is a subset of C.'' More detailed answer: ``Proof: Each element of A is an element of C. Specifically, if x is an element of A, then x is an element of B, since A is a subset of B; so x is also an element of C, since B is a subset of C. Therefore, A is a subset of C.''

Sample question: ``Prove or disprove that (A union B) union B = A.'' Adequately detailed answer: ``Disproof: Define A = {1} and B = {2}. Then A union B = {1,2}, so (A union B) union B = {1,2} != {1} = A.''

31 August 2005

Class material from Monday: Venn diagrams, and special Venn diagrams.

Today's class material: Statement involving set names, union, intersection, minus, equal, subset is true for all sets if and only if it's true for special Venn diagram. Example: Venn proof that S intersect T is a subset of T. Example: Venn proof that (X-S) intersect (X-T) = X - (S union T). For comparison, non-Venn proof. Picture of non-Venn proof. Using Venn diagrams to disprove ``T - S is a subset of S,'' i.e., to disprove ``for every set S: for every set T: T - S is a subset of S.'' Example where T - S is a subset of S. Set product (Cartesian product): S x T is the set of strings (a,b) where a is in S and b is in T. Example: {5,6} x {7,8,9} = {(5,7),(5,8),(5,9),(6,7),(6,8),(6,9)}. Example: {1,2} x {2,1} = {(1,1),(1,2),(2,1),(2,2)}. (1,2) is not (2,1).

9 September 2005

Oops, I left out a chapter from my copy of the book! Here are all the chapters of ``A short course in discrete mathematics'':
  1. Table of Contents
  2. Unit BF: Boolean Functions and Computer Arithmetic
  3. Unit Lo: Logic
  4. Unit NT: Number Theory and Cryptography
  5. Unit SF: Sets and Functions
  6. Unit EO: Equivalence and Order
  7. Unit IS: Induction, Sequences and Series
  8. Solutions
  9. Index

Class material from last Friday: Two pairs (a,b) and (c,d) are equal if and only if their first coordinates are equal and their second coordinates are equal: i.e., (a,b)=(c,d) iff a=c and b=d. Some names for the pieces a,b of a pair (a,b): components of a vector; components of a pair; components of an ordered pair; elements of an array; symbols in a string; etc. Review of Cartesian product. A relation from S to T is a subset of S x T. Examples. Functions from S to T. Steps to prove that f is a function from S to T: prove that each element of f is a pair; prove that, for each pair, the first component is in S; prove that, for each pair, the second component is in T; prove that, for each element x of S, there's a pair (x,something) in f; prove that, for each element x of S, there aren't two pairs (x,y) and (x,z) in f except when y=z. Examples. A function f is surjective (``onto T'') iff, for each element y of T, there's a pair (something,y) in f. A function f is injective (``into''; ``one-to-one'') iff, for each element y of T, there aren't two pairs (x,y) and (z,y) in f except when x=z. A function is bijective iff it is both surjective and injective. Examples.

Practice exam due Friday 9 September: 1. Define f: \N -> \N by f(x) = x^2 + x; i.e., consider the function from \N={0,1,2,3,...} to \N that has elements (x,x^2+x). Is f one-to-one? Is f onto? 2. Give an example of an onto function from {1,2,3,4} to {3,4,5}. Give an example of an injective function from {3,4,5} to {1,3,5,7,9}. 3. Find a bijection from {0,1,2,3,4,...} to {...,-2,-1,0,1,2,...}. 4. Prove: If {{a},{a,b}} = {{c},{c,d}} then a = c and b = d. (Side note: Some people define the pair (a,b) as {{a},{a,b}}.)

Wednesday's class material: View of function from S to T as a rule specifying, for each element of S, an element of T. Warning: two different-sounding rules can be the same function. Functions f, g are equal iff they are equal as sets. These three functions from {1,2,3} to \N = {0,1,2,...} are equal to each other: the function {(1,2),(2,4),(3,6)}; the rule specifying, for each element x of {1,2,3}, the number 2x; the rule specifying, for each element x of {1,2,3}, the number sqrt(3x^2 + x(x-1+1)). View of function from S to T as a table. Warning: reordering table doesn't change function. View of function from S to T as a graph. Can also graph relations. The notation f(x) for the unique y such that (x,y) is in f. ``Argument'' is function input. ``Value'' is function output. f:S->T means that f is a function from S to T. Example: ``Define f:{1,2,3}->\N by f(x)=x^2'' is a standard way to define the function {(1,1),(2,4),(3,9)}. Another example: ``Define f:\N->\N by f(x)=x/2 if x is even, 3x+1 if x is odd.'' This example is surjective, not injective, not bijective. Composition of functions: if f is a function from S to T, and g is a function from T to U, then gf is the function from S to U such that (gf)(x) = g(f(x)) for each x in S. Examples.

Today's class material: Let f be a function from S to T. The domain of f is the set of first components of elements of f; i.e., the domain of f is S. The image of f is the set of second components of elements of f; this is a subset of T. The codomain of f is T; beware that codomain, like surjectivity, does not depend on f alone. The range of f is the codomain of f; beware that some people instead define range as image. The inverse image set of y under f is the set of x's such that (x,y) is in f. ``Inverse image'' means ``inverse image set.'' The coimage of f is the set of nonempty inverse image sets under f. Example: the function {(1,5),(2,4)} from {1,2} to {4,5}; domain, image, codomain, range, various inverse images; coimage is {{2},{1}}. Example: the function {(1,6),(2,5),(3,5),(4,6)} from {1,2,3,4} to {5,6,7,8}; domain, image, codomain, range, various inverse images; coimage is {{1,4},{2,3}}. The coimage of f is a partition of S. Definition of partition. Example: All partitions of {1,2,3,4}. All partitions of S are coimages of various functions. ``Equivalence relations'': can convert a partition into a relation from S to S; can recognize from ``transitivity'' etc. whether a relation from S to S is obtained from a partition.

Practice exam due Friday 16 September: 1. What is the domain of the function f:\N->\N defined by f(x) = x/2 for x even and f(x) = 3x+1 for x odd? What is the codomain? What is the coimage? 2. Simplify the Boolean function (p v q) v ((q v (~r)) ^ (p v r)) as far as possible; i.e., write the shortest formula for it. 3. Write a truth table for (p ^ (p => q)) => q. Here p=>q is defined as q v (~p). 4. Simplify the Boolean function ((p ^ (~q)) => r) => (p => (q v r)) as far as possible.

The first exam will be Monday 19 September. It will cover sets, functions, and Boolean functions.

18 September 2005

Class material from Monday: The Boolean function ^ (``and'') is the function from {0,1}x{0,1} to {0,1} defined as follows: ^(0,0) = 0; ^(0,1) = 0; ^(1,0) = 0; ^(1,1) = 1. Repeated in standard notation: 0^0 = 0; 0^1 = 0; 1^0 = 0; 1^1 = 1. The Boolean function v (``or'') is the function from {0,1}x{0,1} to {0,1} defined as follows: 0v0 = 0; 0v1 = 1; 1v0 = 1; 1v1 = 1. The Boolean function ~ (``not'') is the function from {0,1} to {0,1} defined as follows: ~0 = 1; ~1 = 0. The Boolean function xor is the function from {0,1}x{0,1} to {0,1} defined as follows: 0 xor 0 = 0; 0 xor 1 = 1; 1 xor 0 = 1; 1 xor 1 = 0. In mathematics, ``a or b'' means ``a or b or both,'' while ``either a or b'' means ``either a or b but not both.'' The Boolean function => (``implies'') is the function from {0,1}x{0,1} to {0,1} defined as follows: 0=>0 = 1; 0=>1 = 1; 1=>0 = 0; 1=>1 = 1. Building more complicated functions; examples of truth tables.

Wednesday and Friday were review. Good luck on the exam!

16 October 2005

Exam questions from 19 September 2005:
  1. Disprove the following statement: ``(A intersect B) union C = A intersect (B union C).'' (Here's an example that fails to disprove the statement: A={1,2,3}, B={1,2}, C={2,3}.)
  2. Find a bijection from {5,6,7} to {10,12,14,12,10}.
  3. Write a truth table for the Boolean function (p ^ (q ^ r)) v ((~p) ^ (~r)).
  4. Consider the function f:{1,2,3}->{3,4,5} defined by f(1)=5, f(2)=4, and f(3)=5. Is f injective? Is f surjective? What is the image of f? What is the coimage of f?
  5. Prove the following statement: ``For each set T, for each subset S of T, there is a function g:T->{0,1} with coimage {S,T-S}.''
Answers:
  1. Define A = {}, B = {}, and C = {1}. Then A intersect B = {}, so (A intersect B) union C = {1}; but B union C = {1}, so A intersect (B union C) = {}; so (A intersect B) union C != A intersect (B union C).
  2. Define f = {(5,14),(6,10),(7,12)}. Then f is a set of pairs; each first component of f is in {5,6,7}; and each second component of f is in {10,12,14,12,10}. (At this point we know that f is a relation from {5,6,7} to {10,12,14,12,10}.) Each element of {5,6,7} appears as a first component of f. Each element of {5,6,7} appears no more than once as a first component of f. (At this point we know that f is a function from {5,6,7} to {10,12,14,12,10}.) Each element of {10,12,14,12,10} appears as a second component of f. (At this point we know that f is a surjective function from {5,6,7} to {10,12,14,12,10}.) Each element of {10,12,14,12,10} appears no more than once as a second component of f. Therefore f is a bijection from {5,6,7} to {10,12,14,12,10}.
  3. Table:
    pqr q^r p^(q^r) ~p ~r (~p)^(~r) (p^(q^r))v((~p)^(~r))
    000001111
    001001000
    010001111
    011101000
    100000100
    101000000
    110000100
    111110001
  4. The image of f is the set of values of f, namely {4,5}. This does not contain the element 3 of {3,4,5}, so f is not surjective; f is also not injective, since f(1) = f(3). The coimage of f is {{1,3},{2}}.
  5. The problem is incorrect as stated. If S={} then S cannot be an element of a coimage; if S=T then T-S={} so T-S cannot be an element of a coimage. The problem should have stated ``for each nonempty proper subset S of T.'' With this modification, here is the proof. Define g as follows: if x is in S then g(x)=0; otherwise g(x)=1. The inverse image of 0 under g is the nonempty set S. The inverse image of 1 under g is the nonempty set T-S. The coimage of g is the set of nonempty inverse images under g, namely {S,T-S}.

The remaining classes in September were devoted to mathematical logic, the study of mathematical truth and mathematical proof. Mathematical truth assigns specific meanings to ``and'' (^); ``or'' (v); ``not'' (~); ``implies'' (=>); ``for all'' (A, upside down); and ``there exists'' (E, backwards). Mathematical proof is a standardized method of guaranteeing mathematical truth: specifically, a proof starts from a set of ``hypotheses,'' and produces various ``proven'' statements, guaranteeing that each proven statement is true if all the hypotheses are true. Mathematicians long ago worked out complete rules for building a mathematical proof at a level that a computer could verify:

One can add additional rules for handling ``and'' and ``or'' and ``there exists'' (all of which can be replaced by combinations of ``not'' and ``implies'' and ``for all''); for handling sets; and for handling definitions of new objects (such as functions).

You have to know the definition of mathematical truth. You don't have to know the low-level rules for building a mathematical proof, but you need to have the practical ability to start from hypotheses and write down proven statements, without accidentally writing down unproven statements.

Practice exam due Friday 7 October:

  1. Write down the negation of the statement ``Every integer is prime''; i.e., simplify the statement ``It is not true that each integer is prime.''
  2. Negate the statement ``For each positive real number x there is an integer n such that n > x.''
  3. Is the following logic mathematically valid? ``Assumptions: If I am wearing a purple coat and I am not wearing blue shoes, then I am wearing red socks. If I am wearing blue shoes or red socks, then I am wearing a green hat. I am wearing a purple coat. Conclusion: I am wearing a green hat.''
  4. It is true that ``Ex: ((x in Z) ^ Ey : ((y in Z) ^ (x^2 + y^2 = 10))).'' Explain.
  5. It is not true that ``Ex: ((x in Z) ^ Ay : ((y in Z) => (x^2 + y^2 = 10))).'' Explain.
  6. Is it true that ``Ec: ((c in Z) ^ (Ex: ((x in Z) ^ Ay : ((y in Z) => (xy = c)))))''? Explain.

Practice exam due Friday 21 October:

  1. Define a_0 = 1 and a_{n+1} = 3 a_n + 2^{n+1} for n >= 0. Prove that a_n = 3^{n+1} - 2^{n+1} for all n >= 0. Here ^ means superscript (in this case exponentiation), not the Boolean ``and'' function.
  2. Prove that sum_{i=1}^n i^2 = n(n+1)(2n+1)/6 for all n >= 0.
  3. Define f_0 = 1, f_1 = 2, f_2 = 4, and f_k = f_{k-1} + 2f_{k-2} + f_{k-3} for all integers k >= 3. Prove that f_n <= 3^n for all integers n >= 0.
  4. Solve a_n = 6a_{n-1} - 9a_{n-2} with a_0 = 1, a_1 = 3.

2 November 2005

Practice exam due Friday 14 October:
  1. What is gcd{-392,273}?
  2. Prove: if 2^k-1 is prime then k is prime.
  3. Prove: if 2^k+1 is prime then k is a power of 2.
  4. Disprove: if n is an integer and n^k+1 is prime then k is a power of 2.
  5. Prove: gcd{2^10000 - 1,2^14000 - 1} = 2^2000 - 1.

Practice exam due Friday 4 November (on combinatorics, covered on the final exam, not covered on the second exam):

  1. Prove that Z and 3Z+1 have the same cardinality.
  2. Prove that Z and N have the same cardinality.
  3. Prove that there are exactly 2^10 subsets of {1,2,3,4,5,6,7,8,9,10}.
  4. A license-plate number consists of three letters followed by three digits. The letters are required to be different. How many possible license-plate numbers are there?

The second exam will be Monday 7 November. It will have 5 questions covering logic, number theory, and induction. Bring your ID to show to the proctor.

Practice exam due Friday 18 November:

  1. Bob is going to choose a selection of 12 chocolates. There are 25 varieties and he can have as many as he wants of each kind. How many ways can he make the selection?
  2. A committee of 7 is being picked from the House of Representatives. At most one of the 7 members will be one of the 53 members of the California delegation (the 52 active members, plus whoever wins the runoff election to replace Chris Cox). The others will be from the remaining 382 representatives. How many ways are there to pick the committee?
  3. Sally invites Alice, Bob, Charlie, Donna, and Eve over for dinner. Charlie and Donna refuse to sit together. How many ways are there for Sally, Alice, Bob, Charlie, Donna, and Eve to sit around Sally's circular table?
  4. In how many ways can one organize the letters a,b,c,d,e,f,g,h,i into a line where a is next to b and c is not next to d?
You may use factorials and binomial coefficients in your answers without calculating their values as integers.

23 November 2005

Practice exam due Wednesday 30 November:
  1. How many ways are there to distribute at most 8 lollipops to 4 different children?
  2. How many ways are there to put 10 red balls and 10 blue balls into 30 different boxes?
  3. How many ways are there to put 10 red balls and 10 blue balls into 30 different boxes, at most one ball in each box?
  4. Prove: If ten points are chosen inside a 3x3 square then at least two of the points lie within distance s of each other, where s is the square root of 2.
  5. Prove: If S is a size-51 subset of {1,2,3,...,100} then S has two different elements x,y such that x divides y.

The final exam will be Monday 5 December. It will start at the usual class time, in the usual room, but will last for 110 minutes. It will have 10 questions. Fewer than half of the questions will be on material covered by the first two exams.