For $A=\{1,2,3,4,5\}$ and $B=\{2,4,6,8,10\}$, find $A\cap B$, $A\cup B$, $A\setminus B$ and $B\setminus A$.

Find the truth table for the compound statement ‘‘$(p\ \&\ q)\Rightarrow(\neg p)$’’, where $p$ and $q$ are statement variables.

For $A=\{1,2,3,\dots,10\}$, list the members of each of the following three sets:

1. (i)

   $B=\{n\in\mathbb{Z}:3n+1\in A\}$;

2. (ii)

   $C=\{3n+1:n\in A\}$;

3. (iii)

   $D=\{n\in A:3n+1\in\mathbb{Z}\}$.

1. (i)

   Express the statement

   ‘‘there exists an integer $m$ such that, for every integer $n$,

   the sum $m+n$ is a natural number’’

   symbolically. (In this context, ‘‘symbolically’’ means using negation, the five connectives and the two quantifiers introduced in Sections 2.3–2.4.)

2. (ii)

   Negate the symbolic statement found in (i). (You should always convert the negation into a positive statement as we did in Examples 2.4.10–2.4.11 in the notes.)

3. (iii)

   Determine whether the statement in (i) is true or false, and justify your answer briefly.

1. (i)

   Read the first three sections C.1–C.3 of Appendix C, about the Self-Explanation strategy for understanding proofs.

2. (ii)

   Apply the strategy to the two practice proofs in Sections C.4–C.5.

   [You might prefer to try the explanation strategy with a friend, either in the workshop or at another time. That can also be very helpful but try to be (constructively) critical of yourself or your friend: keep going until you are sure you understand every step, line by line. Feel free to try the strategy with other proofs from the course, or other courses, too.]

Show that the two compound statements ‘‘$p\ \&\ (q\ \text{or}\ r)$’’ and ‘‘$(p\ \&\ q)$ or $(p\ \&\ r)$’’ are logically equivalent.

Remark. This result can be rephrased as saying that the connective ‘‘$\&$’’ is distributive over ‘‘or’’ because it resembles the usual distributive law from arithmetic: $a\cdot(b+c)=(a\cdot b)+(a\cdot c)$ for numbers $a$, $b$ and $c$.

1. (a)

   Express each of the following statements symbolically.

   1. (i)

      ‘‘There is an integer $n$ such that $n^{3}=18$.’’

   2. (ii)

      ‘‘For each rational number $r$, there are integers $m$ and $n$ such that $n$ is non-zero and $r=m/n$.’’

   3. (iii)

      ‘‘The equation $3x^{2}-2x+9=0$ has a real solution.’’

2. (b)

   Negate each of the three statements in (a).

3. (c)

   For each of the three statements in (a), decide whether it is true or false and justify your answer briefly.

Use truth tables to show that, for any statement variables $p$ and $q$, the compound statements ‘‘$p\Rightarrow q$’’ and ‘‘$(\neg p)$ or $q$’’ are logically equivalent.

Find the parity table for the expression $(\sim\!x)\times y$, where $x,y\in\mathbb{Z}$.

For

find $C\cap D$, $C\cup D$, $C\setminus D$ and $D\setminus C$.

Find the truth table for the compound statement ‘‘$\bigl(p\ \&\ (\neg q)\bigr)\Rightarrow r$’’, where $p$, $q$ and $r$ are statement variables.

Use truth tables to show that the logical connective ‘‘or’’ is distributive over ‘‘$\&$’’; that is, show that the two compound statements ‘‘$p\ {\hbox{or}}\ (q\ \&\ r)$’’ and ‘‘$(p\ {\hbox{or}}\ q)\ \&\ (p\ {\hbox{or}}\ r)$’’ are logically equivalent, where $p$, $q$ and $r$ are statement variables.

1. (i)

   Use truth tables to show that the two compound statements

   $$\text{``}\neg(p\ \&\ q)\text{''\qquad and\qquad``}(\neg p)\ \text{or}\ (\neg q)\text{''}$$

   are logically equivalent, where $p$ and $q$ are statement variables.

2. (ii)

   As in Remark 2.3.3, construct an example that shows that this result agrees with our everyday usage of ‘‘negation’’, ‘‘and’’ and ‘‘or’’.

Express each of the following statements and its negation symbolically.

1. (i)

   ‘‘For all integers $a$ and $b$, the equation $ax=b$ has a rational solution.’’

2. (ii)

   ‘‘For each integer $n$ greater than $9$, the square root of $n$ is greater than $3$.’’

3. (iii)

   ‘‘$-27=n^{3}$ for some integer $n$.’’

4. (iv)

   ‘‘For each natural number $n$, there is a real number $x$ such that $n=x^{4}$.’’

Negate the following three statements:

