Formula (mathematical logic)

In mathematical logic, a formula is a type of abstract object a token of which is a symbol or string of symbols which may be interpreted as any meaningful unit (i.e. a name, an adjective, a proposition, a phrase, a string of names, a string of phrases, etcetera) in a formal language. Two different strings of symbols may be tokens of the same formula. It is not necessary for the existence of a formula that there be any tokens of it. The exact definition of a formula depends on the particular formal language in question. [Hunter, Geoffrey, Metalogic: An Introduction to the Metatheory of Standard First-Order Logic]

A fairly typical definition (specific to first-order logic) goes as follows: Formulas are defined relative to a particular formal language and "relation symbols", where each of the function and relation symbols comes supplied with an arity that indicates the number of arguments it takes.

Then a term is defined recursively as
#A variable,
#A constant, or
#"f"("t"₁,...,"t"_"n"), where "f" is an "n"-ary function symbol, and "t"₁,...,"t"_"n" are terms.

An atomic formula is one of the form:
#"t"₁="t"₂, where "t"₁ and "t"₂ are terms, or
#"R"("t"₁,...,"t"_"n"), where "R" is an "n"-ary relation symbol, and "t"₁,...,"t"_"n" are terms.

Finally, the set of formulae is defined to be the smallest set containing the set of atomic formulae such that the following holds:
#$egphi$ is a formula when $phi$ is a formula;
#$(phi\; land\; psi)$ and $(phi\; lor\; psi)$ are formulae when $phi$ and $psi$ are formulae;
#$exists\; x,\; phi$ is a formula when "x" is a variable and $phi$ is a formula;
#$forall\; x,\; phi$ is a formula when $x$ is a variable and $phi$ is a formula (alternatively, $forall\; x,\; phi$ could be defined as an abbreviation for $egexists\; x,\; egphi$).

If a formula has no occurrences of $exists\; x$ or $forall\; x$, for any variable $x$, then it is called "quantifier-free". An "existential formula" is a string of existential quantification followed by a quantifier-free formula.

ee also

*Well-formed formula
*Theorem

References

*cite book | author = Hinman, P. | title = Fundamentals of Mathematical Logic | publisher = A K Peters | year = 2005 | id = ISBN 1-568-81262-0