### Formula (mathematical logic)

In mathematical logic, a **well-formed formula**, shortly **wff**, often simply **formula**, is a word (i.e. a finite sequence of symbols from a given alphabet) which is part of a formal language.^{[1]} A formal language can be considered to be identical to the set containing all and only its formulas.

A formula is a syntactic formal object that can be informally given a semantic meaning.

## Contents

## Introduction

A key use of formulas is in propositional logic and predicate logics such as first-order logic. In those contexts, a formula is a string of symbols φ for which it makes sense to ask "is φ true?", once any free variables in φ have been instantiated. In formal logic, proofs can be represented by sequences of formulas with certain properties, and the final formula in the sequence is what is proven.

Although the term "formula" may be used for written marks (for instance, on a piece of paper or chalkboard), it is more precisely understood as the sequence being expressed, with the marks being a token instance of formula. It is not necessary for the existence of a formula that there be any actual tokens of it. A formal language may thus have an infinite number of formulas regardless whether each formula has a token instance. Moreover, a single formula may have more than one token instance, if it is written more than once.

Formulas are quite often interpreted as propositions (as, for instance, in propositional logic). However formulas are syntactic entities, and as such must be specified in a formal language without regard to any interpretation of them. An interpreted formula may be the name of something, an adjective, an adverb, a preposition, a phrase, a clause, an imperative sentence, a string of sentences, a string of names, etc.^{[broken citation]}. A formula may even turn out to be nonsense, if the symbols of the language are specified so that it does. Furthermore, a formula need not be given *any* interpretation.

## Propositional calculus

The formulas of propositional calculus, also called propositional formulas,^{[2]} are expressions such as $(A\; \backslash land\; (B\; \backslash lor\; C))$. Their definition begins with the arbitrary choice of a set *V* of propositional variables. The alphabet consists of the letters in *V* along with the symbols for the propositional connectives and parentheses "(" and ")", all of which are assumed to not be in *V*. The formulas will be certain expressions (that is, strings of symbols) over this alphabet.

The formulas are inductively defined as follows:

- Each propositional variable is, on its own, a formula.
- If φ is a formula, then $\backslash lnot$φ is a formula.
- If φ and ψ are formulas, and • is any binary connective, then ( φ • ψ) is a formula. Here • could be (but is not limited to) the usual operators ∨, ∧, →, or ↔.

This definition can also be written as a formal grammar in Backus–Naur form, provided the set of variables is finite:

::= p | q | r | s | t | u | ... (the arbitrary finite set of propositional variables)

Using this grammar, the sequence of symbols

- (((
*p*$\backslash rightarrow$*q*) $\backslash wedge$ (*r*$\backslash rightarrow$*s*)) $\backslash vee$ ($\backslash neg$*q*$\backslash wedge$ $\backslash neg$*s*))

is a formula, because it is grammatically correct. The sequence of symbols

- ((
*p*$\backslash rightarrow$*q*)$\backslash rightarrow$(*qq*))*p*))

is not a formula, because it does not conform to the grammar.

A complex formula may be difficult to read, owing to, for example, the proliferation of parentheses. To alleviate this last phenomenon, precedence rules (akin to the standard mathematical order of operations) are assumed among the operators, making some operators more binding than others. For example, assuming the precedence (from most binding to least binding) 1. $\backslash neg$ 2. $\backslash rightarrow$ 3. $\backslash wedge$ 4. $\backslash vee$. Then the formula

- (((
*p*$\backslash rightarrow$*q*) $\backslash wedge$ (*r*$\backslash rightarrow$*s*)) $\backslash vee$ ($\backslash neg$*q*$\backslash wedge$ $\backslash neg$*s*))

may be abbreviated as

*p*$\backslash rightarrow$*q*$\backslash wedge$*r*$\backslash rightarrow$*s*$\backslash vee$ $\backslash neg$*q*$\backslash wedge$ $\backslash neg$*s*

This is, however, only a convention used to simplify the written representation of a formula. If the precedence was assumed, for example, to be left-right associative, in following order: 1. $\backslash neg$ 2. $\backslash wedge$ 3. $\backslash vee$ 4. $\backslash rightarrow$, then the same formula above (without parentheses) would be rewritten as

- (
*p*$\backslash rightarrow$ (*q*$\backslash wedge$*r*)) $\backslash rightarrow$ (*s*$\backslash vee$ (($\backslash neg$*q*) $\backslash wedge$ ($\backslash neg$*s*)))

## Predicate logic

The definition of a formula in first-order logic $\backslash mathcal\{QS\}$ is relative to the signature of the theory at hand. This signature specifies the constant symbols, relation symbols, and function symbols of the theory at hand, along with the arities of the function and relation symbols.

The definition of a formula comes in several parts. First, the set of **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*_{1},...,*t*_{n}), where*f*is an*n*-ary function symbol, and*t*_{1},...,*t*_{n}are terms, is again a term.

The next step is to define the atomic formulas.

- If
*t*_{1}and*t*_{2}are terms then*t*_{1}=*t*_{2}is an atomic formula - If
*R*is an*n*-ary relation symbol, and*t*_{1},...,*t*_{n}are terms, then*R*(*t*_{1},...,*t*_{n}) 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:

- $\backslash neg\backslash phi$ is a formula when $\backslash \; \backslash phi$ is a formula
- $(\backslash phi\; \backslash land\; \backslash psi)$ and $(\backslash phi\; \backslash lor\; \backslash psi)$ are formulas when $\backslash \; \backslash phi$ and $\backslash \; \backslash psi$ are formulas;
- $\backslash exists\; x\backslash ,\; \backslash phi$ is a formula when $\backslash \; x$ is a variable and $\backslash \; \backslash phi$ is a formula;
- $\backslash forall\; x\backslash ,\; \backslash phi$ is a formula when $\backslash \; x$ is a variable and $\backslash \; \backslash phi$ is a formula (alternatively, $\backslash forall\; x\backslash ,\; \backslash phi$ could be defined as an abbreviation for $\backslash neg\backslash exists\; x\backslash ,\; \backslash neg\backslash phi$).

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

## Atomic and open formulas

An *atomic formula* is a formula that contains no logical connectives nor quantifiers, or equivalently a formula that has no strict subformulas.
The precise form of atomic formulas depends on the formal system under consideration; for propositional logic, for example, the atomic formulas are the propositional variables. For predicate logic, the atoms are predicate symbols together with their arguments, each argument being a term.

According to some terminology, an *open formula* is formed by combining atomic formulas using only logical connectives, to the exclusion of quantifiers.^{[3]} This has not to be confused with a formula which is not closed.

## Closed formulas

A *closed formula*, also *ground formula* or *sentence*, is a formula in which there are no free occurrences of any variable. If **A** is a formula of a first-order language in which the variables *v _{1}*, ...,

*v*have free occurrences, then

_{n}**A**preceded by $\backslash forall$

*v*... $\backslash forall$

_{1}*v*is a closure of

_{n}**A**.

## Properties applicable to formulas

- A formula
**A**in a language $\backslash mathcal\{Q\}$ is*valid*if it is true for every interpretation of $\backslash mathcal\{Q\}$. - A formula
**A**in a language $\backslash mathcal\{Q\}$ is*satisfiable*if it is true for some interpretation of $\backslash mathcal\{Q\}$. - A formula
**A**of the language of arithmetic is*decidable*if it represents a decidable set, i.e. if there is an effective method which, given a substitution of the free variables of**A**, says that either the resulting instance of**A**is provable or its negation is.

## Usage of the terminology

In earlier works on mathematical logic (e.g. by Church^{[4]}), formulas referred to any strings of symbols and among these strings, well-formed formulas were the strings that followed the formation rules of (correct) formulas.

Several authors simply say formula.^{[5]}^{[6]}^{[7]}^{[8]} Modern usages (especially in the context of computer science with mathematical software such as model checkers, automated theorem provers, interactive theorem provers) tend to retain of the notion of formula only the algebraic concept and to leave the question of well-formedness, i.e. of the concrete string representation of formulas (using this or that symbol for connectives and quantifiers, using this or that parenthesizing convention, using Polish or infix notation, etc.) as a mere notational problem.

However, the expression well-formed formulas can still be found in various works,^{[9]}^{[10]}^{[11]} these authors using the name well-formed formula without necessarily opposing it to the old sense of formula as arbitrary string of symbols so that it is no longer common in mathematical logic to refer to arbitrary strings of symbols in the old sense of formulas.

The expression "well-formed formulas" (WFF) also pervaded in popular culture. Indeed, *WFF* is part of an esoteric pun used in the name of the academic game "WFF 'N PROOF: The Game of Modern Logic," by Layman Allen,^{[12]} developed while he was at Yale Law School (he was later a professor at the University of Michigan). The suite of games is designed to teach the principles of symbolic logic to children (in Polish notation).^{[13]} Its name is an echo of *whiffenpoof*, a nonsense word used as a cheer at Yale University made popular in *The Whiffenpoof Song* and The Whiffenpoofs.^{[14]}

## See also

**
**

## Notes

## References

## External links

- Java quiz.
- Well-Formed Formula at ProvenMath
- WFF N PROOF game site