辅导R assignment 辅导讲解留学生R assignment、R经济统计语言辅导

日期：2018-08-23 09:20

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 satisifi-

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 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