COS3761 Assignment 2 2023 (ANSWERS)

COS3761 Assignment 2 2023 (ANSWERS) ASSIGNMENT 2 Please note that this is a written assignment. You need to prepare and submit a document in Word or PDF format. Predicates D(x) x is a degree M(x, y) x is a major subject of y L(x, y) x loves y H(x, y) x hates y T(x, y) x takes y Constants c Computer Science i Information Systems Table 2 QUESTION 1 Use the predicate, and constant symbols and their intended meanings given in Table 2 to translate the English sentences given below into predicate logic: Question 1.1 There is a degree with Information Systems as a major subject. Question 1.2 Everyone who loves Computer Science takes it as a major subject of a degree. Question 1.3 If someone loves Computer Science, they do not necessarily hate Information Systems. Question 1.4 Some students take Information Systems or Computer Science, but not both. Question 1.5 Some students take subjects they hate. QUESTION 2 Use the predicate, and constant symbols and their intended meanings given in Table 2 and translate the following formulas of predicate logic into English: Question 2.1 ∃x (D(x) ∧ ¬ ∃y M(y, x)) COS3761/103/0/2023 14 Question 2.2 ¬ ∀x (D(x) → M(c, x) ∨ M(i, x)) Question 2.3 ∃x ∀y L(x, y) Question 2.4 ∀x ∀y ∃z (L(x, y) → M(y, z) ∧ D(z)) QUESTION 3 Let • P and Q be two predicate symbols, each with two arguments, • f a function symbol with one argument, • c a constant symbol, and • x and y are variables. For each of the following, state whether it is a term or a well-formed formula (wff) or neither. If it is neither a term nor a wff, state the reason. Question 3.1 ∀x (P(f(c), x) ∧ Q(y, f(x))) Question 3.2 ¬ P(f(c), c) ∨ P(¬ f(c), c) Question 3.3 ∃x ∀x ∃x Q(x, x) Question 3.4 x Question 3.5 f(P(x, y)) Question 3.6 ∃x Q(c, f(f(c))) Question 3.7 P(f(f(x), f(y))) QUESTION 4 Let φ be the formula ∃x (¬ (P(x, y) ∨ ∀x P(x, z)) → ∃z P(x, x)) ∧ P(y, x) Question 4.1 Draw the parse tree of the formula and indicate the free and bound variables. Question 4.2 Suppose f is a function symbol with one argument. For each of the following substitutions, state whether it will create a problem. If there is no problem, write down the substituted formula. If there will be a problem, state how you would solve it and then write down the substituted formula. Question 4.2.1 φ[f(z) / x] Question 4.2.2 φ[f(z) / y] Question 4.2.3 φ[f(x) / y] COS3761/103/0/2023 15 QUESTION 5 Show that the following set of formulas is consistent by constructing a mathematical model where both formulas are true. Take A, the universe of concrete values, as the set of all integers. ∀x ∀y (P(x, y) → Q(y, x)) ∀x ∃y (P(x, y) ∧ Q(x, y)) QUESTION 6 You are given the formula ∀x ∀y ∀z (R(x, y) ∧ S(z, x) → S(z, y)) where R and S are both predicates with two arguments. Question 6.1 Show that the formula is satisfiable by constructing a non-mathematical model where the formula is true. Question 6.2 Show that the formula is not valid by constructing a non-mathematical model where the formula is false. For questions 6.1 and 6.2, use the set of people as the universe of concrete values, and use different human relations as the interpretations of the predicates. Explain why your model shows that the formula has the required property. QUESTION 7 Given the formula ∃x ∀y (R(x, y) → R(y, x)) does the model M below satisfy it? Explain your answer. A = {a, b, c, d} RM = {(a, b), (a, c), (b, a), (b, b), (b, d), (c, b), (d, a)} QUESTION 8 In this question you have to use the fact that a set of formulas semantically entails a single formula if the single formula is true in all models of the set of formulas. Question 8.1 Show that the entailment ∀x ∃y P(x, y) ⊨ ∃y ∀x P(x, y) does not hold by constructing a mathematical model where the formula(s) to the left of ⊨ evaluate(s) to T but the formula to the right of ⊨ evaluates to F. Question 8.2 Show that the entailment COS3761/103/0/2023 16 ∀x (Q(x) → R(x)) ⊨ ∀x (R(x) → Q(x)) does not hold by constructing a non-mathematical model where the formula(s) to the left of ⊨ evaluate(s) to T but the formula to the right of ⊨ evaluates to F. QUESTION 9 Using the rules of natural deduction, prove the validity of the following sequents in predicate logic. In all cases, number your steps, indicate which rule you are using and indicate subproof boxes clearly. Question 9.1 ∀x (P(x) → Q(x)) ⊢ ∃x P(x) → ∃x Q(x) Question 9.2 ∀x (¬ P(x) ∨ ∃y Q(x, y)), ∀x ∀y (Q(x, y) → ¬ P(x)) ⊢ ∀x ¬ P(x) Question 9.3 ∀x (P(x) → (Q(x) ∨ R(x))), ¬ ∃x (P(x) ∧ R(x)) ⊢ ∀x (P(x) → Q(x)) Question 9.4 ⊢ ∀x (P(x) → Q(x)) ∧ ∃x ¬ Q(x) → ∃x ¬ P(x) Question 9.5 ∀x (P(x) ∨ Q(x)), ∃x ¬ Q(x), ∀x (R(x) → ¬ P(x)) ⊢ ∃x ¬ R(x)