# 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)
$$