# Solve logical program as a linear system of (in)equalities

**URL:** <https://swi-prolog.discourse.group/t/solve-logical-program-as-a-linear-system-of-in-equalities/7360>\
**Category:** Discussion\
**Created:** [April 8, 2024, 8:00am UTC](https://swi-prolog.discourse.group/t/solve-logical-program-as-a-linear-system-of-in-equalities/7360 "2024-04-08T08:00:03Z")\
**Posts on this page:** 13\
**Page:** 1

<div class="post-metadata">

**Author:** ![jli05](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/jli05/32/6222_2.png) [@jli05](https://swi-prolog.discourse.group/u/jli05)\
**Post date:** [April 8, 2024, 8:00am UTC](https://swi-prolog.discourse.group/t/solve-logical-program-as-a-linear-system-of-in-equalities/7360/1 "2024-04-08T08:00:03Z")

</div>

A question on transforming (some) logical program as a linear system of equalities/inequalities:

Say proposition X=0 for false, X=1 for true, and likewise for all propositions, then X → Y (X leads to Y) can be written as

- X + Y \>= 0

As above, one may transform (some) logical program into a linear system of equalities/inequalities. Has it been applied to logical program solution/deduction/abduction? Any good, basic, definitive reference paper(s) on the approach?

---

<div class="post-metadata">

**Author:** ![anon419083](https://avatars.discourse-cdn.com/v4/letter/a/53a042/32.png) [@anon419083](https://swi-prolog.discourse.group/u/anon419083)\
**Post date:** [April 8, 2024, 8:49am UTC](https://swi-prolog.discourse.group/t/solve-logical-program-as-a-linear-system-of-in-equalities/7360/2 "2024-04-08T08:49:59Z")

</div>

> [@jli05](#):
>
> X → Y (X leads to Y)

I am not sure that I understand exactly what you mean. That notation usually means “X can be rewritten as Y”. It’s a rewrite rule. It seems like you use it in a different way

---

<div class="post-metadata">

**Author:** ![brebs](https://avatars.discourse-cdn.com/v4/letter/b/e9c0ed/32.png) [@brebs](https://swi-prolog.discourse.group/u/brebs)\
**Post date:** [April 8, 2024, 9:25am UTC](https://swi-prolog.discourse.group/t/solve-logical-program-as-a-linear-system-of-in-equalities/7360/3 "2024-04-08T09:25:17Z")

</div>

> [@jli05](#):
>
> Has it been applied

Yes - [clpb](https://www.swi-prolog.org/pldoc/man?section=clpb).

Recent [example usage](https://swi-prolog.discourse.group/t/prolog-easter-challenge-2024/7338/15).

---

<div class="post-metadata">

**Author:** ![brebs](https://avatars.discourse-cdn.com/v4/letter/b/e9c0ed/32.png) [@brebs](https://swi-prolog.discourse.group/u/brebs)\
**Post date:** [April 8, 2024, 9:27am UTC](https://swi-prolog.discourse.group/t/solve-logical-program-as-a-linear-system-of-in-equalities/7360/4 "2024-04-08T09:27:07Z")

</div>

> [@anon419083](#):
>
> It’s a rewrite rule

No - `X implies Y` says nothing about Y, if X is false.

X and Y can be completely different expressions.

---

<div class="post-metadata">

**Author:** ![anon419083](https://avatars.discourse-cdn.com/v4/letter/a/53a042/32.png) [@anon419083](https://swi-prolog.discourse.group/u/anon419083)\
**Post date:** [April 8, 2024, 9:31am UTC](https://swi-prolog.discourse.group/t/solve-logical-program-as-a-linear-system-of-in-equalities/7360/5 "2024-04-08T09:31:08Z")

</div>

Ah ok. So it’s a different thing. I thought it was a rewrite rule. But it’s logical implication

---

<div class="post-metadata">

**Author:** ![anon419083](https://avatars.discourse-cdn.com/v4/letter/a/53a042/32.png) [@anon419083](https://swi-prolog.discourse.group/u/anon419083)\
**Post date:** [April 8, 2024, 11:13am UTC](https://swi-prolog.discourse.group/t/solve-logical-program-as-a-linear-system-of-in-equalities/7360/6 "2024-04-08T11:13:25Z")

</div>

> [@jli05](#):
>
> - X + Y \>= 0

Still this notation remains obscure to me, but it’s not a big issue. Just for the sake of discussion

PS: the formatting didn’t work right…i don’t know why the minus sign was replaced by a dot 🤷‍♂️

---

<div class="post-metadata">

**Author:** ![jli05](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/jli05/32/6222_2.png) [@jli05](https://swi-prolog.discourse.group/u/jli05)\
**Post date:** [April 8, 2024, 11:37am UTC](https://swi-prolog.discourse.group/t/solve-logical-program-as-a-linear-system-of-in-equalities/7360/7 "2024-04-08T11:37:20Z")

</div>

Hey I had edited the post — I had had to prepend the minus sign with a backslash, otherwise it will be displayed as a black dot for bullet point. Not sure why you still see the black dot though.

---

<div class="post-metadata">

**Author:** ![brebs](https://avatars.discourse-cdn.com/v4/letter/b/e9c0ed/32.png) [@brebs](https://swi-prolog.discourse.group/u/brebs)\
**Post date:** [April 8, 2024, 11:49am UTC](https://swi-prolog.discourse.group/t/solve-logical-program-as-a-linear-system-of-in-equalities/7360/8 "2024-04-08T11:49:18Z")

</div>

> [@jli05](#):
>
> reference paper

Does [https://www.metalevel.at/swiclpb.pdf](https://www.metalevel.at/swiclpb.pdf) suffice?

There is also clpBNR:

- [GitHub - ridgeworks/clpBNR: CLP(BNR) module for SWI-Prolog](https://github.com/ridgeworks/clpBNR)
- [https://ridgeworks.github.io/clpBNR/CLP\_BNR\_Guide/CLP\_BNR\_Guide.html](https://ridgeworks.github.io/clpBNR/CLP_BNR_Guide/CLP_BNR_Guide.html)

---

<div class="post-metadata">

**Author:** ![jli05](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/jli05/32/6222_2.png) [@jli05](https://swi-prolog.discourse.group/u/jli05)\
**Post date:** [April 8, 2024, 12:16pm UTC](https://swi-prolog.discourse.group/t/solve-logical-program-as-a-linear-system-of-in-equalities/7360/9 "2024-04-08T12:16:36Z")

</div>

Thanks very much. clpBNR does seem to help.

A question for now. On [https://github.com/ridgeworks/clpBNR](https://github.com/ridgeworks/clpBNR) it is stated its advantage consists in

- CLP(BNR) is complete in that any real number can be finitely represented even though the set of reals is infinite. It does this by sacrificing precision: a real number _R_ is represented by an interval (_L,U_) where _L=\<R=\<U_ and _L_and _U_ are numbers as defined by SWI-Prolog (integers, rationals or floats, including the IEEE infinity values). A precise value (_L=U_) is represented directly by the number.
- CLP(BNR) arithmetic is mathematically sound. Any computed interval will contain the precise value. Due to the well-known pitfalls of IEEE floating point arithmetic, any CLP(_R_) based on conventional IEEE floating point arithmetic is unsound. (Try: `?- 1.21 =:= 1.1*1.1.`) In particular the add and multiply operations are non-associative and non-distributive. Relational interval arithmetic in CLP(BNR) (and some others) ensures that computed intervals contain the mathematically correct real value.

How _crucial_ are the above points, if for a logical program, most real values are bounded, but can take value NaN (not-a-value), or infinity?

The above two advantage come at cost of how much additional compute, generally speaking?

---

<div class="post-metadata">

**Author:** ![brebs](https://avatars.discourse-cdn.com/v4/letter/b/e9c0ed/32.png) [@brebs](https://swi-prolog.discourse.group/u/brebs)\
**Post date:** [April 8, 2024, 12:35pm UTC](https://swi-prolog.discourse.group/t/solve-logical-program-as-a-linear-system-of-in-equalities/7360/10 "2024-04-08T12:35:41Z")

</div>

Perhaps @ridgeworks is available to answer.

---

<div class="post-metadata">

**Author:** ![ridgeworks](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/ridgeworks/32/886_2.png) [@ridgeworks](https://swi-prolog.discourse.group/u/ridgeworks)\
**Post date:** [April 8, 2024, 3:09pm UTC](https://swi-prolog.discourse.group/t/solve-logical-program-as-a-linear-system-of-in-equalities/7360/11 "2024-04-08T15:09:52Z")

</div>

> [@jli05](#):
>
> How _crucial_ are the above points, if for a logical program, most real values are bounded, but can take value NaN (not-a-value), or infinity?

First point is not to conflate reals and floating point values; the latter is an imperfect approximation of reals.

NaN’s are not real numbers, as the name would imply, so they’re not legal in the “real” domain of clpBNR. However infinities are included in the real domain so a real interval can be bounded by an infinity, but it’s just a bound. When applied, constraints cause the domain of a “real” to narrow (a domain never gets wider), so infinite bounds generally disappear in the course of a computation.

New bounds are the intersection of the current bounds and the computed bounds as defined by constraints. Now the computed bounds may produce NaN’s or infinities, but that just generally means the interval doesn’t narrow as a result of the computation.

I think the above points are fairly crucial for logical correctness which, to me at least, implies mathematical correctness (and completeness) over the domain of real numbers.

> [@jli05](#):
>
> The above two advantage come at cost of how much additional compute, generally speaking?

Off the top of my head a fair amount, all things considered. A primitive interval relation like `{Z == X+Y}` requires 6 arithmetic ops (including rounding control if bounds are floating point) plus domain intersection for a total of 9. Plus the additional overhead of running an IA virtual machine implemented in Prolog. (In general the clpBNR VM is responsible for propagating changes in one real value to co-constrained values and checking for consistency.) I typically observe 100,000-200,000 narrowing ops per second, so I’d guess 1-2 orders of magnitude over functional Prolog arithmetic.

A simple interval arithmetic library which just preserves correctness without all the constraint stuff would obviously do better. And there are a number of IA libraries available which should provide background information to help answer your question.

---

<div class="post-metadata">

**Author:** ![anon419083](https://avatars.discourse-cdn.com/v4/letter/a/53a042/32.png) [@anon419083](https://swi-prolog.discourse.group/u/anon419083)\
**Post date:** [April 8, 2024, 4:33pm UTC](https://swi-prolog.discourse.group/t/solve-logical-program-as-a-linear-system-of-in-equalities/7360/12 "2024-04-08T16:33:46Z")

</div>

Not a big issue. It’s a good thing that you (being a young student, I assume) have this kind of intellectual ambitions. Last thing I did in “programming” was creating a Snake game in Python (following a tutorial on Youtube) and I have to say that I’m quite happy with the result…Tic-Tac-Toe should come next 😅 🦉

---

<div class="post-metadata">

**Author:** ![wlodr](https://avatars.discourse-cdn.com/v4/letter/w/dec6dc/32.png) [@wlodr](https://swi-prolog.discourse.group/u/wlodr)\
**Post date:** [April 11, 2024, 1:49pm UTC](https://swi-prolog.discourse.group/t/solve-logical-program-as-a-linear-system-of-in-equalities/7360/13 "2024-04-11T13:49:57Z")

</div>

maybe a ralated paper: Taisuke Sato. _A linear algebraic approach to datalog evaluation_, TPLP 2017, doi:10.1017/S1471068417000023  
Matrix operations over reals are employed there.