NAND, XOR and AND

Question

This is the question I am trying to prove.

Assume that p NAND q is logically equivalent to ¬(p ∧ q). Then,

(a) prove that {NAND} is functionally complete, i.e., any propositional formula is equivalent to one whose only connective is NAND. Now,

(b) prove that any propositional formula is equivalent to one whose only connectives are XOR and AND, along with the constant TRUE. Prove these using a series of logical equivalences.

For part a, I have

(A NAND B) NAND (A NAND B)

ㄱ[(A NAND B) ⋀ (A NAND B)] LOGICALLY EQUIVALENT

ㄱ[ ㄱ(A ⋀ B) ⋀ ㄱ(A ⋀ B)] LOGICALLY EQUIVALENT

(A ⋀ B) V (A ⋀ B) DE MORGAN

(A ⋀ B) IDEMPOTENT

using Table 6

and using Table 7 and 8

I believe that is all I have to do for part a but I am confused on how to do part b. I think I have to make another propositional formula using just XOR and AND but what am I trying to prove it to, just (A OR B)?

Answer 1

Your proof of a) is incomplete, though what you have so far is correct.

Sentences in propositional calculus usually consist of atomic propositions $P_i$ and the connectives $\land, \lor, \to$ as well as $\neg$. Thus you need to prove that any sentence built out of these symbols has an equivalent formula using only NAND.

So you have already shown that $A \land B \equiv (A ~\text{NAND} ~B) ~\text{NAND} ~(A ~\text{NAND} ~B)$, but now you need to do the same for the other symbols. You need to show that $A \lor B$, $A \to B$, and $\neg A$ can be rewritten using only NAND.

For b), you essentially need to do the same thing, prove that any formula using $\land, \lor, \to, \neg$ can be rewritten to use only XOR, $\land$, and a constant $T$. But there is a shortcut, if you can simply prove that $A~ \text{NAND} ~B$ is equivalent to some combination of XOR, $\land, T$, then you can use a) to prove b).