Something else to note, which doesn't seem to have been mentioned in the thread, is that a wide class of constraint satisfaction problems are theoretically equivalent to determining the satisfiability of expressions in Boolean logic. This is the complexity class of NP-complete problems, which includes many decision and optimization problems.

http://en.wikipedia.org/wiki/Boolean_satisfiability_problem Phil

> Date: Sat, 11 Oct 2014 02:14:17 -0400

> From: sowa@xxxxxxxxxxx

> To: ontolog-forum@xxxxxxxxxxxxxxxx

> Subject: Re: [ontolog-forum] Constraint Solving versus Inferencing

>

> I just wanted to clarify some points in this thread.

>

> > For a constraint to be expressed in Boolean logic, aren't you then

> > moving out of the realm of propositional logic and into the realm

> > of first order predicate logic?

>

> No. Boolean logic is usually used as a synonym for propositional logic.

>

> But it's important to note that Boolean algebra is actually more general

> than propositional logic, since George Boole himself applied the algebra

> to several different domains:

>

> 1. If the letters represent propositions, you get propositional logic:

> 1 represents truth, 0 falsity, AxB is AND, A+B is OR, -A is NOT.

> Peirce observed that if A implies B, the truth value of A must be

> less than or equal to the truth value of B. Therefore, A≤B can

> be used to represent "If A, then B."

>

> 2. But GB also used the letters to represent a Boolean algebra of

> monadic predicates: 1 is the predicate that is true of everything,

> 0 is true of nothing, AxB is the predicate that is true of

> everything for which A and B are both true, etc.

>

> 3. GB also used the letters to represent sets: 1 is the universe

> of discourse, 0 is the empty set, A+B is the union of A and B,

> AxB is the intersection, and -A is the complement of A. But

> Boole's version of set theory was actually a version of mereology:

> he did not distinguish a single value x from the set {x}.

>

> Description logics take advantage of points #2 and #3 by treating

> a class a pair: a set and a predicate that is true of everything

> in the set. The same Boolean operators apply to both the sets and

> the predicates that determine them.

>

> > Even if you only use equality (=), and non-equality ('=)

> > to express your constraints, don't those two act as predicates?

>

> Well, yes. But you don't get predicate calculus without quantifiers.

> If you only have constants as the arguments of the predicates, the

> expressive power is limited to propositional logic.

>

> You can have constraint logic programming (CLP) with just equality.

> If you extend the notation to support inequalities, the solution

> to a CLP problem may consist of a family of possible options.

>

> John

>

> _________________________________________________________________

> Message Archives: http://ontolog.cim3.net/forum/ontolog-forum/

> Config Subscr: http://ontolog.cim3.net/mailman/listinfo/ontolog-forum/

> Unsubscribe: mailto:ontolog-forum-leave@xxxxxxxxxxxxxxxx

> Shared Files: http://ontolog.cim3.net/file/

> Community Wiki: http://ontolog.cim3.net/wiki/

> To join: http://ontolog.cim3.net/cgi-bin/wiki.pl?WikiHomePage#nid1J

>