<em class="emphasis"><dfn class="terminology">Boolean Identities</dfn></em>

Skip to main content

\(\newcommand{\N}{\mathbb N} \newcommand{\Z}{\mathbb Z} \newcommand{\Q}{\mathbb Q} \newcommand{\R}{\mathbb R} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \definecolor{fillinmathshade}{gray}{0.9} \newcommand{\fillinmath}[1]{\mathchoice{\colorbox{fillinmathshade}{$\displaystyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\textstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptscriptstyle\phantom{\,#1\,}$}}} \)

Subsection 5.4.1 Boolean Identities

Table 5.4.1. Ambiguous Keyboard Characters and Alternatives


Double Negation	\(p\) \(\equiv \neg(\neg p) \)
Equivalence:	\((p \equiv q) \equiv (p \rightarrow q ) ∧ ( q \rightarrow p )\)
Idempotence:	\((p ∧ p) \equiv p \)
	\((p \vee p) \equiv p \)
DeMorgan1:	\((¬(p ∧ q)) \equiv (¬p ∨ ¬q)\)
DeMorgan2:	\(\neg (p \vee q) \equiv (\neg p \wedge \neg q)\)
Commutativity of or	\((p ∨ q) \equiv (q ∨ p)\)
Commutativity of and	\((p ∧ q) \equiv (q ∧ p)\)
Associativity of or	\((p ∨ (q ∨ r)) \equiv ((p ∨ q) ∨ r)\)
Associativity of and	\((p ∧ (q ∧ r)) \equiv ((p ∧ q) ∧ r)\)
Distributivity of and over or	\((p ∧ (q ∨ r)) \equiv ((p ∧ q) ∨ (p ∧ r))\)
Distributivity of or over and	\((p ∨ (q ∧ r)) \equiv ((p ∨ q) ∧ (p ∨ r))\)
Conditional Disjunction	\((p \rightarrow q) \equiv (¬p ∨ q)\)
Contrapositive	\((p \rightarrow q) \equiv (¬q \rightarrow ¬p)\)

Table 5.4.2. Boolean Inference Rules


Modus Ponens	From \(p and p \rightarrow q\)	infer \(q\)
Modus Tollens	From \(p \rightarrow q and \neg q\)	infer \(\neg p \cdots\)
Disjunctive Syllogism	From \(p ∨ q and ¬q\)	infer \(p \cdots \)
Simplification	From \(p ∧ q \)	infer \(p \cdots \)
Addition	From \(p\)	infer \(p ∨ q \cdots \)
Conjunction	From p and q	infer \(p ∧ q\)
Hypothetical Syllogism	From \(p \rightarrow q and q \rightarrow r \)	infer \(p \rightarrow r \)
Contradictory Premises	From \(p and ¬p \)	infer \(q\)
Resolution	From p ∨ q and ¬p ∨ r	infer q ∨ \(r \cdots \)
Conditionalization:	Assume premises A.
	Then, if (A ∧ p) entails q	infer \(p \rightarrow q\)

Table 5.4.3. A Useful Axiom


Law of the Excluded Middle:	\(p ∨ ¬p\)

Table 5.4.4. Quantifier Exchange


Quantifier Exchange A:	\(\equiv ¬(∃x (P(x))\)
Quantifier Exchange B:	\(\equiv ¬(∃x (P(x))\)

Table 5.4.5. Instantiation and Generalization


Universal Instantiation:	From \(∀x (P(x))\)	infer \(P(c/x)\)
Universal Generalization:	From \(P(c/x)\)	infer \(∀x (P(x)) \)
Existential Instantiation:	From \(∃x (P(x))\)	infer \(P(c*/x)\)
Existential Generalization:	From \(P(c/x)\)	infer \(∃x (P(x))\)