MTH4000 Home

MTH 4000: Practice Midterm 1

Problem 1. Prove that \[\neg \left( \left(P\wedge Q\right)\to \left(R\vee S\right)\right) \equiv \left(P\wedge Q\wedge \neg R\wedge \neg S\right)\]

Problem 2. Let \(P\) and \(Q\) be two propositions. The proposition \[\left(\left(P\leftrightarrow Q\right)\to\left(\neg P\right)\right)\wedge \neg Q \] is equivalent to:
  • (A) \(P\)
  • (B) \(Q\)
  • (C) \(\neg P\)
  • (D) \(\neg Q\)
  • (E) \(P\wedge Q\)
  • (F) \(P\wedge \neg Q\)
  • (G) \(\neg P\wedge Q\)
  • (H) \(\neg P\wedge \neg Q\)

Problem 3. For each of the following propositions write one of the letters T or F. Write T if the proposition is true, and F if the proposition is false. Your answer should be a word of length exactly 5 consisting of letters T and F only.
  • (a) For every set \(A\) and every relation \(R\) on the set \(A\) the intersection \(A\cap R\) is empty set.
  • (b) For every transitive relation \(R\) on \(\{1,2,3,4,5\}\) the following holds: If \((1,2)\in R\) and \((2,5)\in R\), then \((1,5)\in R\).
  • (c) If \(A\) and \(B\) are two sets such that \(\left(A\times A\right)\cap \left(B\times B\right)\neq \emptyset\), then \(A \cap B\neq \emptyset\).
  • (d) For every finite subset \(A\) of \(\mathbb N\) with at least three elements there exists a relation \(R\) on \(A\) such that \(\left(\forall x\in A\right)\left(\exists y\in A\right)\left((x,y)\in R\mbox{ and }(y,x)\not\in R\right)\).
  • (e) There exists a set \(A\) with \(10\) elements and an equivalence relation \(R\) on the set \(A\) such that \(|R|=11\).

Problem 4. For each of the following sentences write one of the letters N, T, or F. Write N if the sentence is not a proposition; T if the sentence is a true proposition, and F if the sentence is a false proposition. Your final answer should be a word of length exactly 5 consisting of letters N, T, and F only.
  • (a) If \(x\) is a natural number, then \(\sqrt{x^2+6x+9}\) is a natural number.
  • (b) If \(x\) is a natural number such that \(x+7 > 25\), then \(x\) is a perfect square of an integer.
  • (c) If \(x\) is a natural number such that \(\sqrt{x^2+6x+10}\) is a natural number, then \(x\) is divisible by \(2021^{2021^{2021}}\).
  • (d) If \(x\) is a natural number such that \(x+7> y\), then \(x\) is a perfect square of an integer.
  • (e) If \(x\) is a real solution of the equation \(x+3=\sqrt{x^2+1}\), then \(x\) is a negative number.

Problem 5.

Are the following statements true or false? Justify your conclusion.

  • (a) If \(a\) and \(b\) are integers, then \(a^2b^2+a^2b+ab^2+ab\) is divisible by \(4\).
  • (b) If \(a\), \(b\), and \(c\) are integers, then \(ab+ac+b^2+c^2\) is an even integer.

Problem 6. Construct an example of two predicates \(P(x)\) and \(Q(x)\) for which \begin{eqnarray*} \mbox{The proposition } &&\left(\forall x\in\mathbb Z\right)\left( P(x) \vee \neg Q(x)\right) \mbox{ is true }\\ \mbox{ and the proposition }&&\left(\exists x\in\mathbb Z\right)\left( P(x) \vee Q(x)\right) \mbox{ is false.}\end{eqnarray*} Provide a rigorous justification for your answer.

Problem 7.

Prove that if \(m\) is an odd integer, then \(7m+9\) is an even integer.

Problem 8.

An integer \(a\) is said to be congruent to \(0\) modulo \(3\) if there exists an integer \(n\) such that \(a=3n\). An integer \(a\) is said to be congruent to \(1\) modulo \(3\) if there exists an integer \(n\) such that \(a=3n+1\). An integer \(a\) is said to be congruent to \(2\) modulo \(3\) if there exists an integer \(n\) such that \(a=3n+2\).

  • (a) Give an example of at least four different integers that are congruent to \(1\) modulo \(3\).
  • (b) Give an example of at least four different integers that are congruent to \(2\) modulo \(3\).
  • (c) Prove that if \(x\) is a positive integer, then \(x^2\) is never congruent to \(2\) modulo \(3\).

Problem 9. Determine whether the following proposition is true or false: For every prime number \(p\), the number \(p^2+4\) is prime.

Problem 10. Determine which of the following propositions are true and which are false. Provide a rigorous justification for your answers.
  • (a) \(\left(\forall x \in \mathbb R_+\right)\left(\exists y\in\mathbb R_+\right)\left(\forall z\in\mathbb R\right)\left( \left(z > y\right) \rightarrow \left(z\cdot x^2 > 1\right)\right)\).
  • (b) \(\left(\forall x \in \mathbb R_+\right)\left(\exists y\in\mathbb R_+\right)\left(\forall z\in\mathbb R\right)\left( \left(z > y\right) \rightarrow \left( x^2 > z\right)\right)\).
  • (c) \(\left(\forall x\in\mathbb R\right)\left(\exists y\in\mathbb R_+\right)\left(\forall z\in\mathbb R\right)\left( \left(z > y\right) \to \left(z^2 \cdot x^2 > y\right)\right)\).

Problem 11. Find all sets of four consecutive positive integers such that the cube of the largest is the sum of the cubes of the other three.

Problem 12. Prove that a perfect square of an integer is congruent to either \(0\) or \(1\) modulo \(3\), and a perfect square of an integer is congruent to either \(0\) or \(1\) modulo \(4\).

Problem 13. Let \(n\) be a positive integer. Prove that if \(a\) and \(b\) are integers such that \(a\equiv b\; (\mbox{mod }n)\), then \(a^x\equiv b^x\; (\mbox{mod }n)\) for every positive integer \(x\).

Problem 14. Find all pairs of integers \(x\) and \(y\) such that \(x+y+xy=80\).

Problem 15. Determine whether the following proposition is true or false. \[\left(\forall k\in\mathbb N\right)\left(\exists m\in\mathbb N\right)\left(\forall n\in\mathbb N\right) \left( (n\geq m) \;\rightarrow \; (n+1)\nmid n^2+k\right).\] Provide a rigorous justification for your answer.

Problem 16. Find all pairs \((x,y)\) of positive integers for which \(2014^x+11^x=y^2\).