COMP4418 – Prolog Programming

COMP 4418, 2014 { Assignment 1

 

Questions 1, 2 & 3 Due: 11:59:59am Wednesday 27 August (Late penalty: 10 marks per day) Questions 4 & 5 Due: 11:59:59am Wednesday 3 September (Late penalty: 10 marks per day)

 

Worth:¹₃ .

 

This assignment consists of ve questions. The rst two questions require written answers only. The second two questions require some programming.

 

1. [10 Marks] (Propositional Inferences)

 

Prove whether or not the following inferences hold in propositional logic using the truth table method.

 

(a) j= p ! (q ! p)

 

(b) p j= q ! p

 

(c) p ! (q ! r) j= r ! (q ! p)

 

(d) p $ q j= (q $ r) ! (p $ r)

 

(e) p $ q j= (p ^ q) _ (:p ^ :q)

 

Prove whether or not the following inferences hold in propositional logic using resolution.

 

(f) :(p ! q) ` :q

 

(g) p ` p _ q

 

(h) p $ q ` :(:p $ :q)

 

(i) ` (:p ^ :q) ! (p $ q)

 

(j) :q ! :p; :r ! :q ` p ! r

 

2. [20 Marks] (Logic Puzzle)

 

Donald and Daisy Duck took their nephews aged 4, 5 and 6 on an outing. Each boy wore a tee-shirt with a di erent design on it and of a di erent colour. You are also given the following information:

 

Huey is younger than the boy in the green tee-shirt

 

The ve year-old wore the tee-shirt with the camel design Dewey’s tee-shirt was yellow

 

Louie’s tee-shirt bore the gira e design

 

The panda design was not featured on the white tee-shirt

 

(a) Represent these facts as sentences in rst-order logic.

 

(b) Using your formalisation in part (2a), is it possible to conclude the age of each boy together with the colour and design of the tee-shirt they’re wearing? Show semantically how you determined your answer.

 

(c) If your answer to part (2b) was `no’, indicate what further sentences you would need to add to your formalisation so that you could conclude the age of each boy together with the colour and design of the tee-shirt they’re wearing.

 

 

 

1

 

 

3. [15 Marks] (Resolution)

 

It is possible to consider several variants to the resolution proof procedure, some of which were men-tioned in lectures. We shall consider one variant here.

 

A unit resolution is one in which a resolvent is obtained using at least one parent which is a unit clause (i.e., a single literal) or a unit factor¹ of a parent clause.

 

A unit deduction is one in which every resolution is a unit resolution. A unit refutation is a unit deduction of the empty clause.

 

(a) While completeness is an important consideration for automated deduction, so is e ciency. At times we may be willing to forego completeness for the sake of e ciency. Show that unit resolution is incomplete. [Hint: exhibit a set of clauses and explain your answer.]

 

(b) Given a set of Horn clauses, show that there is a unit refutation from S if and only if S is unsatis able.

 

4. [35 Marks] (Satis ability)

 

Determining whether a set of clauses is satis able or not is a fundamental problem in knowledge representation and reasoning (and in arti cial intelligence and computer science where it was the problem considered in describing the notion of NP-complete problems). In order to better understand the computational nature of the satis ability problem, researchers have investigated various instances of the problem. One well studied instance is 3-SAT which focusses on the satis ability of sets of clauses (i.e., disjunctions of literals) which have exactly three literals. For example, fp _ q _ r; p _ :s _ tg. 3-SAT is known to be NP-complete.

 

It is also known that 3-SAT exhibits an easy-hard-easy computational pattern. Determining the satisi – ability of sets of clauses that are small in relation to the total number of distinct propositional variables in the set is usually easy because there are fewer constraints in assigning truth values to the propo-sitional variables. Determining the satisi ability of sets of clauses that are large in relation to the total number of distinct propositional variables in the set is usually easy because there are too many constraints to assign truth values to the propositional variables and the set is unsatis able. Somewhere in between these two extremes the satis ability problem becomes hard.

 

Your task in this question is to determine empirically at what point the satis ability problem becomes di cult. More speci cally, you are to determine, approximately, a constant value C for number of propositional variables n at which C:n clauses constitutes a hard satisi ability problem.

 

To help you in this task, the satis ablity solver minisat is available on the CSE machines from:

 

~morri/bin/minisat

 

You can run this program as follows:

 

~morri/bin/minisat file.cnf

 

where file.cnf is a le containing clauses in CNF in DIMACS format. DIMACS format consists of three types of lines:

 

lines beginning with the letter c are comments;

 

one line with the format p cnf variables clauses where variables is the number of propositional variables and clauses is the number of clauses;

 

¹If two (or more) literals of a clause C have a most general uni er , then C is known as a factor of C. For example, C = [Q(x); Q(g(y)); :R(x)] has a most general uni er = fx=g(y)g giving the factor [Q(g(y)); :R(g(y))].

 

 

 

2

 

 

lines specifying clauses where a positive literal is speci ed by a number (identifying the literal) and a negative literal is speci ed by the corresponding negative number; each line is terminated by the number 0.

 

For example, the set of clauses fp _ q _ r; p _ :s _ tg would be represented DIMACS formart as:

 

c example CNF file with 5 propositional variables and 2 clauses p cnf 5 2

 

1 2 3 0

 

1 -4 5 0

 

While you can write your own satis ability solver and are welcome to do so, your task is to write a program to randomly generate test les containing clauses and to use these test les to empirically determine the value C explained above.

 

You are then to write a report explaining your empirical results and how you determined the value C. The use of tables and graphs to support your results is desirable.

 

For this question you must submit your report and any source code les used in answering this question.

 

5. [20 Marks] (Automated Theorem Proving)

 

In 1958 the logician Hao Wang implemented one of the rst automated theorem provers. He succeeded in writing several programs capable of automatically proving a majority of theorems from the rst ve chapters of Whitehead and Russell’s Principia Mathematica (in fact, his program managed to prove over 200 of these theorems within about 37 minutes, and 12/13 of the time is used for read-in and print-out”). This was an impressive achievment at the time; previous attempts had only succeeded in proving a handful of the theorems in Principia Mathematica.

 

Background

 

Wang’s idea is based around the notion of a sequent (this idea had been introduced years earlier by Gentzen) and the manipulation of sequents. A sequent is essentially a list of formulae on either side of a sequent (or provability) symbol `. The sequent ` , where and are strings (i.e., lists) of formulae, can be read as he formulae in the string follow from the formulae in the string ” (or, equivalently, he formulae in string prove the formulae in string “).

 

To prove whether a given sequent is true all you need to do is start from some basic sequents and successively apply a series of rules that transform sequents until you end up with the sequent you desire. This process is detailed below.

 

Additionally, determining whether a formula is a theorem, is equivalent to determining whether the sequent ; ` is true (e.g., ` : _ ).

 

