Skip to end of metadata
Go to start of metadata

I found this challenge at Max Blog you can read a lot more about it there. Here I only want to explain the solution path.

The challenge is basically simple to describe:

Invert 3 signals using only 2 inverters plus any amount of AND/OR gates. No other logic elements are allowed.

Decision path

First lets try to apply common "abstract problem solving skills" to the challenge and see how far we get.

Step 0

Take a deep breath.

Step 1

As Max says it is doable and there are no tricks. From this we can conclude that none of the inverters is directly connected to input or output. Why? If it would then the challenge would reduce itself to "two signals with one inverter" and that would not solve - if it would then it would be challenge. But it is not, so we can be sure that the solution is possible with 3 signals and 2 inverters and not possible with 2 signals and 1 inverter. Well you can try to solve the reduced challenge if you like. To our best knoledge it does not solve.

So based on the above (inverter inputs and outputs are not directly connected to global input or outputs) we can the draw schematic of the signal path:

Drawing 1

In this schematic I have introcuded a block "NiL" this is a LUT (look up table) that can be made with AND and OR gates only, I call it NonInvertingLogic (NiL).

It is easy to understand that if the challenge can be solved then the schematic is correct for the solution. We only need to find the NiL functions. Why this schematic is correct? Very simple, this generic schematic can visualize correctly any schematic you can make up using the constraints of the challenge. So if there is a solution then it must look like this, or it must be possible to convert it to look like this.

NiL's N1 and N2 are present once each, from NiL N3 there are 3 instances one for each of the inverted output signals.

Why there is no wire from signal Y to NiL N1 input you may ask(well I hope you did not ask this). If we would add wire from Y to input of N1 then resulting schematic would be a KNOWN NOT WORKING solution. We can feed back only one inverter output to the input function block or we create a "combinatorical loop". Combinatorical loop can cause the outputs to be in UNDEFINED state. This is not what we want.

This is not the full solution, but if you would have this challenge at exam a the university and you would submit this drawing as answer, I bet you would get scored above 0 points.

Funny is that to make this drawing we do not need to think at all if it works or how it works or how to find the functions N1, N2 or N3. Still we can say if something works then this is it.

Step 2

All we need todo now is to find 3 NiL functions N1, N2 and N3. How can we do this? Or is there is some question we can answer for sure? Should we start from N1 or N2 or N3 - can we answer this? This is the question!

Now of course we have no way to check our solution if we do not know N3 (as N3 delivers the output signal we need to generate and verify) - but to find N3 we need to know X and Y and those depend on N1 and N2. Similarly we can not find N2 first as it depends on X and function implemented in N1.

Can we start from block N1 ? Well as we can not start from N2 or N3 and we must start from somewhere then yes, we must start from block N1.

But how, we have criteria how to choose the function N1? We can postpone this question and look what the "content" of N1 could like like, and we make a drawing of all possible functions:

Drawing 2

This schematic shows all possible content variants for 3 input NiL functions. The white boxes can be AND or OR gates, those 4 variants include all possible choices. So what ever correct solution for N1 is, it must be one of the 4 from Drawing 2. Variants 1 and 2 are symmetrical functions while variants 3 and 4 are assymetrical (in the regard to 3 inputs A, B, C).

There are several decision paths to select the correct one.

#Decision/PathCommentSecond Comment
1We can first try to figure out if the solution is symmetrical or notif N1 is not symmetrical then N2 must also be not symmetricalThere is possible some easy explanation why a not symmetrical function can not be used (smile)
2We look at the simplest version, variant 3 firstWe have no criteria to select which of the 3 inputs is not usedWe exclude it as we have no single resolution, same applies to 4 as well
3Based on decision 2 we have excluded non symmetrical functions  
4We look at the simplest one left over - variant 1 firstWe have no criteria to select AND3 or OR3 for the function configurationWe exclude it as we have no single resolution (we can not select both AND3 and OR3 at the same time)
5Based on decisions 2 and 4 we have only variant 2 left overFunction 2 delivers same output no matter we use AND2 + OR3 or OR2 + AND3We choose 2 as there are no more choises and as this function delivers same output in both possible configurations

Table 1

The above decision path tells us what must be inside N1.

There is a more elegant decision path - you look at Drawing 4 and choose Variant 2 because it is most complex and feeds the inputs signals to the output and to our very valued inverter via more processing paths then other 3. So variant 3 maximizes the processing efficiency of our first inverter. So you choose 2 because it maximes the first inverter efficience and from this reason only (you dont bother with any other reasoning).

Now we can already write the logic function for X:

X = not ((A and B) or (A and C) or (B and C))

This is getting even more funny, we have the drawing for the overall circuit we know must work, and we have the content of first function block N1 as well. And we still do not know how it actually works and we can not verify that our circuit can deliver the inverted outputs as needed. But we know that we are right with all decisions made so far (there are no other singular choices that could be made hence our choice must be right).

