ontolog-forum
[Top] [All Lists]

## Re: [ontolog-forum] Constraint Solving versus Inferencing

 To: "[ontolog-forum]" Philip Jackson Sat, 11 Oct 2014 06:45:57 -0400
 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>
```
_________________________________________________________________
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    (01)

```
 Current Thread [ontolog-forum] Constraint Solving versus Inferencing, David Whitten Re: [ontolog-forum] Constraint Solving versus Inferencing, Simon Spero Re: [ontolog-forum] Constraint Solving versus Inferencing, Rich Cooper Re: [ontolog-forum] Constraint Solving versus Inferencing, David Whitten Re: [ontolog-forum] Constraint Solving versus Inferencing, Rich Cooper Re: [ontolog-forum] Constraint Solving versus Inferencing, John F Sowa Re: [ontolog-forum] Constraint Solving versus Inferencing, Philip Jackson <= Re: [ontolog-forum] Constraint Solving versus Inferencing, Rich Cooper