3. a) i) Using truth tables determine whether the following holds, or not. (2 marks) (P ) P ii) State what other method can be used to answer this question, and very briefly say how (but you do not need to give a full alternative argument). (2 marks) b) Consider this propositional formula. B ((C A) (A B)) i) Use our CNF algorithm to transform this formula into conjunctive normal form. (4 marks) ii) Simplify your answer as much as possible. (2 marks) c) Give a natural deduction proof for the following. (4 marks) ((P Q) P) R ` R Use the inference rules of our natural deduction system, which are given on the last pages of this exam paper. d) Consider the first-order language with one ternary predicate symbol A, five binary predicate symbols SI,TP,CV,F,R, three unary predicate symbols H,P,D, one constant John and a supply of variables x, y,z,.... Assume the non-logical symbols are interpreted as follows. A(x, y,z) means that x is admitted by y to z SI(x, y) means that x is staying in y TP(x) means that x has tested positive CV(x, y) means that x can be visited by y F(x, y) means that x is a friend of y R(x, y) means that x is a relative of y H(x) means that x is a hospital P(x) means that x is a patient D(x) means that x is a doctor John is interpreted as the person John Express each of the following sentences as formulas. (6 marks) i) Every patient staying in hospital must have been admitted by a doctor. ii) John has been tested positive but has not been admitted to any hospital. iii) Every patient can be visited by their friends and relatives.

3. a) ) Using truth tables determine whether the following holds, or not. (2 marks) (P+1)=P ii) State what other method can be used to answer this question, and very briefly say how (but you do not need to give a full alternative argument). (2 marks) b) Consider this propositional formula. B+(+A) + (AMB)) i) Use our CNF algorithm to transform this formula into conjunctive normal form. (4 marks) ii) Simplify your answer as much as possible. (2 marks) c) Give a natural deduction proof for the following. (4 marks) ((PAD) +P) +RER Use the inference rules of our natural deduction system, which are given on the last pages of this exam paper. d) Consider the first-order language with one ternary predicate symbol A, five binary predicate symbols SI,TP, CV,F,R, three unary predicate symbols H,P, D, one constant John and a supply of variables x,y,z,.... Assume the non-logical symbols are interpreted as follows. A(x,y,z) means that x is admitted by y to z SI(x,y) means that x is staying in y TP(x) means that x has tested positive CV(x,y) means that x can be visited by y F(x,y) means that x is a friend of y R(x,y) means that x is a relative of y Hx) means that x is a hospital P(x) means that x is a patient D(x) means that x is a doctor John is interpreted as the person John Express each of the following sentences as formulas. (6 marks) i) Every patient staying in hospital must have been admitted by a doctor. ii) John has been tested positive but has not been admitted to any hospital. iii) Every patient can be visited by their friends and relatives