propositional logic

(2.8 hours to learn)


Propositional logic is a logical formalism where the variables correspond to atomic sentences which are either true or false. Formulas are constructed using the connectives AND, OR, NOT, and IMPLIES. The semantics can be defined in terms of "truth tables," or equivalently boolean functions.


-this concept has no prerequisites-


  • understand the meanings of the propositional connectives AND, OR, NOT, and IMPLIES
  • be able to evaluate the truth value of a propositional formula given the truth values of the variables
  • be aware of ways in which IMPLIES does not correspond to our intuitive notions of implication
  • be able to manipulate propositional formulas (e.g. with distributive laws, de Morgan’s laws)
  • be able to define mathematically: a truth assignment, whether a formula is satisfied
  • define what it means for one set of formulas to tautologically imply another

Core resources (read/watch one of the following)


Coursera: Introduction to Logic (2014)
An introductory logic course geared towards computer scientists.
Author: Michael Genesereth
Other notes:
  • Click on "Preview" to see the videos.
Notes on Logic (2013)
Lecture notes for a course on first order logic.
Author: Henry Cohn
Coursera: Logic: Language and Information (2014)
An introductory logic course geared towards philosophers.
Authors: Greg Restall,Jen Davoren


See also

-No Additional Notes-