NAND is Not Associative

Theorem

Let $\uparrow$ signify the NAND operation.

Then there exist propositions $p,q,r$ such that:

$p \uparrow \left({q \uparrow r}\right) \not \vdash \left({p \uparrow q}\right) \uparrow r$

That is, NAND is not associative.

Proof by Tableau

Proceed by the Tableau method:

$\neg \left({ \left({p \uparrow q}\right) \uparrow r \implies p \uparrow \left({q \uparrow r}\right) }\right)$

Line		Pool	Formula	Rule	Depends upon	Notes
1		1	$\left({p \uparrow q}\right) \uparrow r \implies p \uparrow \left({q \uparrow r}\right)$	$\mathrm A$	(None)
2		2	$p \land \neg r$	$\mathrm A$	(None)
3		2	$p$	$\land \mathcal E_1$	2
4		2	$\neg r$	$\land \mathcal E_2$	2
5		2	$\left({\neg q}\right) \lor \left({\neg r}\right)$	$\lor \mathcal I_2$	4
6		2	$\neg \left({q \land r}\right)$	$\mathrm {DM}$	5
7		2	$q \uparrow r$	By definition	6
8		2	$p \land \left({q \uparrow r}\right)$	$\land \mathcal I$	3,7
9		2	$\neg \neg \left({p \land \left({q \uparrow r}\right)}\right)$	$\neg \neg \mathcal I$	8
10		2	$\neg \left({p \uparrow \left({q \uparrow r}\right) }\right)$	By definition	9
11		2	$\left({\neg \left({p \uparrow q}\right) }\right) \lor \left({\neg r}\right)$	$\lor \mathcal I_2$	4
12		2	$\neg \left({\left({p \uparrow q}\right) \land r}\right)$	$\mathrm {DM}$	11
13		2	$\left({p \uparrow q}\right) \uparrow r$	By definition	12
14		2	$\neg \neg \left({\left({p \uparrow q}\right) \uparrow r}\right)$	$\neg \neg \mathcal I$	13
15		2	$\neg \neg \left({\left({p \uparrow q}\right) \uparrow r}\right) \land \neg \left({p \uparrow \left({q \uparrow r}\right) }\right)$	$\land \mathcal I$	13,10
16		2	$\neg \left({\neg \left({\left({p \uparrow q}\right) \uparrow r}\right) \lor \left({p \uparrow \left({q \uparrow r}\right)}\right) }\right)$	$\mathrm {DM}$	15
17		2	$\neg \left({ \left({p \uparrow q}\right) \uparrow r \implies p \uparrow \left({q \uparrow r}\right) }\right)$	$\mathrm {TI}$	16	Disjunction and Implication
18		1,2	$\bot$	$\neg \mathcal E$	1,17

Taking $p = \top$, $r = \bot$, we find $\vdash p \land \neg r$, and conclude our initial assumption was false.

$\blacksquare$

Proof by Truth Table

We apply the Method of Truth Tables:

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

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

$\blacksquare$