计算机逻辑代写-CS 245
时间:2021-08-10
CS 245: Spring 2021 Final Assessment CS 245: Spring 2021
Copyright ?2021
Due Tuesday, August 10, by 4:00pm EDT, to Crowdmark.
TIME LIMIT: 2 hours (120 minutes), plus a grace period, starting when you access the assessment.
Exception: no submission will be accepted following the deadline above.
To minimize the effect of possible internet delays, we provide the following information and advice.
? You should submit each answer page (or pages) to Crowdmark as soon as you complete it.
You may re-submit for a question any number of times, up to the time limit. Only the last
submission will be marked.
? The grace period permits time for submission, including possible temporary internet inter-
ruptions or delays. NO ACCOMMODATION will be made for such delays, unless substantial
work has already been submitted before the start of the grace period.
? Your deadline as shown by Crowdmark already includes the grace period. Its time is the
absolutely final deadline.
? If you lose access to the internet, or to Crowdmark specifically, send email to course staff at
ddvorski@uwaterloo.ca with an explanation, as soon as possible. Include the work done,
with each page as a separate attachment.
The allotment of credit in such an event will be determined on a case-by-case basis.
Submitting this Assessment confirms that you have read and agree to the following.
1. The work I submit here is entirely my own.
2. I have not discussed and will not discuss the contents of this assessment with anyone be-
yond the course staff (i.e. instructors and instructional assistants) until after the end of the
submission deadline shown above (4:00pm EDT, August 10).
3. I have not used any unauthorized aids. The only authorized aids are:
(a) the course textbook by Lu,
(b) the sites for CS 245 (Spring 2021) on Learn and Piazza. and
(c) the student’s own marked assignments for CS 245, as held on Crowdmark.
4. I am aware that misconduct related to assessments can result in significant penalties, including
failing the course and suspension (this is covered in Policy 71:
http://uwaterloo.ca/secretariat/policies-procedures-guidelines/policy-71).
Signed:
Question 1 (12 marks)
Consider the following assumptions.
If the dragon is mythical, then it is immortal, but if it is not mythical, then it is a mortal
mammal. If the dragon does not have scales, then it is mortal and not a mammal. The
dragon is magical if it has scales.
(a) Use the following proposition symbols, represent each sentence of the above as a propositional[3]
formula.
= The dragon is magical.
= The dragon is a mammal.
= The dragon is mortal.
= The dragon is mythical.
= The dragon has scales.
Convert each of the formulas into conjunctive normal form.
(b) For each of the following questions, determine whether or not its answer is implied by the
assumptions above. If so, give a resolution proof of the implication. If not, give sufficient
counter-example(s).
i. Is the dragon mythical?[3]
ii. Is the dragon magical?[3]
iii. Does the dragon have scales?[3]
Question 2 (8 marks)
(a) Give the parse tree for the formula ?(?() → ()).[2]
(b) Give a formal proof (using Natural Deduction) of ? ? ?(?() → ()).[6]
In your proof, you may use the 17 basic rules and also any of the following.
? (∈), (???), (?+), and/or (Tr).
? Excluded Middle.
? , ? ? , for any and . (Sometimes called “ex falso”.)
Question 3 (8 marks)
In this question, you will use resolution to determine whether or not the formula
??(() = ) ∧ ???((()) = )
is satisfiable.
When this requires you to make an arbitrary choice, specify what choice you have made.
(a) Convert the formula to an equivalent formula in prenex normal form. (Keep all of the quan-[2]
tifiers present at this step.)
(b) Modify the formula from the previous step to produce a set of clauses (without quantifiers)[2]
suitable to apply resolution.
(c) Show the steps of the resolution, until either the process stops or you have made four new[3]
clauses.
(d) From the outcome of the previous step, what can you conclude about the satisfiability of the[1]
original formula?
Question 4 (6 marks)
(a) Prove that[2]
{?(() → ()), ?()} ? ?().
(b) Use part 4a to prove that[2]
{?(() → ()), ?()} ? ?().
(c) Because of the result of part 4b, there must be at least one error in this “proof”:[2]
(1) ?(() → ()), () ? () (by (∈))
(2) ?(() → ()), () ? ?(() → ()) (by (∈))
(3) ?(() → ()), () ? () → () (by (??), (2))
(4) ?(() → ()), () ? () (by (→ ?), (1), (3))
(5) ?(() → ()), () ? ?() (by (?+), (4))
(6) ?(() → ()), ?() ? ?() (by (??), (5))
State which line number is the first one having en error. Briefly explain what the error is.
Question 5 (6 marks)
An enhanced Turing machine (ETM) has all the features of an ordinary Turing machine,
except that its transitions may leave the tape head unmoved (i.e., move neither left nor right).
Prove that an enhanced Turing machine is no more powerful than an ordinary Turing machine.
Explain, in detail, how to implement an ETM transition of the form
(1, 1) = (2, 2, ),
(where indicates that the tape head should stay in its current position), in an ordinary Turing
machine.
Question 6 (12 marks)
(a) Fill in the blanks with appropriate annotations to prove partial correctness, with the given[7]
pre- and post-conditions.
Note that you will first need to determine an invariant.
? = 0 ∧ 0 ≥ 0? precondition
? ?
s := 0 ;
? ?
x := 1 ;
? ?
while ( n > 0 ) {
? ?
? ?
n := n - 1 ;
? ?
s := s + x ;
? ?
x := x + 2 ;
? ?
}
? ?
? = 20 ?
Question 6, continued
(b) Justify (informally but carefully) any “implied” conditions required by the annotations, to[3]
complete the proof of partial correctness.
(c) Is the program totally correct? Justify your answer.[2]
Question 7 (6 marks)
Recall that the array-assignment rule: ?[{1 ← 2}/] ? A[e1]:= e2 ; ? ?.
Consider the following code and its annotation. and ′ are formulas that you will specify below.
?1? ? ? pre-condition
?2? ?′ ? implied
?3? A[ m ] := n ;
?4? ?[[]] = ? array assignment
(The line numbers in angle brackets are only for reference. The variables , and take arbitrary
integer values. The array can have any integer as index [i.e., it is infinite – which does not matter
here].)
(a) Write down the exact formula ′, so that the array-assignment rule is used correctly. (Do not[2]
simplify it for this part.)
(b) Determine a non-trivial pre-condition and prove (informally) the resulting implication.[4]
(To get full marks, your should be equivalent to ′ and also as simple as possible. You do
not need to prove either of these conditions, however.)
Question 8 (6 marks)
Prove that the following problem is undecidable:
Given two Turing machines 1 and 2,
Is the set of strings accepted by 1 a subset of the set of strings accepted by 2?











































































































































essay、essay代写