You think we made an possible incorrect decision regarding the variant 2? You can try the other configuration for X:

X = not ((A or B) and (A or C) and (B or C))

This function delivers same output as the other one so the variant 2 is truly a singular solution.

We have no means to verify N1 at this stage as we do not know what X has to be.

Step 3

We have so far fixed the overall schematic and also the functional content of the NiL function block N1 that deliver signal X (output of the first inverter). So all we need now are functions for blocks N2 and N3 from Drawing 1. So should we start from N2 or N3? All Inputs to N2 are now known so it could be possible to solve N2 first. We can not validate it directly as we do not know N3 yet, but we could start with N2. Can we also start from N3? Lets take a look at Drawing 1 again, N1 and function X are now known, so for N3 we know the output and also 4 out of 5 inputs.

Note: we could also decide to solve N2 first and then N3.

It is more tempting to continue with N3 as it may tell us a bit if we are on right track or not. Well we think we are because we know no other way, but thats all we have made no attempt to verify the solution or to evaluate if it solves. So next N3!

As we know exactly what N3 has to output, then it is  for this we must look how the signal X looks like, so we make a table:

ABCXnot Anot Bnot Cfix Afix Bfix C
0001111   
0011110CLEAR  
0101101 CLEAR 
0110100  

SET

1001011  CLEAR
1010010 SET 
1100001SET  
1110000   

Table 2

In table 2 are all possible input combinations with correct outputs, our signal X and in colums "fix .." I have listed what function in N3 has todo with X to produce correct outputs (inversions of A, B and C). They are listed as CLEAR if N3 has to clear a bit, and with SET if N3 has to set a bit.

We can convert X to "not A" if we set one bit and clear one bit. And the same for "not B" and "not C" as well. How this can be done, or if it can be done we can not now as we do not know Y at this time. But can we finalize N3 at this time without knowing its input Y?

Lets see what we can conclude from table 2 and our previosly made choices and considerations.

First it is clear that we can solve for any output we want, they all are similar they all need to implement once SET and once CLEAR. Bit CLEAR function can be done with AND gate and bit SET can be done with OR gate so far so good. So we can write:

not A = X or F1(Y, A, B, C) and F2(Y, A, B, C)

Where F1 and F2 are both NiL functions (no inversion inside). F1 implements the SET function and F2 implements the CLEAR function.

We do not have yet full function for N3, but we have implemented a partial function that we know must be present in the final solution, the AND and OR gates that must be present in N3:

 

Drawing 3

Now the functions F1 and F2 - what can we say about them? There is one thing we can say for sure, the function inside F1 and F2 can not be symmetrical in the regard of inputs A, B and C. It is very easy to see why - if F1 (and F2) would be symmetrcial then N3 would deliver same output always but we need 3 different outputs (the inverted A, B and C).

Lets look at F1, this function has to provide output that clears one bit only. For this output of F1 must be 1 most of the time (or it would clear too many bits). If we need more 1 then we must use OR more than AND. So we can say in F1 AND is used more than OR.

If we now look at F2 then the opposite is true, F2 must use OR more and less AND.

So F1 and F2 are no longer fully black boxes, we know something about them.

What else? F1 and F2 are non symmetrical then F1 and F2 must include a NiL Function variant 3 (2 inputs)  or variant 4 (3 inputs) from Drawing 2.

Next decision to make, is the non symmetrical function in F1 and F2 with 2 or 3 inputs? This can be answered also. If we choose 3 input NiL function (that includes one AND and one OR) for both F1 and F2 we can not use more AND in one and more OR in the other (both F1 and F2 would same amount of AND and OR). If we choose 2 input functions then we simple choose once AND and once OR.

So we have reduced one input for both F1 and F2.

Next question do both F1 and F2 use same 2 inputs (from A, B, C) or not? Of course they both must use Y.

Lerts consider first they do not, in that case we do not have single resolution, there will be two equal possibilities and we can not decide which one is right. We can only decide both are wrong what gives us a single resolution: both F1 and F2 and also N3 use same set of inputs from A, B and C.

Now we can write simplified function N3 for all 3 outputs:

not A = X or F1(Y, B, C) and F2(Y, B, C)
not B = X or F1(Y, A, C) and F2(Y, A, C)
not C = X or F1(Y, A, B) and F2(Y, A, B)

Can we do something more? We need to maximize AND in F1 and OR in F2, the only way to-do this is that:

not A = X or (Y and B and C) and (Y or B or C)
not B = X or (Y and A and C) and (Y or B or C)
not C = X or (Y and A and B) and (Y or A or B)

Hm, nothing left to-do with N3 function it is also complete. We still do not know if it works, as we do not know Y.

Step 4

Now lets look what we can tell about Block N2, it does not matter if we did solve N3 before N2 or if we are solving N2 after N1. We do not know what N2 should produce as output and we will not make attempt to figure it out or in any way validate the output function of N2. We are only interested to see if we can fix the content of N2.

