In
mathematical logic
Mathematical logic is the study of formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory. Research in mathematical logic commonly addresses the mathematical properties of formal ...
,
propositional logic
Propositional calculus is a branch of logic. It is also called propositional logic, statement logic, sentential calculus, sentential logic, or sometimes zeroth-order logic. It deals with propositions (which can be true or false) and relations b ...
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 quantifie ...
, a well-formed formula, abbreviated WFF or wff, often simply formula, is a finite
sequence
In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is calle ...
of
symbols from a given
alphabet
An alphabet is a standardized set of basic written graphemes (called letters) that represent the phonemes of certain spoken languages. Not all writing systems represent language in this way; in a syllabary, each character represents a syllab ...
that is part of a
formal language
In logic, mathematics, computer science, and linguistics, a formal language consists of words whose letters are taken from an alphabet and are well-formed according to a specific set of rules.
The alphabet of a formal language consists of sy ...
. 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.
Introduction
A key use of formulas is in
propositional logic
Propositional calculus is a branch of logic. It is also called propositional logic, statement logic, sentential calculus, sentential logic, or sometimes zeroth-order logic. It deals with propositions (which can be true or false) and relations b ...
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 quantifie ...
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 quantifie ...
. In those contexts, a formula is a string of symbols φ for which it makes sense to ask "is φ true?", once any
free variable
In mathematics, and in other disciplines involving formal languages, including mathematical logic and computer science, a free variable is a notation (symbol) that specifies places in an expression where substitution may take place and is not ...
s 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 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
Propositional calculus is a branch of logic. It is also called propositional logic, statement logic, sentential calculus, sentential logic, or sometimes zeroth-order logic. It deals with propositions (which can be true or false) and relations ...
, also called
propositional formula
In propositional logic, a propositional formula is a type of syntactic formula which is well formed and has a truth value. If the values of all variables in a propositional formula are given, it determines a unique truth value. A propositional for ...
s, are expressions such as
. Their definition begins with the arbitrary choice of a set ''V'' of
propositional variable
In mathematical logic, a propositional variable (also called a sentential variable or sentential letter) is an input variable (that can either be true or false) of a truth function. Propositional variables are the basic building-blocks of proposit ...
s. 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:
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 quantifie ...
is relative to the
signature
A signature (; from la, signare, "to sign") is a handwritten (and often stylized) depiction of someone's name, nickname, or even a simple "X" or other mark that a person writes on documents as a proof of identity and intent. The writer of a ...
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 subformu ...
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:
#
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 quantifier-free. An ''existential formula'' is a formula starting with a sequence of
existential quantification
In predicate logic, an existential quantification is a type of quantifier, a logical constant which is interpreted as "there exists", "there is at least one", or "for some". It is usually denoted by the logical operator symbol ∃, which, ...
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 ...
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
Propositional calculus is a branch of logic. It is also called propositional logic, statement logic, sentential calculus, sentential logic, or sometimes zeroth-order logic. It deals with propositions (which can be true or false) and relations b ...
, for example, the atomic formulas are the
propositional variable
In mathematical logic, a propositional variable (also called a sentential variable or sentential letter) is an input variable (that can either be true or false) of a truth function. Propositional variables are the basic building-blocks of proposit ...
s. 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 quantifie ...
, the atoms are predicate symbols together with their arguments, each argument being a
term
Term may refer to:
* Terminology, or term, a noun or compound word used in a specific context, in particular:
**Technical term, part of the specialized vocabulary of a particular field, specifically:
***Scientific terminology, terms used by scient ...
.
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 formula'' or ''sentence'', is a formula in which there are no
free occurrences of any
variable. 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
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
In logic, mathematics and computer science, especially metalogic and computability theory, an effective method Hunter, Geoffrey, ''Metalogic: An Introduction to the Metatheory of Standard First-Order Logic'', University of California Press, 1971 or ...
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
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
* C ...
), 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 provers,
interactive theorem provers) tend to retain of the notion of formula only the algebraic concept and to leave the question of
well-formedness
__NOTOC__
Well-formedness is the quality of a clause, word, or other linguistic element that conforms to the grammar of the language of which it is a part. Well-formed words or phrases are grammatical, meaning they obey all relevant rules of gramma ...
, 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
Polish may refer to:
* Anything from or related to Poland, a country in Europe
* Polish language
* Poles
Poles,, ; singular masculine: ''Polak'', singular feminine: ''Polka'' or Polish people, are a West Slavic nation and ethnic group, w ...
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
WFF 'N PROOF is a game of modern logic, developed to teach principles of symbolic logic. It was developed by Layman E. Allen in 1962 a former professor of Yale Law School and the University of Michigan.
Rules
In the game, players must be able ...
: The Game of Modern Logic," by Layman Allen, developed while he was at
Yale Law School
Yale Law School (Yale Law or YLS) is the law school of Yale University, a private research university in New Haven, Connecticut. It was established in 1824 and has been ranked as the best law school in the United States by '' U.S. News & Worl ...
(he was later a professor at the
University of Michigan
, mottoeng = "Arts, Knowledge, Truth"
, former_names = Catholepistemiad, or University of Michigania (1817–1821)
, budget = $10.3 billion (2021)
, endowment = $17 billion (2021)As o ...
). The suite of games is designed to teach the principles of symbolic logic to children (in
Polish notation
Polish notation (PN), also known as normal Polish notation (NPN), Łukasiewicz notation, Warsaw notation, Polish prefix notation or simply prefix notation, is a mathematical notation in which operators ''precede'' their operands, in contrast ...
). Its name is an echo of ''
whiffenpoof'', 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 ps ...
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 Engli ...
at
Yale University
Yale University is a Private university, private research university in New Haven, Connecticut. Established in 1701 as the Collegiate School, it is the List of Colonial Colleges, third-oldest institution of higher education in the United Sta ...
made popular in ''The Whiffenpoof Song'' and
The Whiffenpoofs
The Yale Whiffenpoofs is a collegiate a cappella singing group. Established at Yale University in 1909, it is the oldest such group in the United States. The line-up is completely replaced each year: the group is always composed of rising senio ...
.
[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
In mathematics, a well-defined expression or unambiguous expression is an expression whose definition assigns it a unique interpretation or value. Otherwise, the expression is said to be ''not well defined'', ill defined or ''ambiguous''. A func ...
Notes
References
*
*
*
*
*
*
*
*
*
External links
Well-Formed Formula for First Order Predicate Logic- includes a short
Java
Java (; id, Jawa, ; jv, ꦗꦮ; su, ) is one of the Greater Sunda Islands in Indonesia. It is bordered by the Indian Ocean to the south and the Java Sea to the north. With a population of 151.6 million people, Java is the world's mos ...
quiz.
Well-Formed Formula at ProvenMath
{{DEFAULTSORT:Well-Formed Formula
Formal languages
Metalogic
Syntax (logic)
Mathematical logic