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?

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

2 Answers 2

3
$\begingroup$

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

$\endgroup$
15
  • $\begingroup$ 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 $\endgroup$
    – Freddy
    Oct 24, 2012 at 19:18
  • $\begingroup$ @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. $\endgroup$ Oct 24, 2012 at 19:20
  • $\begingroup$ Also, it is wrong that "x xor (x xnor x) is true" -- try evaluating it with x=true. $\endgroup$ Oct 24, 2012 at 19:21
  • $\begingroup$ 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? $\endgroup$
    – Freddy
    Oct 24, 2012 at 19:36
  • $\begingroup$ @Freddy: What's wrong with my answer (the part after "however")? You seem to be deliberately ignoring it. $\endgroup$ Oct 24, 2012 at 19:38
3
$\begingroup$

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .