======================================================================
=                        Logical equivalence                         =
======================================================================

                            Introduction
======================================================================
In logic and mathematics, statements p and q are said to be logically
equivalent, if they are provable from each other under a set of
axioms, or have the same truth value in every model. The logical
equivalence of p and q is sometimes expressed as p \equiv q,
\textsf{E}pq, or p \iff q, depending on the notation being used.
However, these symbols are also used for material equivalence, so
proper interpretation would depend on the context. Logical equivalence
is different from material equivalence, although the two concepts are
intrinsically related.


                        Logical equivalences
======================================================================
In logic, many common logical equivalences exist and are often listed
as laws or properties. The following tables illustrate some of these.

=== General logical equivalences ===
'Equivalence' !! 'Name'
p \wedge \top \equiv p p \vee \bot \equiv p      Identity laws
p \vee \top \equiv \top p \wedge \bot \equiv \bot        Domination laws
p \vee p \equiv p p \wedge p \equiv p    Idempotent laws
\neg (\neg p) \equiv p   Double negation law
p \vee q \equiv q \vee p p \wedge q \equiv q \wedge p    Commutative
laws
(p \vee q) \vee r \equiv p \vee (q \vee r) (p \wedge q) \wedge r
\equiv p \wedge (q \wedge r)     Associative laws
p \vee (q \wedge r) \equiv (p \vee q) \wedge (p \vee r) p \wedge (q
\vee r) \equiv (p \wedge q) \vee (p \wedge r)    Distributive laws
\neg (p \wedge q) \equiv  \neg p \vee \neg q \neg (p \vee q) \equiv
\neg p \wedge \neg q     De Morgan's laws
p \vee (p \wedge q) \equiv p p \wedge (p \vee q) \equiv p
Absorption laws
p \vee \neg p \equiv \top p \wedge \neg p \equiv \bot    Negation laws


Logical equivalences involving conditional statements
=======================================================
:#p \implies q \equiv \neg p \vee q
:#p \implies q \equiv \neg q \implies \neg p
:#p \vee q \equiv \neg p \implies q
:#p \wedge q \equiv \neg (p \implies \neg q)
:#\neg (p \implies q) \equiv p \wedge \neg q
:#(p \implies q) \wedge (p \implies r) \equiv p \implies (q \wedge r)
:#(p \implies q) \vee (p \implies r) \equiv p \implies (q \vee r)
:#(p \implies r) \wedge (q \implies r) \equiv (p \vee q) \implies r
:#(p \implies r) \vee (q \implies r) \equiv (p \wedge q) \implies r


Logical equivalences involving biconditionals
===============================================
:#p \iff q \equiv (p \implies q) \wedge (q \implies p)
:#p \iff q \equiv \neg p \iff \neg q
:#p \iff q \equiv (p \wedge q) \vee (\neg p \wedge \neg q)
:#\neg (p \iff q) \equiv p \iff \neg q


In logic
==========
The following statements are logically equivalent:

#If Lisa is in Denmark, then she is in Europe (a statement of the form
d \implies e).
#If Lisa is not in Europe, then she is not in Denmark (a statement of
the form \neg e \implies \neg d).

Syntactically, (1) and (2) are derivable from each other via the rules
of contraposition and double negation.  Semantically, (1) and (2) are
true in exactly the same models (interpretations, valuations); namely,
those in which either 'Lisa is in Denmark' is false or 'Lisa is in
Europe' is true.

(Note that in this example, classical logic is assumed. Some
non-classical logics do not deem (1) and (2) to be logically
equivalent.)


In mathematics
================
In mathematics, two statements p and q are often said to be logically
equivalent, if they are provable from each other given a set of axioms
and presuppositions. For example, the statement "n is divisible by 6"
can be regarded as equivalent to the statement "n is divisible by 2
and 3", since one can prove the former from the latter (and vice
versa) using some knowledge from basic number theory.


                  Relation to material equivalence
======================================================================
Logical equivalence is different from material equivalence. Formulas p
and q are logically equivalent if and only if the statement of their
material equivalence (p \iff q)  is a tautology.

The material equivalence of p and q (often written as p \iff q) is
itself another statement in the same object language as p and q. This
statement expresses the idea "'p if and only if q'". In particular,
the truth value of p \iff q can change from one model to another.

On the other hand, the claim that two formulas are logically
equivalent is a statement in the metalanguage, which expresses a
relationship between two statements p and q. The statements are
logically equivalent if, in every model, they have the same truth
value.


                              See also
======================================================================
* Entailment
* Equisatisfiability
* If and only if
* Logical biconditional
* Logical equality


License
=========
All content on Gopherpedia comes from Wikipedia, and is licensed under CC-BY-SA
License URL: http://creativecommons.org/licenses/by-sa/3.0/
Original Article: http://en.wikipedia.org/wiki/Logical_equivalence

You are viewing proxied material from sdf.org. The copyright of proxied material belongs to its original authors. Any comments or complaints in relation to proxied material should be directed to the original authors of the content concerned. Please see the disclaimer for more details.