Reference: propositional equivalences 2.23 2002/03/18 2008/02/06 18:57:53.840 US/Central Ian Barland ibarland@radford.edu John Greiner greiner@cs.rice.edu Phokion Kolaitis kolaitis@cse.ucsc.edu Moshe Vardi vardi@cs.rice.edu Matthias Felleisen matthias@ccs.neu.edu Ian Barland ibarland@radford.edu John Greiner greiner@cs.rice.edu (Blank Abstract) 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. Propositional Logic Equivalences Double Complementation φ φ Complement φ φ φ φ Identity φ φ φ φ Dominance φ φ 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 . For example, using Identity and Commutativity, we have b b b b b .