Monotonic Replacement (Propositional Logic)

logic propositional-logic

Definition

Monotonic Replacement ( Propositional Logic)

Let $A$ be a propositional formula, let $\pi$ be a position in $A$, and let $B$ be a propositional formula.

We write $A[B{]}_{\pi }$ for the formula obtained from $A$ by replacing the subformula at position $\pi$ by $B$.

Monotonic replacement is the principle that implication is preserved at a fixed occurrence according to its polarity.

More precisely, if

$$I\models B_1\to B_2,$$

then:

• if $\mathrm{pol}(A,\pi )=1$, replacing $B_1$ by $B_2$ at $\pi$ preserves implication in the same direction;
• if $\mathrm{pol}(A,\pi )=-1$, replacing $B_1$ by $B_2$ at $\pi$ reverses the implication direction.

Intuition

Why implication is enough

Equivalent replacement uses

$$B_1\leftrightarrow B_2,$$

so the chosen occurrence keeps exactly the same truth value.

Monotonic replacement uses only

$$B_1\to B_2.$$

This means that $B_1$ is stronger than $B_2$: whenever $B_1$ is true, $B_2$ is also true. So replacing $B_1$ by $B_2$ makes that occurrence easier to satisfy.

What this does to the whole formula depends on the polarity of the occurrence:

• in a positive occurrence, making the part easier also makes the whole formula easier;
• in a negative occurrence, making the part easier makes the whole formula harder.

So monotonic replacement is one-sided: we do not keep equivalence, we keep only one implication direction.

Positive occurrence

We start with a valid implication

$$p\wedge q\to p.$$

So

$$B_1=p\wedge q,B_2=p.$$

Now put this occurrence in a positive position, for example

$$A=(p\wedge q)\vee r.$$

Replacing the occurrence of $p\wedge q$ by $p$ gives

$$A^{\prime }=p\vee r.$$

Why does

$$A\to A^{\prime }$$

hold? If $(p\wedge q)\vee r$ is true, then either $r$ is already true, or $p\wedge q$ is true. In the second case, $p$ is true as well. Hence $p\vee r$ is true. Therefore

$$(p\wedge q)\vee r\to p\vee r.$$

So replacing a positive occurrence by a weaker formula makes the whole formula weaker.

Negative occurrence

Again start with

$$p\wedge q\to p.$$

Now put the occurrence in a negative position, for example

$$A=\neg (p\wedge q).$$

Replacing $p\wedge q$ by $p$ gives

$$A^{\prime }=\neg p.$$

Here the implication direction reverses. Why does

$$A^{\prime }\to A$$

hold? If $\neg p$ is true, then $p$ is false. Therefore $p\wedge q$ is false as well, so $\neg (p\wedge q)$ is true. Hence

$$\neg p\to \neg (p\wedge q).$$

So replacing a negative occurrence by a weaker formula makes the whole formula stronger.

Lemma

Monotonic Replacement

Let $A,B_1,B_2$ be formulas, let $\pi$ be a position, let $I$ be an interpretation, and assume

$$I\models B_1\to B_2.$$

Then:

$$\mathrm{pol}(A,\pi )=1⟹I\models A[B_1{]}_{\pi }\to A[B_2{]}_{\pi },$$

and

$$\mathrm{pol}(A,\pi )=-1⟹I\models A[B_2{]}_{\pi }\to A[B_1{]}_{\pi }.$$

Proof sketch $B_1\to B_2$, the formula $B_2$ is weaker than $B_1$. In a positive occurrence, replacing $B_1$ by the weaker $B_2$ weakens the whole formula, so $A[B_1{]}_{\pi }\to A[B_2{]}_{\pi }$. In a negative occurrence, the anti-monotonic context reverses the direction, so $A[B_2{]}_{\pi }\to A[B_1{]}_{\pi }$.

Since

Global Form

Positive Polarity

Let $A,B_1,B_2$ be formulas such that

$$\models B_1\to B_2.$$

Let $A^{\prime }$ be obtained from $A$ by replacing one or more positive occurrences of $B_1$ by $B_2$. Then

$$\models A\to A^{\prime }.$$

Negative Polarity

Let $A,B_1,B_2$ be formulas such that

$$\models B_1\to B_2.$$

Let $A^{\prime }$ be obtained from $A$ by replacing one or more negative occurrences of $B_1$ by $B_2$. Then

$$\models A^{\prime }\to A.$$

Special Case

Replacing by $\top$

Since

$$\models p\to \top ,$$

replacing positive occurrences of an atom $p$ by $\top$ yields a one-sided consequence of the original formula. This is the form used in monotonic replacement inside the splitting algorithm.