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

EquivalenceNote
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”)

EnglishFOL
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