1
$\begingroup$

There are two functions

f(x,y,z) = x'yz + xy' + y'z'

g(x,y,z) = x'yz + x'yz' + xy

Are these functions functionally complete ?


For first one, We can have f(x,x,y) = (x + y)' which is NOR and is known to be functionally complete so f is functionally complete.

One small doubt I have here is, for proving NOR and NAND operations for 3 variables, do we have to include all 3 variables or is 2 variables enough ? Like is it enough if we check if f is capable of determining (x.y)' or should it be capable of determining (x.y.z)' and (x.y)' is not enough?

In second function I am not able to determine any of the known functionally complete sets like NAND or NOR. But I am not sure whether it is really not functionally complete.

Can someone help me with second function ?

Thanks.

$\endgroup$
1
$\begingroup$

As far as your first doubt goes: $f$ really is functionally complete. If you need a function of $3$ variables, you just use the appropriate number of $f$ functions instantiated with the appropriate terms. For example, if we want to capture $x(y+z)$, then given that that is equivalent to $(x'+(y+z)')'$ and thus to $(x \ NOR \ x) \ NOR \ (y \ NOR \ z)$, we would use the expression $f(f(x,x,x),f(x,x,x),f(y,y,z))$

For your second function, note that:

$$g(x,y,z)=x'yz+x'yz'+xy= \text{ (Adjacency)}$$

$$x'y+xy=\text{ (Adjacency)}$$

$$y$$

So no, $g(x,y,z)$ is clearly not functionally complete.

$\endgroup$
3
  • $\begingroup$ Can you help me with the first doubt ? $\endgroup$ – Zephyr Nov 14 '17 at 4:42
  • $\begingroup$ @Zephyr Added that to my Answer $\endgroup$ – Bram28 Nov 14 '17 at 11:48
  • $\begingroup$ Ok. So for functional completeness, proving that a function can derive a known functionally complete set of 2 variables without using 1's and 0's is enough right ? Also if possible can you help me realize (x+y+z)' ? $\endgroup$ – Zephyr Nov 14 '17 at 12:18

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.