# Formula equivalence (propositional logic)

### From Learning Logic for Computer Science

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.