Mutual Entailment

logic

Definition

Mutual Entailment

Two formulas mutually entail each other (are equivalent) if they have the same truth value under every interpretation.

$$A\equiv B:⟺A\models B\wedge B\models A$$

Hence, there is no interpretation that makes one of them true and the other false, so we cannot distinguish them semantically. Semantic equivalence is an equivalence relation on formulas.

Proof

Mutual Entailment

Let $v$ be an arbitrary interpretation. Assume that $v(A)=\top$. Then:

$$A\vee B=\top$$

Since $A\vee B\models A\wedge B$, it follows that:

$$v(A\wedge B)=\top$$

Hence $v(B)=\top$, so $A\models B$.

Symmetrically, we can assume that $v(B)=\top$, then:

$$v(A\vee B)=\top$$

Since $A\vee B\models A\wedge B$, it follows that:

$$v(A\wedge B)=\top$$

Hence $v(A)=\top$, so $B\models A$.

We have $A\models B$ and $B\models A$. Hence, there is no interpretation that makes one of them true and the other false, so we cannot distinguish them semantically. Therefore:

$$v(A)=v(P)\text{ for all }v$$

which means:

$$A\equiv B$$

Equivalent Replacement

Definition

Equivalent Replacement ( Propositional Logic)

Let $A[B]$ denote a propositional formula $A$ with one fixed occurrence of a subformula $B$.

Formally, that fixed occurrence may be identified by a propositional formula position in $A$.

Let $A[B\to B^{\prime }]$ denote the propositional formula obtained from $A$ by replacing that fixed occurrence of $B$ by $B^{\prime }$.

Link to original