Negative Monotonic Replacement (Propositional Logic)

Definition

Negative Monotonic Replacement (Propositional Logic)

Let $p$ be a pure atom in formula $F$ with negative polarity with $I\models F$. Define

$$I^{\prime }:=I\cup \{p\mapsto 0\}.$$

We can then infer that

$$I^{\prime }\models F,$$

i.e., $I$ with $p$ being false is also a model of $F$.

Proof

Negative Monotonic Replacement (Propositional Logic)

Assume that $I\models F$ and that every occurrence of $p$ in $F$ has negative polarity. The following implication is a tautology:

$$\models \perp \to p.$$

Negative polarity reverses this implication along every path from an occurrence of $p$ to the root. Replacing all occurrences simultaneously therefore gives

$$\models F\to F_p^{\perp }.$$

Since $I\models F$, it follows that

$$1=I(F)\le I(F_p^{\perp }).$$

The right-hand side is a truth value, so $I(F_p^{\perp })=1$. Evaluating $F_p^{\perp }$ under $I$ is the same as evaluating $F$ under $I^{\prime }$, because $I^{\prime }$ assigns $0$ to $p$ and otherwise agrees with $I$. Hence

$$I^{\prime }(F)=I(F_p^{\perp })=1,$$

and therefore $I^{\prime }\models F$.