MAT422: Sept 2012 – Jan 2013

Mathematical Logic & Proving Techniques

Class Schedule

Monday

• 1400-1550 – MAT422 (CSB2At, CSB3At, CSB4At, CSB4Bt) A108-TEC

Wednesday

• 1600-1650 – MAT422 (CSB2At, CSB3At, CSB4At, CSB4Bt) A214
• 1700-1750 – MAT422 (CSB2At, CSB3At) A214

Thursday

• 1500-1550 – MAT422 (CSB4At, CSB4Bt) F232

Contents

1. Set Theory
   • Sets and Subsets
   • Set Operations
   • Laws of Set Theory
   • Counting and Venn Diagrams
2. Logic
   • Propositions: primitive, compound, truth values
   • Logical connectives and truth tables; negation, conjunction, disjunction, implication, biconditional
   • Converse, contrapositive, inverse
   • Translating English statements into symbolic form
   • Tautology, contradiction
   • Logical equivalences
   • Laws of logic, principle of duality
   • Logical implication
   • Arguments – validity of arguments by using truth tables and rules of inference, invalidity of arguments by using counterexamples
   • Quantifiers – existential and universal quantifiers, logical connectives and negations, logical equivalences, logical implications
   • Nested Quantifiers
3. How to do proofs
   • Introduction
   • The Forward – Backward method
   • Definitions and Mathematical Terminology
   • The Construction Method
   • The Choose Method
   • Specialization Method
   • Negations
   • The Contradiction Method
   • The Contrapositive Method
   • Induction Method

Textbooks

1. Douglas Ralph P. Grimaldi, Discrete and Combinatorial Mathematics,  4th edition, Addison Wesley, 1999.
2. Daniel Solow, How to Read and Do Proofs, 4th edition. John Wiley & Sons, 2005.