Part of a series on 
Formal languages 

In mathematical logic, propositional logic and predicate logic, a wellformed 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.^{[1]}
The abbreviation wff is pronounced "woof", or sometimes "wiff", "weff", or "whiff". ^{[12]}
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.
YouTube Encyclopedic

1/5Views:18 2205 98921 35340 79519 746

Well Formed Formula  WFF  MFCS  Propositional Logic  Discrete Mathematics

Logic  Well Formed Formula (Wff)

Well formed formulas

Well Formed Formula  WFF  DMS  MFCS  Propositional Logic  Discrete Mathematics

Propositional Logic Syntax and Structure
Transcription
Introduction
A key use of formulas is in propositional logic and predicate logic such as firstorder 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 (for instance, on a piece of paper or chalkboard), it is more precisely understood as the sequence of symbols being expressed, with the marks being a token instance of formula. This distinction between the vague notion of "property" and the inductivelydefined notion of wellformed formula has roots in Weyl's 1910 paper "Uber die Definitionen der mathematischen Grundbegriffe".^{[13]} 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,^{[14]} 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 "(" and ")", all of which are assumed to not be in V. The formulas will be certain expressions (that is, strings of symbols) 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 (but is not limited to) the usual operators ∨, ∧, →, or ↔.
This definition can also be written as a formal grammar in Backus–Naur form, provided the set of variables is finite:
<alpha set> ::= p  q  r  s  t  u  ... (the arbitrary finite set of propositional variables)
<form> ::= <alpha set>  ¬<form>  (<form>∧<form>)  (<form>∨<form>)  (<form>→<form>)  (<form>↔<form>)
Using this grammar, the sequence of symbols
 (((p → q) ∧ (r → s)) ∨ (¬q ∧ ¬s))
is a formula, because it is grammatically correct. The sequence of symbols
 ((p → q)→(qq))p))
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 (akin to the standard mathematical order of operations) are assumed among the operators, making some operators more binding than others. For example, assuming the precedence (from most binding to least binding) 1. ¬ 2. → 3. ∧ 4. ∨. Then the formula
 (((p → q) ∧ (r → s)) ∨ (¬q ∧ ¬s))
may be abbreviated as
 p → q ∧ r → s ∨ ¬q ∧ ¬s
This is, however, only a convention used to simplify the written representation of a formula. If the precedence was assumed, for example, to be leftright associative, in following order: 1. ¬ 2. ∧ 3. ∨ 4. →, then the same formula above (without parentheses) would be rewritten as
 (p → (q ∧ r)) → (s ∨ (¬q ∧ ¬s))
Predicate logic
The definition of a formula in firstorder 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(t_{1},...,t_{n}), where f is an nary function symbol, and t_{1},...,t_{n} are terms, is again a term.
The next step is to define the atomic formulas.
 If t_{1} and t_{2} are terms then t_{1}=t_{2} is an atomic formula
 If R is an nary predicate symbol, and t_{1},...,t_{n} are terms, then R(t_{1},...,t_{n}) is an atomic formula
Finally, the set of formulas is defined to be the smallest set containing the set of atomic formulas such that the following holds:
 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 (alternatively, could be defined as an abbreviation for ).
