HOME

TheInfoList



OR:

In the
philosophy of logic Philosophy of logic is the area of philosophy that studies the scope and nature of logic. It investigates the philosophical problems raised by logic, such as the presuppositions often implicitly at work in theories of logic and in their application ...
, a rule of inference, inference rule or transformation rule is a
logical form In logic, logical form of a statement is a precisely-specified semantic version of that statement in a formal system. Informally, the logical form attempts to formalize a possibly ambiguous statement into a statement with a precise, unambiguou ...
consisting of a function which takes premises, analyzes their
syntax In linguistics, syntax () is the study of how words and morphemes combine to form larger units such as phrases and sentences. Central concerns of syntax include word order, grammatical relations, hierarchical sentence structure ( constituency) ...
, and returns a conclusion (or conclusions). For example, the rule of inference called ''
modus ponens In propositional logic, ''modus ponens'' (; MP), also known as ''modus ponendo ponens'' (Latin for "method of putting by placing") or implication elimination or affirming the antecedent, is a deductive argument form and rule of inference. ...
'' takes two premises, one in the form "If p then q" and another in the form "p", and returns the conclusion "q". The rule is valid with respect to the semantics of
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 ...
(as well as the semantics of many other
non-classical logic Non-classical logics (and sometimes alternative logics) are formal systems that differ in a significant way from standard logical systems such as propositional and predicate logic. There are several ways in which this is done, including by way of ...
s), in the sense that if the premises are true (under an interpretation), then so is the conclusion. Typically, a rule of inference preserves truth, a semantic property. In
many-valued logic Many-valued logic (also multi- or multiple-valued logic) refers to a propositional calculus in which there are more than two truth values. Traditionally, in Aristotle's logical calculus, there were only two possible values (i.e., "true" and "false" ...
, it preserves a general designation. But a rule of inference's action is purely syntactic, and does not need to preserve any semantic property: any function from sets of formulae to formulae counts as a rule of inference. Usually only rules that are
recursive Recursion (adjective: ''recursive'') occurs when a thing is defined in terms of itself or of its type. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in mathematics ...
are important; i.e. rules such that there is an
effective procedure In logic, mathematics and computer science, especially metalogic and computability theory, an effective methodGeoffrey Hunter (logician), Hunter, Geoffrey, ''Metalogic: An Introduction to the Metatheory of Standard First-Order Logic'', University o ...
for determining whether any given formula is the conclusion of a given set of formulae according to the rule. An example of a rule that is not effective in this sense is the infinitary ω-rule. Popular rules of inference 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 ...
include ''
modus ponens In propositional logic, ''modus ponens'' (; MP), also known as ''modus ponendo ponens'' (Latin for "method of putting by placing") or implication elimination or affirming the antecedent, is a deductive argument form and rule of inference. ...
'', ''
modus tollens In propositional logic, ''modus tollens'' () (MT), also known as ''modus tollendo tollens'' (Latin for "method of removing by taking away") and denying the consequent, is a deductive argument form and a rule of inference. ''Modus tollens' ...
'', and
contraposition In logic and mathematics, contraposition refers to the inference of going from a conditional statement into its logically equivalent contrapositive, and an associated proof method known as proof by contraposition. The contrapositive of a stateme ...
. First-order
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 ...
uses rules of inference to deal with
logical quantifier 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 everything i ...
s.


Standard form

In
formal logic 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 premis ...
(and many related areas), rules of inference are usually given in the following standard form:   Premise#1
  Premise#2
        ...
  Premise#n   
  Conclusion This expression states that whenever in the course of some logical derivation the given premises have been obtained, the specified conclusion can be taken for granted as well. The exact formal language that is used to describe both premises and conclusions depends on the actual context of the derivations. In a simple case, one may use logical formulae, such as in: : A \to B : \underline\,\! : B\! This is the ''
