FOL 10 · Beyond the Slides (GATE extras)
Not in the Neso Chapter 2 deck
Topics GATE uses that the slides skip. Learn after notes 01–09.
1. Free vs bound variables, scope
- A variable is bound if it’s inside the scope of a quantifier on that variable; otherwise it’s free.
- In : x is bound, y is free ⇒ this is not a proposition (truth depends on y).
- A formula with no free variables is a sentence (closed formula) and has a truth value.
- Scope: quantifiers bind tighter than every connective. means — the last x is free!
Same letter, different variables
In the two x’s are unrelated. It’s equivalent to .
2. Moving quantifiers past a formula A where x is NOT free
| Equivalence | Note |
|---|---|
| non-empty domain | |
| non-empty domain | |
| quantifier stays | |
| quantifier stays; non-empty domain | |
| ⚠️ quantifier flips | |
| ⚠️ quantifier flips; non-empty domain |
Why it flips in the antecedent
. Pulling the quantifier out of flips it (De Morgan). Also: .
Prenex normal form — all quantifiers at the front, e.g. . Get there with De Morgan + the table above (rename variables first if they clash).
3. Counting quantifiers (“exactly”, “at least”, “at most”, “only”)
| English | FOL |
|---|---|
| At least one | |
| At most one | |
| Exactly one () | |
| At least two | |
| Exactly two | |
| Only S are P | |
| S are the only P | |
| Everyone except c is P | (strict) or |
"At most one" is true when none exist. "Exactly one" = at least one ∧ at most one.
4. Valid, satisfiable, and finite domains
- Valid FOL formula: true in every interpretation (every non-empty domain, every meaning of the predicates).
- Satisfiable: true in some interpretation.
- To disprove validity: build a counter-model — usually a 2-element domain is enough.
- Over a finite domain : , — FOL reduces to propositional logic.
Counting interpretations (NAT-friendly)
Domain of size :
| Predicate | # of possible interpretations |
|---|---|
| unary | |
| binary | |
| k-ary |
For unary P on n elements: true in exactly 1 of them, in , in .
5. Empty domain convention
Standard FOL assumes the domain is non-empty. If a question allows an empty domain: is TRUE (vacuously), is FALSE — so fails there.
6. Theory crossover (TOC / complexity)
- Validity of FOL is undecidable (Church–Turing) but semi-decidable (valid formulas can be enumerated / proved).
- Propositional validity is decidable (co-NP-complete).
- Monadic FOL (only unary predicates) is decidable.
7. Higher-order quick check
“First order” = quantify over individuals only. “For every property P…” () is second-order — not allowed in FOL.
Prev ← FOL 09 Inference for Quantified Statements · Next → FOL 11 GATE PYQs