Logic and Computation
CS 2800 Fall 2014

College of Computer and Information Science
Northeastern University

Lectures, Notes, and textbook pointers

On this page we post the Notes accompanying the lectures of the class, and point to the relevant chapters in the (optional) textbook. Note the following:

  1. Read the material as soon as it is posted, even before it is covered in class. It is ok to not understand every aspect before we cover it.
  2. Read all of the Notes material (even though we will not cover everything in class).
Working with the recommended textbook will give you an alternative perspective on the course material and thus broaden your horizon. If you decide to do so:
  1. Go at least through the (sub-)chapters in the order specified.
  2. "[advanced]" means that the material is essentially also covered in class, but notation and terminology differ slightly from what we do in class. Read such sub-chapters with a flexible mind, and do not hesitate to use Piazza or approach the instructor for questions.
  3. Feel free to also read sub-chapters not mentioned below. The comment above on notation and terminology applies especially to those chapters.

Lecture Topic
Lecture Notes    
Textbook chapters + comments
Review: Propositional Logic
 propositional-logic.pdf
 Chapter 1:
  • 1.1 (except: right-associativity of =>, which we do not assume)
  • 1.3
  • 1.4.1
  • [advanced] 1.2 (introduces our "logical validities" as a proof system called "natural deduction")
The ACL2s
Programming Language
 acl2.pdf
 (not covered in the textbook)
The ACL2s Logic: Definitions and Termination
 defns-termination.pdf
 Chapter 4:
  • 4.4: "Proof calculus for total correctness": this means a calculus that can prove termination. Ignore what the text says on "Hoare triples" (we did not cover this), but read the strategy for proving termination on page 293, and the Collatz example on page 295.
Equational Reasoning
 equational-reasoning.pdf
 (not covered in the textbook)
Induction
 induction.pdf
 Chapter 1:
  • 1.2.5: proof by contradiction
  • 1.4.2: mathematical induction

Read especially about "structural induction" and how it relates to induction over the natural numbers.