## Black Box Logic Gates.

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

### Black Box Logic Gates.

You have a collection of arbitrarily labeled Boolean logic gates. Among the set are all the symmetrical gates (ones where [1,0]=[0,1], except for TRUE and FALSE.

AND, NAND, OR, XOR, NOR, and XNOR, each with a distinct but unconnected label, until tested you can't know what each label represents.

A single test involves building a Boolean circuit, and running all four possible bitsets through, reading the 1 output bit. Rearranging the circuit or moving the output reader mid-test isn't allowed.

The easy way to accurately label all 6 would be to make 5 1-gate circuits, and then label the leftover by process of elimination. But is there a way to be able to label all 6 gate types with 4 or fewer tests?
Catinthewall

Posts: 3
Joined: Fri Jan 08, 2010 7:35 am UTC

### Re: Black Box Logic Gates.

Can I choose my 2nd circuit based on the results of the first? Can I introduce 1/0 inputs, eg having the test inputs go into two different gates which have a constant 1 on their second input?

You have some free information you can leverage. In a single gate setup your test of 0,1 and 1,0 will give the same result, so rewiring so that this isn't necessarily the case gives you more info.
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.
mike-l

Posts: 2513
Joined: Tue Sep 04, 2007 2:16 am UTC

### Re: Black Box Logic Gates.

Can I choose my 2nd circuit based on the results of the first?

Yes, and the third and the fourth as well. However,
Spoiler:
I believe it can be solved with 4 circuits tested and analyzed in parallel

Can I introduce 1/0 inputs, eg having the test inputs go into two different gates which have a constant 1 on their second input?

No, besides the wire (which can be branched) and the gates, all you have is the testing input nodes, and the testing output node. Running the test in effect prints a Boolean table immediately.

You have some free information you can leverage. In a single gate setup your test of 0,1 and 1,0 will give the same result, so rewiring so that this isn't necessarily the case gives you more info.

Yes, yes it does.
Catinthewall

Posts: 3
Joined: Fri Jan 08, 2010 7:35 am UTC

### Re: Black Box Logic Gates.

Testing a single gate simply tells you which gate it is. So obviously you must build circuits composed of more than one gate. We'll call the inputs A and B. Given a gate G, we'll describe the output as G(A, B).
Spoiler:
Take two gates, G and P. Test the following circuit: G(A, P(B, B)):

1. Symmetric: P must be either AND or OR, and G is fully determined
2. Constant (False): P is XOR and G is AND; or P is XNOR and G is NOR
3. Constant (True): P is XOR and G is NAND; or P is XNOR and G is OR
4. Constant in B (G = A): P is XOR and G is OR; or P is XNOR and G is AND
5. Constant in B (G = ~A): P is XOR and G is NOR or XNOR; or P is XNOR and G is NAND or XOR
6. Other: P is either NAND or NOR, and G is fully determined

The decision tree gets rather large, but this should get you started.
Ben-oni

Posts: 268
Joined: Mon Sep 26, 2011 4:56 am UTC

### Re: Black Box Logic Gates.

It can't be done in fewer than
Spoiler:
3 tests. 2 tests give at best 2*4=8 bits of information, enough to distinguish between 2^8=256 possibilities. But there are 6!=720 possible permutations of the gates.
HonoreDB

Posts: 147
Joined: Tue Feb 06, 2007 4:32 pm UTC

### Re: Black Box Logic Gates.

Similar to Ben-oni:
Spoiler:
In addition, it is possible to test G(A,P(A,B)) and make a big decision tree for the different gates. As we have 16 possible logic tables and 30 possible gate combinations, I don't want to analyse this in detail.
Combinations with 3 or more gates are possible, too, but they make the decision tree even more complex.

However, we have to save just one test, compared to the trivial 5-test solution. Maybe it is possible to test 3 gates and use an appropriate test (from the two options given here) to determine the last 3 gates. Only if (AND and OR) or (NAND and NOR) or (XOR and NOR and XNOR) or (XNOR and NAND and XOR) are left, the G(A, P(B, B)) does not work. We would have to work out whether G(A,P(A,B)) can distinguish the gates in these cases or not.
mfb

Posts: 803
Joined: Thu Jan 08, 2009 7:48 pm UTC

### Re: Black Box Logic Gates.

Spoiler:
The G(A, P(A, B)) wiring is actually worse: it only yields 13 possible results, whereas G(A, P(B, B)) yields 14. The spread is about the same in both.

The three gate wiring G(A, H(B, I(A, A))) offers all 16 possibilities, but two results account for most of the configurations.

With a 4 gate wiring, F(G(a, a), H(b, I(a, a))) gives the best spread:

Code: Select all
`Results | # of Configurations—————————————————————————————   3    |    12   1    |    14   3    |    18   1    |    20   4    |    26   2    |    30   2    |    36`

I'm thinking it would be best to go for a full 6 gate wiring and use rearrangements upon for successive tests.
Ben-oni

Posts: 268
Joined: Mon Sep 26, 2011 4:56 am UTC