9.3 Coursework Sheet 2

Hand in your solutions in the appropriate way by Monday, 23 October 2023, 19:00.

Exercise 1

Let \(P\) and \(Q\) be logical statements.

Define the logical operator \(P\barwedge Q\) by \[ P\barwedge Q = \lnot(P\land Q) \] (this is called the nand operator and is important in Computer Science). Show that

  1. \(\lnot P = P\barwedge P\),
  2. \(P\lor Q = (P\barwedge P)\barwedge(Q\barwedge Q)\),
  3. \(P\land Q = (P\barwedge Q)\barwedge(P\barwedge Q)\).

Exercise 2

Negate the following statements

  1. \((\forall x\in\mathbb R) -1\le\sin(x)\le 1\).
  2. \((\exists x\in\mathbb R) x^2-3x+1=0\).
  3. \((\forall\epsilon>0)(\exists\delta>0)|x-\pi/2|<\delta\implies|\sin(x-\pi/2)|<\epsilon\).

Exercise 3

Consider the following theorem.
Suppose \(x\) and \(y\) are real numbers and \(x+y=12\). Then \(x\ne4\) and \(y\ne7\).

Is the following proof correct? Give reasons for your answer.

Suppose the conclusion is false. Then \(x=4\) and \(y=7\) and so \(x+y=11\), a contradiction. Hence the conclusion is true and \(x\ne4\) and \(y\ne 7\).

Exercise 4

Write the following statement symbolically then prove it.
For every real number \(x\), if \(x>-1\) then there exists a real number \(y\) such that \(y(y+2)=x\).

Exercise 5

List all the divisors of each of the integers \(330\) and \(462\) and hence find \(\gcd(330, 462)\). What is the greatest common divisor of the set \(\{9486, 462, 330\}\)? [You do not need to use the Euclidean algorithm to compute this.]

Exercise 6

Use the Euclidean algorithm to demonstrate that \(\gcd(4052, 1031)=1\), and find integers \(p,q\) such that \(1=4052.p + 1031.q\). You should clearly show your working.