1. Logic and Proofs

This chapter will set the foundations of mathematical reasoning and thinking to be used in this course and in all your subsequent math and computer science courses. Fundamental to all mathematics and computer science is logical arguments and proofs.

In this first chapter we will explore different logic systems, namely propositional logic and predicate logic. Within these systems we will see how to form formulas, logical arguments, inferences, and how to prove with certainty if some mathematical statement is correct or not.

The reason we need to study logic more formally is that English, and many natural languages, are very ambiguous.

Example

Is there a linguistic difference between “every student knows discrete math” and “any student knows discrete math”? There certainly is a mathematical difference! See Predicate Logic.

Throughout this chapter we will see how to use English to make precise mathemtical statements which are exact, unambiguous, and (hopefully) provably correct.

This chapter is organized into three parts.

• 1.1. Propositional Logic
  • 1.1.1. The Language of Propositions
    • Propositions
      • Constructing Propositions
    • Connectives
      • Negation
      • Conjunction
      • Disjunction
      • Implication
      • Biconditional
    • Propositional Formulas
    • Truth Tables
    • Implication, Inverse, Converse, and Contrapositive
  • 1.1.2. Applications
    • Translating English to Propositional Logic
    • Boolean Searches
    • Formal Specifications
    • Solving logic puzzles
  • 1.1.3. Logical Equivalences
    • Logically Equivalent
    • Equivalence proof
  • 1.1.4. Exercises
    • Basic Propositions
    • Applications
    • Logical Equivalences
• 1.2. Predicate Logic
  • 1.2.1. Predicates and Variables
    • Compound Expressions
  • 1.2.2. Quantifiers
    • Precedence of Quantifiers
    • Negating Quantifiers
    • Truth and Fallacy of Quantifiers
  • 1.2.3. Nested Quantifiers
    • Order of Quantifiers
    • Translating between English and Logic
    • Revisiting System Specifications
  • 1.2.4. Possible Pitfalls
    • Negating many Quantifiers
    • Quantifiers and Connectives
  • 1.2.5. Exercises
    • Predicates and Variables
    • Quantifiers
    • Nested Quantifiers
• 1.3. Proofs
  • 1.3.1. Theorems
    • Theorem Statements
    • Proving “obvious” theorems
  • 1.3.2. Direct Proofs
    • Proving biconditionals
  • 1.3.3. Indirect Proofs
    • Proof by Contrapositive
    • Proof by Contradiction
  • 1.3.4. Strategies to help with proofs
    • Finding errors in proofs
    • Proof by cases
    • Without loss of generality
    • Disproof by counterexample
  • 1.3.5. Even more types of proofs
    • Existence proofs
    • Uniqueness proofs
  • 1.3.6. Exercises