2
$\begingroup$

I read in a note the following:

Suppose we have a boolean function $f(x,y,z,w)$, if $f(a,a,a,a)=1$ then $f$ can't be functionally complete.

Why is that? how does it imply that $f$ can't produce nand or nor?

$\endgroup$
2
$\begingroup$

The claim is false if you're allowed to use constants. Take $f(x,y,0,0) = f(x,y,1,1) = 1$ and $f(x,y,0,1) = f(x,y,1,0) = x \text{ NAND } y$. If you're not allowed to use constants, then every function that you can get by composing $f$ with itself will have the property that if all inputs are 1, then so is the output. NAND doesn't have that property.

$\endgroup$
  • $\begingroup$ Oh comparing properties directly. Is it possible to also deduce which one (or both) of $not$ or $and$ can't be produced from that function? $\endgroup$ – shinzou Mar 6 '16 at 18:53
  • $\begingroup$ Perhaps, but I'll leave that as an exercise for you to solve. $\endgroup$ – Yuval Filmus Mar 6 '16 at 18:53
  • $\begingroup$ Just after I wrote this I figured that $and$ does have that property but $not$ doesn't.. $\endgroup$ – shinzou Mar 6 '16 at 19:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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