first-order logic

(2.9 hours to learn)


First-order logic refers to a class of formal languages which include the propositional connectives, quantifiers, functions, and predicates. It underlies many automated reasoning systems and can be used to define various formalizations of mathematics, such as Peano arithmetic, and Zermelo-Frankl set theory.


This concept has the prerequisites:


  • know the meanings of existential and universal quantifiers
  • be able to manipulate expressions containing quantifiers
  • be able to express simple statements of arithmetic and set theory in FOL
  • be able to determine if a variable occurs free in an expression
  • understand the semantics of FOL at an informal level

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:
  • This actually covers relational logic, but at the level of this concept node, most of the ideas are the same. See the bonus lecture "First order logic (a very brief introduction)" for an explanation of the differences.
  • Click on "Preview" to see the videos.


Supplemental resources (the following are optional, but you may find them useful)


Notes on Logic (2013)
Lecture notes for a course on first order logic.
Author: Henry Cohn


See also

-No Additional Notes-