Standard simplification / rewriting rules for propositional
logic
Remember that every simplificaion / rewriting rule is based on a
tautology with an equivalence ($\Leftrightarrow$) on the top level!
- associativity/commutitivity/distributivity - you need
to remember which operators these apply to!
- De Morgan's Laws
$\neg(a\vee b) \Leftrightarrow \neg a \wedge \neg b$
$\neg(a\wedge b) \Leftrightarrow \neg a \vee \neg b$
- $\neg \neg a \Leftrightarrow a$ : double negation
- $(a \Rightarrow b) \Leftrightarrow (\neg b \Rightarrow
\neg a)$ : equivalence of the contrapositive
- $\neg(a \Leftrightarrow b) \Leftrightarrow (a \Leftrightarrow \neg b)$
: negation-of-equivalence
- $a \Rightarrow b \Leftrightarrow \neg a \vee b$ :
implication rewriting
-
$(a \Leftrightarrow b) \Leftrightarrow (a \Rightarrow b)
\wedge (b \Rightarrow a)$ : equivalence splitting
-
$(a \vee a) \Leftrightarrow a$: Idempotence $\vee$
$(a \wedge a) \Leftrightarrow a$: Idempotence $\wedge$
Standard deduction rules for propositional logic
Remember that every deduction rule is based on a
tautology with an implication ($\Rightarrow$) on the top level!
-
Modus ponens: If you know $A \Rightarrow B$ and $A$ are true, you
may deduce $B$ is true. [ Based on tautology
$(A \Rightarrow B) \wedge A \Rightarrow B$ ]
-
And-elimination: If you know $A \wedge B$ is true, you
may deduce $A$ is true. [ Based on tautology
$A \wedge B \Rightarrow A$ ]
-
Or-introduction: If you know $A$ is true, you
may deduce $A \vee B$ is true. [ Based on tautology
$A \Rightarrow (A \vee B)$ ]
-
And-introduction: If you know $A$ is true and you
know $B$ is true, you
may deduce $A \wedge B$ is true. [ Yes it's obvious! ]
-
Warning! There is no "Or-elimination" rule!