CS 245 Final Assessment
Final Assessment
CS 245 Final Assessment
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?