propositional proofs

(4.1 hours to learn)


A formal proof is an argument in a formal system where each step is justified by one of a precisely defined set of inference rules. Formal proofs are used as a model for studying mathematics itself, and are used in formal verification. One hopes a proof system is sound, in that each inference rule yields only true statements when its premises are true. A system is complete if all true statements expressible in some logical language can be proved within the system. Various proof systems have been defined for propositional logic which are both sound and complete.


This concept has the prerequisites:


  • understand the difference between formal and informal proofs
  • be able to prove tautologies in a formal propositional proof system
  • know what it means for a proof system to be sound and complete
  • prove the soundness of a propositional proof system
  • prove the completeness of a propositional proof system

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.
Coursera: Logic: Language and Information (2014)
An introductory logic course geared towards philosophers.
Authors: Greg Restall,Jen Davoren
Notes on Logic (2013)
Lecture notes for a course on first order logic.
Author: Henry Cohn


See also

-No Additional Notes-