One Stop Computer Science

1 Jan

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*(part)*if*

–May be single term or conjunction

- Left side:
*consequent*(part)*then*

–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

## Leave a reply