Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
how about showing you can build not with {or,xor,xnor} and and with {or, xor, xnor}? – sperners lemma Oct 24 '12 at 19:03
up vote 3 down vote accepted

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".

share|cite|improve this answer
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 – Freddy Oct 24 '12 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. – Henning Makholm Oct 24 '12 at 19:20
Also, it is wrong that "x xor (x xnor x) is true" -- try evaluating it with x=true. – Henning Makholm Oct 24 '12 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? – Freddy Oct 24 '12 at 19:36
@Freddy: What's wrong with my answer (the part after "however")? You seem to be deliberately ignoring it. – Henning Makholm Oct 24 '12 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))$
share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.