modus ponens In propositional logic, ''modus ponens'' (; MP), also known as ''modus ponendo ponens'' (Latin for "method of putting by placing") or implication elimination or affirming the antecedent, is a deductive argument form and rule of inference. ...
'' rule of
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 ...
. Rules of inference are often formulated as schemata employing
metavariable In logic, a metavariable (also metalinguistic variable or syntactical variable) is a symbol or symbol string which belongs to a metalanguage and stands for elements of some object language. For instance, in the sentence :''Let A and B be two sente ...
s. In the rule (schema) above, the metavariables A and B can be instantiated to any element of the universe (or sometimes, by convention, a restricted subset such as
proposition In logic and linguistics, a proposition is the meaning of a declarative sentence. In philosophy, " meaning" is understood to be a non-linguistic entity which is shared by all sentences with the same meaning. Equivalently, a proposition is the no ...
s) to form an
infinite set In set theory, an infinite set is a set that is not a finite set. Infinite sets may be countable or uncountable. Properties The set of natural numbers (whose existence is postulated by the axiom of infinity) is infinite. It is the only set th ...
of inference rules. A proof system is formed from a set of rules chained together to form proofs, also called ''derivations''. Any derivation has only one final conclusion, which is the statement proved or derived. If premises are left unsatisfied in the derivation, then the derivation is a proof of a ''hypothetical'' statement: "''if'' the premises hold, ''then'' the conclusion holds."


Example: Hilbert systems for two propositional logics

In a
Hilbert system :''In mathematical physics, ''Hilbert system'' is an infrequently used term for a physical system described by a C*-algebra.'' In logic, especially mathematical logic, a Hilbert system, sometimes called Hilbert calculus, Hilbert-style deductive s ...
, the premises and conclusion of the inference rules are simply formulae of some language, usually employing metavariables. For graphical compactness of the presentation and to emphasize the distinction between axioms and rules of inference, this section uses the
sequent In mathematical logic, a sequent is a very general kind of conditional assertion. : A_1,\,\dots,A_m \,\vdash\, B_1,\,\dots,B_n. A sequent may have any number ''m'' of condition formulas ''Ai'' (called " antecedents") and any number ''n'' of asse ...
notation (\vdash) instead of a vertical presentation of rules. In this notation, \begin \text 1 \\ \text 2 \\ \hline \text \end is written as (\text 1), (\text 2) \vdash (\text). The formal language for classical
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 ...
can be expressed using just negation (¬), implication (→) and propositional symbols. A well-known axiomatization, comprising three axiom schemata and one inference rule (''modus ponens''), is: (CA1) ⊢ ''A'' → (''B'' → ''A'')
(CA2) ⊢ (''A'' → (''B'' → ''C'')) → ((''A'' → ''B'') → (''A'' → ''C''))
(CA3) ⊢ (¬''A'' → ¬''B'') → (''B'' → ''A'')
(MP) ''A'', ''A'' → ''B'' ⊢ ''B'' It may seem redundant to have two notions of inference in this case, ⊢ and →. In classical propositional logic, they indeed coincide; the
deduction theorem In mathematical logic, a deduction theorem is a metatheorem that justifies doing conditional proofs—to prove an implication ''A'' → ''B'', assume ''A'' as an hypothesis and then proceed to derive ''B''—in systems that do not have an ...
states that ''A'' ⊢ ''B'' if and only if ⊢ ''A'' → ''B''. There is however a distinction worth emphasizing even in this case: the first notation describes a deduction, that is an activity of passing from sentences to sentences, whereas ''A'' → ''B'' is simply a formula made with a
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 ...
, implication in this case. Without an inference rule (like ''modus ponens'' in this case), there is no deduction or inference. This point is illustrated in
Lewis Carroll Charles Lutwidge Dodgson (; 27 January 1832 – 14 January 1898), better known by his pen name Lewis Carroll, was an English author, poet and mathematician. His most notable works are ''Alice's Adventures in Wonderland'' (1865) and its sequel ...
's dialogue called " What the Tortoise Said to Achilles",preprint (with different pagination)
/ref> as well as later attempts by Bertrand Russell and Peter Winch to resolve the paradox introduced in the dialogue. For some non-classical logics, the deduction theorem does not hold. For example, the
three-valued logic In logic, a three-valued logic (also trinary logic, trivalent, ternary, or trilean, sometimes abbreviated 3VL) is any of several many-valued logic systems in which there are three truth values indicating ''true'', ''false'' and some indeterminate ...
of Łukasiewicz can be axiomatized as: (CA1) ⊢ ''A'' → (''B'' → ''A'')
(LA2) ⊢ (''A'' → ''B'') → ((''B'' → ''C'') → (''A'' → ''C''))
(CA3) ⊢ (¬''A'' → ¬''B'') → (''B'' → ''A'')
(LA4) ⊢ ((''A'' → ¬''A'') → ''A'') → ''A''
(MP) ''A'', ''A'' → ''B'' ⊢ ''B'' This sequence differs from classical logic by the change in axiom 2 and the addition of axiom 4. The classical deduction theorem does not hold for this logic, however a modified form does hold, namely ''A'' ⊢ ''B'' if and only if ⊢ ''A'' → (''A'' → ''B'').


