Definition:Logical Equivalence

From ProofWiki
(Redirected from Definition:Interderivable)
Jump to navigation Jump to search

Definition

If two statements $p$ and $q$ are such that:

$p \vdash q$, that is: $p$ therefore $q$
$q \vdash p$, that is: $q$ therefore $p$

then $p$ and $q$ are said to be (logically) equivalent.


That is:

$p \dashv \vdash q$

means:

$p \vdash q$ and $q \vdash p$


Note that because the conclusion of an argument is a single statement, there can be only one statement on either side of the $\dashv \vdash$ sign.


In symbolic logic, the notion of logical equivalence occurs in the form of provable equivalence and semantic equivalence.


Provable Equivalence

Let $\mathscr P$ be a proof system for a formal language $\LL$.

Let $\phi, \psi$ be $\LL$-WFFs.


Then $\phi$ and $\psi$ are $\mathscr P$-provably equivalent if and only if:

$\phi \vdash_{\mathscr P} \psi$ and $\psi \vdash_{\mathscr P} \phi$

that is, if and only if they are $\mathscr P$-provable consequences of one another.


The provable equivalence of $\phi$ and $\psi$ can be denoted by:

$\phi \dashv \vdash_{\mathscr P} \psi$


Semantic Equivalence

Let $\mathscr M$ be a formal semantics for a formal language $\LL$.

Let $\phi, \psi$ be $\LL$-WFFs.


Then $\phi$ and $\psi$ are $\mathscr M$-semantically equivalent if and only if:

$\phi \models_{\mathscr M} \psi$ and $\psi \models_{\mathscr M} \phi$

that is, if and only if they are $\mathscr M$-semantic consequences of one another.


Also known as

Two logically equivalent statements are also referred to as:


Also denoted as

Some sources denote $p \dashv \vdash q$ by $p \leftrightarrow q$.

Others use $p \equiv q$.


In modal logic, logical equivalence is expressed as:

$\Box \paren {p \equiv q}$


On $\mathsf{Pr} \infty \mathsf{fWiki}$, during the course of development of general proofs of logical equivalence, the notation $p \leadstoandfrom q$ is used as a matter of course.


The $\LaTeX$ code for \(p \leadstoandfrom q\) is p \leadstoandfrom q .

The $\LaTeX$ code for \(\Box \paren {p \equiv q}\) is \Box \paren {p \equiv q} .


Note that in Distinction between Logical Implication and Conditional, the distinction between $\implies$ and $\leadsto$ is explained.

In the same way, $\leadstoandfrom$ and $\iff$ are not the same -- it makes no sense to write:

$A \iff B \iff C$

when what should be written is:

$A \leadstoandfrom B \leadstoandfrom C$


Also see

  • Results about logical equivalence can be found here.


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Definition:Logical_Equivalence&oldid=696993"