A
formula
In science, a formula is a concise way of expressing information symbolically, as in a mathematical formula or a ''chemical formula''. The informal use of the term ''formula'' in science refers to the general construct of a relationship betwee ...
of the
predicate calculus
Predicate or predication may refer to:
* Predicate (grammar), in linguistics
* Predication (philosophy)
* several closely related uses in mathematics and formal logic:
**Predicate (mathematical logic)
**Propositional function
**Finitary relation, o ...
is in prenex
normal form (PNF) if it is
written
Writing is a medium of human communication which involves the representation of a language through a system of physically inscribed, mechanically transferred, or digitally represented symbols.
Writing systems do not themselves constitute h ...
as a string of
quantifiers and
bound variables
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 ...
, called the prefix, followed by a quantifier-free part, called the matrix. Together with the normal forms 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 ...
(e.g.
disjunctive normal form
In boolean logic, a disjunctive normal form (DNF) is a canonical normal form of a logical formula consisting of a disjunction of conjunctions; it can also be described as an OR of ANDs, a sum of products, or (in philosophical logic) a ''cluster c ...
or
conjunctive normal form
In Boolean logic, a formula is in conjunctive normal form (CNF) or clausal normal form if it is a conjunction of one or more clauses, where a clause is a disjunction of literals; otherwise put, it is a product of sums or an AND of ORs. As a can ...
), it provides a
canonical normal form
In Boolean algebra, any Boolean function can be expressed in the canonical disjunctive normal form ( CDNF) or minterm canonical form and its dual canonical conjunctive normal form ( CCNF) or maxterm canonical form. Other canonical forms include ...
useful in
automated theorem proving
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 ...
.
Every formula in
classical logic
Classical logic (or standard logic or Frege-Russell logic) is the intensively studied and most widely used class of deductive logic. Classical logic has had much influence on analytic philosophy.
Characteristics
Each logical system in this class ...
is equivalent to a formula in prenex normal form. For example, if
,
, and
are quantifier-free formulas with the free variables shown then
:
is in prenex normal form with matrix
, while
:
is logically equivalent but not in prenex normal form.
Conversion to prenex form
Every
first-order
In mathematics and other formal sciences, first-order or first order most often means either:
* "linear" (a polynomial of degree at most one), as in first-order approximation and other calculus uses, where it is contrasted with "polynomials of high ...
formula is
logically equivalent
Logic is the study of correct reasoning. It includes both formal and informal logic. Formal logic is the science of deductively valid inferences or of logical truths. It is a formal science investigating how conclusions follow from premises ...
(in classical logic) to some formula in prenex normal form.
[Hinman, P. (2005), p. 111] There are several conversion rules that can be recursively applied to convert a formula to prenex normal form. The rules depend on which
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 appear in the formula.
Conjunction and disjunction
The rules for
conjunction
Conjunction may refer to:
* Conjunction (grammar), a part of speech
* Logical conjunction, a mathematical operator
** Conjunction introduction, a rule of inference of propositional logic
* Conjunction (astronomy), in which two astronomical bodies ...
and
disjunction
In logic, disjunction is a logical connective typically notated as \lor and read aloud as "or". For instance, the English language sentence "it is raining or it is snowing" can be represented in logic using the disjunctive formula R \lor S ...
say that
:
is equivalent to
under (mild) additional condition
, or, equivalently,
(meaning that at least one individual exists),
:
is equivalent to
;
and
:
is equivalent to
,
:
is equivalent to
under additional condition
.
The equivalences are valid when
does not appear as a
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 ...
of
; if
does appear free in
, one can rename the bound
in
and obtain the equivalent
.
For example, in the language of
rings
Ring may refer to:
* Ring (jewellery), a round band, usually made of metal, worn as ornamental jewelry
* To make a sound with a bell, and the sound made by a bell
:(hence) to initiate a telephone connection
Arts, entertainment and media Film and ...
,
:
is equivalent to
,
but
:
is not equivalent to
because the formula on the left is true in any ring when the free variable ''x'' is equal to 0, while the formula on the right has no free variables and is false in any nontrivial ring. So
will be first rewritten as
and then put in prenex normal form
.
Negation
The rules for negation say that
:
is equivalent to
and
:
is equivalent to
.
Implication
There are four rules for
implication: two that remove quantifiers from the antecedent and two that remove quantifiers from the consequent. These rules can be derived by
rewriting
In mathematics, computer science, and logic, rewriting covers a wide range of methods of replacing subterms of a well-formed formula, formula with other terms. Such methods may be achieved by rewriting systems (also known as rewrite systems, rewr ...
the implication
as
and applying the rules for disjunction above. As with the rules for disjunction, these rules require that the variable quantified in one subformula does not appear free in the other subformula.
The rules for removing quantifiers from the antecedent are (note the change of quantifiers):
:
is equivalent to
(under the assumption that
),
:
is equivalent to
.
The rules for removing quantifiers from the consequent are:
:
is equivalent to
(under the assumption that
),
:
is equivalent to
.
For example, when the
range of quantification
In logic, a quantifier is an operator that specifies how many individuals in the domain of discourse satisfy an open formula. For instance, the universal quantifier \forall in the first order formula \forall x P(x) expresses that everythin ...
is the non-negative
natural number
In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country").
Numbers used for counting are called ''Cardinal n ...
(viz.
), the statement
:
is
logically equivalent
Logic is the study of correct reasoning. It includes both formal and informal logic. Formal logic is the science of deductively valid inferences or of logical truths. It is a formal science investigating how conclusions follow from premises ...
to the statement
: