Logic Rules Cheat Sheet

When working with logic in discrete math appliations there are a plethora of rules you can use for working with the well formed formulas. Remembering them all can be a daunting task, which is why I like to have a cheat sheet available. As such, here’s a simple one that I like to use when working with these problems.

Equivalence Rules

ExpressionEquivalent ToName of the Rule
Commutative - comm.
Commutative - comm.
Associative - ass.
Associative - ass.
DeMorgan’s Law
DeMorgan’s Law
Implication - imp.
Double Negation - dn.
Definition of Equivalence - equ.

Inference Rules

ExpressionCan DeriveName of the Rule
Modus Ponens - mp.
Modus Tollens - mt.
Conjunction - con.
Simplification - simp.
Addition - add.
Hypothetical Syllogism - hs
Disjunctive Syllogism - ds.
Contraposition - cont.
Contraposition - cont.
Self Reference - self.
Self Reference - self.
Exportation - exp.
Inconsistency - inc.

Derivation Rules

The general workflow for using derivation rules is:

  • Strip off the quantifiers
  • Work with the independent well formed formulas
  • Insert the quantifiers back in

Universal Instantiation - ui.: From we can deduce .

Note: t must not already appear as a variable in the expression for .

Existential Instantiation - ei.: From we can deduce .

Note: t must be introduced for the first time. As such, you will want to do these early in proofs.

Universal Generalization - ug.: From we can deduce .

Notes:

  • hasn’t been deduced by existential instantiation from any hypothesis in which x was a free variable.
  • hasn’t been deduced by existential instantiation from another wff in which x was a free variable.

Existential Generalization - eg.: From we can deduce .

Note: x must not appear in .