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.