代写R编程设计、代做data编程、代做R留学生编程

日期：2021-01-14 10:35

Mathematical and Logical Foundations of Computer Science

Second Class Test

Question 1 [Linear Algebra]

(a) Consider the following two vectors in R

(i) Show that ~v and ~w are linearly independent of each other. [2 marks]

(i) Show that the triangle has a right angle, and say at which corner it occurs.

[4 marks]

(ii) The triangle defines a plane E in R

3

. Give its parametric representation and

its normal form. [4 marks]

(iii) A line L in R

. Compute its point of

intersection with the plane E from the previous item. [4 marks]

(c) Let B = {~v1, ~v2, . . . , ~vn} be a basis for an algebra of vectors V , and let ~w be an

arbitrary vector in V .

(i) When do we say that scalars a1, a2, . . . , an are the coordinates of ~w with respect

to B? [1 mark]

(ii) Prove that the coordinates of ~w with respect to B are uniquely determined.

[3 marks]

Question 2 [SAT & Predicate Logic]

(a) (i) Let p0, p1, q0, q1, r0, r1 be atoms capturing the states of three cells called p, q,

and r, that can each either hold a 0 or a 1: pi captures the fact that cell p

2

35324 LC Mathematical and Logical Foundations of Computer

Science

holds the value i, and similarly for the other atoms. Consider the following

formula:

(p0 ∨ p1) ∧ (q0 ∨ q1) ∧ (r0 ∨ r1) ∧ (¬p0 ∨ ¬p1) ∧ (¬q0 ∨ ¬q1) ∧ (¬r0 ∨ ¬r1)

∧(p0 ∨ q0 ∨ r0) ∧ (p1 ∨ q1) ∧ (p1 ∨ r1) ∧ (q1 ∨ r1)

Using DPLL, prove whether the above formula is satisfiable or not. Detail your

answer. What property of the three cells p, q, and r, is this formula capturing?

[4 marks]

(ii) Given a CNF (Conjunctive Normal Form) that contains a clause composed of

a single literal, can it be proved using Natural Deduction? Justify your answer.

[2 marks]

(b) Consider the following domain and signature:

❼ Domain: N

❼ Function symbols: zero (arity 0); succ (arity 1); ∗ (arity 2)

❼ Predicate symbols: even (arity 1); odd (arity 1); = (arity 2)

We will use infix notation for the binary symbols ∗ and =. Consider the following

formulas that capture properties of the above predicate symbols:

❼ let S1 be ∀x.(even(x) → ∃y.x = 2 ∗ y )

❼ let S2 be ∀x.((∃y.x = succ(2 ∗ y )) → odd(x))

❼ let S3 be ∀x.∀y.(x = y → succ(x) = succ(y ))

where for simplicity we write 0 for zero, 1 for succ(zero), 2 for succ(succ(zero)),

etc.

(i) Provide a constructive Sequent Calculus proof of:

S1, S2, S3 ` ∀x.(even(x) → odd(succ(x)))

[6 marks]

(ii) Provide a model M such that M ∀x.(even(x) → odd(succ(x))) [2 marks]

(iii) Provide a model M such that ¬ M ∀x.(even(x) → odd(succ(x))) [2 marks]

(c) Let p be a predicate symbol of arity 1 and q be a predicate symbol of arity 2. Let F

be the Predicate Logic formula (∀x.(p(x) ∧ ∃y.q(x, y ))) → ∀x.∃y.(p(x) ∧ q(x, y )).

Provide a constructive Natural Deduction proof of F . You are not allowed to make

use of further assumptions so all your hypotheses should be canceled in the final

proof tree. [4 marks]

3