Show that every boolean function with 3 variables can be represented with maximum number of 10 gates I need to show that every Boolean function with 3 variables can be represented with maximum number of 10 gates, limited to the following: AND(2 ins), OR(2 ins), NOT(1 in).
I tried to find Boolean function with 3 variables, of a higher complexity, which is non minimizable any further, and show that it takes up 10 gates to represent it.
I used Karnaugh map, and defined this function:
F(x,y,z) = xyz + x'yz' + xy'z' + x'y'z
I additionally used some identities to minimize it which resulted in this:
F(x,y,z) = x(yz + y'z') + x'(yz' + y'z) = x(yz + y')(yz + z') + x'(yz' + y')(yz' + z) = x(z + y')(y + z') + x'(z' + y')(y + z)
As you can see, now I need 12 gates(3 NOTs, 5 ORs and 4 ANDs), and I can't seem to find a way to reduce this number.
Any opinion would be great.
Much appreciation.
 A: Since
$$F(x,y,z)=g(g(x,y),z)\qquad{\rm where}\qquad g(x,y)=xy'+x'y,$$
and $g(x,y)$ can clearly be implemented with 5 gates (2 ANDs, 2 NOTs and 1 OR), $F$ can be implemented with 10 gates.  I do not know whether it can be implemented with fewer gates.
A: Use associative law to get two-inputs.
AND $$x•y•z = (x•y)•z$$


*

*2 ANDs

*additional terms add an AND


OR $$x+y+z = (x+y)+z$$


*

*2 ORs

*additional terms add an OR


NAND (Take DeMorgan's) $$\overline {xyz} = \bar x + \bar y + \bar z = (\bar x + \bar y) + \bar z$$ 


*

*3 NOTs, 2 ORs

*additional terms add a NOT and OR


NOR (Take DeMorgan's) $$\overline {x + y + z} = \bar x • \bar y • \bar z  = (\bar x • \bar y) • \bar z$$ 


*

*3 NOTs, 2 ANDs

*additional terms add a NOT and AND


XOR $$x ⊕ y ⊕ z = (x ⊕ y) ⊕ z = (\bar x•y + x•\bar y) ⊕ z$$


*

*2 NOTs, 2 ANDs and OR (for two terms)


Let A = $(\bar x•y + x•\bar y)$ 
XOR $$x ⊕ y ⊕ z = A ⊕ z = \bar A•z + A•\bar z$$


*

*4 NOTs, 4 ANDs and 2 ORs 

*additional terms add two NOTs, two ANDs, OR


XNOR $$x ⊙ y ⊙ z = (x ⊙ y) ⊙ z = (\bar x•\bar y + x•y) ⊙ z $$


*

*2 NOTs, 2 ANDs and OR (for two terms)


Again let A = $(\bar x•\bar y + x•y)$
XNOR $$x ⊙ y ⊙ z = A ⊙ z = \bar A•\bar z + A•z$$


*

*4 NOTs, 4 ANDs and 2 ORs 

*additional terms add two NOTs, two ANDs, OR


All 3 variables logic in 10 gates or less....
Boolean Laws
