Formula (mathematical logic)

From Wikipedia, the free encyclopedia

In mathematical logic, a formula is a formal syntactic object that expresses a proposition, except that the proposition may depend on the values of the free variables of the formula.

The exact definition of a formula depends on the particular development of formal logic in question, but a fairly typical one (specific to first-order logic) goes as follows: Formulas are defined relative to a particular language; that is, a collection of constant symbols, function symbols, 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

1. A variable,
2. A constant symbol, or
3. f(t₁,...,t_n), where f is an n-ary function symbol, and t₁,...,t_n are terms.

Finally, a formula is defined recursively as

1. t₁=t₂, where t₁ and t₂ are terms, or
2. R(t₁,...,t_n), where R is an n-ary relation symbol, and t₁,...,t_n are terms, or
3. (¬φ), where φ is a formula, or
4. (φ∧ψ), where φ and ψ are formulas, or
5. (∃x)(φ), where x is a variable and φ is a formula.

The first two cases are called atomic formulas.

[edit] See also

• WFF

[edit] References

Hinman, P. (2005). Fundamentals of Mathematical Logic. A K Peters. ISBN 1-568-81262-0.