Proving functional completeness

Question

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.

Answer 1

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.