Formulae

 

Connectives

 

We allow the following connectives in decreasing order of precedence:

 

: | negation

 

^ | conjunction; _ | disjunction (both same precedence)

 

! | implication; $ | biconditional (both same precedence).

 

 

3

 

 

Formula

 

A propositional symbol (e.g., p; q; : : 🙂 is an atomic formula (and thus a formula).

 

If ; are formulae, then : ; ^ ; _ ; ! ; $ are formulae.

 

Sequent

 

If and are strings of formulae (possibly empty strings) and is a formula, then ; ; is a string and ` is a sequent.

 

Rules

 

The logic consists of the following sequent rules. The rst rule (P1) gives a characterisation of simple theorems. The remaining rules are simply ways of transforming sequents into new sequents. The manner in which you can construct a proof for a sequent to determine whether it holds or not is given below.

 

P1 Initial Rule: If ; are strings of atomic formulae, then ` is a theorem if some atomic formula occurs on both side of the sequent `.

In the following ten rules and are always strings (possibly empty) of formulae.

 

Proofs

 

The basic idea in proving a sequent ` is to begin with instance(s) of Rule P1 and successively apply the remaining rules until you end up with the sequent you are hoping to prove.

 

For example, suppose you wanted to prove the sequent :(p_q) ` :p. One possible proof would proceed as follows.

 

However, a simpler idea (as it will involve much less search) is to begin with the sequent(s) to be proved and apply the rules above in the ackward” direction until you end up with the sequent you desire. In the example then, you would begin at step 4 and apply each of the rules in the backward direction until you end up at step 1 at which point you can conclude the original sequent is a theorem.

 

4

 

Question Speci cation

 

In this assignment you are to emulate Hao Wang’s feats and implement a propositional theorem prover.

 

The main predicate of your program is to be prove/1 which is to take a list of sequents as argument and determine whether every sequent in the list can be proved. For example, prove([[neg(p or q)] seq [neg p]]) would return Yes.

 

Sequents are to be speci ed as List1 seq List2 where List1 and List2 are lists (strings) of propo-sitional formulae and seq represents the sequent symbol `. For example, [neg(p or q)] seq [neg p] is a sequent. The predicate prove is to take a list of sequents (as speci ed above) and return true (Yes) if all the sequents in the list are true.

 

Furthermore, propositional formulae are to be constructed using the operators neg, and, or, imp and iff representing the connectives described above. You are to introduce these using Prolog’s op/3 predicate (you might like to consult the SWI manual on-line).

 

Submission for this Question

 

There are to be two parts to your submission for this question.

 

Your commented Prolog code in a le that must be named a1-q5.pl

 

A brief report detailing the strategy you adopted in writing your program and a description of the main predicates you have used. Be direct and to the point. Place the report in a text le that must be named a1-q5.txt.

 

Marking for this Question

 

Code: 40%

 

Given test data: 20% Hidden test data: 20% Report: 20%

 

Bonus Marks

 

Bonus marks (maximum 5%) will be awarded if you can modify your program to include a predicate printprove/1 which prints out a proof of the sequent if one exists. The format of the output is up to you but it must be clear which rule is being applied and include references to line numbers of the proof in your proof output. Marks will be awarded for the clarity of output.

 

References

 

[1] Hao Wang, Toward Mechanical Mathematics, IBM Journal for Research and Development, volume 4, 1960. (Reprinted in: Hao Wang, “Logic, Computers, and Sets”, Sciene Press, Peking, 1962. Hao Wang, “A Survey of Mathematical Logic”, North Holland Publishing Company, 1964. Hao Wang, “Logic, Computers, and Sets”, Chelsea Publishing Company, New York, 1970.)

 

[2] Alfred North Whitehead and Bertrand Russell, Principia Mathematica, 2nd Edition, Cambridge University Press, Cambridge, England, 1927.

 

 

5

 

A List of 10 Propositional Theorems

 

You may nd it instructional to prove these by hand rst.

 

(a) ` :p _ p

 

(b) :(p _ q) ` :p

 

(c) p ` q ! p

 

(d) p ` p _ q

 

(e) (p ^ q) ^ r ` p ^ (q ^ r)

 

(f) p $ q ` :(p $ :q)

 

(g) p $ q ` (q $ r) ! (p $ r)

 

(h) ` (:p ^ :q) ! (p $ q)

 

(i) p $ q ` (p ^ q) _ (:p ^ :q)

 

(j) p ! q; :r ! :q ` p ! r

 

Assignment Submission

 

There are two parts to your assignment submission.

 

Your answers to Questions 1, 2 and 3 in a PDF le which can be submitted using the command: give cs4418 a1 1 file.pdf

 

The deadline for this submission is 11:59:59am Wednesday 27 August.

 

Your answers to Questions 4 in a PDF le along with any source code les used in answering this question. As noted above, for Question 5 you must submit two les that are named a1-q5.pl and a1-q5.txt. All these les ccan be submitted using the command:

 

give cs4418 a1 2 q3-file.pdf q3-other-files a1-q4.pl a1-q4.txt

 

The deadline for this submission is 11:59:59am Wednesday 3 September.

 

Late Submissions

 

In case of late submissions, 2% will be deducted for each day late.

 

No extensions will be given for any of the assignments (except in case of illness or misadventure). Read the study guide carefully for the rules regarding plagiarism.