Session 13: Logic Programming Language

A. Definition of Logic Programming

Logic programming is a type of programming paradigm which is largely based on formal logic. Any program written in a logic programming language is a set of sentences in logical form, expressing facts and rules about some problem domain. Major logic programming language families include Prolog, Answer set programming (ASP) and Datalog.

Logic programming languages sometimes called declarative programming languages. Logic programming language express programs in a form of symbolic logic and use a logical inferencing process to produce results.

 

B. Background for Logic

• Proposition

A proposition is a logical statement that may or may not be true

• Today is Tuesday
• The Earth is round

Propositions can be stated in two forms:

• Fact: proposition is assumed to be true
• Query: truth of proposition is to be determined

Compound proposition:

• Have two or more atomic propositions
• Propositions are connected by operators

 

• Symbolic logic

Symbolic logic uses propositions to express ideas, relationships between ideas and to generate new ideas based on the given propositions

For symbolic logic, we use 1^st order predicate calculus

• statements include predicates like round(x) where this is true if we can find an x that makes it true such as round(Earth) or round(x) when x = Earth
• you might think of a predicate as a Boolean function except that rather than returning T or F, it finds an x that makes it true

• Object Representation

Objects in propositions are represented by simple terms: either constants or variables

• Constant is a symbol that represents an object
• Variable is a symbol that can represent different objects at different times

 

• Compound Terms

Compund terms is one element of a mathematical relation, written like a mathematical function.

• Mathematical function is a mapping
• Can be written as a table

Atomic propositions consists of compunds terms.

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)

 

C. Logical Operators & Quantifiers

Logical Operator

• Equivalence means that both expressions have identical truth tables
• Implication is like an if-then statement
• if a is true then b is true
• note that this does not necessarily mean that if a is false that b must also be false

 

Quantifier

• Universal quantifier says that this is true no matter what x is
• Existential quantifier says that there is an X that fulfills the statement

 

D. Definition of Prolog

Prolog is a programming language that allows the programmer to specify declarative statements only

declarative statements (things you are declaring) fall into 2 categories

• predicates/propositions that are true
• clauses (truth preserving rules in clausal form)

once specified, the programmer then introduces questions to be answered. Prolog uses unification to perform the problem solving automatically resolution (backward chaining) and

 

E. Elements of Prolog

• Terms: constant, variable, structure
  • Constants are atoms or integers (atoms are like those symbols found in Lisp)
  • Atom is a symbolic value of Prolog.
  • Variables are any string of letters, digits, and underscores beginning with an uppercase letter
  • Instantiation is the binding of a variable to a value. An instantiation will last as long as it takes to complete a goal
  • Structures are predicates and are represented as functor(parameter list) where functor is the name of the predicate
• All statements in Prolog consist of clauses
  • headed clauses are rules
  • headless clauses are statements that are always true
    • in reality, a headless clause is a rule whose condition is always true
  • all clauses must end with a period

 

F. Rules

All rules are stated in Horn clause form

• the consequence comes first
  • the symbol :- is used to separate the consequence from the antecedent
• And is denoted by , and Or is denoted by ; or separating the rule into two separately rules
• variables in rules are indicated with upper-case letters
• rules end with a “.” (dot).
• examples:
  • parent(X, Y) :- mother(X, Y).
  • parent(X, Y) :- father(X, Y).
  • grandparent(X, Z) :- parent(X, Y), parent(Y, Z).
  • sibling(X, Y) :- mother(M, X), mother(M, Y), father(F, X), father(F, Y).
• we can use _ as a wildcard meaning this is true if we can find any clause that fits
  • father(X) :- father(X, _), male(X).

X is a father if X is male and is someone’s father

 

G. Goal Statements

Goal statement theorem proving is in form of proposition that we want system to prove or disprove.

Goal statement has the same format as headless Horn

• man(fred)

Conjunctive propositions and propositions with variables are also legal goals

• father(X, mike)

 

 

H. 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, must find a chain of inference rules and/or facts. For goal Q:

P₂ :- P₁

P₃ :- P₂

…

Q :- P_n

• Process of proving a subgoal is called matching, satisfying, or resolution

I. Backtracking and Trace

Backtracking is finding an alternative solution in a previous subgoal when a subgoal in a goal with multiple subgoal fail to show truth.

Backtracking begin search at where the previous search left off

Backtracking can take a lot of time and space because it may need to find all possible proofs in every subgoal.

Tracing is a built-in structure that displays instantiations at each step

Tracing has 4 model of execution:

• Call, is the beginning of an attempt to satisfy goal
• Exit, is when a goal has been satisfied
• Redo, is when backtrack occurs
• Fail, is when goal fails

J. 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 sor

Source(s) :

https://en.wikipedia.org/wiki/Logic_programming#Logic_and_control

www.nku.edu/~foxr/CSC407/NOTES/ch16.ppt

www.sce.carleton.ca/courses/sysc-3101/w12/…/pl9ch16.ppt

Slide Binus Maya