first-order logic
(2.9 hours to learn)
Summary
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.
Context
This concept has the prerequisites:
- propositional logic (First-order logic includes the propositional connectives.)
Goals
- 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)
-Free-
→ Coursera: Introduction to Logic (2014)
An introductory logic course geared towards computer scientists.
Location:
Lecture sequence "Relational logic"
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.
-Paid-
→ Artificial Intelligence: a Modern Approach
A textbook giving a broad overview of all of AI.
- Section 8.2, "Syntax and semantics of first-order logic," pages 245-253
- Section 8.3, "Using first-order logic," pages 253-260
Other notes:
- See Section 7.2 for a description of the Wumpus World.
→ The Language of First-Order Logic
An undergraduate logic textbook aimed at philosophers, with an educational software package.
- Chapter 5, "Introduction to quantification," up through Section 5.9, "Logical equivalences involving negation and quantifiers," pages 115-134
- Chapter 6, "Sentences with more than one quantifier," up through Section 6.2, "Mixed quantifiers," pages 154-159
→ A Mathematical Introduction to Logic
An undergraduate textbook in mathematical logic, with proofs.
- Section 2.0, "Preliminary remarks," pages 67-69
- Section 2.1, "First-order languages," pages 69-79
Supplemental resources (the following are optional, but you may find them useful)
-Free-
→ Notes on Logic (2013)
Lecture notes for a course on first order logic.
-Paid-
→ Knowledge Representation and Reasoning
An introductory textbook on knowledge representation.
Location:
Chapter 2, "The language of first-order logic," pages 15-30
See also
-No Additional Notes-