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)?