Conjunction has no Inverse

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $\land$ denote the conjunction operation of propositional logic.


Then there exists no binary logical connective $\circ$ such that:

$(1): \quad \forall p, q \in \left\{{T, F}\right\}: \left({p \land q}\right) \circ q = p$


Proof

This will be proven by contradiction.

Let such an operation $\circ$ exist.

Let $f^\circ: \mathbb B^2 \to \mathbb B$ be the associated truth function.


Suppose now that $q = F$, while $p$ remains unspecified.

Then:

$p \land q = f^\land \left({p, F}\right) = F$

where $f^\land$ is the truth function of conjunction.

It does not matter what $p$ is, for:

$f^\land \left({T, F}\right) = f^\land \left({F, F}\right) = F$

Hence, for $\left({p \land q}\right) \circ q = p$ to hold, $f^\circ$ must satisfy:

$f^\circ \left({F, F}\right) = p$

However, because $p$ could still be either $T$ or $F$, this identity cannot always hold.

Therefore, $\circ$ cannot exist.

$\blacksquare$