# Help with producing a circuit that costs 17, then 9

I'm am completely stuck on this question:

We want to design a circuit that determines if a four-bit number is less than 10 and is also even.

a. (10 points) Write an expression of M such that M=1 if the four-bit number X (x3 x2 x1 x0) is less than 10 and is also even.

b. (20 points) Using only NOT gates, AND gates, and OR gates, show that the cost of the circuit you produced in part a can be implemented with a cost of 17.

c. (15 points) After further inquiry, we have determined that it is not strictly necessary that M=1 in order to determine if X matches our criteria. Write the expression for M̅, the complement of M.

d. (15 points) Draw the circuit which implements M̅, using only NOT, AND, and OR gates. Show that the cost of the circuit produced in part c is 9.

Ok so I did part a and got this formula: f(X3,X2,X1,X0) = X3'X0' + X2'X1'X0'.

I had M = (0, 2, 4, 6, 8), which is where I got the above equation from.

My problem is that in part b, I keep getting a cost of 18, not 17. I even used a digital logic calculator to help figure it out, but no matter what, even adding the 10 or removing the 0 and such, I can never get a cost of 17.

I can't even get a cost of 9 for part d.

Is there a typo in this problem or something? How is a cost of 9 even possible? Did I do this problem incorrectly? I've spent so much time on it and tried every possible solution, but I cannot get a cost of 17 or 9.

EDIT: the cost is calculated as follows, example: a 2 input AND gate would have a cost of 3 (2 inputs, plus the gate itself). Not gates have a cost of 2 (one gate plus one input). So for part b, I keep getting a cost of 18 because of 4 NOT gates = 8, one AND gate with 3 inputs, and one AND gate with 2 inputs = 7, and one OR gate with 2 inputs = 3, therefore 8 + 7 + 3 = 18.

• What definition of "cost" is this problem using?
– user39382
Feb 9, 2019 at 5:59
• @duskwuff the cost is calculated as follows, example: a 2 input AND gate would have a cost of 3 (2 inputs, plus the gate itself). Not gates have a cost of 2 (one gate plus one input). So for part b, I keep getting a cost of 18 because of 4 NOT gates = 8, one AND gate with 3 inputs, and one AND gate with 2 inputs = 7, and one OR gate with 2 inputs = 3, therefore 8 + 7 + 3 = 18.
– ESM
Feb 9, 2019 at 6:03
• I don't know. It looks like two OR, one AND, one NOT, to me. Or two AND, one OR, and one NOT. That costs 11, right?
– jonk
Feb 9, 2019 at 7:34

the simplest I can manage using 2 input gates is 11

associative rule

X3'X0' + X2'X1'X0' = (X3' + X2'X1')X0'

Now apply de Morgan's theorem repeatedly.

M = (X3'+(X2+X1)') X0'

M = (X3(X2+X1))' X0'

M = ((X3(X2+X1))+X0)'

for a cost of 11

but the complement M' = (X3(X2+X1))+X0)

for a cost of 9.

• Another way I like to see things is to realize that you get lots of free NOT gates when you switch from an AND to an OR, or visa versa.
– jonk
Feb 9, 2019 at 7:45
• with the NOT gate at the end the cost is 11 :/
– ESM
Feb 9, 2019 at 8:00
• ah yes, I missed the part where M' was used instead of M Feb 9, 2019 at 8:15
• Best you can do is 11. Mar 15, 2019 at 1:42