# Well-formed formula

In mathematical logic, propositional logic and predicate logic, a

**well-formed formula**, abbreviated

**WFF**or

**wff**, often simply

**formula**, is a finite sequence of symbols from a given alphabet that is part of a formal language. A formal language can be identified with the set of formulas in the language.

A formula is a syntactic object that can be given a semantic meaning by means of an interpretation. Two key uses of formulas are in propositional logic and predicate logic.

## Introduction

A key use of formulas is in propositional logic and predicate logic 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, it is more precisely understood as the sequence of symbols being expressed, with the marks being a token instance of formula. Thus the same formula may be written more than once, and a formula might in principle be so long that it cannot be written at all within the physical universe.

Formulas themselves are syntactic objects. They are given meanings by interpretations. For example, in a propositional formula, each propositional variable may be interpreted as a concrete proposition, so that the overall formula expresses a relationship between these propositions. A formula need not be interpreted, however, to be considered solely as a formula.

## Propositional calculus

The formulas of propositional calculus, also called propositional formulas, are expressions such as. 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 "", all of which are assumed to not be in

*V*. The formulas will be certain expressions over this alphabet.

The formulas are inductively defined as follows:

- Each propositional variable is, on its own, a formula.
- If φ is a formula, then ¬φ is a formula.
- If φ and ψ are formulas, and • is any binary connective, then is a formula. Here • could be the usual operators ∨, ∧, →, or ↔.

Using this grammar, the sequence of symbols

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

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 are assumed among the operators, making some operators more binding than others. For example, assuming the precedence 1. ¬ 2. → 3. ∧ 4. ∨. Then the formula

may be abbreviated as

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. ¬ 2. ∧ 3. ∨ 4. →, then the same formula above would be rewritten as

## Predicate logic

The definition of a formula in first-order logic is relative to the 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 arities of the function and predicate 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*, where*f*is an*n*-ary function symbol, and*t*_{1},...,*t*_{n}are terms, is again a term.

- If
*t*_{1}and*t*_{2}are terms then*t*_{1}=*t*_{2}is an atomic formula - If
*R*is an*n*-ary predicate symbol, and*t*_{1},...,*t*_{n}are terms, then*R*is an atomic formula

- is a formula when is a formula
- and are formulas when and are formulas;
- is a formula when is a variable and is a formula;
- is a formula when is a variable and is a formula.

*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. 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

*v*...

_{1}*v*is a closure of

_{n}**A**.

## Properties applicable to formulas

- A formula
**A**in a language is*valid*if it is true for every interpretation of. - A formula
**A**in a language is*satisfiable*if it is true for some interpretation of. - 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

Several authors simply say formula. Modern usages 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 as a mere notational problem.

While the expression

*well-formed formula*is still in use, these authors do not necessarily use it in contradistinction to the old sense of

*formula*, which is no longer common in mathematical logic.

The expression "well-formed formulas" also crept into popular culture.

*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, developed while he was at Yale Law School. The suite of games is designed to teach the principles of symbolic logic to children. 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.