Subsection 3.7.3 Appendices
Boolean Identities
Double Negation : p ≡ ¬(¬ p )
Equivalence: ( p ≡ q ) ≡ ( p → q ) ∧ ( q → p )
Idempotence: ( p ∧ p ) ≡ p
( p ∨ p ) ≡ p
DeMorgan 1 : (¬( p ∧ q )) ≡ (¬ p ∨ ¬ q )
DeMorgan 2 : ¬( p ∨ q ) ≡ (¬ p ∧ ¬ q )
Commutativity of or : ( p ∨ q ) ≡ ( q ∨ p )
Commutativity of and : ( p ∧ q ) ≡ ( q ∧ p )
Associativity of or : ( p ∨ ( q ∨ r )) ≡ (( p ∨ q ) ∨ r )
Associativity of and : ( p ∧ ( q ∧ r )) ≡ (( p ∧ q ) ∧ r )
Distributivity of and over or : ( p ∧ ( q ∨ r )) ≡ (( p ∧ q ) ∨ ( p ∧ r ))
Distributivity of or over and : ( p ∨ ( q ∧ r )) ≡ (( p ∨ q ) ∧ ( p ∨ r ))
Conditional Disjunction : ( p → q ) ≡ (¬ p ∨ q )
Contrapositive : ( p → q ) ≡ (¬ q → ¬ p )
Boolean Inference Rules
Modus Ponens : From p and p → q , infer q
Modus Tollens : From p → q and ¬ q , infer ¬ p . . .
Disjunctive Syllogism : From p ∨ q and ¬ q , infer p . . .
Simplification : From p ∧ q , infer p . . .
Addition : From p , infer p ∨ q . . .
Conjunction : From p and q , infer p ∧ q
Hypothetical Syllogism : From p → q and q → r , infer p → r
Contradictory Premises : From p and ¬ p , infer q
Resolution : From p ∨ q and ¬ p ∨ r , infer q ∨ r . . .
Conditionalization: Assume premises A.
Then, if ( A ∧ p ) entails q, infer p → q
Computation
p ∨ ¬ p ≡ T ¬ p ∨ p ≡ T
p ∧ ¬ p ≡ F ¬ p ∧ p ≡ F
p ∨ T ≡ T T ∨ p ≡ T
p ∨ F ≡ p F ∨ p ≡ p
p ∧ T ≡ p T ∧ p ≡ p
p ∧ F ≡ F F ∧ p ≡ F
p ∨ ¬ p ≡ T ¬ p ∨ p ≡ T
p ∧ ¬ p ≡ F ¬ p ∧ p ≡ F
p ∨ T ≡ T T ∨ p ≡ T
p ∨ F ≡ p F ∨ p ≡ p
p ∧ T ≡ p T ∧ p ≡ p
p ∧ F ≡ F F ∧ p ≡ F
A Useful Axiom
Law of the Excluded Middle: p ∨ ¬ p