# 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

Expression Equivalent To Name 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

Expression Can Derive Name 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(x)$$

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(x) hasn’t been deduced by existential instantiation from any hypothesis in which x was a free variable.
• P(x) 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(a)$$