2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ The graphical representation of the text is slightly modified. The grey fields are supposed to be complements (of the variable). Sorry for the inconvenience. $\endgroup$
    – Korunoski
    Commented Mar 21, 2015 at 0:49
  • $\begingroup$ fixed, the reverse quote was the problem. $\endgroup$
    – Joffan
    Commented Mar 21, 2015 at 0:51
  • $\begingroup$ 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? $\endgroup$
    – JMoravitz
    Commented Mar 21, 2015 at 0:54

2 Answers 2

3
$\begingroup$

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.

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

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .