(b) Add the atomic tableau of into atomic tableaux. (2 marks) (c) Discuss the validity of(A⊕B)→((A∧=B)V(=A∧B)) by using tableau 3. Given a formula (a, y)=(p(a, y)+(va)(ab()v.r)(a, y))), answer the follow ing questions. (8 marks) (a)Show which occurrence of every variable is free. If it is bound, show which quantifier bounds it 3 marks (b)Given a function f(a, r), is y/f(a, )in (a, y) substitutable? Show your reason 2 marks (c) Discuss its truth of (a, y) (3 marks) 4. Prove or disprove the following statements using tableau proof system. If it is false, a counterexample is needed:( 9 marks) (a)(AVB, BVC, CVD)HA+D (3 marks) (b)Var(o(a)vv(a))+vaco()vara(a)) nar (c) Vary(p V3x)V=yw(p Vv(z/w)), where p and w are any formulas with free variables T, y and z. w is a variable not appearing in p and al.3 marks) 5. Give two sentence a=(Var P(a))->Q and B= Va(P(r)Q).(9 marks) (a)Prove that B h a in semantics approach (4 marks) (b) Prove it by using tableau proof (2 marks) (c) If a is free in Q, discuss the truth of the following assertion (wxP(x)→Q(x)hwr(P(x)→Q(x) (3 marks 6. Construct a set of sentences S and prove that it has only infinite models marks 7. Let S=oi(al,., Ini s n for some n be a set of open formulas on top of a language L. If S is unsatisfiable, there are only finitely many ground instance of elements of S whose conjunction is unsatisfiable 5 marks) 8. A graph G=(V, E is 2-colorable if and only if G has no odd cycle. Given a binary predicate E(, y), which means that there is a edge between vertex and vertex y (9 marks) (a) Construct a sentence n to represent there is no cycle with n-length.(Hints Construct it recursively . (3 marks) (b) Use a set of sentences E to describe that G is 2-colorable 2 marks) (c)Prove that a graph is 2-colorable cannot be described by a sentence v(Hints Consider -a/ and sentence set 2, then apply Compactness Theorem. ) (4(b) Add the atomic tableau of ⊕ into atomic tableaux. (2 marks) (c) Discuss the validity of (A ⊕ B) → ((A ∧ ¬B) ∨ (¬A ∧ B)) by using tableau proof. (3 marks) 3. Given a formula Φ(x, y) = (ϕ(x, y) → (∀x)(ψ(x)∨(∃x)ϕ(x, y))), answer the follow￾ing questions.(8 marks) (a) Show which occurrence of every variable is free. If it is bound, show which quantifier bounds it. (3 marks) (b) Given a function f(z, x), is y/f(z, x) in Φ(x, y) substitutable? Show your reason. (2 marks) (c) Discuss its truth of Φ(x, y). (3 marks) 4. Prove or disprove the following statements using tableau proof system. If it is false, a counterexample is needed: (9 marks) (a) {A ∨ ¬B, B ∨ ¬C, C ∨ ¬D} ` A → D. (3 marks) (b) ∀x(φ(x) ∨ ψ(x)) ↔ (∀xφ(x) ∨ ∀xψ(x)). (3 marks) (c) ∀x∃y(ϕ∨ ∃zψ) → ∀x∃y∃w(ϕ∨ψ(z/w)), where ϕ and ψ are any formulas with free variables x, y and z. w is a variable not appearing in ϕ and ψ. (3 marks) 5. Give two sentence α = (∀xP(x)) → Q and β = ∀x(P(x) → Q). (9 marks) (a) Prove that β |= α in semantics approach. (4 marks) (b) Prove it by using tableau proof. (2 marks) (c) If x is free in Q, discuss the truth of the following assertion ((∀xP(x)) → Q(x)) ` ∀x((P(x) → Q(x)). (3 marks) 6. Construct a set of sentences S and prove that it has only infinite models. (4 marks) 7. Let S = {φi(x1, . . . , xni )|i ≤ n for some n} be a set of open formulas on top of a language L. If S is unsatisfiable, there are only finitely many ground instance of elements of S whose conjunction is unsatisfiable. (5 marks) 8. A graph G = hV, Ei is 2-colorable if and only if G has no odd cycle. Given a binary predicate E(x, y), which means that there is a edge between vertex x and vertex y. (9 marks) (a) Construct a sentence φn to represent there is no cycle with n-length. (Hints: Construct it recursively.) (3 marks) (b) Use a set of sentences Σ to describe that G is 2-colorable. (2 marks) (c) Prove that a graph is 2-colorable cannot be described by a sentence ψ. (Hints: Consider ¬ψ and sentence set Σ, then apply Compactness Theorem.) (4 marks) 2