Equivalent Replacement (Propositional Logic)

logic propositional-logic

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 }$.

Lemma

Equivalent Replacement

Let $I$ be an interpretation. If

$$I\models B_1\leftrightarrow B_2,$$

then

$$I\models A[B_1]\leftrightarrow A[B_2].$$

In other words, if two subformulas have the same truth value under $I$, then replacing one fixed occurrence of one by the other does not change the truth value of the whole propositional formula under $I$.

Intuition

Compositionality

The truth value of a propositional formula depends on the truth values of its immediate parts. Therefore, if one occurrence of a subformula is replaced by another with the same value under the same interpretation, the value of the whole formula stays the same.