# 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, ...