Home

## Inference and replacement rules

### A long list

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

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.

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

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

Form
⊢ P↔¬¬P
Proof tree

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

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