Natural Deduction Rules for Sentential Logic
(Revised 5 January 2011)
Note: in the following rules, the greek letters "φ" and
"ψ" are names of SL wffs.
A (Rule of Assumption)
You can write down any SL wff, depending on itself.
&I (Conjunction Introduction)
If you have derived φ and ψ,
you can write down (φ&ψ),
depending on everything φ and ψ depend on.
&E (Conjunction Elimination)
If you have derived (φ&ψ),
you can write down φ or ψ,
depending on everything (φ&ψ) depends on.
→I (Conditional Introduction)
If you have assumed φ, and you have derived ψ,
you can write down (φ→ψ),
depending on everything ψ depends on except φ.
→E (Conditional Elimination or Modus Ponens)
If you have derived (φ→ψ)
and φ,
you can write down ψ,
depending on everything (φ→ψ)
and φ depend on.
~I (Negation Introduction)
If you have assumed ψ, and you have derived (φ&~φ),
then you can write down ~ψ,
depending on everything (φ&~φ) depends on except ψ.
~E (Negation Elimination)
If you have assumed ~ψ, and you have derived (φ&~φ),
then you can write down ψ,
depending on everything (φ&~φ) depends on except ~ψ.
∨I (Disjunction Introduction)
If you have derived φ,
you can write down (φ∨ψ)
or (ψ∨φ),
depending on everything φ depends on.
(ψ is any SL wff.)
∨E (Disjunction Elimination or Disjunctive
Syllogism)
If you have derived (φ∨ψ)
and ~ψ,
you can write down φ,
depending on everything (φ∨ψ)
and ~ψ depend on.
If you have derived (φ∨ψ)
and ~φ,
you can write down ψ,
depending on everything (φ∨ψ)
and ~φ depend on.
PC (Proof by Cases)
If you have derived (φ∨ψ)
and (φ→α)
and (ψ→β),
then you can write down (α∨β),
depending on everything (φ∨ψ)
and
(φ→α)
and (ψ→β)
depend on.
↔I (Biconditional Introduction)
If you have derived ((φ→ψ)&(ψ→φ)),
you can write down (φ↔ψ),
depending on everything ((φ→ψ)&(ψ→φ))
depends on.
↔E (Biconditional Elimination)
If you have derived (φ↔ψ),
you can write down ((φ→ψ)&(ψ→φ))
depending on everything (φ↔ψ)
depends on.