Black Box Logic Gates.

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

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

Black Box Logic Gates.

Postby Catinthewall » Fri May 11, 2012 2:08 pm UTC

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
Posts: 2758
Joined: Tue Sep 04, 2007 2:16 am UTC

Re: Black Box Logic Gates.

Postby mike-l » Fri May 11, 2012 3:29 pm UTC

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.

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

Re: Black Box Logic Gates.

Postby Catinthewall » Fri May 11, 2012 6:26 pm UTC

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. :D

Ben-oni
Posts: 278
Joined: Mon Sep 26, 2011 4:56 am UTC

Re: Black Box Logic Gates.

Postby Ben-oni » Fri May 11, 2012 11:33 pm UTC

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
Posts: 161
Joined: Tue Feb 06, 2007 4:32 pm UTC
Contact:

Re: Black Box Logic Gates.

Postby HonoreDB » Sat May 12, 2012 5:23 pm UTC

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
Posts: 950
Joined: Thu Jan 08, 2009 7:48 pm UTC

Re: Black Box Logic Gates.

Postby mfb » Tue May 29, 2012 9:49 am UTC

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
Posts: 278
Joined: Mon Sep 26, 2011 4:56 am UTC

Re: Black Box Logic Gates.

Postby Ben-oni » Tue May 29, 2012 11:28 am UTC

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.


Return to “Logic Puzzles”

Who is online

Users browsing this forum: No registered users and 11 guests