# Functional completeness of $\{\text{or},\text{ xor}, \text{ xnor}\}$

I need to prove the functional completeness of $\{\text{or},\text{ xor},\text{ xnor}\}$ with the help of $\{\text{not},\text{ or},\text{ and}\}$ (which have been already proven to be functional complete). My attempt is that I only have to show that $\{\text{or},\text{ xor}\}$ is functional complete as $\text{xnor}$ is the negation of $\text{xor}$ while $\text{xor}$ is defined as $(x \wedge ¬y) \vee (¬x \wedge y)$. My attempt is to show that I can use $\{\text{or},\text{ xor}\}$ for $\{\text{not},\text{ or},\text{ and}\}$ but I already fail showing that $¬x$ can be replaced by $\{\text{or},\text{ xor}\}$... $¬x = ¬x+¬x = ¬¬(¬x+¬x)$ at this point I have no clue how to continue any constructive ideas?

• how about showing you can build not with {or,xor,xnor} and and with {or, xor, xnor}? Oct 24, 2012 at 19:03

Having "or" and "xor" alone is not enough -- since false or false = false xor false = false, there's no way for any combination of those two operations to produce "true" if all you have is "false". So you have no hope of expressing negation.

However: Note that $x\text{ xnor }x$ is always true, and therefore $x\text{ xor }(x\text{ xnor }x)$ is ...?

Now use De Morgan to build "and".

• x and x can be either true or false depending on x (0/1) I've just learned that 'x xor (x xnor x)' is true so "and" should be: '(x xor (x xnor x)) or (x xor x)' or am I mistaken Oct 24, 2012 at 19:18
• @Freddy: My first paragraph assumes that "or" and "xor" is all you have, since you wrote that your strategy was to make do with those two. There's no "and" among those. Oct 24, 2012 at 19:20
• Also, it is wrong that "x xor (x xnor x) is true" -- try evaluating it with x=true. Oct 24, 2012 at 19:21
• It is indeed wrong... so 'x xor (x xnor x)' can only be true in one case which is x = false. Since we only have one case in which 'and' can be 'true' I need to try and connect this 'x xor (x xnor x)' somehow. I came up with this: not (not x xnor (not x xor not x) or not x xnor (not x xor not x)) Am I going into the right direction? Oct 24, 2012 at 19:36
• @Freddy: What's wrong with my answer (the part after "however")? You seem to be deliberately ignoring it. Oct 24, 2012 at 19:38

A few hints:

• $a \text{ XOR } a = \text{false}$
• $a \text{ XNOR } a = \text{true}$
• $a \text{ XOR } \text{true} = \text{NOT } a$
• $a \text{ AND } b = \text{NOT }((\text{NOT } a) \text{ OR } (\text{NOT }b))$