Well-formed formula

From Wikipedia, the free encyclopedia

In logic, a well-formed formula (often abbreviated WFF, pronounced "wiff") is a string that is generated by a formal grammar. To say that a string $\ S$ is a WFF with respect to a given formal grammar $\ G$ is equivalent to saying that $\ S$ belongs to the language generated by $\ G$ , i.e. $S \in \boldsymbol{L}(G)$ .

In formal logic, proofs are 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.

1 Example
2 Trivia
3 Notes
4 See also
5 External links

The well-formed formulae of the propositional calculus $\mathcal{L}$ are defined by the following formal grammar, written in BNF:

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

::= | $\neg$ | ( $\wedge$ ) | ( $\vee$ ) | ( $\rightarrow$ ) | ( $\leftrightarrow$ )

The sequence of symbols

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

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

((p $\rightarrow$ q) $\rightarrow$ (qq))p))

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

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. $\neg$ 2. $\leftarrow$ , $\rightarrow$ 3. $\wedge$ 4. $\vee$ , the above correct expression may be written as:

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

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

WFF is part of an esoteric pun used in the name of "WFF 'N PROOF: The Game of Modern Logic," by Layman Allen^[1], 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)^[2]. Its name is a pun on whiffenpoof, a nonsense word used as a cheer at Yale University made popular in The Whiffenpoof Song and The Whiffenpoofs.^[3]

^ Ehrenberg, Rachel. "He's Positively Logical", Michigan Today, University of Michigan, Spring 2002. Retrieved on 2007-08-19.
^ More technically, propositional logic using the Fitch-style calculus.
^ 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.