1. What is First-Order Logic (FOL)

1.1 v.s. Propositional Logic

• "Eric is younger than Ronghui".
• How to present "Every student is younger than Ronghui"?
• The only way is to write this as an atomic fact.
• We need a richer logic to reason about "every", "younger", etc.

1.2 Introduction of First-Order Logic

First Order Logic := Propositional Logic + :

• Terms: syntax only, e.g., "Eric", "Ronghui", etc.
• Predicates: property of terms:
  • $S$(Eric): Eric is a student
  • $Y$(Eric, Ronghui): Eric is younger than Ronghui
• How to talk about every student？
  • FOL uses variables and universal quantification $\forall$
  • $\forall x. S(x)$: "all terms are students"
  • $\forall x. S(x) \rightarrow \cdots$: "for all terms who are students, ..."
• How to talk about the existence of at least one Instructor
  • FOL uses variables and existential quantification $\exists$
  • $\exists x. I(x) \wedge Y(\text{Eric}, x)$: "there exists a term which is an Instructor and Eric is younger than this instructor".

Example: Not all birds can fly

• $\neg\forall x.(B(x)\rightarrow F(x))$
• $\exists x.(B(x)\wedge \neg F(x))$

1.3 Syntax of FOL

Terms are strings:

$$ t::= x\ |\ c\ |\ f(t_1,...,t_n) $$

• variable: x, y, z, ...