Black Box Logic Gates.

[Catinthewall]

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?

[mike-l]

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.

[Catinthewall]

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.

[Ben-oni]

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.

[HonoreDB]

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.

[mfb]

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.

[Ben-oni]

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.