MATH 2513 - Discrete Mathematical Structures, Section 002 - Spring 2007
MWF 8:30-9:20 a.m., 116 PHSC

Instructor: Nikola Petrov, 802 PHSC, (405)325-4316, npetrov AT math.ou.edu.

Office Hours: Mon 2:30-3:30 p.m., Wed 10:30-11:30 a.m., Thu 2:30-3:30 p.m., or by appointment.

The final exam will be on Monday, May 7, 10:30 a.m. - 12:30 p.m.

Prerequisite: MATH 2423 (Calculus and Analytic Geometry IV) or concurrent enrollment.

Course catalog description: A course for math majors or prospective math majors. Provides an introduction to discrete concepts such as finite sets and structures, and their properties and applications. Also exposes students to the basic procedures and styles of mathematical proof. Topics include basic set theory, functions, integers, symbolic logic, predicate calculus, induction, counting techniques, graphs and trees. Other topics from combinatorics, probability, relations, Boolean algebras or automata theory may be covered as time permits. (F, Sp, Su)

Text: Kenneth H. Rosen. Discrete Mathematics and Its Applications, 6th ed, McGraw-Hill, 2007, ISBN 978-0-07-288008-3. The course will cover parts of chapters 1-5 and 8.

Homework (solutions are deposited after the due date in the Chemistry-Mathematics Library, 207 PHSC):

• Homework 1, due Fri, Jan 26.
• Homework 2, due Fri, Feb 2.
• Homework 3, due Fri, Feb 9.
• Homework 4, due Fri, Feb 16.
• Homework 5, due Fri, Mar 2.
• Homework 6, due Fri, Mar 9.
• Homework 7, due Fri, Mar 16.
• Homework 8, due Fri, Apr 6.
• Homework 9, due Fri, Apr 13.
• Homework 10, due Fri, Apr 20.
• Homework 11, due Wed, Apr 25. Note the unusual due date!

Course content:

• Logic and proofs: propositional logic, propositional equivalences, predicates and quantifiers, inference, proof methods.
• Basic structures: sets, set operations, functions, sequences and summations.
• Integers: integers and division, primes and greatest common divisors.
• Induction and recursion: mathematical induction, recursive algorithms.
• Counting: basics of counting, pigeonhole principle, permutations, combinations, binomial coefficients, binomial theorem.
• Relations: relations and their properties, equivalence relations.

Content of the lectures:

