(Solved): Need An Online Exam Taken Between The Hours Of 1400 And 1700 May 5Th.

Show all work. Question 1. 1a (8 marks). Construct a CNF (not DNF) with the following truth-table. X Y Z 0 0 0 0 0 0 1 1 0 1 0 1 0 1 1 0 X Y Z 1 0 0 1 1 0 1 0 1 1 0 1 1 1 1 0 1b (12 marks). Construct a resolution proof that the following CNF is inconsistent UWX, UW X , U WX , U W X, UY, U Y , V WY, V WY , V W Y, V W Y , V X, V X Question 2 Consider a first order theoryK which has a multiplication operator ×, usually omitted so xy means x× y, and has various proper axioms to ensure an equality theory (with = representing equality). It also has an axiom (associativity) ∀x1∀x2∀x3(x1(x2x3)) = ((x1x2)x3) Let A′, A,B′, B be the formulae below A′(x1) : ∀x2(x1x2 = x2), A(x1) : ∃x1A ′(x1), B ′(x1) : ∀x2(x2x1 = x2), B(x1) : ∃x1B ′(x1) and let K+A, K+A+B be the theories formed by adding A (respectively A,B) as an axiom (axioms). 2a (8 marks). Show that the interpretation I with domain {a, b}, =I the identity relation on {a, b}, and ×I a b a a b b a b is a model of K + A. (Show this informally without bringing in the idea of ‘snapshots.’) 2b (4 marks). Determine whether or not it is a model of K + A+ B. 2c (8 marks). Give a careful proof within K as a first-order theory (with equality: you may use equality reasoning informally) that A′(x1) ∧ A ′(x3) ∧ B ′(x4) =⇒ x1 = x3. (Hint: the proof should be guided by the fact that x1x4 = x1 = x4.) Question 3. 3a (6 marks). Prove that, in any first-order theory K, under a certain condition A(t) =⇒ ∃xiA(xi) is a theorem, stating the required condition. 3b (4 marks). Give an example showing that (3a) is not true (in every interpretation) if that condition is not met. 3c (5 marks). (Note: a countable set D is one which can be listed as a countable sequence d1, d2, . . ., so for every nonempty subset X of D there is a smallest i such that di ∈ X.) Suppose that K is a first-order theory, P (x1, x2) an atomic formula, and M is a model of K, with countable domain D, such that M |= ∃x2P (x1, x2) Show that for every a ∈ D there exists a b ∈ D such that PM(a, b) is true. 3d (5 marks) (Continuing 3c). Show that one can define a function F : D → D such that for every a ∈ D, M |= P (a, F (a)). (F can be used, for example, in connection with Skolem functions.) Question 4 Referring to the proof in the notes that it is consistent to assume that infinite integers exist, the idea was to extend PA with a new constant symbol a plus infinitely many formulae which together imply that a is infinite. 4a (6 marks) Construct an interpretation of this extension, with domain N∪{∞}, extending the definitions of s(),+,×, so that every axiom of PA except possibly Axiom 4 (induction), is true in this interpretation. Also, you may ignore the equality axioms. 4a (14 marks) Show that the 7 axioms mentioned in (4a) are true in the interpretation. You may skip the induction axiom.

Need An Online Exam Taken Between The Hours Of 1400 And 1700 May 5Th.

Related Study Services

Post your Answer - free or at a fee

Answer Review

Need An Online Exam Taken Between The Hours Of 1400 And 1700 May 5Th.

Related Study Services

Post your Answer - free or at a fee

Login to your tutor account to post an answer