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\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)$$.
