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

Expand Messages
• 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
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.