Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

A 2-way universal logic processor (2ULP) is a network of logic gates that takes two input wires A and B, as well as four other inputs L_, L_a, L_b, and L_ab, and produces a single output L(a, b) using the four L inputs as a truth table function:

  • The 2ULP returns L_ if A and B are both 0.
  • It returns L_a if A = 1 and B = 0.
  • It returns L_b if A = 0 and B = 1.
  • It returns L_ab if A and B are both 1.

For example, given the inputs L_ = 0, L_a = 1, L_b = 1, and L_ab = 0, then the output L(a, b) will be equal to A xor B.

Your task is to build a 2ULP using only NAND gates, using as few NAND gates as possible. To simplify things, you may use AND, OR, NOT, and XOR gates in your diagram, with the following corresponding scores:

  • NOT: 1
  • AND: 2
  • OR: 3
  • XOR: 4

Each of these scores corresponds to the number of NAND gates that it takes to construct the corresponding gate.

The logic circuit that uses the fewest NAND gates to produce a correct construction wins.

share|improve this question
1  
My digital logic design skills are so rusty it's laughable, but I greatly enjoy the end results of these competitions. +1 –  ProgrammerDan Mar 28 at 16:23
    
With two-input NAND gates, there's not much room for creativity in this design. Perhaps, rather than requiring that the device take six inputs, design a block with has an arbitrary number of inputs and one output, and require that given two inputs A and B and a choice of one of the sixteen functions, it must be possible to connect the block's inputs to some combination of A, B, High, and Low, such that the output will yield that function. Such a device would be a universal 2-way logic processor (just add wires), but could probably be done in a lot less than 11 gates. –  supercat Mar 28 at 18:56
    
We should invent gate-golf, where you write in the smallest amount of gates. –  TheDoctor Mar 29 at 13:53
    
That's what atomic-code-golf + logic-gates is for. –  Joe Z. Mar 29 at 15:03

3 Answers 3

11 NANDs

Define the gate MUX (cost 4) as

MUX(P, Q, R) = (P NAND Q) NAND (NOT P NAND R)

with truth table

P Q R    (P NAND Q)   (NOT P NAND R)    MUX
0 0 0        1               1           0
0 0 1        1               0           1
0 1 0        1               1           0
0 1 1        1               0           1
1 0 0        1               1           0
1 0 1        1               1           0
1 1 0        0               1           1
1 1 1        0               1           1

Then this is the familiar ternary operator MUX(P, Q, R) = P ? Q : R

We simply have

2ULP = MUX(A, MUX(B, L_ab, L_a), MUX(B, L_b, L_))

for a cost 12, but there's a trivial one-gate saving by reusing the NOT B from the two inner MUXes.

share|improve this answer
2  
You just gave me an idea of something to try with redstone in Minecraft, thanks –  David Wilkins Mar 28 at 17:18

By using Wolfram language I can get a 13 gates formula:

logicfunc = Function[{a, b, Ln, La, Lb, Lab},
                   {a, b, Ln, La, Lb, Lab} -> Switch[{a, b},
                          {0, 0}, Ln, {1, 0}, La, {0, 1}, Lb, {1, 1}, Lab]
                  ];
trueRuleTable = Flatten[Outer[logicfunc, ##]] & @@ ConstantArray[{0, 1}, 6] /. {0 -> False, 1 -> True};
BooleanFunction[trueRuleTable, {a, b, Ln, La, Lb, Lab}] // BooleanMinimize[#, "NAND"] &

which outputs:

NAND formula

Here Ln, La, Lb and Lab are the L_, L_a, L_b and L_ab separately in OP.

sidenote: The results of the BooleanMinimize function in Wolfram language are restricted to two-level NAND and NOT when invoking as BooleanMinimize[(*blabla*), "NAND"], so it's not as good as Peter Taylor's four-level formula above.

share|improve this answer

cost: 4*4*14+4*(13)+13*3+3*3+24*1+4=352

I'm not a boolean man, this is my best in coding this things (I know this won't give me many immaginary internet points..).

# l1 is for a=F , b=F
# l2 is for a=F , b=T
# l3 is for a=T , b=F
# l4 is for a=T , b=T

2ULP(l1,l2,l3,l4,a,b) =
 (l1&l2&l3&l4)|             # always true
 (!l1&l2&l3&l4)&(a|b)|      # a=F,b=F->F; ee in T
 (l1&!l2&l3&l4)&(!a&b)|     # a=F,b=T->F; ee in T
 (!l1&!l2&l3&l4)&(a)|       # a=F,b=F->F; a=F,b=T->F; a=T,b=F->T; a=T,b=T->T; 
 (l1&l2&!l3&l4)&(a&!b)|     # a=T,b=F->F, ee in T
 (!l1&l2&!l3&l4)&(b)|       # a=T,b=F->F, ee in T
 (!l1&!l2&!l3&l4)&(a&b)|    # a=T,b=T->T, ee in F
 (l1&l2&l3&!l4)&(!(a|b))|   # a=T,b=T->F, ee in T
 (!l1&l2&l3&!l4)&(!(avb))|  # a=T,b=F->T, a=F,b=T->T, ee in T , note v is the exor.
 (l1&!l2&l3&!l4)&(!b)|      # T when b=T
 (!l1&!l2&l3&!l4)&(a&!b)|   # T when a=T,b=F
 (l1&l2&!l3&!l4)&(!a)|      # T when a=F
 (!l1&l2&!l3&!l4)&(!a&b)|   # T when a=F,B=T
 (l1&!l2&!l3&!l4)&(!(a|b))  # T when a=F,B=F
share|improve this answer
    
If you follow the system outlined by the bullet points in the question then you get a cost of 29, so this is impressively bad. –  Peter Taylor Mar 28 at 17:31
    
I'm sorry Mr Taylor, I just hope this haven't ruin your eyes. –  Antonio Ragagnin Mar 28 at 18:09

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.