This is a list of rules of inference , logical laws that relate to mathematical formulae.
Introduction [ edit ]
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 can be used to infer any valid conclusion if it is complete, while never inferring an invalid conclusion, if it is sound. A sound and complete set of rules need not include every rule in the following list, as many of the rules are redundant, and can be proven with the other rules.
Discharge rules permit inference from a subderivation based on a temporary assumption. Below, the notation
φ ふぁい
⊢
ψ ぷさい
{\displaystyle \varphi \vdash \psi }
indicates such a subderivation from the temporary assumption
φ ふぁい
{\displaystyle \varphi }
to
ψ ぷさい
{\displaystyle \psi }
.
Rules for negations [ edit ]
Reductio ad absurdum (or Negation Introduction )
φ ふぁい
⊢
ψ ぷさい
{\displaystyle \varphi \vdash \psi }
φ ふぁい
⊢
¬
ψ ぷさい
_
{\displaystyle {\underline {\varphi \vdash \lnot \psi }}}
¬
φ ふぁい
{\displaystyle \lnot \varphi }
Reductio ad absurdum (related to the law of excluded middle )
¬
φ ふぁい
⊢
ψ ぷさい
{\displaystyle \lnot \varphi \vdash \psi }
¬
φ ふぁい
⊢
¬
ψ ぷさい
_
{\displaystyle {\underline {\lnot \varphi \vdash \lnot \psi }}}
φ ふぁい
{\displaystyle \varphi }
Ex contradictione quodlibet
φ ふぁい
{\displaystyle \varphi }
¬
φ ふぁい
_
{\displaystyle {\underline {\lnot \varphi }}}
ψ ぷさい
{\displaystyle \psi }
Rules for conditionals [ edit ]
Deduction theorem (or Conditional Introduction )
φ ふぁい
⊢
ψ ぷさい
_
{\displaystyle {\underline {\varphi \vdash \psi }}}
φ ふぁい
→
ψ ぷさい
{\displaystyle \varphi \rightarrow \psi }
Modus ponens (or Conditional Elimination )
φ ふぁい
→
ψ ぷさい
{\displaystyle \varphi \rightarrow \psi }
φ ふぁい
_
{\displaystyle {\underline {\varphi \quad \quad \quad }}}
ψ ぷさい
{\displaystyle \psi }
Modus tollens
φ ふぁい
→
ψ ぷさい
{\displaystyle \varphi \rightarrow \psi }
¬
ψ ぷさい
_
{\displaystyle {\underline {\lnot \psi \quad \quad \quad }}}
¬
φ ふぁい
{\displaystyle \lnot \varphi }
Rules for conjunctions [ edit ]
Adjunction (or Conjunction Introduction )
φ ふぁい
{\displaystyle \varphi }
ψ ぷさい
_
{\displaystyle {\underline {\psi \quad \quad \ \ }}}
φ ふぁい
∧
ψ ぷさい
{\displaystyle \varphi \land \psi }
Simplification (or Conjunction Elimination )
φ ふぁい
∧
ψ ぷさい
_
{\displaystyle {\underline {\varphi \land \psi }}}
φ ふぁい
{\displaystyle \varphi }
φ ふぁい
∧
ψ ぷさい
_
{\displaystyle {\underline {\varphi \land \psi }}}
ψ ぷさい
{\displaystyle \psi }
Rules for disjunctions [ edit ]
Addition (or Disjunction Introduction )
φ ふぁい
_
{\displaystyle {\underline {\varphi \quad \quad \ \ }}}
φ ふぁい
∨
ψ ぷさい
{\displaystyle \varphi \lor \psi }
ψ ぷさい
_
{\displaystyle {\underline {\psi \quad \quad \ \ }}}
φ ふぁい
∨
ψ ぷさい
{\displaystyle \varphi \lor \psi }
Case analysis (or Proof by Cases or Argument by Cases or Disjunction elimination )
φ ふぁい
→
χ かい
{\displaystyle \varphi \rightarrow \chi }
ψ ぷさい
→
χ かい
{\displaystyle \psi \rightarrow \chi }
φ ふぁい
∨
ψ ぷさい
_
{\displaystyle {\underline {\varphi \lor \psi }}}
χ かい
{\displaystyle \chi }
Disjunctive syllogism
φ ふぁい
∨
ψ ぷさい
{\displaystyle \varphi \lor \psi }
¬
φ ふぁい
_
{\displaystyle {\underline {\lnot \varphi \quad \quad }}}
ψ ぷさい
{\displaystyle \psi }
φ ふぁい
∨
ψ ぷさい
{\displaystyle \varphi \lor \psi }
¬
ψ ぷさい
_
{\displaystyle {\underline {\lnot \psi \quad \quad }}}
φ ふぁい
{\displaystyle \varphi }
Constructive dilemma
φ ふぁい
→
χ かい
{\displaystyle \varphi \rightarrow \chi }
ψ ぷさい
→
ξ くしー
{\displaystyle \psi \rightarrow \xi }
φ ふぁい
∨
ψ ぷさい
_
{\displaystyle {\underline {\varphi \lor \psi }}}
χ かい
∨
ξ くしー
{\displaystyle \chi \lor \xi }
Rules for biconditionals [ edit ]
Biconditional introduction
φ ふぁい
→
ψ ぷさい
{\displaystyle \varphi \rightarrow \psi }
ψ ぷさい
→
φ ふぁい
_
{\displaystyle {\underline {\psi \rightarrow \varphi }}}
φ ふぁい
↔
ψ ぷさい
{\displaystyle \varphi \leftrightarrow \psi }
Biconditional elimination
φ ふぁい
↔
ψ ぷさい
{\displaystyle \varphi \leftrightarrow \psi }
φ ふぁい
_
{\displaystyle {\underline {\varphi \quad \quad }}}
ψ ぷさい
{\displaystyle \psi }
φ ふぁい
↔
ψ ぷさい
{\displaystyle \varphi \leftrightarrow \psi }
ψ ぷさい
_
{\displaystyle {\underline {\psi \quad \quad }}}
φ ふぁい
{\displaystyle \varphi }
φ ふぁい
↔
ψ ぷさい
{\displaystyle \varphi \leftrightarrow \psi }
¬
φ ふぁい
_
{\displaystyle {\underline {\lnot \varphi \quad \quad }}}
¬
ψ ぷさい
{\displaystyle \lnot \psi }
φ ふぁい
↔
ψ ぷさい
{\displaystyle \varphi \leftrightarrow \psi }
¬
ψ ぷさい
_
{\displaystyle {\underline {\lnot \psi \quad \quad }}}
¬
φ ふぁい
{\displaystyle \lnot \varphi }
φ ふぁい
↔
ψ ぷさい
{\displaystyle \varphi \leftrightarrow \psi }
ψ ぷさい
∨
φ ふぁい
_
{\displaystyle {\underline {\psi \lor \varphi }}}
ψ ぷさい
∧
φ ふぁい
{\displaystyle \psi \land \varphi }
φ ふぁい
↔
ψ ぷさい
{\displaystyle \varphi \leftrightarrow \psi }
¬
ψ ぷさい
∨
¬
φ ふぁい
_
{\displaystyle {\underline {\lnot \psi \lor \lnot \varphi }}}
¬
ψ ぷさい
∧
¬
φ ふぁい
{\displaystyle \lnot \psi \land \lnot \varphi }
In the following rules,
φ ふぁい
(
β べーた
/
α あるふぁ
)
{\displaystyle \varphi (\beta /\alpha )}
is exactly like
φ ふぁい
{\displaystyle \varphi }
except for having the term
β べーた
{\displaystyle \beta }
wherever
φ ふぁい
{\displaystyle \varphi }
has the free variable
α あるふぁ
{\displaystyle \alpha }
.
Universal Generalization (or Universal Introduction )
φ ふぁい
(
β べーた
/
α あるふぁ
)
_
{\displaystyle {\underline {\varphi {(\beta /\alpha )}}}}
∀
α あるふぁ
φ ふぁい
{\displaystyle \forall \alpha \,\varphi }
Restriction 1:
β べーた
{\displaystyle \beta }
is a variable which does not occur in
φ ふぁい
{\displaystyle \varphi }
.
Restriction 2:
β べーた
{\displaystyle \beta }
is not mentioned in any hypothesis or undischarged assumptions.
Universal Instantiation (or Universal Elimination )
∀
α あるふぁ
φ ふぁい
{\displaystyle \forall \alpha \,\varphi }
φ ふぁい
(
β べーた
/
α あるふぁ
)
¯
{\displaystyle {\overline {\varphi {(\beta /\alpha )}}}}
Restriction: No free occurrence of
α あるふぁ
{\displaystyle \alpha }
in
φ ふぁい
{\displaystyle \varphi }
falls within the scope of a quantifier quantifying a variable occurring in
β べーた
{\displaystyle \beta }
.
Existential Generalization (or Existential Introduction )
φ ふぁい
(
β べーた
/
α あるふぁ
)
_
{\displaystyle {\underline {\varphi (\beta /\alpha )}}}
∃
α あるふぁ
φ ふぁい
{\displaystyle \exists \alpha \,\varphi }
Restriction: No free occurrence of
α あるふぁ
{\displaystyle \alpha }
in
φ ふぁい
{\displaystyle \varphi }
falls within the scope of a quantifier quantifying a variable occurring in
β べーた
{\displaystyle \beta }
.
Existential Instantiation (or Existential Elimination )
∃
α あるふぁ
φ ふぁい
{\displaystyle \exists \alpha \,\varphi }
φ ふぁい
(
β べーた
/
α あるふぁ
)
⊢
ψ ぷさい
_
{\displaystyle {\underline {\varphi (\beta /\alpha )\vdash \psi }}}
ψ ぷさい
{\displaystyle \psi }
Restriction 1:
β べーた
{\displaystyle \beta }
is a variable which does not occur in
φ ふぁい
{\displaystyle \varphi }
.
Restriction 2: There is no occurrence, free or bound, of
β べーた
{\displaystyle \beta }
in
ψ ぷさい
{\displaystyle \psi }
.
Restriction 3:
β べーた
{\displaystyle \beta }
is not mentioned in any hypothesis or undischarged assumptions.
The following are special cases of universal generalization and existential elimination; these occur in substructural logics, such as linear logic .
Rule of weakening (or monotonicity of entailment ) (aka no-cloning theorem )
α あるふぁ
⊢
β べーた
{\displaystyle \alpha \vdash \beta }
α あるふぁ
,
α あるふぁ
⊢
β べーた
¯
{\displaystyle {\overline {\alpha ,\alpha \vdash \beta }}}
Rule of contraction (or idempotency of entailment ) (aka no-deleting theorem )
α あるふぁ
,
α あるふぁ
,
γ がんま
⊢
β べーた
_
{\displaystyle {\underline {\alpha ,\alpha ,\gamma \vdash \beta }}}
α あるふぁ
,
γ がんま
⊢
β べーた
{\displaystyle \alpha ,\gamma \vdash \beta }
Table: Rules of Inference [ edit ]
The rules above can be summed up in the following table.[1] The "Tautology " column shows how to interpret the notation of a given rule.
Rules of inference
Tautology
Name
p
p
→
q
∴
q
¯
{\displaystyle {\begin{aligned}p\\p\rightarrow q\\\therefore {\overline {q\quad \quad \quad }}\\\end{aligned}}}
(
p
∧
(
p
→
q
)
)
→
q
{\displaystyle (p\wedge (p\rightarrow q))\rightarrow q}
Modus ponens
¬
q
p
→
q
∴
¬
p
¯
{\displaystyle {\begin{aligned}\neg q\\p\rightarrow q\\\therefore {\overline {\neg p\quad \quad \quad }}\\\end{aligned}}}
(
¬
q
∧
(
p
→
q
)
)
→
¬
p
{\displaystyle (\neg q\wedge (p\rightarrow q))\rightarrow \neg p}
Modus tollens
p
→
q
q
→
r
∴
p
→
r
¯
{\displaystyle {\begin{aligned}p\rightarrow q\\q\rightarrow r\\\therefore {\overline {p\rightarrow r}}\\\end{aligned}}}
(
(
p
→
q
)
∧
(
q
→
r
)
)
→
(
p
→
r
)
{\displaystyle ((p\rightarrow q)\wedge (q\rightarrow r))\rightarrow (p\rightarrow r)}
Hypothetical syllogism
p
→
q
∴
p
→
(
p
∧
q
)
¯
{\displaystyle {\begin{aligned}p\rightarrow q\\\therefore {\overline {p\rightarrow (p\wedge q)}}\\\end{aligned}}}
(
p
→
q
)
→
(
p
→
(
p
∧
q
)
)
{\displaystyle (p\rightarrow q)\rightarrow (p\rightarrow (p\wedge q))}
Absorption
p
q
∴
p
∧
q
¯
{\displaystyle {\begin{aligned}p\\q\\\therefore {\overline {p\wedge q}}\\\end{aligned}}}
(
(
p
)
∧
(
q
)
)
→
(
p
∧
q
)
{\displaystyle ((p)\wedge (q))\rightarrow (p\wedge q)}
Conjunction introduction
p
∧
q
∴
p
¯
{\displaystyle {\begin{aligned}p\wedge q\\\therefore {\overline {p\quad \quad \quad }}\\\end{aligned}}}
(
p
∧
q
)
→
p
{\displaystyle (p\wedge q)\rightarrow p}
Conjunction elimination
p
∴
p
∨
q
¯
{\displaystyle {\begin{aligned}p\\\therefore {\overline {p\vee q}}\\\end{aligned}}}
p
→
(
p
∨
q
)
{\displaystyle p\rightarrow (p\vee q)}
Disjunction introduction
p
→
q
r
→
q
p
∨
r
∴
q
¯
{\displaystyle {\begin{aligned}p\rightarrow q\\r\rightarrow q\\p\vee r\\\therefore {\overline {q\quad \quad \quad }}\\\end{aligned}}}
(
(
p
→
q
)
∧
(
r
→
q
)
∧
(
p
∨
r
)
)
→
q
{\displaystyle ((p\rightarrow q)\wedge (r\rightarrow q)\wedge (p\vee r))\rightarrow q}
Disjunction elimination
p
∨
q
¬
p
∴
q
¯
{\displaystyle {\begin{aligned}p\vee q\\\neg p\\\therefore {\overline {q\quad \quad \quad }}\\\end{aligned}}}
(
(
p
∨
q
)
∧
¬
p
)
→
q
{\displaystyle ((p\vee q)\wedge \neg p)\rightarrow q}
Disjunctive syllogism
p
∨
p
∴
p
¯
{\displaystyle {\begin{aligned}p\vee p\\\therefore {\overline {p\quad \quad \quad }}\\\end{aligned}}}
(
p
∨
p
)
→
p
{\displaystyle (p\vee p)\rightarrow p}
Disjunctive simplification
p
∨
q
¬
p
∨
r
∴
q
∨
r
¯
{\displaystyle {\begin{aligned}p\vee q\\\neg p\vee r\\\therefore {\overline {q\vee r}}\\\end{aligned}}}
(
(
p
∨
q
)
∧
(
¬
p
∨
r
)
)
→
(
q
∨
r
)
{\displaystyle ((p\vee q)\wedge (\neg p\vee r))\rightarrow (q\vee r)}
Resolution
p
→
q
q
→
p
∴
p
↔
q
¯
{\displaystyle {\begin{aligned}p\rightarrow q\\q\rightarrow p\\\therefore {\overline {p\leftrightarrow q}}\\\end{aligned}}}
(
(
p
→
q
)
∧
(
q
→
p
)
)
→
(
p
↔
q
)
{\displaystyle ((p\rightarrow q)\wedge (q\rightarrow p))\rightarrow (p\leftrightarrow q)}
Biconditional introduction
All rules use the basic logic operators. A complete table of "logic operators" is shown by a truth table , giving definitions of all the possible (16) truth functions of 2 boolean variables (p , q ):
p
q
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
T
T
F
F
F
F
F
F
F
F
T
T
T
T
T
T
T
T
T
F
F
F
F
F
T
T
T
T
F
F
F
F
T
T
T
T
F
T
F
F
T
T
F
F
T
T
F
F
T
T
F
F
T
T
F
F
F
T
F
T
F
T
F
T
F
T
F
T
F
T
F
T
where T = true and F = false, and, the columns are the logical operators :
0 , false , Contradiction ;
1 , NOR , Logical NOR (Peirce's arrow );
2 , Converse nonimplication ;
3 , ¬p , Negation ;
4 , Material nonimplication ;
5 , ¬q , Negation ;
6 , XOR , Exclusive disjunction ;
7 , NAND , Logical NAND (Sheffer stroke );
8 , AND , Logical conjunction ;
9 , XNOR , If and only if , Logical biconditional ;
10 , q , Projection function ;
11 , if/then , Material conditional ;
12 , p , Projection function ;
13 , then/if, Converse implication ;
14 , OR , Logical disjunction ;
15 , true , Tautology .
Each logic operator can be used in an assertion about variables and operations, showing a basic rule of inference. Examples:
The column-14 operator (OR), shows Addition rule : when p =T (the hypothesis selects the first two lines of the table), we see (at column-14) that p ∨q =T.
We can see also that, with the same premise, another conclusions are valid: columns 12, 14 and 15 are T.
The column-8 operator (AND), shows Simplification rule : when p ∧q =T (first line of the table), we see that p =T.
With this premise, we also conclude that q =T, p ∨q =T, etc. as shown by columns 9–15.
The column-11 operator (IF/THEN), shows Modus ponens rule : when p →q =T and p =T only one line of the truth table (the first) satisfies these two conditions. On this line, q is also true. Therefore, whenever p → q is true and p is true, q must also be true.
Machines and well-trained people use this look at table approach to do basic inferences, and to check if other inferences (for the same premises) can be obtained.
Example 1 [ edit ]
Consider the following assumptions: "If it rains today, then we will not go on a canoe today. If we do not go on a canoe trip today, then we will go on a canoe trip tomorrow. Therefore (Mathematical symbol for "therefore" is
∴
{\displaystyle \therefore }
), if it rains today, we will go on a canoe trip tomorrow".
To make use of the rules of inference in the above table we let
p
{\displaystyle p}
be the proposition "If it rains today",
q
{\displaystyle q}
be "We will not go on a canoe today" and let
r
{\displaystyle r}
be "We will go on a canoe trip tomorrow". Then this argument is of the form:
p
→
q
q
→
r
∴
p
→
r
¯
{\displaystyle {\begin{aligned}p\rightarrow q\\q\rightarrow r\\\therefore {\overline {p\rightarrow r}}\\\end{aligned}}}
Example 2 [ edit ]
Consider a more complex set of assumptions: "It is not sunny today and it is colder than yesterday". "We will go swimming only if it is sunny", "If we do not go swimming, then we will have a barbecue", and "If we will have a barbecue, then we will be home by sunset" lead to the conclusion "We will be home by sunset."
Proof by rules of inference: Let
p
{\displaystyle p}
be the proposition "It is sunny today",
q
{\displaystyle q}
the proposition "It is colder than yesterday",
r
{\displaystyle r}
the proposition "We will go swimming",
s
{\displaystyle s}
the proposition "We will have a barbecue", and
t
{\displaystyle t}
the proposition "We will be home by sunset". Then the hypotheses become
¬
p
∧
q
,
r
→
p
,
¬
r
→
s
{\displaystyle \neg p\wedge q,r\rightarrow p,\neg r\rightarrow s}
and
s
→
t
{\displaystyle s\rightarrow t}
. Using our intuition we conjecture that the conclusion might be
t
{\displaystyle t}
. Using the Rules of Inference table we can prove the conjecture easily:
Step
Reason
1.
¬
p
∧
q
{\displaystyle \neg p\wedge q}
Hypothesis
2.
¬
p
{\displaystyle \neg p}
Simplification using Step 1
3.
r
→
p
{\displaystyle r\rightarrow p}
Hypothesis
4.
¬
r
{\displaystyle \neg r}
Modus tollens using Step 2 and 3
5.
¬
r
→
s
{\displaystyle \neg r\rightarrow s}
Hypothesis
6.
s
{\displaystyle s}
Modus ponens using Step 4 and 5
7.
s
→
t
{\displaystyle s\rightarrow t}
Hypothesis
8.
t
{\displaystyle t}
Modus ponens using Step 6 and 7
See also [ edit ]
References [ edit ]
^ Kenneth H. Rosen: Discrete Mathematics and its Applications , Fifth Edition, p. 58.
Major fields
Foundations Lists