The following lists some propositional formula equivalences. Remember that we use the symbol ≡ as a relation between two WFFs, not as a connective inside a WFF. In these, φ, ψ, and θ are meta-variables standing for any WFF.
|
Double Complementation |
¬¬φ ≡ φ |
|
|
Complement |
φ ∨ ¬φ ≡ true |
φ ∧ ¬φ ≡ false |
|
Identity |
φ ∨ false ≡ φ |
φ ∧ true ≡ φ |
|
Dominance |
φ ∨ true ≡ true |
φ ∧ false ≡ false |
|
Idempotency |
φ ∨ φ ≡ φ |
φ ∧ φ ≡ φ |
|
Absorption |
φ ∧ (φ ∨ ψ) ≡ φ |
φ ∨ φ ∧ ψ ≡ φ |
|
Redundancy |
φ ∧ (¬φ ∨ ψ) ≡ φ ∧ ψ |
φ ∨ ¬φ ∧ ψ ≡ φ ∨ ψ |
|
DeMorgan's Laws |
¬ (φ ∧ ψ) ≡ ¬φ ∨ ¬ψ |
¬ (φ ∨ ψ) ≡ ¬φ ∧ ¬ψ |
|
Associativity |
φ ∧ (ψ ∧ θ) ≡ (φ ∧ ψ) ∧ θ |
φ ∨ (ψ ∨ θ) ≡ (φ ∨ ψ) ∨ θ |
|
Commutativity |
φ ∧ ψ ≡ ψ ∧ φ |
φ ∨ ψ ≡ ψ ∨ φ |
|
Distributivity |
φ ∧ (ψ ∨ θ) ≡ φ ∧ ψ ∨ φ ∧ θ |
φ ∨ ψ ∧ θ ≡ (φ ∨ ψ) ∧ (φ ∨ θ) |
Equivalences for implication are omitted above for brevity and for tradition. They can be derived, using the definition a ⇒ b ≡¬a ∨ b.
Example 6.1
For example, using Identity and Commutativity, we have true ⇒ b ≡¬true ∨ b ≡ false ∨ b ≡ b ∨ false ≡ b.
- 2155 reads
