Browse Groups

• ## Re: [PrimeNumbers] Re: Boolean algebra solver?

(13)
• NextPrevious
• Hi Ron, R Justin asked me for a real life example of how this technique R can be used to find factors, so at the risk of boring everyone R else, I thought
Message 1 of 13 , Jun 4, 2004
View Source
Hi Ron,

R> Justin asked me for a real life example of how this technique
R> can be used to find factors, so at the risk of boring everyone
R> else, I thought I'd post it here on the forum. Here is a sample
R> Maple code snippet ('#' begins a comment) that illustrates the
R> problem:

Thanks Ron. I think I've finally understood the idea of the technique. I
also understand long-hand multiplication at long last ;)

R> n:= [0,0,1,1,1,1]: # factor binary 001111 = decimal 15 = 3*5

R> eqn := {a1+b1 = 1,
R> a2+a1*b1+b2+c1 = 1,
R> a2*b1+a1*b2+c2 = 1,
R> a2*b2+c3+c4 = 0,
R> c5 = 0};

As you know, these equations in the Z(2) field are equivalent to boolean
expressions. So they can be transformed the following way to eliminate the
equality:

lhs == 1 -> lhs
lhs == 0 -> NOT(lhs) -> lhs+1 (equivalent to NOT using only xor)

now all the ex-equations can be combined to one with AND (ie multiplication
in Z(2)) to form one expression:

(a1+b1) (a2+a1*b1+b2+c1) (a2*b1+a1*b2+c2) (a2*b2+c3+c4+1) (c5+1)

This can be reduced algebraically and transformed to boolean:

(a1 && b2 && ! a2 && ! b1) || (a2 && b1 && ! a1 && ! b2)

Which in effect is indeed your solution:

R> # But the solution is:

R> a2:=0: a1:=1: # a0:=1, so that a= "011" binary = 3 decimal
R> b2:=1: b1:=0: # a0:=1, so that b= "101" binary = 5 decimal

R> # Where a=3 and b=5 are the factors of 15.

I use Mathematica, and am not familiar with Maple, but I suppose it is
just as capable of these transformations.

I'm not sure about the practicability though. It already took a few seconds
to reduce your example expressions (albeit with somewhat straightforward
and probably not really efficient reduction algorithm).

But then, what do I know? ;P

--
Justin
ICQ 37456745
AIM jasticle
Your message has been successfully submitted and would be delivered to recipients shortly.
• Changes have not been saved
Press OK to abandon changes or Cancel to continue editing
• Your browser is not supported
Kindly note that Groups does not support 7.0 or earlier versions of Internet Explorer. We recommend upgrading to the latest Internet Explorer, Google Chrome, or Firefox. If you are using IE 9 or later, make sure you turn off Compatibility View.