Introduction

  • Programs in logic languages are expressed in a form of symbolic logic
  • Use a logical inferencing process to produce results
  • Declarative rather that procedural:

–Only specification of results are stated (not detailed procedures for producing them)

Compound Terms

  • Atomic propositions consist of compound terms
  • Compound term: one element of a mathematical relation, written like a mathematical function

–Mathematical function is a mapping

–Can be written as a table

  • Compound term composed of two parts

–Functor: function symbol that names the relationship

–Ordered list of parameters (tuple)

  • Examples:

student(jon)

like(seth, OSX)

like(nick, windows)

like(jim, linux)

Logical Operators

Name Symbol Example Meaning
negation Ø Ø a not a
conjunction Ç a Ç b a and b
disjunction È a È b a or b
equivalence º a º b a is equivalent to b
implication É

Ì

a É b

a Ì b

a implies b

b implies a

Quantifiers

Name Example Meaning
universal “X.P For all X, P is true
existential $X.P There exists a value of X such that P is true

Terms

  • This book uses the Edinburgh syntax of Prolog
  • Term: a constant, variable, or structure
  • Constant: an atom or an integer
  • Atom: symbolic value of Prolog
  • Atom consists of either:

–a string of letters, digits, and underscores beginning with a lowercase letter

–a string of printable ASCII characters delimited by apostrophes

  • Variable: any string of letters, digits, and underscores beginning with an uppercase letter
  • Instantiation: binding of a variable to a value

–Lasts only as long as it takes to satisfy one complete goal

  • Structure: represents atomic proposition

functor(parameter list)

Overview of Logic Programming

  • Declarative semantics

–There is a simple way to determine the meaning of each statement

–Simpler than the semantics of imperative languages

  • Programming is nonprocedural

–Programs do not state now a result is to be computed, but rather the form of the result

Rule Statements

  • Used for the hypotheses
  • Headed Horn clause
  • Right side: antecedent (if part)

–May be single term or conjunction

  • Left side: consequent (then part)

–Must be single term

  • Conjunction: multiple terms separated by logical AND operations (implied)

Goal Statements

  • For theorem proving, theorem is in form of proposition that we want system to prove or disprove – goal statement
  • Same format as headless Horn

  man(fred)

  • Conjunctive propositions and propositions with variables also legal goals

  father(X, mike)

Approaches

  • Matching is the process of proving a proposition
  • Proving a subgoal is called satisfying the subgoal
  • Bottom-up resolution, forward chaining
  • Top-down resolution, backward chaining
  • Prolog implementations use backward chaining

Subgoal Strategies

  • When goal has more than one subgoal, can use either

–Depth-first search:  find a complete proof for the first subgoal before working on others

–Breadth-first search: work on all subgoals in parallel

  • Prolog uses depth-first search

–Can be done with fewer computer resources

Backtracking

  • With a goal with multiple subgoals, if fail to show truth of one of subgoals, reconsider previous subgoal to find an alternative solution: backtracking
  • Begin search where previous search left off
  • Can take lots of time and space because may find all possible proofs to every subgoal

Trace

  • Built-in structure that displays instantiations at each step
  • Tracing model of execution – four events:

Call (beginning of attempt to satisfy goal)

Exit (when a goal has been satisfied)

Redo (when backtrack occurs)

Fail (when goal fails)

List Structures

  • Other basic data structure (besides atomic propositions we have already seen): list
  • List is a sequence of any number of elements
  • Elements can be atoms, atomic propositions, or other terms (including other lists)

  [apple, prune, grape, kumquat]

[]   (empty list)

  [X | Y]   (head X and tail Y)

Deficiencies of Prolog

  • Resolution order control

–In a pure logic programming environment, the order of attempted matches is nondeterministic and all matches would be attempted concurrently

  • The closed-world assumption

–The only knowledge is what is in the database

  • The negation problem

–Anything not stated in the database is assumed to be false

  • Intrinsic limitations

–It is easy to state a sort process in logic, but difficult to actually do—it doesn’t know how to sort