Home

Inference and replacement rules

A long list

About

This page is meant as a resource on a large number of inference rules. Inference rules are rules that describe when one can validly infer a conclusion from a set of premises. Replacement rules are rules of what one can replace and still have a wff with the same truth-value; in other words, they are a list of logical equivalencies. The main difference between the two set of rules is that the first kind allows valid inference from the first set of propositions (premises) to the second set (the conclusion), but with replacement rules we can validly infer both ways.

The images were creating using ScreenHunter (for image capturing) and Proof Tools (for creating the trees).

Inference rules for propositional logic

Some of the rules are known under multiple names. I have tried to list a few of the popular ones.

Modus Ponens (MP) / Implication Elimination

Form1. P→Q
2. P
⊢ 3. Q

Example
1. If the earth exists, then a planet exists.
2. The earth exists.
Therefore, 3. A planet exists.

Proof tree

Modus Tollens (MT)

Form
1. P→Q
2. ¬Q
⊢ 3. ¬P

Example
1. If Socrates is a man, then Socrates is mortal.
2. Socrates is not mortal.
Therefore, 3. Socrates is not a man.

Proof tree

Hypothetical  Syllogism (HS)

Form
1. P→Q
2. Q→R
⊢ 3. P→R

Example
1. If  it rains, then the street is wet.
2. If the street is wet, then the street is slippery.
Therefore, 3. If it rains, then the street is slippery.

Proof tree

Disjunctive Syllogism (DS)

Form
1. P∨Q
2. ¬P
⊢ 3. Q

Example
1. Socrates is either male or female.
2. Socrates is not female.
Therefore, 3. Socrates is male.

Proof tree

Constructive Dilemma (CD)

Form
1. (P→Q)∧(R→S)
2. P∨R
⊢ 3. Q∨S

Example
1. If Socrates is a man, then Socrates is mortal, and is Plato is a man, then Plato is mortal.
2. Either Socrates or Plato is a man.
Therefore, 3. Either Socrates or Plato is mortal.

Proof tree

Destructive Dilemma (DD)

Form
1. (P→Q)∧(R→S)
2. ¬Q∧¬S
⊢ 3. ¬P∧¬R
1. If Socrates is a woman, then Socrates is dumb, and is Plato is a man, then Plato is dumb.
2. Socrates is not dumb and Plato is not dumb.
Therefore, 3. Socrates is not a woman and Plato is not a man.

Proof tree

Conjunction Introduction (Conj.) / Adjunction

Form
1. P
2. Q
⊢ 3. P∧Q

Example
1. It rains.
2. It is monday.
Therefore, 3. It rains and it is monday.

Proof tree

Simplification (Simp.) / Conjunction Elimination (CE)

Form
1. P∧Q
⊢ 2. P

Example
1. It is tuesday and the sun shines.
Therefore, 2. It is tuesday.

Proof tree

Addition (Add.) / Disjunction Introduction (DI)

Form
1. P
⊢ 2. P∨Q

Example
1. I won the lottery.
Therefore, 2. I won the lottery or I am a woman.

Proof tree

Replacement rules for propositional logic

I will ommit exmaples of these and just list the forms and proofs.

De Morgan's laws

Forms
⊢ ¬(P∧Q)↔(¬P∨¬Q)
⊢ ¬(P∨Q)↔(¬P∧¬Q)
Proof trees

Commutation (Com.)

Forms⊢ P∧Q↔Q∧P
⊢ P∨Q↔Q∨P
Proof trees


Association (Assoc.)

Forms
⊢ ((P∨Q)∨R)↔(P∨(Q∨R))
⊢ (P∧(Q∧R))↔((P∧Q)∧R)
Proof trees


Distrubution (Dist.)

Forms
⊢ (P∧(Q∨R))↔((P∧Q)∨(P∧R))
⊢ (P∨(Q∧R))↔((P∨Q)∧(P∨R))
Proof trees

Double Negation (DN)

Form
⊢ P↔¬¬P
Proof tree

Material Implication (M. Imp.) / Material Conditional

Forms
⊢ (P→Q)↔(¬P∨Q)
⊢ (P→Q)↔¬(P∧¬Q)
Proof trees


Transposition (Trans.) / Contraposition (CP.)

Form
⊢ (P→Q)↔(¬Q→¬P)
Proof tree

Material Bi-implication / Material Equivalence (M. Equiv.)

Forms
⊢ (P↔Q)↔((P→Q)∧(Q→P))
⊢ (P↔Q)↔((P∧Q)∨(¬P∧¬Q))
Proof trees

Exportation

Form⊢ ((P∧Q)→R)↔((P→(Q→R)))
Proof tree

Inference rules for predicate logic

Universal Instantiation (UI)

Form
1. ∀xFx
⊢ 2. Fa

Where "a" is some constant which ∀x quantifies over.

Example:
1. All humans have lungs.
Therefore 2. Socrates has lungs.

Proof tree

Existential Generalization (EG)

Form
1. Fa
⊢ 2. ∃xFx

Example:
1. Socrates has lungs.
⊢ 2. There is someone who has lungs.

Proof tree

Replacement rules for predicate logic

Quantifier rules

⊢ ((∃x)(...))↔(¬(∀x)(¬(...)))

⊢ ((∀x)(...) ↔(¬(∃x)(¬(...)))

"..." can be replaced by whatever as long as it results in a wff. I used "Fx" in my proof.

Proof trees