As previously concluded both N1 and N2 must be symmtrical NiL functions in the regard to the inputs A, B and C. We used NiL variant 2 already in for N1 (and there is only one configuration for this variant). As it does not make sense to apply inversion to same function twice, we must choose the other symmetrical Nil function variant 1 from Drawing 2. There are configurations for this, it can be either OR3 or AND3 function. Can we decide wich one is correct? No we can not, so we do not choose between AND and OR at all. Can we choose both? Yes we can lets make a drawing:

Drawing 4

So far the content of N2 must be correct. Obviously we can not use the output of AND as N2 output as then we can not use OR output any more, and we must keep the OR3 in N2 (see above as we can choose between AND and OR we must choose both). The only thing we know we can do is to connect the outputs of AND3 and OR3 to another logic gates (AND or OR).

Drawing 5

What do see now? To complete the circuit we should minimize open inputs and outputs at the end we can only have one output anyway as this block only has one final output. So if we can connect one of the output of the 2 input gate to the open input of the another we are closer to the solution. Can we decide with one? Actually we can, it really does not make in difference the function would remain the same. What next? Now we have only one open output, if we use it as final output of N2, then we only have one open input left. What should we do with it? we have no internal signal left inside N2. Now we need to look at Drawing 1 we actually have one signal in the design, this is the output of first inverter named as X. So the only thing we can do is to use the last open input as N2 block input wicht is connected extenally to X (output of first inverter).

Drawing 6

Hey wait a moment, what was the reason to choose OR to follow AND? This is very simple to explain, if we would have AND3 feeding AND2 and OR3 feeding OR2 the overall complexity of N2 would be lower. We would have less signal paths feeding the second inverter and those the second inverter computing efficiency would be lower. So this is the only possible content there is for N2. We can now write out the function for Y:

Y = not ((X or (A and B and C)) and (A or B or C))

Wait a moment we have done it all? There is nothing else to solve?

Step 5

Does it work what we did, does it implement 3 inversions as it has too? So far we have no proof that it does. At no stage we validated anything we did to be correct, as we had no means to verify anything. We did find the content for 3 different black boxes without knowing what they should do. But solution we did come up with is the only possible one. The decision path leads to one and only one solution for all our 3 black boxes. So if a solution exists as it has been claimed by Max then our solution must work. It must provide 3 inverted outputs for 3 input signals.

And the solution is really working, you can test it out on paper or using a spread sheet. You can also check Max blog and compare the solutions he has described there. Well all the solutions are actually functionally one and the same.

So Challenge solved?

Yes?

Really?

Are you still holding your breath?

I hape not, because we should now proceed to next step:

Step 6

Take a deep breath.

Step 7

The challenge as posted by Max and the solutions Max as accepted as correct solution and also the solution path I provided - they do not actually solve the challenge!

How? Very simple, the Challenge Max posted has no solution, it can not be solved.

I can not do it.

Nobody can. Why?

Lets think, is there some common rule that we can apply? What about this saying:

If something is too good to be true it is not true

Inverting 3 signals with 2 inverters sounds like too good to be true, so it can not be true and in reality is not true.

Question is how can we prove that it is not possible?

Let's try to verify it is true (3 inversions with 2 inverters is possible), if we succeed in failing during that verification then we have proved it. Next step verification!

Step 8

How to verify those 3 inversions we have succeeded implementing with 2 inverters are working or not? What about this: we create a small and simple circuitry that uses 3 inversions and verify its operation? This is not full verification, but it would be a start.

So here it is some real circuit that uses 3 inversions, we use our black box (with 2 inverters inside) to provide the 3 inversions we need:

Drawing 7

Test circuit for 3 inversions, we have one switch connected to inverter A and LED to check the inverted input. From inverters B and C we make a R-S Latch using two addiotional AND gates. We connect 2 more switches and two more LED's.

Exciting, does it work?

Lets test the R-S Latch, I use switches SW2 and SW3 to check its operation, and It works correctly!

It works? But it should fail? Hm..

What about SW1 ? I press and release SW1.

All 3 LED's are on !

This means that both the single inverter and our R-S Latch stopped working!

We succeeded to fail. First indicator that the challenge solution is not a real solution.

 

 

 

 

 

===

< work in progress...>

 

 

 

You do not believe me? Well seeing is believing so please take a look at "not A" signal may look like with static 0 applied to input A, if we invert 0 we should get 1, but what do get is this:

Vivado Logic Analyzer capturing "inverted A" signal generated by logic provided as solution to the challenge by Max from static 0 input A. Tested on Trenz Electronic TE0723. Well it the same result would be on any FPGA. FPGA - but if we make the solution from real discrete AND/OR gates and inverters? Would it work then? No it would also not work.

 

To Be Continued...

And please do not hold your breath (wink)

 

 

 

 

 

 

  • No labels