Show that every boolean function with 3 variables can be represented with maximum number of 10 gates

Question

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.

Answer 1

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.

Answer 2

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