Logic Programming and Symbolic Logic

Introduction

• Logic languages are expressed in a form of symbolic logic.
• Logical referencing is used to produce results.
• Logic languages are declarative, meaning only results are specified, not the procedures.

Proposition

• A proposition is a logical statement that may or may not be true.
• Propositions consist of objects and relationships between objects.

Symbolic Logic

• Symbolic logic expresses propositions.
• Symbolic logic expresses relationships between propositions.
• Symbolic logic describes how propositions can be inferred from other propositions.
• Predicate calculus is a form of symbolic logic used for logic programming.

Object Representation

• Objects in propositions are represented by simple terms consisting of constants and variables.
• A constant is a symbol that represents an object.
• A variable is a symbol that can represent different objects at different times.
• Object representation in logic programming is different from variables in imperative languages.

Compound Terms

• Atomic propositions consist of compound terms.
• A compound term is one element of a mathematical relation, written like a mathematical function.
• Mathematical functions are a mapping that can be written as a table.

Parts of a Compound Term

• Compound terms are composed of a functor and an ordered list of parameters (tuple).
• The functor is a function symbol that names the relationship.
• Examples include student(jon), like(seth, OSX), like(nick, windows), like(jim, linux).

Forms of a Proposition

• Propositions can be stated as facts or queries.
• A fact is a proposition assumed to be true.
• A query is a proposition whose truth is to be determined.
• Compound propositions have two or more atomic propositions.
• Propositions are connected by operators.

Logical Operators

• 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 implies b), a ⊂ b (b implies a)

Quantifiers

• Universal: ∀X.P (For all X, P is true)
• Existential: ∃X.P (There exists a value of X such that P is true)

Clausal Form

• Clausal form is a standard form for propositions.
• B₁ ∪ B₂ ∪ ... ∪ Bₙ ⊂ A₁ ∩ A₂ ∩ ... ∩ Aₘ means if all the As are true, then at least one B is true
• Antecedent is the right side of the expression.
• Consequent is the left side of the expression.

Predicate Calculus and Proving Theorems

• Propositions are used to discover new theorems that can be inferred from known axioms and theorems.
• Resolution is an inference principle that allows inferred propositions to be computed from given propositions.

Resolution

• Unification finds values for variables that allows a matching process to succeed.
• Instantiation assigns temporary values to the variable to allow unification to succeed.
• Backtracking is sometimes required if the matching fails after instantiating a variable, and a different value needs to be instantiated.

Proof by Contradiction

• Hypotheses: set of pertinent propositions.
• Goal: theorem negation stated as a proposition.
• Theorem proven by finding an inconsistency.

Theorem Proving

• Theorem proving is the basis for logic programming.
• When propositions are used for resolution, only a restricted form can be used.
• Horn clauses have only two forms: headed and headless.
• Headed: single atomic proposition on left side.
• Headless: empty left side (used to state facts).
• Most propositions can be stated as Horn clauses.

Overview of Logic Programming

• Declarative semantics: a simple way to determine the meaning of each statement that is simpler than the semantics of imperative languages.
• Programming is nonprocedural: Programs do not state how a result is to be computed, but rather the form of the result.

Example: Sorting a List

• Describe the characteristics of a sorted list, not the process of rearranging a list i.e. sort(old_list, new_list) ⊂ permute (old_list,new_list) ∩ sorted (new_list)
• The formula* sorted (list) ⊂ ∀j such that 1≤ j < n, list(j) ≤ list (j+1)* is an example of describing the characteristics of a sorted list.

The Origins of Prolog

• University of Aix-Marseille (Calmerauer & Roussel): Natural language processing
• University of Edinburgh (Kowalski): Automated theorem proving

Terms

• Edinburgh syntax of Prolog is used.
• A term is a constant, variable, or structure.
• A constant is an atom or an integer.
• An atom is a symbolic value of Prolog and consists of a string of letters, digits, and underscores beginning with a lowercase letter or a string of printable ASCII characters delimited by apostrophes.

Terms: Variables and Structures

• A variable is any string of letters, digits, and underscores beginning with an uppercase letter.
• Instantiation is the binding of a variable to a value and lasts only as long as it takes to satisfy one complete goal.
• Structure represents atomic proposition functor (parameter list)

Fact Statements

• Fact statements are used for the hypotheses.
• They are headless Horn clauses i.e. female(shelley)., male(bill)., father(bill, jake).

Rule Statements

• Rule statements are used for the hypotheses.
• They are headed Horn clauses
• The right side of a rule statement is the antecedent (if part) which may be single term or conjunction
• The left side of a rule statement is the consequent (then part) which must be single term
• Conjunction is multiple terms separated by logical AND operations (implied).

