Question

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.

Answer 1

For A :

Note that

(pNORq)≡(¬p∧¬q),(pNOR⁡q)≡(¬p∧¬q),

so that

¬p≡(pNORp)¬p≡(pNOR⁡p)

and therefore

(p∧q)≡(¬pNOR¬q).(p∧q)≡(¬pNOR⁡¬q).

Now, NAND is defined as:

(pNANDq)≡¬(p∧q),(pNAND⁡q)≡¬(p∧q),

so by the above, it's clear how to express it using NOR.

for B :

We can construct an expression for XOR in terms of AND, OR, and NOT, using the following reasoning:

• The second row tells us that p XOR q is TRUE when p is FALSE and q is TRUE. In other words, p XOR q is TRUE if NOT p AND q is TRUE.
• The third row tells us that p XOR q is TRUE when p is TRUE and q is FALSE. In other words, p XOR q is TRUE if p AND NOT q is TRUE
• The other rows tell us that p XOR q is FALSE in all other cases
• So p XOR q is TRUE if NOT p AND q is TRUE, or if p AND NOT q is true.