T A T-C F C TB→C FB TC TA→B⑧ FAT B 5: Tableau of 4.( a) Solution.(a) If Va P(r) Q is true, then Var P() is false or Q is true. (1 mark) If Va P(r)is false, there is at least a ground term t make P(t) false. We have -P(t)or Q(1 mark)So there is a ground term t make P(t),Q(1 mark) Finally we have r(P(x)→Q)(1mark (b) We first give the tableau proof as Figure8. The tableau is contradictory. It means BHa. By soundness theorem, we have BEa (c There is a formula. It is to prove 3 r(P()Q())H Vr(va P(a)>Q(a).(I mark Its tableau proof is given in Figure 9.(1 mark) The right branch is noncontradictory. We can construct a model A with A=co, C1, P=co, C1, Q=c1 such that A make the assertion wrong. (1 mark 6. Construct a set of sentences S subject to the following properties (5 marks (a) Every finite subset of S has only finite model (b)It has only infinite model (3 marks You should prove why the property holds.(Hints: there is no size limit on S) Solution. Define a sentence as n=3c1..in A1<iti<n -(ai=aj). Then we can form a set of sentences S=oili>1.(1 m (a)Consider any finite subset Si=oil, .. oin], where i1 <.. ik. To satisfy S,we need only ik distinct elements, which means the model is finite.(1 mark) (b) Because every finite subset of s is satisfiable, S is also satisfiable according to Com pactness theorem (1 mark) Suppose the model is still finite, say N. Consider i with i>N, which can't be satisfied. So the model can only be infinite.(2 marks)F ¬A T A T ¬C F C T B → C F B T C T A → B ⊗ F A T B ⊗ ⊗ Figure 5: Tableau of 4.(a) Solution. (a) If ∀xP(x) → Q is true, then ∀xP(x) is false or Q is true.(1 mark) If ∀xP(x) is false, there is at least a ground term t make P(t) false. We have ¬P(t) or Q.(1 mark) So there is a ground term t make P(t) → Q.(1 mark) Finally we have ∃x(P(x) → Q).(1 mark) (b) We first give the tableau proof as Figure 8. The tableau is contradictory. It means β ⊢ α. By soundness theorem, we have β |= α. (c) There is a formula. It is to prove ∃x(P(x) → Q(x)) ⊢ ∀x(∀xP(x) → Q(x)). (1 mark) Its tableau proof is given in Figure 9. (1 mark) The right branch is noncontradictory. We can construct a model A with A = {c0, c1}, P = {c0, c1}, Q = {c1} such that A make the assertion wrong. (1 mark) 6. Construct a set of sentences S subject to the following properties: (5 marks) (a) Every finite subset of S has only finite model. (2 marks) (b) It has only infinite model. (3 marks) You should prove why the property holds. (Hints: there is no size limit on S.) Solution. Define a sentence as ϕn = ∃x1 . . . ∃xn ∧ 1≤i̸=j≤n ¬(xi = xj ). Then we can form a set of sentences S = {ϕi |i ≥ 1}. (1 mark) (a) Consider any finite subset Si = {ϕi1 , . . . , ϕik }, where i1 < · · · < ik. To satisfy S ′ , we need only ik distinct elements, which means the model is finite. (1 mark) (b) Because every finite subset of S is satisfiable, S is also satisfiable according to Com￾pactness theorem.(1 mark) Suppose the model is still finite, say N. Consider ϕi with i > N, which can’t be satisfied. So the model can only be infinite. (2 marks) 5