1. (i)

   ‘‘some triangles are isosceles’’;

2. (ii)

   ‘‘all triangles are similar’’;

3. (iii)

   ‘‘$\bigl(\exists\,p\in\mathbb{P}\setminus\{2\}\bigr)(\forall n\in\mathbb{N})\bigl((p\neq 4n+1)\ \&\ (p\neq 4n-1)\bigr)$’’
   (where $\mathbb{P}$ is the set of prime numbers).

(4 points) Use truth tables to decide whether the two statements

are logically equivalent for all statement variables $p$, $q$ and $r$.

1. (a)

   (3 points) Express the statement

   ‘‘for each non-zero integer $m$ between $-3$ and $3$ (both inclusive),

   there is a positive rational number $q$ such that $\frac{1}{m}=q-\frac{3}{2}$’’

   symbolically.

2. (b)

   (1 point) Negate the statement in (a). (Recall from Exercise 1.4(ii) that this includes converting the negation into positive form.)

3. (c)

   (2 points) Decide whether the statement in (a) is true or false, and justify your answer.

(Truth table) Find the truth table for the compound statement

where $p$, $q$ and $r$ are statement variables, and hence decide which one of the five columns (A)–(E) below gives the correct truth table for $s$.

(Parity table) Find the parity table for the expression $x\times\bigl((\sim y)+z\bigr)$, where $x,y,z\in\mathbb{Z}$, and hence decide which one of the five columns (A)–(E) below gives the correct parity table for this expression.

(Finding the sets $M$ and $N$) For $L=\{-1,0,1,2\}$, find

and hence decide which one of the following five statements is true:

1. (A)

   $M=\{-4,-1,2,5\}$ and $N=\{-1,0\}$;

2. (B)

   $M=\{-4,-1,2,5\}$ and $N=\{-1,1,3,5\}$;

3. (C)

   $M=\{0,1\}$ and $N=\{-1,0\}$;

4. (D)

   $M=\{0,1\}$ and $N=\{-1,1,3,5\}$;

5. (E)

   none of the above.

(Translating text into symbols) Decide which one of the five symbolic statements (A)–(E) below corresponds to the sentence ‘‘for each pair of real numbers $x$ and $y$, there is a natural number which is greater than the sum of the squares of $x$ and $y$’’.

1. (A)

   $(\exists\,n\in\mathbb{N})(\forall x\in\mathbb{R})(\forall y\in\mathbb{R})(n>x^{2}+y^{2})$

2. (B)

   $(\exists\,n\in\mathbb{N})(\forall x\in\mathbb{R})(\exists\,y\in\mathbb{R})(n>x^{2}+y^{2})$

3. (C)

   $(\forall n\in\mathbb{N})(\exists\,x\in\mathbb{R})(\exists\,y\in\mathbb{R})(n>x^{2}+y^{2})$

4. (D)

   $(\forall x\in\mathbb{R})(\forall y\in\mathbb{R})(\exists\,n\in\mathbb{N})(n>x^{2}+y^{2})$

5. (E)

   $(\forall x\in\mathbb{R})(\forall y\in\mathbb{R})(\forall n\in\mathbb{N})(n>x^{2}+y^{2})$

(Symbolic negation) Decide which one of the five symbolic statements (A)–(E) below is the correct negation of the statement

1. (A)

   $(\exists\,x\in\mathbb{R})(\forall y\in\mathbb{Q})(\exists\,z\in\mathbb{R})\bigl((z>x)\ \&\ (z\leqslant y)\bigr)$

2. (B)

   $(\exists\,x\in\mathbb{R})(\forall y\in\mathbb{Q})(\exists\,z\in\mathbb{R})\bigl((z>x)\Rightarrow(z\leqslant y)\bigr)$

3. (C)

   $(\exists\,x\in\mathbb{R})(\forall y\in\mathbb{Q})(\exists\,z\in\mathbb{R})\bigl((z\leqslant x)\ \&\ (z>y)\bigr)$

4. (D)

   $(\exists\,x\in\mathbb{R})(\forall y\in\mathbb{Q})(\exists\,z\in\mathbb{R})\bigl((z>x)\ \text{or}\ (z\leqslant y)\bigr)$

5. (E)

   $(\exists\,x\in\mathbb{R})(\forall y\in\mathbb{Q})(\exists\,z\in\mathbb{R})\bigl((z\leqslant x)\ \text{or}\ (z>y)\bigr)$

(2 points) Show that the connective ‘‘$\Rightarrow$’’ can be expressed in terms of the connective ‘‘&’’ and the negation.

(2 points) Express the statement

‘‘the polynomial $2x^{3}+x^{2}-4x+4$ has at least two distinct real roots’’

symbolically, and decide (with full justification) whether it is true or false.