Well-formed formula

From Wikipedia, the free encyclopedia

[edit] Propositional calculus

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

Each propositional variable is, on its own, a formula.
If φ is a formula, then $\lnot \phi$ 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)

Using this grammar, 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. $\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).

[edit] 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, 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₁,...,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.

If t₁ and t₂ are terms then t₁=t₂ is an atomic formula
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:

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

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

[edit] Trivia

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

[edit] See also

[edit] Notes

^ 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.
^ Ehrenberg, Rachel (Spring 2002). "He's Positively Logical". Michigan Today (University of Michigan). http://www.umich.edu/~newsinfo/MT/02/Spr02/mt9s02.html. 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.

[edit] External links

Logic portal

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

[0] 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.

[1] Ehrenberg, Rachel (Spring 2002). "He's Positively Logical". Michigan Today (University of Michigan). http://www.umich.edu/~newsinfo/MT/02/Spr02/mt9s02.html. Retrieved on 2007-08-19.

[2] More technically, propositional logic using the Fitch-style calculus.

[3] 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.

[1]

[2]

[3]

[4]

Well-formed formula

From Wikipedia, the free encyclopedia

Contents

[edit] Propositional calculus

[edit] Predicate logic

[edit] Trivia

[edit] See also

[edit] Notes

[edit] External links

Views

Personal tools

Navigation

Search

Interaction

Toolbox

Languages