Week 9 Intro to Prolog

Question 1

Logic programming

Answer 1

Logic is used to express knowlege (describe program)
Inference is used to compute and obtain solutions to programs

Question 2

Advantages of logic programming

Answer 2

Advantages:
. declarative style of programming
. program can be used in different ways
. PRECISE AND SIMPLE SEMANTICS
. same formalism to write programs , manipulate them , prove properties

Question 3

Disadvantage of logic programming

Answer 3

The capability to handle arithmetic and IO operations comes at the expense of declarative semantics
. Only a fragment of classical first order logic

Question 4

What is domain of computation in prolog

Answer 4

Terms

Question 5

What are terms

Answer 5

Variable (X,Y,Z)
function symbols ie f with arity n that takes t1 … tn as arguments where t1…tn are terms

function with arity 0 is a constant ie a (lowecase)
function with arity n>=1 f(t1…tn)

Question 6

Predicate symbols

Answer 6

if p is a predicate with arity n and has arguments t1 …tn where t1..tn are terms then p(t1…tn) is an Atomic formula A

Question 7

What is a literal

Answer 7

Atomic formula or its negation

Question 8

IMPORTANT

Answer 8

PREDICATES TAKE TERMS AS ARGUMENTS NOT OTHER PREDICATES

Question 9

horn clause

Answer 9

disjunction of literals of which at most one is positive

Question 10

definite horn clause

Answer 10

disjunction of literals where there is exactly one positive literal

Question 11

Horn clause 3 cases

Answer 11

One positive (fact)
one positive some negfative (rule)
only negatives (goal)

Question 12

What is a program in prolog

Answer 12

set of definite horn clauses ie a set of facts and rules

Question 13

IMPORTANT NOTE ABOUT VARIABLES

Answer 13

ALL VARIABLES IN PROLOG INDIVIDUALLY UNIVERSALLY QUANTIFIED

Question 14

What is a value

Answer 14

term associated to variables by means of a substitutiobn

Question 15

Substitiution

Answer 15

partial mapping of Variables to terms

NOT TERMS TO VARIABLES AS NOT ALL TERMS CAN BE REPLACED (IE CONSTANTS …

Question 16

IMPORTANT FACT ABOUT SUBSTITUTION

Answer 16

simultaneously replace each variable

ie t = loves ( X, Y) σ = {X -> Y , Y -> a }

tσ = loves( Y , a)

NOT loves(a,a) since we simultaneously replace not one after the other

Question 17

JUST READ

Answer 17

Order of clauses significant as resolution applied in program order
selection function picks leftmost goal

Question 18

Just READ - Language limitationbs

Answer 18

Negation:

Prolog programs are composed of definite clauses which contain one +ve literal. Therefore it is impossible to state facts involving negative statements or rules with negative literals in their head

General Resolution:

If there was no restrictions then 1) clauses can be resolved in multiple ways, 2) we need to arbitrarily chose the next pair of clauses
Consequences: resolution of a program with a goal can be made unique and deterministic, Resolvent of 2 clauses will either be empty(success) or generate a new goal