Substitutionslemma

Dieses Lemma besagt, dass Äquivalenz unter Substitution erhalten bleibt. Es ist die Grundlage für viele logische Umformungen.

Sei $S$ eine Substitution und seien $\varphi ,{\varphi }^{\prime }\in AL$ Formeln.
Dann gilt: $$ \phi \equiv \phi' \implies \phi S \equiv \phi'S $$