Substitution (Logic)

Logical substitution is the process of remapping the syntax (i.e. the symbols) of a formula. Depending on the type of logic, i.e. whether we are considering propositional logic or predicate logic, different operations may be allowed.

In Propositional Logic §

A formula, $\phi$, can be substituted by replacing every occurrence of one or more atoms with propositions.

For example, take the formula:

$$\phi :\neg (P\wedge Q)$$

We can convert this to a disjunction by substituting $P$ with $\neg P$ and $Q$ with $\neg Q$:

$$\phi [P:=\neg P,Q:=\neg Q]:\neg (\neg P\wedge \neg Q)$$

If we let $\rho :\neg (\neg P\wedge \neg Q)$, then $\rho$ is a substitution instance of $\phi$

Interchange of Equivalent Formulae §

Theorem T2 means we can actually replace a formula with any logically equivalent form.

Let us start by assuming that $\neg \neg P\equiv P$ (we know that this is true, anyway, but for now we assume it is true).

#tosee how we can convert the LHS of the above to RHS??

Theorems §

T1: Substitution preserves valid formulae

One way to see this is in propositional logic, a tautology (which is the propositional version of a valid formula) is unchanged after a substitution.

$$\begin{array}{rl}\phi & :P\to P\\ \phi [P:=(R\wedge S)]& :(R\wedge S)\to (R\wedge S)\end{array}\text{\hspace{1em}(Tautology)(Still a tautology...)}$$

C1: Substitution preserves unsatisfiable formulae

This can be derived from T1 since we can take the negation of the tautology, which produces a contradiction. Since the negation is a unary operation and does introduce any new atoms, we cannot add new substitutions that are different from those applied on T1.#tosee ???

T2: Substitution preserves logical equivalence

If we have two formulae $F$ and $G$ that are logically equivalent, then any substitutions applied on both formulae preserves this equivalence:

$$\text{If }F\equiv G,\text{ then }F[P:=H]\equiv G[P:=H]$$

where $P$ can be any atom and $H$ is a formula.