COMP4418–Assignment 1

COMP4418–Assignment 1

Worth: 15%.
This assignment consists of four questions. The first two questions and the fourth question require written
answers only. The third question requires some programming and a written report.
1. [20 Marks] (Propositional Inferences)
For each of the following inferences:
(i) prove whether or not the following inferences hold in propositional logic using the truth table
method; and,
(ii) prove whether or not the following inferences hold in propositional logic using resolution.
Note that the following inferences will need to be proved or disproved both (i) semantically (|=) using
the truth table method; and, (ii) syntactically (`) using resolution:
(a) p ∧ (q ∨ r)[|= / `](p ∧ q) ∨ (p ∧ r)
(b) [|= / `]p → (q → p)
(c) ¬p → ¬q[|= / `]p → q
(d) ¬p → ¬q, ¬q → ¬p[|= / `]p ↔ q
(e) p → q, q → r[|= / `]¬r → ¬q
2. [30 Marks] (First-Order Logic Puzzle)
The following puzzle is taken from Professor Raymond M. Smullyan’s book “Alice in Puzzle Land: A
Carrollian Tale for Children Under Eighty”, Dover, 1987. Professor Smullyan was a renowned logician
and magician!
Consider the following scenario:
“How about making us some nice tarts?” the King of Hearts asked the Queen of Hearts one
cool summer day.
“What’s the sense of making tarts without jam?” said the Queen furiously. “The jam is the
best part!”
“Then use jam,” said the King.
“I can’t!” shouted the Queen. “My jam has been stolen!”
“Really!” said the King. “This is quite serious! Who stole it?”
“How do you expect me to know who stole it? If I knew, I would have had it back long ago
and the miscreant’s head in the bargain!”
Well, the King had his soldiers scout around for the missing jam, and it was found in the
house of the March Hare, the Mad Hatter, and the Doormouse. All three were promptly
arrested and tried.
“Now, now!” exclaimed the King at the trial. “I want to get to the bottom of this! I don’t
like people coming into my kitchen and stealing my jam!”
“Why not?” asked one of the guinea pigs.
1
“Supress that guinea pig!” shouted the Queen. The guinea pig was promptly suppressed.
(Those that have read Alices’ Adventures in Wonderland will recall the meaning of the word
suppress: The officers of the court put the guinea pig into a canvas bag, which tied up at
the mouth with strings, and sat upon it.)
“Now then,” said the King, after the commotion of suppressing the guinea pig had died
down, “I want to get to the bottom of this!”
“You’ve already said that,” remarked a second guinea pig. (This guinea pig was also promptly
suppressed.)
“Did you by chance steal the jam?” the King asked the March Hare.
“I never stole the jam!” pleaded the March Hare. (At this point all the remaining guinea
pigs cheered, and were all promptly supressed.)
“What about you?” the King roared to the Hatter, who was trembling like a leaf. “Are you
by any chance the culprit?”
The Hatter was unable to utter a word; he just stood there gasping and sipping his tea.
“If he has nothing to say, that only proves his guilt, ” said the Queen, “so off with his head
immediately!”
“No, no!” pleaded the Hatter. “One of us stole it, but it wasn’t me!”
“Make a note of that!” said the King to the jury. “This evidence might turn out to be quite
important!”
“And what about you?” continued the King to the Doormouse.
“What do you have to say about all this? Did the March Hare and the Hatter both tell the
truth?”
“At least one of them did,” replied the Doormouse, who then fell asleep for the rest of the
trial.
As subsequent investigation revealed, the March Hare and the Doormouse were not both
speaking the truth.
Who stole the jam?
(a) Represent the facts in this paragraph in first-order logic using the following constant symbols:
• marchHare, madHatter and doormouse; the names of the protagonists
• jam; the name of the object that was stolen
and the following predicates:
• Lying(x) and Stole(x,y).
(b) Using your formalisation in part (2a), is it possible to conclude who stole the jam? 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 who stole the jam.
(d) Using all the sentences you have added, determine who stole the jam syntactially.
3. [30 Marks] (Satisfiability)
Determining whether a set of clauses is satisfiable or not is a fundamental problem in knowledge
representation and reasoning (and in artificial 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 satisfiability problem, researchers have investigated various instances
of the problem. One well studied instance is 3-SAT which focusses on the satisfiability of sets of clauses
(i.e., disjunctions of literals) which have exactly three literals. For example, {p ∨ q ∨ r, p ∨ ¬s ∨ t}.
3-SAT is known to be NP-complete.
2
It is also known that 3-SAT exhibits an easy-hard-easy computational pattern. Determining the satisifiability 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 propositional variables. Determining the satisifiability 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 unsatisfiable. Somewhere
in between these two extremes the satisfiability problem becomes hard.
Your task in this question is to determine empirically at what point the satisfiability problem becomes
difficult for the 4-SAT problem (i.e., disjunctions with exactly 4 literals), if at all. More specifically,
you are to determine whether, approximately, a constant value C for number of propositional variables
n at which C.n clauses constitutes a hard satisifiability problem. It has been empirically established
for the general case of clauses in 3-SAT that C ≈ 4.2. You are to investigate whether satisfiability
for the 4-SAT problem exhibits an easy-hard-easy pattern and, if so, determine the value of C where
clauses are restricted to clauses with exactly 4 literals.
To help you in this task, the satisfiablity 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 file 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;
• lines specifying clauses where a positive literal is specified by a number (identifying the literal)
and a negative literal is specified by the corresponding negative number; each line is terminated
by the number 0.
For example, the set of Horn clauses {¬p∨¬q∨r, p∨¬s∨¬t} would be represented in 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 satisfiability solver and are welcome to do so, your task is to write a
program to randomly generate test files containing Horn clauses and to use these test files to empirically
determine whether an easy-hard-easy pattern exists and, if so, the value C explained above.
You are then to write a report explaining your empirical results and whether an easy-hard-easy pattern
exists and, if so, how you determined the value C. The use of statistical analysis, tables and graphs to
support your results is required.
For this question you must submit your report and any source code files used in answering this question.
4. [20 Marks] (Knowledge Representation and Reasoning)
Select a method for knowledge representation and reasoning that we have not covered in lectures and
write 1–2 pages addressing the following:
3
(a) briefly describe how the method represents knowledge and include an example;
(b) briefly describe the inference procedure(s) adopted by the method for reasoning; and,
(c) identify some importance issues in using the method (try and assess both advantages and shortcomings).
In answering this question some sources you might consult include:
• Ronald Brachman and Hector Levesque, Knowledge Representation and Reasoning, Morgan Kaufmann, 2004.
• Stuart Russell and Peter Norvig, Artificial Intelligence: A Modern Approach, Third Edition,
Prentice Hall, 2010.
• The Principles of Knowledge Representation and Reasoning conference series (www.kr.org).
• The Association for the Advancement of Artificial Intelligence conference series (www.ijcai.org).
• The International Joint Conference on Artificial Intelligence series (www.aaai.org).
Assignment Submission
You will need to submit answers to Questions 1, 2, 4 and the report for Question 3 in a PDF file named
assn1.pdf along with any source code files for Questions 3. Your report for Question 3 in assn1.pdf should
describe the additional files you submit for this question and how they can used to replicate/generate your
results.
give cs4418 assn1 assn1.pdf assn1-q3-files
The deadline for this submission is 23:59:59am Sunday 26 August.
Late Submissions
In case of late submissions, 10% will be deducted from the maximum mark for each day late.
No extensions will be given for any of the assignments (except in case of illness or misadventure). Read
the course outline carefully for the rules regarding plagiarism.
4