You are here

Propositional equivalences

26 July, 2019 - 12:03
Available under Creative Commons-ShareAlike 4.0 International License. Download for free at http://cnx.org/contents/383d4b87-2d7b-454e-99fe-2eaa43eae8ff@20.20

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.  

Table 6.1 Propositional Logic Equivalences

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 ab ≡¬ab.

Example 6.1

For example, using Identity and Commutativity, we have trueb ≡¬truebfalsebbfalseb.