Skip to main content

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