2
$\begingroup$

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?

  • 1
    how about showing you can build `not` with `{or,xor,xnor}` and `and` with `{or, xor, xnor}`?2012-10-24

2 Answers 2

3

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

  • 0
    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 mistaken2012-10-24
  • 0
    @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.2012-10-24
  • 0
    Also, it is _wrong_ that "x xor (x xnor x) is true" -- try evaluating it with x=true.2012-10-24
  • 0
    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?2012-10-24
  • 0
    @Freddy: What's wrong with my answer (the part after "however")? You seem to be deliberately ignoring it.2012-10-24
  • 0
    I am sorry, with wrong I refer to my statement above. I have no clue what x xor (x xnor x) is. When I use x = false I get true and when I use x = true I get false as a result. It looks resembels the negation of x.2012-10-24
  • 0
    @Freddy: It doesn't only "resemble" negation -- it _is_ the negation function. For every input the output is the same as the output of "not x"; therefore, the function being computed is the same. So now you know how to express "not". Do you know De Morgan's laws?2012-10-24
  • 0
    Sorry for double posting but assuming 'x xor (x xnor x)' is the negation of x (or negation of y) then 'x and y' after De Morgan is: 'not(not x or not y)' but 'not(not x or not y)' is 'not(x xor (x xnor x) or y xor (y xnor y)) which when x=0/1 and y=0/1 returns the 'and' chart. Is this correct?2012-10-24
  • 0
    @Freddy: Right, though there's still the outer "not" to unfold. But you don't actually need to write down the somewhat forbidding result of that in order to prove that {or,xor,xnor} is complete. It is much more readable to do the proof in steps: First argue that {or,xor,xnor} is enough to express "not", and then argue that {or,xor,xnor,not} is enough to express "and" -- and you already know that {or,xor,xnor,not,and} is more than enough to express everything. Since you only need to prove that it _can_ be done, you can leave it to the skeptical and interested reader to put (cont.d)2012-10-24
  • 0
    (cont.d) the pieces together if he wants to see the final result. For a _proof_ that a solution always exists, it is enough that you show the pieces themselves and explain _how_ they can be put together to get the desired result.2012-10-24
  • 0
    I am glad that you helped me! Thank you very much. However I also need to proove {>,not}. May I respond in here with my solution (in a few minutes) and you have a quick look at it?2012-10-24
  • 0
    @Freddy: Better make that a new question -- this comment thread is sprawling enough already.2012-10-24
  • 0
    Alright will do, thank you!2012-10-24
  • 0
    @Freddy: By the way, notice that it is somewhat more mathematically "dignified" to write down the proof in the opposite ("direct") order: "_Suppose_ we have some boolean function we want to express. We already know how to express it using {and,or,not}. Use such-and-such technique on every "and" to get it into a form that uses only {or,not}. Then use such-and-such technique on every "not" to get it into a form that uses only {or,xor,xnor}. Which was what we wanted, Q.E.D.".2012-10-24
  • 0
    Ok, I understand the argumentation.2012-10-24
2

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