AR5 LP Eng

Views:
 
     
 

Presentation Description

No description available.

Comments

Presentation Transcript

Logic Programming: 

Logic Programming Automated Reasoning in practice

Motivation: monotonicity: 

Motivation: monotonicity

Default reasoning:: 

Default reasoning: Is a form of reasoning that we’d like to use permanently otherwise the rules are far too complex! Is usually supported by hierarchy, inheritance and exceptions in OOP also an early AI-formalism CANNOT be expressed in FOL independent on the knowledge representation !! CAN be expressed in some FOL extensions non-monotone logics the simplest one of those is … …

Logic Programming: 

Logic Programming Resolution-based automated reasoning: restricted to Horn clauses restricted to backwards linear resolution BUT: with 3 important new extensions: return Answer Substitutions Least-model semantics instead of standard FOL model semantics Extending Horn clause logic with Negation as Finite Failure

Answer substitutions: 

Answer substitutions The link to programming

Answer substitutions: 

Answer substitutions false  anc(u,v) That is: u = A and v = C (composition of all mgu’s applied to the goal variables)

And computes ALL answers: 

The third answer: u = B and v = C Another answer: u = A and v = B And computes ALL answers false  anc(u,v)

Logic PROGRAMMING: 

Logic PROGRAMMING Prolog, Mercury, XSB, … with an efficiency comparable with C ! and even faster for some programs.

Practical programming?: 

Practical programming?

Least model semantics: 

Least model semantics Specify in a more compact way

Least model semantics: 

Least model semantics We get no proof of inconsistency ! FOL semantics says: celebrity(DeSchreye) is not logically entailed, thus: we do not know if it is true or not! Least model semantics says: ~ celebrity(DeSchreye)

Formally: the idea: 

In FOL: Formally: the idea Consequences are in the intersection: p en ~r. We do not know anything about the truth of q and s. In LP: Consequences are in the intersection: p en ~r. Other predicates are NOT true: ~q and ~s.

Relation with FOL: 

Relation with FOL

The “closed” assumption: 

The 'closed' assumption Logic programming provides a compact way to express ‘complete knowledge’ on some subject. If you do not say that something is true, than it is false. In other words: Logic Programming supports formulating definitions of the concepts. Not just state what is true about these concepts (=FOL) ! The Closed World Assumption ! (= everything not entailed by the theory is false)

How relevant is the change of semantics?: 

How relevant is the change of semantics? In FOL: {smart(Kelly)} implies neither strong(Kelly) nor ~strong(Kelly) In LP: {smart(Kelly)} implies ~strong(Kelly) In particular: LP is a non-monotone logic !! In {smart(Kelly), strong(Kelly)} , ~strong(Kelly) is no longer entailed. Knowledge is differently represented in these 2 formalisms. Also: some concepts can be completely axiomatized in LP but not in FOL. Ex.: the natural numbers !

Negation as finite failure: 

Negation as finite failure

Negation as finite failure: 

Negation as finite failure The basic idea: extending the representation power of Logic Programming beyond the Horn Clauses logic How? equivalent: allow disjunctions in the heads allow negation before the body atoms both give complete predicate logic ! (but: with the least model semantics we will get something different from FOL!)

Meaning of negation as finite failure: 

Not the meaning of standard negation Meaning of negation as finite failure This is meaningful only with the least model semantics (where everything that is not proven to be ‘true’, is considered to be ‘false’)

The ancestor example: 

Try to prove that 'anc(John,B)' holds! The ancestor example Conclusion: not anc(John,B)

Another example: 

even(0) even(s(s(x)))  even(x) odd(y)  not even(y) false  odd(s(s(s(0)))) Another example

And another example: 

q  q p  not q false  p And another example But ~q is true according to the least model semantics!

Default reasoning in LP (1):: 

Default reasoning in LP (1): locomotion(x,Fly)  isa(x,Bird), not abnormal1(x) locomotion(x,Walk)  isa(x,Ostrich), not abnormal2(x) isa(x,Bird)  isa(x,Ostrich) abnormal1(x)  isa(x,Ostrich) false andlt;- isa(Fred,Bird), not abnormal1(Fred) false andlt;- not abnormal1(Fred) fails false andlt;- isa(Fred,Ostrich)

Default reasoning in LP (2):: 

Default reasoning in LP (2): locomotion(x,Fly)  isa(x,Bird), not abnormal1(x) locomotion(x,Walk)  isa(x,Ostrich), not abnormal2(x) isa(x,Bird)  isa(x,Ostrich) abnormal1(x)  isa(x,Ostrich) isa(Fred,Bird) false andlt;- isa(Fred,Bird), not abnormal1(Fred) false andlt;- not abnormal1(Fred) false andlt;- isa(Fred,Ostrich) false andlt;-

Default reasoning (3):: 

Default reasoning (3): false andlt;- isa(Fred,Ostrich), not abnormal2(Fred) false andlt;- not abnormal2(Fred) fails

Prolog: 

A specific programming language based on LP. Prolog Uses a depth-first strategy to search linear resolution proofs. incomplete can get stuck in infinite branches Has a bunch of built-in predicates (sometimes without logical meaning) for: Numerical computations, input-output, changing the search strategy, meta-programming, etc. More recent LP languages: Goedel, Mercury, Hal, ..

Beyond FOL and Logic Programming: 

Beyond FOL and Logic Programming Logic Programming is very useful if you have a COMPLETE knowledge over your predicates FOL is very useful if your knowledge is INCOMPLETE Combine ! Open Logic Programming LP-definitions for the part for which you have a complete knowledge, FOL formulae for the rest.

Constraint Logic Programming : 

Constraint Logic Programming Integrate constraint processing techniques (consistency, forward checking, looking ahead, …) with Logic Programming. Advantages of Logic for knowledge representation Advantages of Constraint solving for efficient problem solving A number of languages: CHIP, Eclipse, Sicsus, etc.

authorStream Live Help