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.

• The graphical representation of the text is slightly modified. The grey fields are supposed to be complements (of the variable). Sorry for the inconvenience. Commented Mar 21, 2015 at 0:49
• fixed, the reverse quote was the problem. Commented Mar 21, 2015 at 0:51
• So you are looking at the function which outputs true if it is either all or exactly one of the inputs is true? I.e. $x\ominus y\ominus z$, where $\ominus$ represents symmetric difference? Commented Mar 21, 2015 at 0:54

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.

• $g(x,y) = xy+x'y'$ ? Commented Mar 21, 2015 at 1:02
• That choice of $g$ will also work. Commented Mar 21, 2015 at 1:02
• Polichinelle, are you able to generalize this solution for n variables? Commented Mar 22, 2015 at 20:33
• That depends on what Boolean function of the $n$ variables you want to compute. Commented Mar 22, 2015 at 20:37

Use associative law to get two-inputs.

AND $$x•y•z = (x•y)•z$$

• 2 ANDs

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

• 2 ORs

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

• 3 NOTs, 2 ORs

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

• 3 NOTs, 2 ANDs

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

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