Session 13(Last) : Logic Programming Languages

Introduction

Logic programs are declarative rather than procedural, which means that only the specifications of the desired results are stated rather than detailed procedures for producing them. Programs in logic programming languages are collections of facts and rules. Programming that uses a form of symbolic logic as a programming language is often called logic programming, and languages based on symbolic logic are called logic programming languages, or declarative languages. We have chosen to describe the logic programming language Prolog, because it is the only widely used logic language.

A proposition can be thought of as a logical statement that may or may not be true. It consists of objects and the relationships among objects. Formal logic was developed to provide a method for describing propositions, with the goal of allowing those formally stated propositions to be checked for validity.

The simplest propositions, which are called atomic propositions, consist of compound terms. A compound term is one element of a mathematical relation, written in a form that has the appearance of mathematical function notation.

A compound term is composed of two parts: a functor, which is the function symbol that names the relation, and an ordered list of parameters, which together represent an element of the relation. A compound term with a single parameter is a 1-tuple; one with two parameters is a 2-tuple, and so forth. For example, we might have the two propositions

            man(jake)                               << 1-tuple

            like(bob, steak)                      << 2-tuple

which state that {jake} is a 1-tuple in the relation named man. that mean a man named jake.

and that bob is a 2-tuple in relation named like. that mean "bob like steak".

Propositions can be stated in two modes: one in which the proposition is defined to be true, and one in which the truth of the proposition is something that is to be determined. In other words, propositions can be stated to be facts or queries.

Propositions can be stated in two forms:

- Fact: proposition is assumed to be true

- Query: truth of proposition is to be determined

Compound propositions have two or more atomic propositions, which are connected by logical connectors, or operators, in the same way compound logic expressions are constructed in imperative languages.

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

Symbolic logic can be used for the three basic needs of formal logic: to express propositions, to express the relationships between propositions, and to describe how new propositions can be inferred from other propositions that are assumed to be true.

Clausal Form

The right side of a clausal form proposition is called the antecedent. The left side is called the consequent because it is the consequence of the truth of the antecedent.

The Basic Elements of Prolog

*Terms

A Prolog term is a constant, a variable, or a structure. A constant is either an atom or an integer.

In particular, an atom is either a string of letters, digits, and underscores that begins with a lowercase letter or a string of any printable ASCII characters delimited by apostrophes.

A variable is any string of letters, digits, and underscores that begins with an uppercase letter or an underscore (_). Variables are not bound to types by declarations. The binding of a value, and thus a type, to a variable is called an instantiation. Instantiation occurs only in the resolution process. A variable that has not been assigned a value is called uninstantiated. Instantiations last only as long as it takes to satisfy one complete goal, which involves the proof or disproof of one proposition. The last kind of term is called a structure. Structures represent the atomic propositions of predicate calculus, and their general form is the same:

functor(parameter list)

The functor is any atom and is used to identify the structure. The parameter list can be any list of atoms, variables, or other structures.

*Fact Statements

Prolog has two basic statement forms; these correspond to the headless and

headed Horn clauses of predicate calculus. The simplest form of headless Horn

clause in Prolog is a single structure, which is interpreted as an unconditional

assertion, or fact. Logically, facts are simply propositions that are assumed to be true.

*Rule Statements

The other basic form of Prolog statement for constructing the database corresponds to a headed Horn clause. This form can be related to a known theorem in mathematics from which a conclusion can be drawn if the set of given conditions is satisfied. The right side is the antecedent, or if part, and the left side is the consequent, or then part. If the antecedent of a Prolog statement is true, then the consequent of the statement must also be true. Because they are Horn clauses, the consequent of a Prolog statement is a single term, while the antecedent can be either a single term or a conjunction. Conjunctions contain multiple terms that are separated by logical AND operations.

*Goal Statements

We have described the Prolog statements for logical propositions, which are used to describe both known facts and rules that describe logical relationships among facts. These statements are the basis for the theorem-proving model. The theorem is in the form of a proposition that we want the system to either prove or disprove. In Prolog, these propositions are called goals, or queries. The syntactic form of Prolog goal statements is identical to that of headless Horn clauses.

*The Inferencing Process of Prolog

Queries are called goals. When a goal is a compound proposition, each of the facts (structures) is called a subgoal. To prove that a goal is true, the inferencing process must find a chain of inference rules and/or facts in the database that connect the goal to one or more facts in the database. Because the process of proving a subgoal is done through a proposition matching process, it is sometimes called matching. In some cases, proving a subgoal is called satisfying that subgoal.

    =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

*Simple Arithmetic

Prolog supports integer variables and integer arithmetic.

The semantics of an is proposition is considerably different from that of an assignment statement in an imperative language. is operator takes an arithmetic expression as right operand and variable as left operand