First-Order Predicate Logic — Syntax — Beginner-Friendly Notes

1. Why We Need FOL (First-Order Logic)

Propositional logic cannot say "all birds fly" without listing each bird. FOL adds objects, relations, variables, quantifiers — so one sentence covers infinitely many individuals.

Propositional = facts. FOL = objects + relations + quantification.

2. Syntax — Vocabulary

• Constants: specific objects — $a, b, John, 3$ (lowercase start).
• Variables: placeholders — $x, y, z$.
• Predicates: relations/properties — $Bird(x)$, $Flies(x)$, $Likes(John, Mary)$, $Greater(x,y)$ — capitalised, arity matters.
• Functions: map objects to objects — $Father(John)$, $Successor(3)$ — not boolean, returns an object.
• Terms: constants, variables, or function applied to terms — e.g., $Father(John)$, $x$.

3. Atomic Sentences

Predicate applied to terms: $Bird(Tweety)$, $Likes(x, y)$, $Greater(Successor(2), 3)$

4. Complex Sentences (build recursively)

If $P, Q$ are sentences and $x$ variable:

• Connectives as before: $
  eg P$,$P \land Q$,$P \lor Q$,$P \Rightarrow Q$,$P \Leftrightarrow Q$
• Quantified: $\forall x\ P(x)$, $\exists x\ P(x)$
• Equality: $x = y$ (optional)

Examples:

• "Every bird flies": $\forall x\ (Bird(x) \Rightarrow Flies(x))$
• "There is a red bird": $\exists x\ (Bird(x) \land Red(x))$
• "John likes everyone": $\forall y\ Likes(John, y)$
• "Someone likes John": $\exists x\ Likes(x, John)$

5. Precedence & Well-Formed Formulas

Quantifiers bind tightest: $\forall x\ Bird(x) \Rightarrow Flies(x)$ means $\forall x\ (Bird(x) \Rightarrow Flies(x))$. Use parentheses to be safe.

6. Why Syntax Matters for AI

• Allows general rules (one rule for all birds) and relations (family, spatial).
• Next topics add quantifiers (meaning) and inference (how to reason).

7. One-Line Summary

First-order logic builds sentences from constants, variables, predicate and function terms with connectives and quantifiers, enabling general statements about objects and relations.

8. Quick Self-Check

1. Is $Likes(John)$ well-formed if Likes expects 2 args?
2. Write "All cats are mammals" in FOL.