Logical Strength

logic

Definition

Logical Strength

Let $\varphi$ and $\psi$ be formulas in a formal language. The formula $\varphi$ is logically stronger than $\psi$ if $\varphi$ entails $\psi$:

$$\varphi \models \psi$$

Equivalently, every interpretation that satisfies $\varphi$ also satisfies $\psi$.

If $\varphi \models \psi$ and $\psi /\models \varphi$, then $\varphi$ is strictly stronger than $\psi$.

If $\varphi \models \psi$ and $\psi \models \varphi$, then $\varphi$ and $\psi$ are logically equivalent.

A stronger formula has fewer models. The weakest formula is $\top$ and the strongest formula is $\perp$.

Weak and Strong Formulas

A formula $F$ is stronger than a formula $G$ when $F$ entails $G$:

$$F\Rightarrow G$$

This means that every model of $F$ is also a model of $G$:

$$\{F\}\subseteq \{G\}$$

Equivalently, $G$ is weaker than $F$ when $G$ is implied by $F$:

$$G\Rightarrow F$$

and then

$$\{G\}\subseteq \{F\}$$

Square Subset Notation

In some contexts (e.g., lattice theory or abstract semantics), logical strength is denoted using “square subset” notation to emphasise the ordering of cases:

$$\varphi ⊑\psi ⟺\mathcal{M}(\varphi )\subseteq \mathcal{M}(\psi )$$

• $\varphi ⊑\psi$: $\varphi$ is stronger than (or equal to) $\psi$.
• $\varphi ⊏\psi$: $\varphi$ is strictly stronger than $\psi$.
• $\varphi ⊒\psi$: $\varphi$ is weaker than (or equal to) $\psi$.

Examples

$x=y$ stronger than $x\ge y$

$x=y$ is stronger than $x\ge y$ because equality implies inequality. Every assignment that satisfies $x=y$ also satisfies $x\ge y$.

$$\{x=y\}\subseteq \{x\ge y\}$$

$x>y$ weaker than $x=y+1$

$x>y$ is weaker than $x=y+1$ because every assignment satisfying $x=y+1$ also satisfies $x>y$.

$$\{x=y+1\}\subseteq \{x>y\}$$

$1$ is the weakest formula

The formula $1$ (true) is the weakest formula. Every other formula implies it, so its satisfaction set is the whole state space.

$$\{1\}=\mathcal{S}$$

$0$ is the strongest formula

The formula $0$ (false) is the strongest formula. It implies every formula, but no non-trivial formula implies it.

$$\{0\}=\varnothing$$

$x=2$ and $x>y$ are incomparable

Neither formula implies the other. There are assignments where $x=2$ holds but $x>y$ does not, and assignments where $x>y$ holds but $x=2$ does not.