Well-formed formula

Well-formed formula

In mathematical logic, a well-formed formula (often abbreviated WFF, pronounced "wiff" or "wuff") is a symbol or string of symbols (a formula) that is generated by the formal grammar of a formal language. 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 oldsymbol{L}(G). A formal language can be identified with the set of its WFFs.

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.

Example

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): ::= | eg | (wedge) | (vee) | ( ightarrow) | (leftrightarrow)

The sequence of symbols

:((("p" ightarrow "q") wedge ("r" ightarrow "s")) vee ( eg"q" wedge eg"s"))

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

:(("p" ightarrow "q") ightarrow("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. eg 2. ightarrow 3. wedge 4. vee, the above correct expression may be written as:

:"p" ightarrow "q" wedge "r" ightarrow "s" vee eg"q" wedge eg"s"

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

Trivia

"WFF" is part of an esoteric pun used in the name of "WFF 'N PROOF: The Game of Modern Logic," by Layman Allen [cite news | first=Rachel | last=Ehrenberg | coauthors= | title=He's Positively Logical | date=Spring 2002 | publisher=University of Michigan | url=http://www.umich.edu/~newsinfo/MT/02/Spr02/mt9s02.html | work=Michigan Today | pages= | accessdate=2007-08-19 | language = ] , 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) [More technically, propositional logic using the Fitch-style calculus.] . 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 [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.] .

ee also

* Atomic formula
* Ground expression
*Woodhull Freedom Foundation & Federation (acronym WFF)

Notes

External links

* [http://www.cs.odu.edu/~toida/nerzic/content/logic/pred_logic/construction/wff_intro.html Well-Formed Formula for First Order Predicate Logic] - includes a short Java quiz.
* [http://www.apronus.com/provenmath/formulas.htm Well-Formed Formula at ProvenMath]
* [http://wffnproof.com/ WFF N PROOF game site]


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • well-formed formula — At its most general a formula may be thought of in logical theory as any string of symbols from the lexicon of the theory. A well formed formula (abbreviated as wff) is one that obeys the formation rules of the system. Since other strings are… …   Philosophy dictionary

  • well-formed formula — noun A statement that is expressed in a valid, syntactically correct, manner. This program works correctly on all well formed formulas but it blows up on illegal input …   Wiktionary

  • well-formed — formula …   Philosophy dictionary

  • well-formed formulae — well formed formula …   Philosophy dictionary

  • Well-formed — may refer to:* Well formed element, an element in webpage design * Well formed formula, a string that is generated by a formal grammar in logic * Well formed outcome, a Neuro Linguistic Programming conceptee also* Well formedness …   Wikipedia

  • Formula (mathematical logic) — In mathematical logic, a formula is a type of abstract object a token of which is a symbol or string of symbols which may be interpreted as any meaningful unit (i.e. a name, an adjective, a proposition, a phrase, a string of names, a string of… …   Wikipedia

  • Formula SAE — is a student design competition organized by the Society of Automotive Engineers. The competition was started back in 1978 and was originally called [http://www.sae.org/students/fsaehistory.pdf SAE Mini Indy] .The concept behind Formula SAE is… …   Wikipedia

  • Atomic formula — In mathematical logic, an atomic formula (also known simply as an atom) is a formula with no deeper propositional structure, that is, a formula that contains no logical connectives or equivalently a formula that has no strict subformulas. Atoms… …   Wikipedia

  • Formula One — F1 redirects here. For other uses, see F1 (disambiguation). For other uses, see Formula One (disambiguation). Formula One Category Single seater Country or region Worldwide …   Wikipedia

  • Formula SimRacing — Infobox motorsport championship logo = pixels = 200px caption = The official Formula SimRacing logo, created for International SimRacing Club. category = Computer sim racing single seaters country/region = International inaugural2 = 2001 drivers …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”