Editing Well-formed formula (section)

==Predicate logic==
The definition of a formula in [[first-order logic]] <math>\mathcal{QS}</math> is relative to the [[Signature (mathematical logic)|signature]] of the theory at hand. This signature specifies the constant symbols, predicate symbols, and function symbols of the theory at hand, along with the [[Arity|arities]] of the function and predicate symbols.

The definition of a formula comes in several parts. First, the set of '''[[Term (logic)|terms]]''' is defined recursively. Terms, informally, are expressions that represent objects from the [[domain of discourse]].
#Any variable is a term.
#Any constant symbol from the signature is a term
#an expression of the form ''f''(''t''<sub>1</sub>,...,''t''<sub>''n''</sub>), where ''f'' is an ''n''-ary function symbol, and ''t''<sub>1</sub>,...,''t''<sub>''n''</sub> are terms, is again a term.

The next step is to define the [[atomic formula]]s.
#If ''t''<sub>1</sub> and ''t''<sub>2</sub> are terms then ''t''<sub>1</sub>=''t''<sub>2</sub> is an atomic formula
#If ''R'' is an ''n''-ary predicate symbol, and ''t''<sub>1</sub>,...,''t''<sub>''n''</sub> are terms, then ''R''(''t''<sub>1</sub>,...,''t''<sub>''n''</sub>) is an atomic formula

Finally, the set of formulas is defined to be the smallest set containing the set of atomic formulas such that the following holds:
#<math>\neg\phi</math> is a formula when <math>\phi</math> is a formula
#<math>(\phi \land \psi)</math> and <math>(\phi \lor \psi)</math> are formulas when <math>\phi</math> and <math>\psi</math> are formulas;
#<math>\exists x\, \phi</math> is a formula when <math>x</math> is a variable and <math>\phi</math> is a formula;
#<math>\forall x\, \phi</math> is a formula when <math>x</math> is a variable and <math>\phi</math> is a formula (alternatively, <math>\forall x\, \phi</math> could be defined as an abbreviation for <math>\neg\exists x\, \neg\phi</math>).

If a formula has no occurrences of <math>\exists x</math> or <math>\forall x</math>, for any variable <math>x</math>, then it is called {{Anchor|Quantifier-free formula}}'''quantifier-free'''. An ''existential formula'' is a formula starting with a sequence of [[existential quantification]] followed by a quantifier-free formula.