Home > Archive > Prolog > November 2007 > Solving a set of boolean equations
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
Solving a set of boolean equations
|
|
| Ecirbaf 2007-10-30, 7:12 pm |
| Hi !
Languages I know are some ASMs, C, C++ and the excellent OCaml.
I have looked a bit at Prolog more than 20 years ago and I now
encounter a problem that makes remember to it :
Please consider you have some boolean equations.
For example these 2 :
X xor Y xor Z = true
X and not Y = false
A solving program should produce for (X, Y, Z) :
{(false, false, true), (false, true, false), (true, true, true)}
Of course an actual question includes much more than 3 variables and
trying the 2^nbr_of_var cases would be impossible...
Although not obvious in current languages, I imagine this contraint
problem would be far easier to solve with Prolog.
Please do you have - small - program example(s) that handle this
kind of problem ?
It would be, for a very beginner, much easier to start with hacking
into existing things.
But maybe the problem I spoke about is common and it soon exists
softs that efficiently solve it ?
Thanks for any hint...
Fabrice
| |
| Neng-Fa Zhou 2007-10-30, 7:12 pm |
| Try a CLP(FD) system (e.g., B-Prolog, Sicstus). Here is an encoding of your
example problem:
solve(Vars):-
Vars=[X,Y,Z],
Vars :: 0..1,
X #\ Y #\ Z #= 1, % the binary operator #\ is for xor
X #/\ (#\ Y) #= 0, % the unary operator #\ is for not
labeling(Vars).
Cheers,
Neng-Fa
"Ecirbaf" <fabrice.marchant@orange.fr> wrote in message
news:1193751455.021085.324550@k79g2000hse.googlegroups.com...
> Hi !
>
> Languages I know are some ASMs, C, C++ and the excellent OCaml.
> I have looked a bit at Prolog more than 20 years ago and I now
> encounter a problem that makes remember to it :
>
> Please consider you have some boolean equations.
> For example these 2 :
>
> X xor Y xor Z = true
> X and not Y = false
>
> A solving program should produce for (X, Y, Z) :
> {(false, false, true), (false, true, false), (true, true, true)}
>
> Of course an actual question includes much more than 3 variables and
> trying the 2^nbr_of_var cases would be impossible...
>
> Although not obvious in current languages, I imagine this contraint
> problem would be far easier to solve with Prolog.
>
> Please do you have - small - program example(s) that handle this
> kind of problem ?
> It would be, for a very beginner, much easier to start with hacking
> into existing things.
> But maybe the problem I spoke about is common and it soon exists
> softs that efficiently solve it ?
>
> Thanks for any hint...
>
> Fabrice
>
| |
| Chip Eastham 2007-10-30, 7:12 pm |
| On Oct 30, 9:37 am, Ecirbaf <fabrice.march...@orange.fr> wrote:
> Hi !
>
> Languages I know are some ASMs, C, C++ and the excellent OCaml.
> I have looked a bit at Prolog more than 20 years ago and I now
> encounter a problem that makes remember to it :
>
> Please consider you have some boolean equations.
> For example these 2 :
>
> X xor Y xor Z = true
> X and not Y = false
>
> A solving program should produce for (X, Y, Z) :
> {(false, false, true), (false, true, false), (true, true, true)}
>
> Of course an actual question includes much more than 3 variables and
> trying the 2^nbr_of_var cases would be impossible...
>
> Although not obvious in current languages, I imagine this contraint
> problem would be far easier to solve with Prolog.
>
> Please do you have - small - program example(s) that handle this
> kind of problem ?
> It would be, for a very beginner, much easier to start with hacking
> into existing things.
> But maybe the problem I spoke about is common and it soon exists
> softs that efficiently solve it ?
>
> Thanks for any hint...
>
> Fabrice
If your boolean equations are very regular, it might be
attractive to treat them as posed over the field (ring)
Z/2Z, taking 0 = false and 1 = true. The usual logical
operations have arithmetic equivalents there, e.g. AND
is multiplication, XOR is addition, and NOT x is 1-x.
This is no panacea, but large systems of linear eqns.
over Z/2Z are solved (using bitwise operations to
effect Gaussian elimination) in high-powered integer
factoring algorithms.
regards, chip
| |
| Ecirbaf 2007-10-31, 7:12 pm |
| On Oct 30, 3:44 pm, "Neng-Fa Zhou" <nz...@acm.org> wrote:
> Try a CLP(FD) system (e.g., B-Prolog, Sicstus). Here is an encoding of your
> example problem:
>
> solve(Vars):-
> Vars=[X,Y,Z],
> Vars :: 0..1,
> X #\ Y #\ Z #= 1, % the binary operator #\ is for xor
> X #/\ (#\ Y) #= 0, % the unary operator #\ is for not
> labeling(Vars).
Thanks a lot for your fine answer !
It's very kind you gave me exactly what I needed : the answer to my
example.
I installed B-Prolog ( I discover you worked on it ) to try the
above code :
B-Prolog Version 7.0, All rights reserved, (C) Afany Software
1994-2007.
Type 'help' for usage.
| ?- [ex0]
consulting::ex0.pl
yes
| ?- listing
solve(A) :-
A=[B,C,D],
A::0..1,
B#\C#\D#=1,
B#/\(#\C)#=0,
labeling(A).
yes
| ?- solve(Solution)
Solution = [1,1,1] ?
---------------------------------------------------------------
It seems to perfectly work.
A very beginner question : it seems to ask me if I want more
solutions, Please how to say it to express the remaining two ?
Regards,
Fabrice
-----------------------------------------------------------------
"What's a color of a chameleon put onto a mirror ?" Steward brand
| |
| Ecirbaf 2007-10-31, 7:12 pm |
| On Oct 30, 7:43 pm, Chip Eastham <hardm...@gmail.com> wrote:
> If your boolean equations are very regular, it might be
> attractive to treat them as posed over the field (ring)
> Z/2Z, taking 0 = false and 1 = true.
Thanks a lot for your interesting answer,
In fact there are a lot of equations that are identical - modulo the
variable names -.
This come from a problem about J.H. Conway Game of Life :
I try here to search the possible "still lifes" inside a square.
("Still lifes" are persistent pattern.)
For example, inside a side 3 square, there are :
**. ... ... .** .*. **. .*. .*. .** **. .**
**. **. .** .** *.* *.* *.* *.* *.* *.* *.*
.... **. .** ... .*. .*. **. .** .*. .** **.
In fact, for any square, there are only 3 types of equations :
- for a corner ( 4 eqns)
- for a side-cell ( (4*(side-2) eqns )
- for an inner cell ( (side-2)*(side-2) eqns )
My idea was to translate original counting Conway rules to boolean
ones.
But I see here, with Prolog your advice to use number and notices
Neng-Fha Zhou used 0 and 1...
> The usual logical
> operations have arithmetic equivalents there, e.g. AND
> is multiplication, XOR is addition, and NOT x is 1-x.
That is clear.
> This is no panacea, but large systems of linear eqns.
> over Z/2Z are solved (using bitwise operations to
> effect Gaussian elimination) in high-powered integer
> factoring algorithms.
Please could you develop a bit or give a bit about this ?
Thanks.
Regards,
Fabrice
| |
| Ecirbaf 2007-10-31, 7:12 pm |
| > | ?- listing
>
> solve(A) :-
> A=[B,C,D],
> A::0..1,
> B#\C#\D#=1,
> B#/\(#\C)#=0,
> labeling(A).
>
> yes
> | ?- solve(Solution)
>
> Solution = [1,1,1] ?
> ---------------------------------------------------------------
> It seems to perfectly work.
> A very beginner question : it seems to ask me if I want more
> solutions, Please how to say it to express the remaining two ?
I read B-Prolog doc and tried to use 'findall' :
| ?- findall(S, solve(S), Sl)
Sl = [[1,1,1]] ?
I thought it shall be :
[[1,1,1],[0,0,1],[0,1,0]]
Please why are the last two solutions missing ?
Thanks,
Fabrice
| |
| Chip Eastham 2007-10-31, 7:12 pm |
| On Oct 31, 11:23 am, Ecirbaf <fabrice.march...@orange.fr> wrote:
> On Oct 30, 7:43 pm, Chip Eastham <hardm...@gmail.com> wrote:
[SNIP]
>
> Please could you develop a bit or give a bit about this ?
When one has a matrix with entries from Z/2Z, elimination
(of nonzero entries under a leading one) becomes simply a
matter of XORing one row with several others. Bitwise
operations such as this can be done using the convenient
wordsize of the computing platform, and of course there
is no roundoff error.
The application I described is obviously quite different
from the one you have in mind, but perhaps you will find
it interesting to hear more details.
Large linear systems of this type arise in integer factoring
algorithms because one tries to find, for a modulus M that
is known to be composite (but for which explicit factors are
sought), solutions X^2 = Y^2 mod M. By various means one
generates many residues X^2 = R mod M which have a good
chance of factoring R = p_1^k_1 * ... * p_t^k_t over some
modestly large "base" of common factors p_i (mostly smallish
primes). If a product of such X's is taken, we need only
concern ourselves with the parity (even or odd) of the
resulting exponents {k_i} for the factor base {p_i}. One
finds nontrivial solutions to the homogeneous equations
corresponding to parities of these factor base exponents.
All even exponents (ie. congruent to 0 mod 2) would be an
exact square Y^2 congruent to the respective product of
the X^2's, and because then M divides X^2 - Y^2, there is
a reasonably good chance gcd(M,X-Y) and gcd(M,X+Y) are
nontrivial factors of M. Given more independent solutions
to the homogeneous equations, the chance of factoring M
becomes higher, approaching a probability of one.
regards, chip
| |
| Neng-Fa Zhou 2007-11-01, 7:12 pm |
|
"Ecirbaf" <fabrice.marchant@orange.fr> wrote in message
news:1193854792.873529.220400@y42g2000hsy.googlegroups.com...
>
> I read B-Prolog doc and tried to use 'findall' :
>
> | ?- findall(S, solve(S), Sl)
>
> Sl = [[1,1,1]] ?
>
> I thought it shall be :
> [[1,1,1],[0,0,1],[0,1,0]]
>
> Please why are the last two solutions missing ?
After reading the manual:-), I realized that #= has higher precedence than
#/\. So the correct encoding should be:
solve(Vars):-
Vars=[X,Y,Z],
Vars :: 0..1,
(X #\ Y #\ Z) #= 1, % or simply X #\ Y #\ Z
(X #/\ (#\ Y)) #= 0, % or simply #\ (X #/\ (#\ Y))
labeling(Vars).
I guess the precedence was set this way because the Boolean operators are
often be used to connect primitive constraints such as (U#=10) #\/ (V#>U).
Cheers,
Neng-Fa
| |
| Ecirbaf 2007-11-01, 7:12 pm |
| (> > Please could you develop a bit or give a bit about this ?
Wanted to say : "Please could you develop a bit or give a LINK about
this ?" Apologize.)
> When one has a matrix with entries from Z/2Z, elimination
> (of nonzero entries under a leading one) becomes simply a
> matter of XORing one row with several others. Bitwise
> operations such as this can be done using the convenient
> wordsize of the computing platform, and of course there
> is no roundoff error.
A kind of assembly code that would run at full speed...
> The application I described is obviously quite different
> from the one you have in mind, but perhaps you will find
> it interesting to hear more details.
I spoke about Game of life on Prolog group and you discuss prime
factoring : I hope comp.lang.prolog isn't moderated...
I joke : I do like arithmetic ! (Very interested about Mahler Z-
numbers.)
> Large linear systems of this type arise in integer factoring
> algorithms because one tries to find, for a modulus M that
> is known to be composite (but for which explicit factors are
> sought), solutions X^2 = Y^2 mod M. By various means one
> generates many residues X^2 = R mod M which have a good
> chance of factoring R = p_1^k_1 * ... * p_t^k_t over some
> modestly large "base" of common factors p_i (mostly smallish
> primes). If a product of such X's is taken, we need only
> concern ourselves with the parity (even or odd) of the
> resulting exponents {k_i} for the factor base {p_i}. One
> finds nontrivial solutions to the homogeneous equations
> corresponding to parities of these factor base exponents.
> All even exponents (ie. congruent to 0 mod 2) would be an
> exact square Y^2 congruent to the respective product of
> the X^2's, and because then M divides X^2 - Y^2, there is
> a reasonably good chance gcd(M,X-Y) and gcd(M,X+Y) are
> nontrivial factors of M. Given more independent solutions
> to the homogeneous equations, the chance of factoring M
> becomes higher, approaching a probability of one.
Thanks a lot to share this interesting subject.
Sincerely,
Fabrice
| |
| Ecirbaf 2007-11-01, 7:12 pm |
| > solve(Vars):-
> Vars=[X,Y,Z],
> Vars :: 0..1,
> (X #\ Y #\ Z) #= 1, % or simply X #\ Y #\ Z
> (X #/\ (#\ Y)) #= 0, % or simply #\ (X #/\ (#\ Y))
> labeling(Vars).
Thanks a lot,
It rocks now !
| ?- findall(S, solve(S), Sl)
Sl = [[0,0,1],[0,1,0],[1,1,1]] ?
Please another question : what is the trailing '?' after the list
answer of 'findall' ?
So I will forget the boolean expression of the problem for a time and
try to express it in B-Prolog, simply using #< or other inequality
tests on integers.
Cheers,
Fabrice
| |
| Neng-Fa Zhou 2007-11-02, 7:09 pm |
| >
> Please another question : what is the trailing '?' after the list
> answer of 'findall' ?
This follows an old Prolog tradition: the system asks you if you need more
solutions. Type ';' to get the next solution and any other key to terminate
the query. The B-Prolog system seems not intelligent enough. It gives you
'?' even if there is obviously no further solution.
> So I will forget the boolean expression of the problem for a time and
> try to express it in B-Prolog, simply using #< or other inequality
> tests on integers.
You should model your problem as a CSP if it is a natural way to do it. If
you model your problem as a SAT (Boolean CSP) problem, then there are
systems (such as minisat) that do a better job than B-Prolog.
Cheers,
Neng-Fa
| |
| Ecirbaf 2007-11-03, 4:20 am |
| On Nov 2, 2:12 pm, "Neng-Fa Zhou" <nz...@acm.org> wrote:
>
> This follows an old Prolog tradition: the system asks you if you need more
> solutions. Type ';' to get the next solution and any other key to terminate
> the query. The B-Prolog system seems not intelligent enough. It gives you
> '?' even if there is obviously no further solution.
Thanks a lot for this ! Maybe ';' choice is for "or" ...
>
> You should model your problem as a CSP if it is a natural way to do it. If
> you model your problem as a SAT (Boolean CSP) problem, then there are
> systems (such as minisat) that do a better job than B-Prolog.
I've downloaded minisat to experiment with it.
However I will continue to play with B-Prolog : seeing how short the
examples code are vs the amount of work they perform is quite
impressive.
( But maybe is this the same thing with (non-B) Prolog, I don't know.)
Thanks a lot for B-Prolog and the explanations.
Regards,
fabrice
|
|
|
|
|