Core Module 2: Proof Methods

To-Do Date: Jan 23 at 11:59pm

Reading: Chapter 1: What is a Proof? of MCS (our second textbook). Several notes:

  • MCS 1.1-1.2 are just a recap now, and we have already covered in class some basic inference rules such as Modus Ponens and Modus Tollens in MCS 1.4.1. Hopefully this eases you into the land of proofs.
  • Please be aware of the notational and stylistic inconsistencies between different textbooks. For two concrete examples:
    •  and ¬ are simply written as IMPLIES and NOT, respectively, in MCS 1.4.1. Note that this is not only because MCS introduces proofs before logic: the entire book doesn’t use logic operator symbols.
    • We write all premises (antecedents) of an inference rule on separated lines, whereas MCS writes them on a same line, delineated with commas.
      • On the other hand, AIDMA doesn’t even explicitly introduce inference rules. This is why we need multiple textbooks!
  • MCS Chapter 1 gives a nice overview of proof techniques. However, it does not really touch the question of what are proofs? Most of discrete math textbooks written for CS don’t bother. This is covered more in detail in our third textbook, MFADM in its Chapters 1 and 11. The reason that it is not used as our required reading is because it is more formal and (in my point of view) too overwhelming for this class.

To earn a satisfactory completion for CM2:

  • Get 80% or more questions correct in CM2: Proof Methods Prepare Quiz (note that there’s a 1hr 15min cooldown between consecutive attempts)
  • Get a completion on recitation work by either attending or submitting on Gradescope
  • Get a satisfactory or above on the Gradescope assignment
  • Get all 4 questions on the PrairieLearn homework (unlimited tries until LDoC)

OR

  • Get an excellent on all Gradescope assignment questions
  • Get all 4 questions on the PrairieLearn homework (unlimited tries until LDoC)

Leave a Reply

Your email address will not be published. Required fields are marked *