Quiz. First Order Logic - Syntax [000w]

bound: if it is within the scope of a quantifier that binds it. E.g., in \(\forall x.\ P(x, y)\), the variable \(x\) is bound.
free: if it is not bound by any quantifier within the formula. E.g., in \(\forall x.\ P(x, y)\), the variable \(y\) is free.

Which of the following are syntactically valid formulas in first order logic?

Solution.

\(f(x)\): Invalid, as \(f\) is a function symbol and cannot stand alone as a formula.
\(p(x)\): Valid, as \(p\) is a relation symbol applied to the term \(x\).
\(p(f(x))\): Valid, as \(f(x)\) is a term and \(p\) is a relation symbol applied to that term.
\(p(p(x))\): Invalid, as \(p(x)\) is a formula, not a term, and cannot be an argument to \(p\).
\(p(f(f(x)))\): Valid, as \(f(x)\) is a term, and applying \(f\) again yields another term, which can be an argument to \(p\).