Sticky logic problem

[Pradu]

g += h & -(e!=f) should look familiar to you. It's your original solution sans all the redundancies you appended.

BTW, it doesn't seem to be equivalent to your solution. I'll have to think about it later, but seems your original solution may be incorrect.

HG got it right. Say e!=f, a==b, and c<d. If e>f you add, if e<f you don't add.

[rjgibert]

Here is Sherwin's specification:

Code: Select all

if(a == b) { 
    if&#40;c < d&#41; &#123; 
        if&#40;e > f&#41; g += h; 
    &#125; else &#123; 
        if&#40;e < f&#41; g += h; 
    &#125; 
&#125; else &#123; 
    if&#40;c < d&#41; &#123; 
        if&#40;e < f&#41; g += h; 
    &#125; else &#123; 
        if&#40;e > f&#41; g += h; 
    &#125; 
&#125; 

The above clearly states that when a == b, c < d and e < f, then you do add. This contrary to what you state.

Note that g += h & -(e!=f) is equivalent to if (e != f) g += h.

[rjgibert]

Oops! I see my mistake now. Tricky (for me).

[Michael Sherwin]

Oops! I see my mistake now. Tricky (for me).

Join the club!

I still have not created a proper example to be reduced, been trying to catch up on my rest. Trying to do this kind of stuff while exhaused is total futility on my part!

[xsadar]

The if (e != f) part is wrong (it gives false positives). My first reply -- which included (e != f) as part of the condition -- is wrong also. I mixed up which else went with which if, as it seems you are doing also. It needs to be e > f or e < f depending on the other variables. For example consider the following case where:

a = b, c < d, and e < f

In this case, g += h would not be executed, but it would in your statement because it's true in this case that e != f. Note that it would also execute in the code I gave in my first reply, so it is wrong also because of this (not to mention that I didn't notice the inequalities on e and f were switched in the a != b case.

[Gerd Isenberg]

Oops! I see my mistake now. Tricky (for me).

Yes, it is tricky.

Code: Select all

if(a == b) {
    if&#40;c < d&#41; &#123;
        if&#40;e > f&#41; g += h;
    &#125; else &#123;
        if&#40;e < f&#41; g += h;
    &#125;
&#125; else &#123;
    if&#40;c < d&#41; &#123;
        if&#40;e < f&#41; g += h;
    &#125; else &#123;
        if&#40;e > f&#41; g += h;
    &#125;
&#125; 

The formal way to solve it, is to build a sum of products by all leaf-conditions
http://www.ibiblio.org/obp/books/socrat ... op_pos.pdf:

Code: Select all

if(
   &#40;a == b & c <  d & e > f&#41;
 | &#40;a == b & c >= d & e < f&#41;
 | &#40;a != b & c <  d & e < f&#41;
 | &#40;a != b & c >= d & e > f&#41;
  )  g += h;

with

Code: Select all

A ::= (a == b)
B &#58;&#58;= &#40;c <  d&#41;
G &#58;&#58;= &#40;e >  f&#41;
L &#58;&#58;= &#40;e <  f&#41;

if&#40; 
   ( A & B & G&#41;
 | ( A &~B & L&#41;
 | (~A & B & L&#41;
 | (~A &~B & G&#41;
  ) g += h;

With that you can build a truth table with four boolean input variables and to draw venn diagram to look for a minimal expression. http://en.wikipedia.org/wiki/Venn_diagram
I guess there are free computer aided algebra programs to solve that, but as HG mentioned, the expressions already looks very xorish, since

Code: Select all

a ^ b ::= (a & ~b) | (~a & b)

Code: Select all

   ( A & B & G)
 | (~A &~B & G)
 | ( A &~B & L)
 | (~A & B & L)
==>
   (~(A ^ B) & G)
 | ( (A ^ B) & L)

With a leading conjunction (e != f), we can replace L by ~G to perform the second xor trick to reduce further:

Code: Select all

==>
(e != f) & ( A ^ B ^ G )

[Pradu]

Oops! I see my mistake now. Tricky (for me).

Yes, it is tricky.

Code: Select all

if(a == b) {
    if&#40;c < d&#41; &#123;
        if&#40;e > f&#41; g += h;
    &#125; else &#123;
        if&#40;e < f&#41; g += h;
    &#125;
&#125; else &#123;
    if&#40;c < d&#41; &#123;
        if&#40;e < f&#41; g += h;
    &#125; else &#123;
        if&#40;e > f&#41; g += h;
    &#125;
&#125; 

The formal way to solve it, is to build a sum of products by all leaf-conditions
http://www.ibiblio.org/obp/books/socrat ... op_pos.pdf:

Code: Select all

if(
   &#40;a == b & c <  d & e > f&#41;
 | &#40;a == b & c >= d & e < f&#41;
 | &#40;a != b & c <  d & e < f&#41;
 | &#40;a != b & c >= d & e > f&#41;
  )  g += h;

with

Code: Select all

A ::= (a == b)
B &#58;&#58;= &#40;c <  d&#41;
G &#58;&#58;= &#40;e >  f&#41;
L &#58;&#58;= &#40;e <  f&#41;

if&#40; 
   ( A & B & G&#41;
 | ( A &~B & L&#41;
 | (~A & B & L&#41;
 | (~A &~B & G&#41;
  ) g += h;

With that you can build a truth table with four boolean input variables and to draw venn diagram to look for a minimal expression. http://en.wikipedia.org/wiki/Venn_diagram
I guess there are free computer aided algebra programs to solve that, but as HG mentioned, the expressions already looks very xorish, since

Code: Select all

a ^ b ::= (a & ~b) | (~a & b)

Code: Select all

   ( A & B & G)
 | (~A &~B & G)
 | ( A &~B & L)
 | (~A & B & L)
==>
   (~(A ^ B) & G)
 | ( (A ^ B) & L)

With a leading conjunction (e != f), we can replace L by ~G to perform the second xor trick to reduce further:

Code: Select all

==>
(e != f) & ( A ^ B ^ G )

As a tool for simplifying boolean algebric expressions into Sum of Products or Product of Sums with few variables (<=6) you can use Karnaugh Maps. There's actually a utility that can do the simplification for up to 8 variables, but it is pretty easy to do it for 6 variables by hand. But I guess changing the sum of products to xors takes some insight though. It isn't quite clear to me how you figured out the second xor part:

With a leading conjunction (e != f), we can replace L by ~G to perform the second xor trick to reduce further:

Code: Select all

==>(e != f) & ( A ^ B ^ G )

Did you take steps to reach this or assumed it as a function of xor and did some guessing to get it right? I understand the e!=f part comes off logically but the ^ of (e>f) seems like a guessed result that happens to work right. I don't see how to pull off the transformation logically.

[Michael Sherwin]

it looks to me like it reduces to:

Code: Select all

if &#40;c < d && e != f&#41;
  g += h;

even still I doubt that's what was intended

I think that you are right Mike. This is now not looking like I intended.

The if a == b makes no sense if followed by the same if c < d and h gets added on inequality in either case.

I will see what the original problem was and post a corrected version.

Thanks

Now that I am half rested I can see that indeed it is a correct example, afterall!

It is funny that the puzzels author was so easily fooled into believing that he had goofed.

But then I would not have called it sticky if it were not so tricky!

I am just glad that I am not the only one that is easily confused by it.

HG and Gerds solutions are truely amazing!

[Gerd Isenberg]

But I guess changing the sum of products to xors takes some insight though. It isn't quite clear to me how you figured out the second xor part:

With a leading conjunction (e != f), we can replace L by ~G to perform the second xor trick to reduce further:

Code: Select all

==>(e != f) & ( A ^ B ^ G )

Did you take steps to reach this or assumed it as a function of xor and did some guessing to get it right? I understand the e!=f part comes off logically but the ^ of (e>f) seems like a guessed result that happens to work right. I don't see how to pull off the transformation logically.

The leading ( e != f ) conjunction is needed to replace Less by ~Greater, which makes the expression an xor-normal form. If (e == f), Less is false as well as Greater, thus the whole expression. We can also replace (e != f) by (L ^ G), (L | G) or (L + G) :

Code: Select all

with X = (A ^ B)

               (~X & G) | ( X & L )   {four instructions)
==> (L ^ G) & ((~X & G) | ( X & ~G ))
==> (L ^ G) &   (X ^ G)               (three instructions)