2.  Your friend has three different tetrahedra (i.e., four-sided dice). You have the following information:

. Each tetrahedron has each of its four surfaces labelled with 0 or 1.

. Each tetrahedron has at least one of its sides labelled with 0, and one labelled with 1.

A random experiment can be conducted with such a tetrahedron by throwing it and reading the label on the surface on which it comes to rest.

a)  For the tetrahedron that has the greatest number of surfaces labelled with 0 give a probability space that describes the corresponding random process.          (2 marks)

b)  You create a binary number by rolling the same tetrahedron three times and writing down the number from left to right.   For each possible tetrahedron what is the probability that the number obtained in this way is at least 2 when translated to base 10?                                (3 marks)

c)  For the situation from part b) create random variables by turning the binary numbers into the corresponding numbers in base 10.  Calculate the expected value for the random variable X you obtain for the tetrahedron from part a).                 (2 marks)

d)  Given the situation from part c) calculate the conditional probability distribution given that the first throw shows 0.          (3 marks)

e)  Your friend picks one of the three tetrahedra, and you are trying to work out which one it is. You do so by Bayesian updating.

Your friend throws the tetrahedron for you and shows you the number labelling the bottom face, keeping the rest of the tetrahedron hidden from you.

They do this three times, obtaining the numbers 0, 0 and 1 in that order.

Carry out the corresponding calculation. Which tetrahedron do you think it is? (10 marks)

Section B

3.  a)  Consider the following propositional formula.

(P ! Q) ! ((Q! R) ! (:S ! :P))

i)  Use our DNF algorithm to transform the formula into disjunctive normal form. (3 marks)

ii)  Give a conjunctive normal form for the formula.                 (1 mark)

iii)  Simplify your answer in ii) as much as possible using our fundamental semantic equivalences.       (2 marks)

iv)  Is the formula a tautology? Explain your answer.                                (2 marks)

v)  Is the formula satisfiable? Explain your answer.                                  (2 marks)

Justify all your steps in your derivations.

b)  Consider this judgement in propositional logic.

P ^ Q- (P ! Q) ^ (Q! P)

Your friend has given the following incorrect natural deduction proof of this judgement.

Say what is (are) the mistake(s) and fix the proof so that it is a correct proof using our natural deduction system in which every step is correctly justified.

The inference rules of our natural deduction system are given on the last pages of this exam paper.        (4 marks)

c)  Consider the first-order language with the three binary predicate symbols C; <; =, four unary predicate symbols D;ID; E ; O, the constants a; 0; 1; 2; : : : ; 9, and a supply of variables x;y; z; : : :.

Suppose the domain of interpretation is the set of all natural numbers.   Further

assume the given predicate and constant symbols have the following interpretations:

State for each of the following formulas what is their truth value in the interpration defined above. Briefly explain you answers.      (4 marks)

i)  (1 < 0) ! 9x(x < 0)

ii)  Ax (D(x) ! 9y(D(y) ^ (x < y),,

iii)  Ax (ID(x) !(9y(D(y) ^ C(x;y) ^ E(y)) ^ 9z (D(z) ^ C(x; z) ^ O(z)),,

Using the language and interpretation given above, express the following sentence as a first-order formula.       (2 marks)

iv)  Every odd digit other than 7 occurs in Ann’s student identification number.