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
$$ P \lor Q $$$$ Q \lor P $$Commutative – comm.
$$ P \land Q $$$$ Q \land P $$Commutative – comm.
$$\left(P\lor Q\right)\lor R$$$$P \lor\left(Q\lor R\right)$$Associative – ass.
$$\left(P\land Q\right)\land R$$$$P\land\left(Q\land R\right)$$Associative – ass.
$$\left(P\lor Q\right)’$$$$P’\land Q’$$DeMorgan’s Law
$$\left(P\land Q\right)’$$$$P’\lor Q’$$DeMorgan’s Law
$$P\rightarrow Q$$$$P’\lor Q$$Implication – imp.
$$P$$$$\left(P’\right)’$$Double Negation – dn.
$$P\iff Q$$$$\left(P\rightarrow Q\right)\land\left(Q\rightarrow P\right)$$Definition of Equivalence – equ.

Inference Rules

ExpressionCan DeriveName of the Rule
$$P,\ P\rightarrow Q$$$$Q$$Modus Ponens – mp.
$$P\rightarrow Q,\ Q’$$$$P’$$Modus Tollens – mt.
$$P,\ Q$$$$P\land Q$$Conjunction – con.
$$P\land Q$$$$P,\ Q$$Simplification – simp.
$$P$$$$P\lor Q$$Addition – add.
$$P\rightarrow Q,\ Q\rightarrow R$$$$P\rightarrow R$$Hypothetical Syllogism – hs
$$P\lor Q,\ P’$$$$Q$$Disjunctive Syllogism – ds.
$$P\rightarrow Q$$$$Q’\rightarrow P’$$Contraposition – cont.
$$Q’\rightarrow P’$$$$P\rightarrow Q$$Contraposition – cont.
$$P$$$$P\land P$$Self Reference – self.
$$P\lor P$$$$P$$Self Reference – self.
$$\left(P\land Q\right)\rightarrow R$$$$P\rightarrow\left(Q\rightarrow R\right)$$Exportation – exp.
$$P,\ P’$$$$Q$$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 $$\left(\forall x\right)P\left(x\right)$$ we can deduce $$P\left(t\right)$$.

Note: t must not already appear as a variable in the expression for $$P\left(x\right)$$.

Existential Instantiation – ei.:
From $$\left(\exists x\right)P\left(x\right)$$ we can deduce $$P\left(t\right)$$.

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

Universal Generalization – ug.:
From $$P\left(x\right)$$ we can deduce $$\left(\forall x\right)P\left(x\right)$$.

Notes:

  • $$P\left(x\right)$$ hasn’t been deduced by existential instantiation from any hypothesis in which x was a free variable.
  • $$P\left(x\right)$$ hasn’t been deduced by existential instantiation from another wff in which x was a free variable.

Existential Generalization – eg.:
From $$P\left(a\right)$$ we can deduce $$\left(\exists x\right)P\left(x\right)$$.

Note: x must not appear in $$P\left(a\right)$$.