• Lecture 1 (Wed, Jan 17): Propositional logic: proposition, propositional variables, truth value (Sec. 1.1).
• Lecture 2 (Fri, Jan 19): Propositional logic (cont.): negation ⌉p, conjunction p∧q, disjunction p∨q, exclusive or p⊕q; conditional statement (implication) p→q (p hypothesis, antecedent, premise; q conclusion, consequence), expressing p→q with words; converse q→p, contrapositive (⌉q)→(⌉p), and inverse (⌉p)→(⌉q) of the implication p→q; equivalent propositions, equivalence of a statement p→q and its contrapositive; biconditional statement (bi-implication) p↔q (Sec. 1.1).
• Lecture 3 (Mon, Jan 22): Propositional logic (cont.): truth tables of compound propositions, precedence of logical operators, translating English sentence into logical statements, logical puzzles ("knights and knaves puzzle"), logic and bit operations, bitwise operations between bit strings (Sec. 1.1).
  Propositional equivalences: tautology T, contradiction F, contingency, logical equivalence of propositions; laws governing logical propositions: (negation, De Morgan's, commutative, distributive, associative, absorption, identity, domination, idempotent, double negation (Sec. 1.2).
• Lecture 4 (Wed, Jan 24): Predicates and quantifiers: universal, existential, and uniqueness quantifiers, logical equivalence involving quantifiers, negating quantified expressions (pages 31, 34-36, 39-43 of Sec. 1.3).
  Nested quantifiers: examples of nested quantifiers (pages 50-53 of Sec. 1.4).
• Lecture 5 (Fri, Jan 26): Nested quantifiers (cont.): examples of nested quantifiers and their negations (pages 54-58 of Sec. 1.4).
  Introduction to proofs: terminology: axiom (postulate), theorem, proposition, lemma, corollary, conjecture, proof; direct proof, proof by contraposition, examples (pages 75-78 of Sec. 1.6).
• Lecture 6 (Mon, Jan 29): Introduction to proofs (cont.): vacuous and trivial proofs, rational and irrational numbers, proof that 2^1/2 is irrational; proofs by contradiction: proof that log₂7 is irrational by using that p≡(⌉p→F), proof that if 3n+2 is odd then n is odd by using that (p→q)≡[(p∧⌉q)→F]; proofs of equivalence: (p↔q)≡[(p→q)∧(q→p)], generalization: p₁↔p₂↔...↔p_n is equivalent to (p₁→p₂)∧(p₂→p₃)∧...∧(p_n→p₁) (pages 79-82 of Sec. 1.6).
• Lecture 7 (Wed, Jan 31): Introduction to proofs (cont.): counterexamples, common mistakes in proofs, circular reasoning (pages 83-85 of Sec. 1.6).
  Proof methods and strategy: exhaustive proofs and proofs by cases, examples (pages 86-90 of Sec. 1.7).
• Lecture 8 (Fri, Feb 2): Proof methods and strategy (cont.): existence proofs - constructive and non-constructive, examples; uniqueness proofs (pages 91-95 of Sec. 1.7).
• Lecture 9 (Mon, Feb 5): Sets: sets and their elements (members), a∈A, a∉A; sets of real numbers R, integers Z={...-2,-1,0,1,2,...}, natural numbers N={1,2,3,...}, rational numbers Q={m/n:m∈Z∧n∈N}; sets and subsets, equal sets, Venn diagrams; empty set ∅, Theorem 1 (that ∅⊆S and S⊆S for any set S) - first try to do the proof of the theorem yourself, and then look in the book (pages 111-115 of Sec. 2.1).
• Lecture 10 (Wed, Feb 7): Sets (cont.): proper subsets A⊂B, finite and infinite sets, cardinality |S| of a finite set S, power set P(S) of a set S, ordered pairs (a,b), ordered triples (a,b,c), ordered n-tuples (a₁,a₂,...,a_n), cartesian product A×B, cartesian product of n sets: A₁×A₂×...×A_n, using set notations with quantifiers, truth sets of quantifiers (pages 115-119 of Sec. 2.1).
  Set operations: union A∪B and intersection A∩B of sets, disjoint sets, Venn diagrams (pages 121-122 of Sec. 2.2).
• Lecture 11 (Fri, Feb 9): Set operations (cont.): difference of sets A-B, universal set U, complement A^c=U-A of the set A, set identities (you have to know all of them, and to remember the names of at least the commutative, associative, distributive, and De Morgan's laws), examples, membership tables (pages 123-126 of Sec. 2.2).
• Lecture 12 (Mon, Feb 12): Set operations (cont.): symmetric difference of sets A⊕B=(A-B)∪(B-A), examples, number of elements in the power set of a finite set: |P(A)|=2^|A| (if |A|<∞).
  Functions: function f:A→B, its domain A, codomain B, range ran(f)=f(A) (page 133 of Sec 2.3).
• Lecture 13 (Wed, Feb 14): Functions (cont.): adding and multiplying functions with values in R: if f₁:A→R and f₂:A→R, then (f₁+f₂):A→R and (f₁⋅f₂):A→R are defined by (f₁+f₂)(x)=f₁(x)+f(x), (f₁⋅f₂)(x)=f₁(x)⋅f(x) (pages 134-135 of Sec. 2.3).
• Lecture 14 (Fri, Feb 16): Functions (cont.): injective (one-to-one), surjective (onto), and bijective functions, increasing and decreasing functions, strictly increasing and strictly decreasing functions, inverse functions (pages 136-139 of Sec. 2.3).
• Lecture 15 (Mon, Feb 19): Hour exam 1.
• Lecture 16 (Wed, Feb 21): Functions (cont.): composition of functions, identity function, graphs of functions (pages 140-142 of Sec. 2.3).
  Sequences and summations: sequences, geometric and arithmetic progression, summation and product notations, sum of a geometric progression, double sums (pages 149-157 of Sec. 2.4).
• Lecture 17 (Fri, Feb 23): Sequences and summations: sum of a geometric series, proof of the formula ∑_n∈Nnr^n-1=1/(1-r)² for |r|<1, cardinality, countable and uncountable sets, proofs that Z and Q are countable, Cantor's proof that (0,1) and R are uncountable (pages 157-160 of Sec. 2.4).
• Lecture 18 (Mon, Feb 26): Integers and division: a|b, a factor and a multiple of an integer, simple theorems about divisibility, the division algorithm: a=dq+r, divisor d, quotient q=adivd, remainder r=amodd, modular arithmetic, (pages 200-204 of Sec. 3.4).
• Lecture 19 (Wed, Feb 28): Integers and division (cont.): simple theorems about modular arithmetic; applications of congruences: hashing functions, pseudorandom generators (pages 205-208 of Sec. 3.4).
• Lecture 20 (Fri, Mar 2): Primes and greatest common divisors: prime and composite numbers, the Fundamental Theorem of Arithmetic, existence of a prime divisor of n no greater than n^1/2, the infinitude or primes, Mersenne primes, the Prime Number Theorem (pages 210-213 of Sec. 3.5).
• Lecture 21 (Mon, Mar 5): Primes and greatest common divisors (cont.): greatest common divisors and least common multiples (pages 215-217 of Sec. 3.5).
  Integers and algorithms: representation of numbers in decimal, hexadecimal, octal, and binary system; Euclidean algorithm for finding gcd(a,b) (pages 219-222 and 227-229 of Sec. 3.6).
• Lecture 22 (Wed, Mar 7): Mathematical induction: induction, examples (pages 263-272 of Sec. 4.1).
• Lecture 23 (Fri, Mar 9): Mathematical induction (cont.): induction - more examples (pages 273-275 of Sec. 4.1).
• Lecture 24 (Mon, Mar 12): Recursive definitions: recursively defined functions - definition and examples, Fibonacci numbers f_n, ratios of consecutive Fibonacci numbers r_n=f_n/f_n+1, limit of r_n as n→∞, golden mean, partial fraction expansions (pages 294-297 of Sec. 4.3).
• Lecture 25 (Wed, Mar 14): The basics of counting: product rule, examples 1-10 (pages 335-338 of Sec. 5.1).
• Lecture 26 (Fri, Mar 16): The basics of counting (cont.): sum rule, inclusion-exclusion principle, examples (pages 338-343 of Sec. 5.1; example 16 is optional).
• Lecture 27 (Mon, Mar 26): The basics of counting (cont.): tree diagrams (pages 343-344 of Sec. 5.1).
  The pigeonhole principle: the pigeonhole principle and the generalized pigeonhole principle, applications (pages 347-349 of Sec. 5.2).
  Permutations and combinations: r-permutations, number of r-permutations of n distinct objects P(n,r)=n!/(n-r)!, particular case: P(n,n)=n!, examples of application (pages 355-357 of Sec. 5.3).
• Lecture 28 (Wed, Mar 28): Hour exam 2.
• Lecture 29 (Fri, Mar 30): Permutations and combinations (cont.): r-combinations of n distinct objects C(n,r)=n!/[r!(n-r)!], binomial coefficients, elementary identitity C(n,r)=C(n,n-r) and its combinatorial proof (pages 357-360 of Sec. 5.3).
  Binomial coefficients: the Binomial Theorem, combinatorial proof of the Binomial Theorem, elementary applications (pages 363-364 of Sec. 5.4).
• Lecture 30 (Mon, Apr 2): Binomial coefficients: more applicaitons of the Binomial Theorem, Pascal's identity (with a combinatorial proof) and Pascal's triangle (pages 365-367 of Sec. 5.4).
• Lecture 31 (Wed, Apr 4): Binomial coefficients (cont.): Vandermonde identity (Theorem 2), corollary, other combinatorial identities - Theorem 4, Exercise 33 (number of itineraries on a rectangular grid) (pages 367-370 of Sec. 5.4).
• Lecture 32 (Fri, Apr 6): Generalized permutations and combinations: permutations with repetition, combinations with repetition (pages 370-372 of Sec. 5.5).
• Lecture 33 (Mon, Apr 9): Generalized permutations and combinations (cont.): combinations with repetition, applications (number of integer solutions of linear equations), permutations with indistinguishable objects (pages 372-376 of Sec. 5.5).
• Lecture 34 (Wed, Apr 11): Generalized permutations and combinations (cont.): distributing objects in boxes: distinguishable objects into distinguishable boxes (same as the MISSISSIPPI problem), indistinguishable objects into distinguishable boxes (same as the bills in boxes problem); examples; Exercise 5.5/10 on pages 379-380 (pages 376-380 of Sec. 5.5).
• Lecture 35 (Fri, Apr 13): Generalized permutations and combinations (cont.): more examples (Sec. 5.5).
• Lecture 36 (Mon, Apr 16): Relations and their properties: n-tuples, pairs, triples, Cartesian products; definition of a relation, examples, functions as relations (pages 219-520 of Sec. 8.1).
• Lecture 37 (Wed, Apr 18): Relations and their properties (cont.): relations on a set, reflexive, symmetric, antisymmetric, transitive relations, examples (pages 521-525 of Sec. 8.1).
• Lecture 38 (Fri, Apr 20): Relations and their properties (cont.): combining relations, composite of two relations, recursive definition of powers Rⁿ of a relation R, necessary and sufficient condition for transitivity in terms of powers of R (pages 525-527 of Sec. 8.1).
• Lecture 39 (Mon, Apr 23): Equivalence relations: equivalence relations, examples, equivalence classes (pages 555-558 of Sec. 8.5).
• Lecture 40 (Wed, Apr 25): Equivalence relations (cont.): equivalence classes and partitions, examples (pages 559-562 of Sec. 8.5).
• Lecture 41 (Fri, Apr 27): Hour Exam 3.
• Lecture 42 (Mon, Apr 30): Solving linear recurrence relations: solving linear homogeneous recurrence relations with constant coefficients in the case of distinct roots of the characteristic equation (Theorem 1) - examples (pages 460-463 of Sec. 7.2).
• Lecture 43 (Wed, May 2): Recurrence relations: definition, Fibonacci sequence, counting the bit strings of length n that do not have two consecutive zeros (pages 449-455 of Sec. 7.1, especially examples 4 and 6).
• Lecture 44 (Fri, May 4): Catalan numbers: Catalan numbers article on Wikipedia, Example 8 on page 456, generating functions (Section 7.4), Exercise 7.4/41 on page 498 (solved on page S-46 of the book).

Attendance: You are required to attend class on those days when an examination is being given; attendance during other class periods is also strongly encouraged. You are fully responsible for the material covered in each class, whether or not you attend. Make-ups for missed exams will be given only if there is a compelling reason for the absence, which I know about beforehand and can document independently of your testimony (for example, via a note or phone call from a doctor or a parent). You should come to class on time; if you miss a quiz because you came late, you won't be able to make up for it.

Homework: It is absolutely essential to solve a large number of problems on a regular basis! Homework assignments will be given regularly throughout the semester and will be posted on this web-site. Each homework will consist of several problems, of which some pseudo-randomly chosen problems will be graded. Your lowest homework grade will be dropped. All homework should be written on a 8.5"×11" paper with your name clearly written, and should be stapled. All hand-in assignments must be submitted in class on the due date. No late homework will be accepted!

You are encouraged to discuss the homework problems with other students. However, you have to write your solutions clearly and in your own words - this is the only way to achieve real understanding! It is advisable that you first write a draft of the solutions and then copy them neatly. Please write the problems in the same order in which they are given in the assignment.

Shortly after a homework assignment's due date, solutions to the problems from that assignment will be placed on restricted reserve in the Chemistry-Mathematics Library in 207 PHSC.

Quizzes: Short pop-quizzes will be given in class at random times; your lowest quiz grade will be dropped. Often the quizzes will use material that has been covered very recently (even in the previous lecture), so you have to make every effort to keep up with the material and to study the corresponding sections from the book right after they have been covered in class.

Grading: Your grade will be determined by your performance on the following coursework:

• three in-class exams, 50 minutes each (each midterm contributes 15% to your overall grade);
• homework (15% of your overall grade; the lowest homework grade will be dropped);
• pop-quizzes (10% of your overall grade; the lowest quiz grade will be dropped);
• final exam (30% of your overall grade).

Academic calendar for Spring 2007.

Policy on W/I Grades : Through February 23, you can withdraw from the course with an automatic W. In addition, it is my policy to give any student a W grade, regardless of his/her performance in the course, through the extended drop period that ends on May 4. However, after April 2, you can only drop via petition to the Dean of your college. Such petitions are not often granted. Furthermore, even if the petition is granted, I will give you a grade of "Withdrawn Failing" if you are indeed failing at the time of your petition.

The grade of I (Incomplete) is not intended to serve as a benign substitute for the grade of F. I only give the I grade if a student has completed the majority of the work in the course (for example everything except the final exam), the coursework cannot be completed because of compelling and verifiable problems beyond the student's control, and the student expresses a clear intention of making up the missed work as soon as possible.

Academic Misconduct: All cases of suspected academic misconduct will be referred to the Dean of the College of Arts and Sciences for prosecution under the University's Academic Misconduct Code. The penalties can be quite severe. Don't do it! For more details on the University's policies concerning academic misconduct see http://www.ou.edu/provost/integrity/.

Students With Disabilities: The University of Oklahoma is committed to providing reasonable accommodation for all students with disabilities. Students with disabilities who require accommodations in this course are requested to speak with the instructor as early in the semester as possible. Students with disabilities must be registered with the Office of Disability Services prior to receiving accommodations in this course. The Office of Disability Services is located in Goddard Health Center, Suite 166: phone 405-325-3852 or TDD (only) 405-325-4173.

Use of calculators and technology: Because of the nature of the course, calculators are not needed (and will not be allowed during the exams).

Good to know:

• The Greek_alphabet.