Editing Logical equivalence

{{Short description|Concept in logic}}
In [[logic]] and [[mathematics]], statements <math>p</math> and <math>q</math> are said to be '''logically equivalent''' if they have the same [[truth value]] in every [[model (logic)|model]].<ref>{{Cite book|title=Introduction to Mathematical Logic|url=https://archive.org/details/introductiontoma00mend|url-access=limited|last=Mendelson|first=Elliott|authorlink = Elliott Mendelson|year=1979|edition=2|pages=[https://archive.org/details/introductiontoma00mend/page/n63 56]|publisher=Van Nostrand |isbn=9780442253073}}</ref> The logical equivalence of <math>p</math> and <math>q</math> is sometimes expressed as <math>p \equiv q</math>, <math>p :: q</math>, <math>\textsf{E}pq</math>, or <math>p \iff q</math>, 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 ===
{| class="wikitable"
|-
! ''Equivalence'' !! ''Name''
|-
| <math>p \wedge \top \equiv p</math><br /><math>p \vee \bot \equiv p</math> || Identity laws
|-
| <math>p \vee \top \equiv \top</math><br /><math>p \wedge \bot \equiv \bot</math> || Domination laws
|-
| <math>p \vee p \equiv p</math><br /><math>p \wedge p \equiv p</math> || Idempotent or tautology laws
|-
| <math>\neg (\neg p) \equiv p</math> || [[Double negation]] law
|-
| <math>p \vee q \equiv q \vee p</math><br /><math>p \wedge q \equiv q \wedge p</math> || [[Commutative law]]s
|-
| <math>(p \vee q) \vee r \equiv p \vee (q \vee r)</math><br /><math>(p \wedge q) \wedge r \equiv p \wedge (q \wedge r) </math>|| [[Associative law]]s
|-
| <math>p \vee (q \wedge r) \equiv (p \vee q) \wedge (p \vee r)</math><br /><math>p \wedge (q \vee r) \equiv (p \wedge q) \vee (p \wedge r)</math> || [[Distributive law]]s
|-
| <math>\neg (p \wedge q) \equiv  \neg p \vee \neg q</math><br /><math>\neg (p \vee q) \equiv  \neg p \wedge \neg q</math> || [[De Morgan's laws]]
|-
| <math>p \vee (p \wedge q) \equiv p</math><br /><math>p \wedge (p \vee q) \equiv p</math> || [[Absorption law]]s
|-
| <math>p \vee \neg p \equiv \top</math><br /><math>p \wedge \neg p \equiv \bot</math> || Negation laws
|}

=== Logical equivalences involving conditional statements ===

:#<math>p \rightarrow q \equiv \neg p \vee q</math>
:#<math>p \rightarrow q \equiv \neg q \rightarrow \neg p</math>
:#<math>p \vee q \equiv \neg p \rightarrow q</math>
:#<math>p \wedge q \equiv \neg (p \rightarrow \neg q)</math>
:#<math>\neg (p \rightarrow q) \equiv p \wedge \neg q</math>
:#<math>(p \rightarrow q) \wedge (p \rightarrow r) \equiv p \rightarrow (q \wedge r)</math>
:#<math>(p \rightarrow q) \vee (p \rightarrow r) \equiv p \rightarrow (q \vee r)</math>
:#<math>(p \rightarrow r) \wedge (q \rightarrow r) \equiv (p \vee q) \rightarrow r</math>
:#<math>(p \rightarrow r) \vee (q \rightarrow r) \equiv (p \wedge q) \rightarrow r</math>

=== Logical equivalences involving biconditionals ===

:#<math>p \leftrightarrow q \equiv (p \rightarrow q) \wedge (q \rightarrow p)</math>
:#<math>p \leftrightarrow q \equiv \neg p \leftrightarrow \neg q</math>
:#<math>p \leftrightarrow q \equiv (p \wedge q) \vee (\neg p \wedge \neg q)</math>
:#<math>\neg (p \leftrightarrow q) \equiv \neg p \leftrightarrow q</math>
:#<math>\neg (p \leftrightarrow q) \equiv p \leftrightarrow \neg q</math>
:#<math>\neg (p \leftrightarrow q) \equiv p \oplus q</math>

Where <math>\oplus</math> represents [[XOR]].

==Examples==

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

#If Lisa is in [[Denmark]], then she is in [[Europe]] (a statement of the form <math>d \rightarrow e</math>).
#If Lisa is not in Europe, then she is not in Denmark (a statement of the form <math>\neg e \rightarrow \neg d</math>).

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 logic]]s do not deem (1) and (2) to be logically equivalent.)

==Relation to material equivalence==

Logical equivalence is different from material equivalence. Formulas <math>p</math> and <math>q</math> are logically equivalent if and only if the statement of their material equivalence (<math>p \leftrightarrow q</math>)  is a tautology.<ref>{{Cite book|title=Introduction to Logic|last1=Copi|first1=Irving|author1link = Irving Copi|last2=Cohen|first2=Carl|author2link = Carl Cohen (philosopher)|last3=McMahon|first3=Kenneth|publisher=Pearson|year=2014|edition=New International|pages=348}}</ref>

The material equivalence of <math>p</math> and <math>q</math> (often written as <math>p \leftrightarrow q</math>) is itself another statement in the same [[formal system|object language]] as <math>p</math> and <math>q</math>. This statement expresses the idea "'<math>p</math> if and only if <math>q</math>'". In particular, the truth value of <math>p \leftrightarrow q</math> can change from one model to another.

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

==See also==
{{Portal|Philosophy|Psychology}}
* [[Logical consequence|Entailment]]
* [[Equisatisfiability]]
* [[If and only if]]
* [[Logical biconditional]]
* [[Logical equality]]
* [[Mathematical Operators (Unicode block)#Block|≡]] the iff symbol (U+2261 ''IDENTICAL TO'')
* [[Mathematical Operators (Unicode block)#Block|∷]] the ''a'' is to ''b'' '''as''' ''c'' is to ''d'' symbol (U+2237 ''PROPORTION'')
* [[Arrows (Unicode_block)#Block|⇔]] the [[Blackboard bold|double struck]] biconditional (U+21D4 ''LEFT RIGHT DOUBLE ARROW'')
* [[Arrow (symbol)#Arrows_in_Unicode|↔]] the bidirectional arrow (U+2194 ''LEFT RIGHT ARROW'')

== References ==
{{reflist}}

{{Mathematical logic}}
{{DEFAULTSORT:Logical Equivalence}}

[[Category:Mathematical logic]]
[[Category:Metalogic]]
[[Category:Logical consequence]]
[[Category:Equivalence (mathematics)]]