HOME

TheInfoList



OR:

In mathematical logic, propositional logic and
predicate logic First-order logic—also known as predicate logic, quantificational logic, and first-order predicate calculus—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quantifi ...
, a well-formed formula, abbreviated WFF or wff, often simply formula, is a finite sequence of symbols from a given
alphabet An alphabet is a standardized set of basic written graphemes (called letter (alphabet), letters) that represent the phonemes of certain spoken languages. Not all writing systems represent language in this way; in a syllabary, each character ...
that is part of a formal language. 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 Interpretation may refer to: Culture * Aesthetic interpretation, an explanation of the meaning of a work of art * Allegorical interpretation, an approach that assumes a text should not be interpreted literally * Dramatic Interpretation, an event ...
. Two key uses of formulas are in propositional logic and predicate logic.


Introduction

A key use of formulas is in propositional logic and
predicate logic First-order logic—also known as predicate logic, quantificational logic, and first-order predicate calculus—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quantifi ...
such as
first-order logic First-order logic—also known as predicate logic, quantificational logic, and first-order predicate calculus—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quantifi ...
. 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 Token may refer to: Arts, entertainment, and media * Token, a game piece or counter, used in some games * The Tokens, a vocal music group * Tolkien Black, a recurring character on the animated television series ''South Park,'' formerly known a ...
instance of formula. This distinction between the vague notion of "property" and the inductively-defined notion of well-formed formula has roots in Weyl's 1910 paper "Uber die Definitionen der mathematischen Grundbegriffe". 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, are expressions such as (A \land (B \lor C)). 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 In computer science, Backus–Naur form () or Backus normal form (BNF) is a metasyntax notation for context-free grammars, often used to describe the syntax of languages used in computing, such as computer programming languages, document formats ...
, provided the set of variables is finite: 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 left-right 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
first-order logic First-order logic—also known as predicate logic, quantificational logic, and first-order predicate calculus—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quantifi ...
\mathcal 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 ''n''-ary function symbol, and ''t''1,…,''t''''n'' are terms, is again a term. The next step is to define the
atomic formula In mathematical logic, an atomic formula (also known as an atom or a prime formula) 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 subformul ...
s. #If ''t''1 and ''t''2 are terms then ''t''1=''t''2 is an atomic formula #If ''R'' is an ''n''-ary 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: #\neg\phi is a formula when \phi is a formula #(\phi \land \psi) and (\phi \lor \psi) are formulas when \phi and \psi are formulas; #\exists x\, \phi is a formula when x is a variable and \phi is a formula; #\forall x\, \phi is a formula when x is a variable and \phi is a formula (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 formula starting with a sequence of existential quantification followed by a quantifier-free formula.


Atomic and open formulas

An ''atomic formula'' is a formula that contains no
logical connective In logic, a logical connective (also called a logical operator, sentential connective, or sentential operator) is a logical constant. They can be used to connect logical formulas. For instance in the syntax of propositional logic, the binary co ...
s 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 First-order logic—also known as predicate logic, quantificational logic, and first-order predicate calculus—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quantifi ...
, 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. This is not to be confused with a formula which is not closed.


Closed formulas

A ''closed formula'', also ''
ground Ground may refer to: Geology * Land, the surface of the Earth not covered by water * Soil, a mixture of clay, sand and organic matter present on the surface of the Earth Electricity * Ground (electricity), the reference point in an electrical c ...
formula'' or ''sentence'', is a formula in which there are no free occurrences of any
variable Variable may refer to: * Variable (computer science), a symbolic name associated with a value and whose associated value may be changed * Variable (mathematics), a symbol that represents a quantity in a mathematical expression, as used in many ...
. If A is a formula of a first-order language in which the variables have free occurrences, then A preceded by is a closure of A.


Properties applicable to formulas

* A formula A in a language \mathcal is '' valid'' if it is true for every
interpretation Interpretation may refer to: Culture * Aesthetic interpretation, an explanation of the meaning of a work of art * Allegorical interpretation, an approach that assumes a text should not be interpreted literally * Dramatic Interpretation, an event ...
of \mathcal. * A formula A in a language \mathcal is '' satisfiable'' if it is true for some
interpretation Interpretation may refer to: Culture * Aesthetic interpretation, an explanation of the meaning of a work of art * Allegorical interpretation, an approach that assumes a text should not be interpreted literally * Dramatic Interpretation, an event ...
of \mathcal. * A formula A of the language of
arithmetic Arithmetic () is an elementary part of mathematics that consists of the study of the properties of the traditional operations on numbers—addition, subtraction, multiplication, division, exponentiation, and extraction of roots. In the 19th c ...
is ''decidable'' if it represents a
decidable set In computability theory, a set of natural numbers is called computable, recursive, or decidable if there is an algorithm which takes a number as input, terminates after a finite amount of time (possibly depending on the given number) and correctly ...
, i.e. if there is an effective method which, given a
substitution Substitution may refer to: Arts and media *Chord substitution, in music, swapping one chord for a related one within a chord progression *Substitution (poetry), a variation in poetic scansion * "Substitution" (song), a 2009 song by Silversun Pic ...
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 Church may refer to: Religion * Church (building), a building for Christian religious activities * Church (congregation), a local congregation of a Christian denomination * Church service, a formalized period of Christian communal worship * Chri ...
), formulas referred to any strings of symbols and among these strings, well-formed formulas were the strings that followed the formation rules of (correct) formulas. Several authors simply say formula. Modern usages (especially in the context of computer science with mathematical software such as
model checkers In computer science, model checking or property checking is a method for checking whether a finite-state model of a system meets a given specification (also known as correctness). This is typically associated with hardware or software systems ...
,
automated theorem prover Automated theorem proving (also known as ATP or automated deduction) is a subfield of automated reasoning and mathematical logic dealing with proving mathematical theorems by computer programs. Automated reasoning over mathematical proof was a maj ...
s, interactive theorem provers) tend to retain of the notion of formula only the algebraic concept and to leave the question of well-formedness, 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. While the expression ''well-formed formula'' is still in use, these authors do not necessarily use it in contradistinction to the old sense of ''formula'', which is no longer common in mathematical logic. The expression "well-formed 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, 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 whiffenpoof was a tool for training Boy Scouts in tracking skills. The whiffenpoof itself was a small log, about the size of a stick of firewood, with nails driven into it on all sides, so that it bristled with nails. This was dragged through th ...
'', a
nonsense word A nonsense word, unlike a sememe, may have no definition. Nonsense words can be classified depending on their orthographic and phonetic similarity with (meaningful) words. If it can be pronounced according to a language's phonotactics, it is a p ...
used as a
cheer Cheering involves the uttering or making of sounds and may be used to encourage, excite to action, indicate approval or welcome. The word cheer originally meant face, countenance, or expression, and came through Old French into Middle Englis ...
at Yale University made popular in ''The Whiffenpoof Song'' and The Whiffenpoofs.Allen (1965) acknowledges the pun.


See also

*
Ground expression In mathematical logic, a ground term of a formal system is a term that does not contain any variables. Similarly, a ground formula is a formula that does not contain any variables. In first-order logic with identity, the sentence Q(a) \lor P(b ...
* Well-defined expression


Notes


References

* * * * * * * * *


External links


Well-Formed Formula for First Order Predicate Logic
- includes a short Java quiz.
Well-Formed Formula at ProvenMath
{{DEFAULTSORT:Well-Formed Formula Formal languages Metalogic Syntax (logic) Mathematical logic