M325K Syllabus

Discrete Mathematics

Prerequisite and degree relevance: M408D or M408L, with a grade of at least C-, or consent of instructor. This is a first course that emphasizes understanding and creating proofs. Therefore, it provides a transition from the problem-solving approach of calculus to the entirely rigorous approach of advanced courses such as M365C or M373K. The number of topics required for coverage has been kept modest so as to allow adequate time for students to develop theorem-proving skills. Topics may include: fundamentals of logic and set theory; functions and relations; basic properties of integers, and elementary number theory; recursion and induction; counting techniques and combinatorics; introductory graph theory.

Text: Faculty have a choice among three recommended texts. The preferred texts are Epp, Discrete Mathematics with Applications, 4th edition; Scheinerman, Mathematics: A Discrete Introduction, first edition. A text in use before these was Grimaldi, Discrete and Combinatorial Mathematics, current edition. Of the three, Grimaldi is the most directed towards applications in computer Science and Electrical Engineering. He also tends to integrate his applications directly into the flow of the text rather than discussing them separately.

Students in M325K are a mixture: some 25% Mathematics majors, 50% Electrical and Computer Engineering, and mixture of  majors such as Computer Science, Economics, etc.  Some of the math majors may have changed their majors from Business or Engineering or Computer Science opting to try Mathematics since they have accumulated more hours in math than in any other area.

The course should serve our majors as a transition from early computational courses, to the more problem-solving, abstract and rigorous courses they will encounter in the BA and BS degree programs. It serves the EE's as a required course in discrete techniques; they are expected to deal with proof techniques in a discrete context. The course is not intended to be all rigour, but proofs and the cognitive skills requisite to read, comprehend and do proofs are a major theme. Students are expected to become familiar with the language and techniques of proof (converse, if and only if, proof by contradiction, etc); they should also see detailed, rigorous proofs presented in class. More importantly, they need to develop the ability to read and understand proofs on their own, and they must begin doing proofs; this cannot be slighted.

Discrete mathematics offers a variety of contexts in which the student can begin to understand mathematical techniques and appreciate mathematical culture. Abstraction per se is not the goal; discrete mathematics offers very concrete computational contexts, and this can be exploited to develop a feeling for what it is that proofs, and proof techniques, say and do.

In the Epp text, one should include the topics below; this leaves time for the Instructor to cover additional topics of their choice. The instructor should focus on depth of understanding rather than breadth of coverage. However, subsequent courses will assume that students have seen induction and set theory in this course, so they must be covered.

Chapter 1 The Logic of Compund Statements (4 - 5 days)

  • 1.1 Logical Form and Logical equivalence
  • 1.2 Conditional Statements
  • 1.3 Valid and Invalid Arguments

Chapter 2 The logic of Quantified Statements (4 days)

  • 2.1 Introduction to Predicates and Quantified Statements I
  • 2.2 Introduction to Predicates and Quantified Statements II
  • 2.3 Statements Containing Multiple Quantifiers
  • 2.4 Arguments with Quantified Statements

Chapter 3 Elementary Number Theory and Statements of Proof (7 days, including 3.7)

  • 3.1 Direct Proof and Counterexample I: Introduction
  • 3.2 Direct Proof and Counterexample II: Rational Numbers
  • 3.3 Direct Proof and Counterexample III: Divisibility
  • 3.4 Direct Proof and Counterexample IV: Division Into Cases
  • 3.6 Indirect Argument: Contradiction and Contraposition

Chapter 4 Sequences and Mathematical Induction (6 days)

  • 4.1 Sequences
  • 4.2 Mathematical Induction I
  • 4.3 Mathematical Induction II
  • 4.4 Strong Mathematical Induction and Well Ordering

Chapter 5 Set Theory (3-4 days; more  if 5.4 is included)

  • 5.1 Basic Definitions of Set Theory
  • 5.2 Properties of Sets
  • 5.3 Disproofs, Algebraic Proofs, and Boolean Algebras
  • 5.4 Russel's Paradox and the Halting Problem

Responsible party: Kathy Davis and Shinko Harper, August 2008