Formula equivalence (propositional logic)

Propositional formulas are equivalent when they evaluate to the same truth value under every variable assignment.

Equivalence of objects is always defined in the same way and to the same effect: objects are considered equivalent when they behave the same in all possible contexts (or contexts considered interesting); equivalent objects can be replaced for one another in all possible contexts (or contexts considered interesting).

For propositional formulas, this is spelled out in what follows.

Formal Definition

Definition Propositional formulas $\varphi$ and $\psi$ are equivalent, $\varphi \SemEquiv \psi$ in symbols, if $$[\![\varphi]\!]_\beta = [\![\psi]\!]_\beta$$ holds for every propositional variable assignment $\beta$.

Example We have $X_0 \vee \neg X_1 \SemEquiv \neg (X_1 \wedge \neg X_0)$ and $\neg X_0 \vee X_0 \SemEquiv \top$, but $X_0 \not\SemEquiv X_0 \vee X_1$.

Basic properties

The relation $\SemEquiv$, defined between propositional formulas, satisfies all properties known from equivalence relations.

Lemma The relation $\SemEquiv$, defined on $F_\text{PL}$, is an equivalence relation. More precisely:

reflexivity

$\varphi \SemEquiv \varphi$ for every $\varphi \in F_\text{PL}$.

symmetry

If $\varphi \SemEquiv \psi$, then $\psi \SemEquiv \varphi$, for all $\varphi, \psi \in F_\text{PL}$.

transitivity

If $\varphi \SemEquiv \psi$ and $\psi \SemEquiv \chi$, then $\varphi \SemEquiv \chi$, for all $\varphi, \psi, \chi \in F_\text{PL}$.

The proof is straightforward.

Congruence property

An important property is that the equivalence relation is compatible with every connective.

Congruence lemma (simple variant) The relation $\SemEquiv$, defined on $F_\text{PL}$, is a congruence relation in the following sense. Given an $n$-ary connective $C$ and propositional formulas $\varphi_0, \dots, \varphi_{n-1}, \psi_0, \dots, \psi_{n-1}$ such that $\varphi_i \SemEquiv \psi_i$ for all $i < n$, then $C(\varphi_0, \dots, \varphi_{n-1}) \SemEquiv C(\psi_0, \dots, \psi_{n-1})$.

Proof Let $C$ be an $n$-ary connective and $\varphi_0, \dots, \varphi_{n-1}, \psi_0, \dots, \psi_{n-1}$ propositional formulas such that $\varphi_i \SemEquiv \psi_i$ for all $i < n$. Further, let $\beta$ be a variable assignment. We have: \begin{aligned} {}\llbracket C(\varphi_0, \dots, \varphi_{n-1})\rrbracket_\beta & = f_C(\llbracket \varphi_0\rrbracket_\beta, \dots, \llbracket \varphi_{n-1}\rrbracket_\beta) && \text{semantics of propositional logic}\\ & = f_C(\llbracket \psi_0\rrbracket_\beta, \dots, \llbracket \psi_{n-1}\rrbracket_\beta) && \text{assumption}\\ & = \llbracket C(\psi_0, \dots, \psi_{n-1})\rrbracket_\beta \enspace. && \text{semantics of propositional logic} \end{aligned} This shows $C(\varphi_0, \dots, \varphi_{n-1}) \SemEquiv C(\psi_0, \dots, \psi_{n-1})$.

A general variant of this lemma involves substitution.

The equivalence relation is compatible with substitution; this is formally stated in the substitution lemma.

List of basic equivalences

There is a list of basic equivalences between propositional formulas.