9.2 Coursework Sheet 1

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

Exercise 1

Let \(P, Q\) and \(R\) be logical statements. Show that

  1. \((P\land\lnot Q)\implies R\) is logically equivalent to \(P\implies (Q\lor R)\).
  2. \((P\land Q)\implies R\) is logically equivalent to \(P\implies (Q\implies R)\).
  3. \(P\land(Q\lor R)\) is logically equivalent to \((P\land Q)\lor (P\land R)\).
  4. \(P\lor(Q\land R)\) is logically equivalent to \((P\lor Q)\land (P\lor R)\).
  5. \((P\implies Q)\land (P\implies R)\) is logically equivalent to \(P\implies(Q\land R)\).
  6. \((Q\implies P)\land (R\implies P)\) is logically equivalent to \((Q\lor R)\implies P\).
  7. \((\lnot P)\Leftrightarrow Q\) is logically equivalent to \(P\Leftrightarrow(\lnot Q)\).

Exercise 2

Using truth tables, demonstrate the following `rules of logic’

  1. Double negation rule. \(P\) is logically equivalent to \(\lnot\lnot P\).
  2. De Morgan’s rule. \(\lnot(P\lor Q)\) is logically equivalent to \((\lnot P)\land(\lnot Q)\). \(\lnot(P\land Q)\) is logically equivalent to \((\lnot P)\lor(\lnot Q)\).
  3. Implication rule. \(P\implies Q\) is logically equivalent to \((\lnot P)\lor Q\).
  4. Contrapositive rule. \(P\implies Q\) is logically equivalent to \((\lnot Q)\implies (\lnot P)\).

Exercise 3

Let \(P, Q\) and \(R\) be logical statements. State the negation, converse and contrapositive of the following statements.

  1. \((P\lor Q)\implies \lnot R\).
  2. \(P\implies (Q\implies R)\).
  3. \((P\implies Q)\implies Q\).
  4. \(P\implies (Q\land\lnot Q)\).

Exercise 4

Let \(P, Q\) and \(R\) be logical statements. Show that the following statements are tautologies.

  1. \((\lnot P)\implies(P\implies Q)\).
  2. \(((\lnot Q)\land (P\implies Q))\implies\lnot P\).
  3. \(((\lnot P)\land(P\lor Q))\implies Q\).

Exercise 5

Find the negation of the following statements

  1. \((\forall x\in\mathbb R) \text{ if }x\ne0\text{ and }1+1/x\le 1\text{ then }x<0\).
  2. \((\exists x\in\mathbb R)\text{ if }x(x-1)\ge0\text{ then }x\ge1\text{ or }x\le 0\).

Exercise 6

What is wrong with the following ``proof’’.

Let \(a=b\). Then \(a^2 = ab\) and so \(a^2-b^2=ab-b^2\). Consequently, \((a-b)(a+b)=b(a-b)\) and so \(a+b=b\). Since \(a=b\) it follows that \(2b=b\) and so \(2=1\).