Example Rules

• Variables can be used to generalize meaning i.e. universally quantified objects.
• parent(X,Y):- mother(X,Y). is an example of a rule statement.
• grandparent(X,Z):- parent(X,Y), parent(Y,Z). is an example of a rule statement.

Goal Statements

• For theorem proving, a theorem is in the form of a proposition that is to be proven or disproven via a goal statement.
• Goal statements have the same format as headless Horn clauses i.e. man(fred)
• Conjunctive propositions and propositions with variables are also legal goals i.e. father(X, mike)

Inferencing Process of Prolog

• Queries are called goals.
• If a goal is a compound proposition, each of the facts is a subgoal.
• To prove a goal is true, a chain of inference rules and/or facts.
• Proving a subgoal is called matching, satisfying, or resolution.

Approaches

• Matching is the process of proving a proposition.
• Proving a subgoal is called satisfying the subgoal.
• Bottom-up resolution is forward chaining which begins with facts and rules of database and finds sequence that leads to goal effectively for large sets of correct answers
• Top-down resolution, or backward chaining, begins with a goal and attempts to find sequence that leads to set of facts in database, effective for small sets of correct answers
• Prolog implementations use backward chaining.

Subgoal Strategies

• When a goal has more than one subgoal, either depth-first or breadth-first search strategies can be used.
• Depth-first search finds a complete proof for the first subgoal before working on others.
• Breadth-first search works on all subgoals in parallel.
• Prolog uses depth-first search and can be done with fewer computer resources.

Backtracking

• When one of multiple subgoals cannot be satisfied, the previous subgoal is reconsidered to find an alternate solution.
• Begin search where previous search left off.
• Backtracking can take lots of time and space because all possible proofs to every subgoal may need to be found.

Simple Arithmetic

• Prolog supports integer variables and integer arithmetic.
• is operator takes an arithmetic expression as right operand and variable as left operand.
• A is operator is not the same as an assignment statement

Example

speed(ford,100).
speed(chevy,105).
speed(dodge,95)
speed(volvo,80).
time(ford,20)
time(chevy,21).
time(dodge,24).
time(volvo,24).
distance(X,Y) :- speed(X,Speed), time(X,Time), Y is Speed * Time.

• Distance is computed as Speed * Time
• A query example is distance(chevy, Chevy_Distance).

Trace

• A trace is a built-in structure that displays instantiations at each step.
• The tracing model of execution includes four events: Call, Exit, Redo, Fail.
• Call is the beginning of attempt to satisfy goal.
• Exit is when a goal has been satisfied.
• Redo is when backtrack occurs.
• Fail is when goal fails.

Example

likes(jake,chocolate).
likes(jake, apricots)
likes(darcie, licorice).
likes(darcie, apricots)
trace.
likes(jake, X), likes(darcie, X).
(1) 1 Call: likes(jake, _0)?
(1) 1 Exit: likes(jake, chocolate)
(2) 1 Call: likes(darcie, chocolate)?
(2) 1 Fail: likes(darcie, chocolate)
(1) 1 Redo: likes(jake, _0)?
(1) 1 Exit: likes(jake, apricots)
(3) 1 Call: likes(darcie, apricots)?
(3) 1 Exit: likes(darcie, apricots)
X = apricots

List Structures

• List is a basic data structure (besides atomic propositions we have already seen) which is a sequence of elements.
• Elements can be atoms, atomic propositions, or other terms (including other lists)
• [apple, prune, grape, kumquat] is a list of atoms
• [] an empty list
• [X | Y] is the head X and tail Y

Append Example

append([], List, List).
append([Head | List_1], List_2, [Head | List_3]) :-
append (List 1, List 2, List 3).

More Examples

• Underscore character means an anonymous variable, meaning instantiation does not matter.

reverse([], []).
reverse([Head | Tail], List) :-
reverse (Tail, Result),
append (Result, [Head], List).

member(Element, [Element | _]).

member(Element, [_ | List]) :-
member(Element, List).

Deficiencies of Prolog

• Resolution order control

• Order Matches are non deterministic as all matches would be attempted concurrently in a pure logic programming environment

• In Closed-world assumption the only knowledge is what in the database.

• Negation Problem in which Anything not stated in the database is assumed to be false

• Intrinsic limitations

• It is easy to state a sort process in logic, but does not know how to sort.

Applications of Logic Programming

• Relational database management systems
• Expert systems
• Natural language processing

Summary

• Symbolic logic provides the basis for logic programming.
• Logic programs should be nonprocedural.
• Prolog statements are facts, rules, or goals.
• Resolution is the primary activity of a Prolog interpreter.
• Although there are a number of drawbacks with the current state of logic programming, it has been used in a number of areas.