Introduction to Logic and Proof

Revised: November, 2009 (Sloan Despeaux)

Course Description

An introduction to the principles of logic and the methods of proof necessary for the successful study of mathematics.

Prerequisites & Notes

PREQ: or COREQ: MATH 140 or MATH 153.
3 Credit Hours.

Objectives

1. To introduce students to principles of logic and methods of proof used in mathematical reasoning.
2. To provide students with practice in communicating mathematical ideas and arguments, both verbally and orally.

Text

Mathematical Proofs: A Transition to Advanced Mathematics (2nd Edition) by Gary Chartrand, Albert D. Polimeni, and Ping Zhang (Addison Wesley)

Grading Procedure

Grading procedures and factors influencing course grade are left to the discretion of individual instructors, subject to general university policy.

Attendance Policy

Attendance policy is left to the discretion of individual instructors, subject to general university policy.

Course Outline

1. Sets
   1. Describing a Set
   2. Subsets
   3. Set Operations
   4. Indexed Collections of Sets
   5. Partitions of Sets
   6. Cartesian Products of Sets
2. Logic
   1. Statements
   2. The Negation of a Statement
   3. The Disjunction and Conjunction of Statements
   4. The Implication
   5. More on Implications
   6. The Biconditional
   7. Tautologies and Contradictions
   8. Logical Equivalence
   9. Some Fundamental Properties of Logical Equivalence
   10. Quantified Statements
   11. Characterizations of Statements
3. Direct Proof and Proof by Contrapositive
   1. Trivial and Vacuous Proofs
   2. Direct Proofs
   3. Proof by Contrapositive
   4. Proof by Cases
   5. Proof Evaluations
4. More on Direct Proof and Proof by Contrapositive
   1. Proofs Involving Divisibility of Integers
   2. Proofs Involving Congruence of Integers
   3. Proofs Involving Real Numbers
   4. Proofs Involving Sets
   5. Fundamental Properties of Set Operations
   6. Proofs Involving Cartesian Products of Sets
5. Existence and Proof by Contradiction
   1. Counterexamples
   2. Proof by Contradiction
   3. A Review of Three Proof Techniques
   4. Existence Proofs
   5. Disproving Existence Statements
6. Mathematical Induction
   1. The Principle of Mathematical Induction
   2. A More General Principle of Mathematical Induction
   3. Proof by Minimum Counterexample
   4. The Strong Principle of Mathematical Induction
7. Prove or Disprove
   1. Conjectures in Mathematics
   2. Revisiting Quantified Statements
   3. Testing Statements
8. Equivalence Relations
   1. Relations
   2. Properties of Relations
   3. Equivalence Relations
   4. Properties of Equivalence Classes
   5. Congruence Modulo n
   6. The Integers Modulo n
9. Functions
   1. The Definition of Function
   2. The Set of All Functions from A to B
   3. One-to-one and Onto Functions
   4. Bijective Functions
   5. Composition of Functions
   6. Inverse Functions
   7. Permutations