If a formula has no occurrences of or , for any variable , then it is called quantifierfree. An existential formula is a formula starting with a sequence of existential quantification followed by a quantifierfree 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.^{[15]} This is 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 firstorder language in which the variables v_{1}, …, v_{n} have free occurrences, then A preceded by ∀v_{1} ⋯ ∀v_{n} is a universal closure of 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
In earlier works on mathematical logic (e.g. by Church^{[16]}), formulas referred to any strings of symbols and among these strings, wellformed formulas were the strings that followed the formation rules of (correct) formulas.
Several authors simply say formula.^{[17]}^{[18]}^{[19]}^{[20]} Modern usages (especially in the context of computer science with mathematical software such as model checkers, automated theorem provers, interactive theorem provers) tend to retain of the notion of formula only the algebraic concept and to leave the question of wellformedness, i.e. of the concrete string representation of formulas (using this or that symbol for connectives and quantifiers, using this or that parenthesizing convention, using Polish or infix notation, etc.) as a mere notational problem.
The expression "wellformed formulas" (WFF) 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,^{[21]} 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).^{[22]} 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.^{[23]}
See also
Notes
 ^ Formulas are a standard topic in introductory logic, and are covered by all introductory textbooks, including Enderton (2001), Gamut (1990), and Kleene (1967)
 ^ Gensler, Harry (20020911). Introduction to Logic. Routledge. p. 35. ISBN 9781134588800.
 ^ Hall, Cordelia; O'Donnell, John (20130417). Discrete Mathematics Using a Computer. Springer Science & Business Media. p. 44. ISBN 9781447136576.
 ^ Agler, David W. (2013). Symbolic Logic: Syntax, Semantics, and Proof. Rowman & Littlefield. p. 41. ISBN 9781442217423.
 ^ Simpson, R. L. (20080317). Essentials of Symbolic Logic  Third Edition. Broadview Press. p. 14. ISBN 9781770484955.
 ^ Laderoute, Karl (20221024). A Pocket Guide to Formal Logic. Broadview Press. p. 59. ISBN 9781770488687.
 ^ Maurer, Stephen B.; Ralston, Anthony (20050121). Discrete Algorithmic Mathematics, Third Edition. CRC Press. p. 625. ISBN 9781568811666.
 ^ Martin, Robert M. (20020506). The Philosopher's Dictionary  Third Edition. Broadview Press. p. 323. ISBN 9781770482159.
 ^ Date, Christopher (20081014). The Relational Database Dictionary, Extended Edition. Apress. p. 211. ISBN 9781430210429.
 ^ Date, C. J. (20151221). The New Relational Database Dictionary: Terms, Concepts, and Examples. "O'Reilly Media, Inc.". p. 241. ISBN 9781491951712.
 ^ Simpson, R. L. (19981210). Essentials of Symbolic Logic. Broadview Press. p. 12. ISBN 9781551112503.
 ^
 "woof"^{[2]}^{[3]}^{[4]}^{[5]}
 "wiff"^{[6]}^{[7]}^{[8]}
 "weff"^{[9]}^{[10]}
 "whiff"^{[11]}
 ^ W. Dean, S. Walsh, The Prehistory of the Subsystems of Secondorder Arithmetic (2016), p.6
 ^ Firstorder logic and automated theorem proving, Melvin Fitting, Springer, 1996 [1]
 ^ Handbook of the history of logic, (Vol 5, Logic from Russell to Church), Tarski's logic by Keith Simmons, D. Gabbay and J. Woods Eds, p568 [2].
 ^ Alonzo Church, [1996] (1944), Introduction to mathematical logic, page 49
 ^ Hilbert, David; Ackermann, Wilhelm (1950) [1937], Principles of Mathematical Logic, New York: Chelsea
 ^ Hodges, Wilfrid (1997), A shorter model theory, Cambridge University Press, ISBN 9780521587136
 ^ Barwise, Jon, ed. (1982), Handbook of Mathematical Logic, Studies in Logic and the Foundations of Mathematics, Amsterdam: NorthHolland, ISBN 9780444863881
 ^ Cori, Rene; Lascar, Daniel (2000), Mathematical Logic: A Course with Exercises, Oxford University Press, ISBN 9780198500483
 ^ Ehrenburg 2002
 ^ More technically, propositional logic using the Fitchstyle calculus.
 ^ Allen (1965) acknowledges the pun.
References
 Allen, Layman E. (1965), "Toward Autotelic Learning of Mathematical Logic by the WFF 'N PROOF Games", Mathematical Learning: Report of a Conference Sponsored by the Committee on Intellective Processes Research of the Social Science Research Council, Monographs of the Society for Research in Child Development, 30 (1): 29–41
 Boolos, George; Burgess, John; Jeffrey, Richard (2002), Computability and Logic (4th ed.), Cambridge University Press, ISBN 9780521007580
 Ehrenberg, Rachel (Spring 2002). "He's Positively Logical". Michigan Today. University of Michigan. Archived from the original on 20090208. Retrieved 20070819.
 Enderton, Herbert (2001), A mathematical introduction to logic (2nd ed.), Boston, MA: Academic Press, ISBN 9780122384523
 Gamut, L.T.F. (1990), Logic, Language, and Meaning, Volume 1: Introduction to Logic, University Of Chicago Press, ISBN 0226280853
 Hodges, Wilfrid (2001), "Classical Logic I: FirstOrder Logic", in Goble, Lou (ed.), The Blackwell Guide to Philosophical Logic, Blackwell, ISBN 9780631206927
 Hofstadter, Douglas (1980), Gödel, Escher, Bach: An Eternal Golden Braid, Penguin Books, ISBN 9780140055795
 Kleene, Stephen Cole (2002) [1967], Mathematical logic, New York: Dover Publications, ISBN 9780486425337, MR 1950307
 Rautenberg, Wolfgang (2010), A Concise Introduction to Mathematical Logic (3rd ed.), New York: Springer Science+Business Media, doi:10.1007/9781441912213, ISBN 9781441912206
External links
 WellFormed Formula for First Order Predicate Logic  includes a short Java quiz.
 WellFormed Formula at ProvenMath