Admissibility and derivability

In a set of rules, an inference rule could be redundant in the sense that it is ''admissible'' or ''derivable''. A derivable rule is one whose conclusion can be derived from its premises using the other rules. An admissible rule is one whose conclusion holds whenever the premises hold. All derivable rules are admissible. To appreciate the difference, consider the following set of rules for defining the
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 ...
s (the
judgment Judgement (or US spelling judgment) is also known as ''adjudication'', which means the evaluation of evidence to decision-making, make a decision. Judgement is also the ability to make considered decisions. The term has at least five distinct u ...
n\,\,\mathsf asserts the fact that n is a natural number): : \begin \begin\\ \hline\end & \begin \\ \hline \end \end The first rule states that 0 is a natural number, and the second states that s(''n'') is a natural number if ''n'' is. In this proof system, the following rule, demonstrating that the second successor of a natural number is also a natural number, is derivable: : \begin \\ \hline \end Its derivation is the composition of two uses of the successor rule above. The following rule for asserting the existence of a predecessor for any nonzero number is merely admissible: : \begin \\ \hline \end This is a true fact of natural numbers, as can be proven by
induction Induction, Inducible or Inductive may refer to: Biology and medicine * Labor induction (birth/pregnancy) * Induction chemotherapy, in medicine * Induced stem cells, stem cells derived from somatic, reproductive, pluripotent or other cell t ...
. (To prove that this rule is admissible, assume a derivation of the premise and induct on it to produce a derivation of n \,\,\mathsf.) However, it is not derivable, because it depends on the structure of the derivation of the premise. Because of this, derivability is stable under additions to the proof system, whereas admissibility is not. To see the difference, suppose the following nonsense rule were added to the proof system: : \begin\\\hline \end In this new system, the double-successor rule is still derivable. However, the rule for finding the predecessor is no longer admissible, because there is no way to derive \mathbf \,\,\mathsf. The brittleness of admissibility comes from the way it is proved: since the proof can induct on the structure of the derivations of the premises, extensions to the system add new cases to this proof, which may no longer hold. Admissible rules can be thought of as
theorem In mathematics, a theorem is a statement that has been proved, or can be proved. The ''proof'' of a theorem is a logical argument that uses the inference rules of a deductive system to establish that the theorem is a logical consequence of th ...
s of a proof system. For instance, in a
sequent calculus In mathematical logic, sequent calculus is a style of formal logical argumentation in which every line of a proof is a conditional tautology (called a sequent by Gerhard Gentzen) instead of an unconditional tautology. Each conditional tautology i ...
where
cut elimination The cut-elimination theorem (or Gentzen's ''Hauptsatz'') is the central result establishing the significance of the sequent calculus. It was originally proved by Gerhard Gentzen in his landmark 1934 paper "Investigations in Logical Deduction" for ...
holds, the ''cut'' rule is admissible.


See also

*
Argumentation scheme In argumentation theory, an argumentation scheme or argument scheme is a template that represents a common type of argument used in ordinary conversation. Many different argumentation schemes have been identified. Each one has a name (for example ...
*
Immediate inference An immediate inference is an inference which can be made from only one statement or proposition. For instance, from the statement "All toads are green", the immediate inference can be made that "no toads are not green" or "no toads are non-green" ...
*
Inference objection In argumentation, an objection is a reason arguing against a premise, argument, or conclusion. Definitions of objection vary in whether an objection is always an argument (or counterargument) or may include other moves such as questioning. An ...
*
Law of thought The laws of thought are fundamental axiomatic rules upon which rational discourse itself is often considered to be based. The formulation and clarification of such rules have a long tradition in the history of philosophy and logic. Generally they ...
*
List of rules of inference This is a list of rules of inference, logical laws that relate to mathematical formulae. Introduction Rules of inference are syntactical transform rules which one can use to infer a conclusion from a premise to create an argument. A set of rules ...
*
Logical truth Logical truth is one of the most fundamental concepts in logic. Broadly speaking, a logical truth is a statement which is true regardless of the truth or falsity of its constituent propositions. In other words, a logical truth is a statement whic ...
* Structural rule


References

{{DEFAULTSORT:Rule Of Inference Propositional calculus Formal systems Syntax (logic) Logical truth Inference Logical expressions