Misplaced Pages

Revision as of 17:19, 3 February 2010

In the formal languages used in mathematical logic and computer science, a well-formed formula or simply formula (often abbreviated wff, pronounced "wiff" or "wuff") is an idea, abstraction or concept which is expressed using the symbols and formation rules (also called the formal grammar) of a particular formal language. To say that a string of symbols ${\displaystyle \ S}$ is a wff with respect to a given formal grammar ${\displaystyle \ G}$ is equivalent to saying that ${\displaystyle \ S}$ belongs to the language generated by ${\displaystyle \ G}$. A formal language can be identified with the set of its wffs.

Although the term "well-formed formula" is commonly used to refer to the written marks, for instance, on a piece of paper or chalkboard which are being used to express an idea; it is more precisely understood as the idea being expressed and the marks as a token instance of the well formed formula. Two different strings of marks may be tokens of the same well-formed formula. This is to say that there may be many different formulations of the same the idea.

It is not necessary for the existence of a well-formed formula that there be any actual tokens of it. Formal languages may have an infinite number of well-formed formula, regardless of whether there actually exist any token instances of them.

Well-formed formulas are quite often interpreted as propositions (as, for instance, in propositional logic). However wffs are syntactic entities, and as such must be specified in a formal language without regard to any interpretation of them. An interpreted well-formed 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, etcetera. A well-formed formula may even turn out to be nonsense, if the symbols of the language are specified so that it does. Furthermore, a well-formed formula need not be given any interpretation.

The set of well-formed formulas of a particular formal language is determined by a fiat of its creator, who simply lays down what things are to be wffs of the language. Usually this is done by specifying a set of symbols, and a set of formation rules.

A key use of wffs 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 wffs with certain properties, and the final wff in the sequence is what is proven. This final wff is called a theorem when it plays a significant role in the theory being developed, or a lemma when it plays an accessory role in the proof of a theorem.

Propositional calculus

The well-formed formulae of the propositional calculus ${\displaystyle {\mathcal {P}}}$ are recursively defined as follows:

• Each propositional variable is, on its own, a formula.
• If φ is a formula, then ${\displaystyle \lnot }$φ is a formula.
• If φ and ψ are formulas, and • is any binary connective, then ( φ • ψ) is a formula. Here • could be ∨, ∧, →, or ↔.

This definition can also be written as a formal grammar in Backus–Naur form:

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

<wff> ::= <alpha set> | ${\displaystyle \neg }$<wff> | (<wff>${\displaystyle \wedge }$<wff>) | (<wff>${\displaystyle \vee }$<wff>) | (<wff>${\displaystyle \rightarrow }$<wff>) | (<wff>${\displaystyle \leftrightarrow }$<wff>)

Using this grammar, the sequence of symbols

(((p ${\displaystyle \rightarrow }$ q) ${\displaystyle \wedge }$ (r ${\displaystyle \rightarrow }$ s)) ${\displaystyle \vee }$ (${\displaystyle \neg }$q ${\displaystyle \wedge }$ ${\displaystyle \neg }$s))

is a WFF because it is grammatically correct. The sequence of symbols

((p ${\displaystyle \rightarrow }$ q)${\displaystyle \rightarrow }$(qq))p))

is not a WFF, because it does not conform to the grammar of ${\displaystyle {\mathcal {P}}}$.

Note that sometimes WFF may become very hard 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 (from most binding to least binding) 1. ${\displaystyle \neg }$   2. ${\displaystyle \rightarrow }$  3. ${\displaystyle \wedge }$  4. ${\displaystyle \vee }$, the above correct expression may be written as:

p ${\displaystyle \rightarrow }$ q ${\displaystyle \wedge }$ r ${\displaystyle \rightarrow }$ s ${\displaystyle \vee }$ ${\displaystyle \neg }$q ${\displaystyle \wedge }$ ${\displaystyle \neg }$s

This is, however, only a convention used to simplify the written representation of a WFF (commonly used in programming languages).

Predicate logic

