Equivalence Properties

Theorems

Equivalence is commutative:

• $p \iff q \dashv \vdash q \iff p$

Equivalence is associative:

• $p \iff \left({q \iff r}\right) \dashv \vdash \left({p \iff q}\right) \iff r$

These can alternatively be rendered as:

	\(\displaystyle \)	\(\displaystyle \vdash\)	\(\displaystyle \)	\(\displaystyle \left({p \iff q}\right)\)	\(\iff\)	\(\displaystyle \left({q \iff p}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \vdash\)	\(\displaystyle \)	\(\displaystyle \left({p \iff \left({q \iff r}\right)}\right)\)	\(\iff\)	\(\displaystyle \left({\left({p \iff q}\right) \iff r}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)

They can be seen to be logically equivalent to the forms above.

We also have that Equivalence destroys copies of itself:

• $p \iff p \dashv \vdash \top$

Proof

Proof by Natural deduction

Commutativity is proved by the Tableau method:

$p \iff q \vdash q \iff p$

Line		Pool	Formula	Rule	Depends upon
1		1	$p \iff q$	P	(None)
2		1	$\left({p \implies q}\right) \land \left({q \implies p}\right)$	By definition	1
4		1	$\left({q \implies p}\right) \land \left({p \implies q}\right)$	Comm	1
5		1	$q \iff p$	By definition	1

$q \iff p \vdash p \iff q$ is proved similarly.

$\blacksquare$

Proof of associativity by natural deduction is just too tedious to be considered.

• The theorem:

$p \iff p \dashv \vdash \top$

is the Law of Identity.

Proof by Truth Table

We apply the Method of Truth Tables to the propositions in turn.

As can be seen by inspection, in all cases the truth values under the main connectives match for all models.

$\begin{array}{|ccc||ccc|} \hline p & \iff & q & q & \iff & p \\ \hline F & T & F & F & T & F \\ F & F & T & T & F & F \\ T & F & F & F & F & T \\ T & T & T & T & T & T \\ \hline \end{array}$

$\blacksquare$

$\begin{array}{|ccccc||ccccc|} \hline p & \iff & (q & \iff & r) & (p & \iff & q) & \iff & r \\ \hline F & F & F & T & F & F & T & F & F & F \\ F & T & F & F & T & F & T & F & T & T \\ F & T & T & F & F & F & F & T & T & F \\ F & F & T & T & T & F & F & T & F & T \\ T & T & F & T & F & T & F & F & T & F \\ T & F & F & F & T & T & F & F & F & T \\ T & F & T & F & F & T & T & T & F & F \\ T & T & T & T & T & T & T & T & T & T \\ \hline \end{array}$

$\blacksquare$

$\begin{array}{|ccc|} \hline p & \iff & p \\ \hline F & T & F \\ T & T & T \\ \hline \end{array}$

$\blacksquare$

Sources

• Donald Kalish and Richard Montague: Logic: Techniques of Formal Reasoning (1964): $\text{II}: \S 5$: Theorem $\text{T91}, \ \text{T92}, \ \text{T94}$
• E.J. Lemmon: Beginning Logic (1965): $\S 1.4$: Theorem $24$