The definition of a formula in a first-order formal system ${\displaystyle {\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.

1. Any variable is a term.
2. Any constant symbol from the signature is a term
3. an expression of the form f(t₁,...,t_n), where f is an n-ary function symbol, and t₁,...,t_n are terms, is again a term.

The next step is to define the atomic formulas.

1. If t₁ and t₂ are terms then t₁=t₂ is an atomic formula
2. If R is an n-ary relation symbol, and t₁,...,t_n are terms, then R(t₁,...,t_n) is an atomic formula

Finally, the set of WFFs is defined to be the smallest set containing the set of atomic WFFs such that the following holds:

1. ${\displaystyle \neg \phi }$ is a WFF when ${\displaystyle \ \phi }$ is a WFF
2. ${\displaystyle (\phi \land \psi )}$ and ${\displaystyle (\phi \lor \psi )}$ are WFFs when ${\displaystyle \ \phi }$ and ${\displaystyle \ \psi }$ are WFFs;
3. ${\displaystyle \exists x\,\phi }$ is a WFF when x is a variable and ${\displaystyle \ \phi }$ is a WFF;
4. ${\displaystyle \forall x\,\phi }$ is a WFF when ${\displaystyle \ x}$ is a variable and ${\displaystyle \ \phi }$ is a WFF (alternatively, ${\displaystyle \forall x\,\phi }$ could be defined as an abbreviation for ${\displaystyle \neg \exists x\,\neg \phi }$).

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

Atomic and molecular formulas

An atomic formula is a formula that contains no logical connectives or equivalently a formula that has no strict subformulas.

A molecular formula is formed by combining atomic formulas using logical connectives.

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.

Closed and open formulas

A closed formula is a formula in which there are no free occurrences of any variable. A formula that is not closed is an open formula.

Valid formula

A formula A of a first order language ${\displaystyle {\mathcal {Q}}}$ is n-valid iff it is true for every interpretation of ${\displaystyle {\mathcal {Q}}}$ that has a domain of exactly n members.

Closure of a formula

If A is a formula of a first-order language in which the variables v₁, ... , v_n have free occurrences, then A preceded by ${\displaystyle \forall }$v₁ ... ${\displaystyle \forall }$v_n is a closure of A.

Satisfiable formula

A formula A of a first order language ${\displaystyle {\mathcal {Q}}}$ is satisfiable iff there is some interpretation ${\displaystyle {\mathcal {I}}}$ of ${\displaystyle {\mathcal {Q}}}$ for which A is satisfied (i.e. there is an interpretation ${\displaystyle {\mathcal {I}}}$ such that A is satisfied by at least one denumerable sequence of members of the domain of ${\displaystyle {\mathcal {I}}}$.)

Undecidable formula

A formula A is decidable in a first-order system ${\displaystyle {\mathcal {QS}}}$ iff either A or its negation is a theorem of ${\displaystyle {\mathcal {QS}}}$.

Wfs in popular culture

WFF is part of an esoteric pun used in the name of "WFF 'N PROOF: The Game of Modern Logic," by Layman Allen, 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). 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.

See also

• Ground expression

Notes

1. Godel, Escher, Bach: An Eternal Golden Braid, Douglas Hofstadter
2. Because non-well-formed formulas are rarely considered, some authors ignore them altogether. For these authors, "formula" and "well-formed formula" are synonyms. Other authors use the term "formula" for any string of symbols in the language; certain of these strings are then singled out as the well-formed formulas.
3. Ehrenberg, Rachel (Spring 2002). "He's Positively Logical". Michigan Today. University of Michigan. Retrieved 2007-08-19. {{cite news}}: Cite has empty unknown parameter: |coauthors= (help)
4. More technically, propositional logic using the Fitch-style calculus.
5. Layman E. Allen.Toward Autotelic Learning of Mathematical Logic by the WFF 'N PROOF Games, Monographs of the Society for Research in Child Development, Vol. 30, No. 1, Mathematical Learning: Report of a Conference Sponsored by the Committee on Intellective Processes Research of the Social Science Research Council (1965), pp. 29-41. Acknowledges the pun.

External links

• Well-Formed Formula for First Order Predicate Logic - includes a short Java quiz.
• Well-Formed Formula at ProvenMath
• WFF N PROOF game site

• Formal languages
• Syntactic entities
• Metalogic