Assignment 2

In addition to correct answers, please:

  • Show how you derived your answer.
  • Make all proofs, and longer-answer questions, beautifully organized and easy to read. This includes perfect spelling and grammar.

Please see Canvas for instructions on how and when to submit this assignment.

Question 1

Let \(p\), \(q\), \(r\), and \(s\) denote the following statements:

\(p\): I’ll do math homework before noon.

\(q\): I’ll go swimming in the afternoon.

\(r\): It’s raining.

\(s\): YouTube is down.

Translate each of the following statements into symbolic form:

  1. If it’s not raining, I won’t go swimming in the afternoon.
  2. For me to go swimming in the afternoon, it’s necessary for me to do my math homework before noon.
  3. It’s not raining, and YouTube is down, is sufficient for me to go swimming in the afternoon.

Question 2

For each of the following statements, say if they are true or false.

  1. If triangles have 4 corners, then \(1 + 1 = 3\).
  2. If squares have 4 corners, then \(2 + 7 = 10\).
  3. If triangles have 4 sides, or squares have 4 sides, then \(3 + 3 = 4\).
  4. If \(1 + 1 = 2\), then water is wet.

Question 3

In the following compound statements, \(p\), \(q\), and \(r\) are primitive statements. Do the following for each compound statement:

  • create a truth table, and highlight the column showing all possible truth-values
  • if the statement is a tautology, or a contradiction, then state which
  1. \(\neg (\neg p \land q) \to \neg p\)
  2. \((p \to q) \to r\)
  3. \(p \to (q \to r)\)
  4. \((p \to q) \to (q \to \neg p)\)
  5. \((p \lor (p \to q)) \to q\)
  6. \((p \land \neg q) \to p\)
  7. \(q \leftrightarrow (\neg p \land q)\)
  8. \(((p \to q) \to (q \to r)) \land (r \to p)\)

Question 4

Negate each of the following statements, and simplify them as much as possible.

  1. \([p \lor (q \lor r)] \land (\neg p \lor \neg q \lor r)\)
  2. \((p \land q) \to r\)
  3. \(p \to (\neg q \land r)\)
  4. \(p \lor q \lor (\neg p \land \neg q \land r)\)

Question 5

Re-write each of the following statements as a logically equivalent statement using just \(p\), \(q\), \(\neg\), and \(\to\) (you can use 0 or more occurrences of each).

  1. \(p \lor q\)
  2. \(p \land q\)

Question 6

Consider the following 10 statements:

  1. Exactly 1 statement on this list is false.
  2. Exactly 2 statements on this list are false.
  3. Exactly 3 statements on this list are false.
  4. Exactly 4 statements on this list are false.
  5. Exactly 5 statements on this list are false.
  6. Exactly 6 statements on this list are false.
  7. Exactly 7 statements on this list are false.
  8. Exactly 8 statements on this list are false.
  9. Exactly 9 statements on this list are false.
  10. Exactly 10 statements on this list are false.
  1. Describe all possible truth values for each statement that make all the statements accurate.
  2. Re-do the previous question, but with a list of statements that goes from 1 to 1000.
  3. Is the following statement true or false? Clearly explain your answer.
    1. Exactly 1 statement on this list is false.

Question 7

State each of the following laws of logic, and then use a truth table to prove that each is valid:

  1. Rule of contradiction
  2. Rule of disjunctive amplification
  3. Rule for proof by cases

Question 8

Suppose the universe of discourse is all fruits and vegetables, and consider the following open statements:

\(f(x):\) \(x\) is a fruit

\(v(x):\) \(x\) is a vegetable

\(a(x):\) \(x\) is an apple

\(b(x):\) \(x\) is broccoli

\(g(x):\) \(x\) is the color green

\(r(x):\) \(x\) is the color red

Translate each of the following statements into equivalent English, and state whether it’s true or false.

  1. \(\forall x . f(x) \lor v(x)\)
  2. \(\exists x . f(x) \land v(x)\)
  3. \(\forall x . g(x) \to b(x)\)
  4. \(\exists x . v(x) \land g(x)\)
  5. \(\forall x . (g(x) \lor r(x)) \leftrightarrow a(x)\)
  6. \(\exists x . a(x) \land \neg r(x)\)
  7. \(\exists x . \neg g(x) \land \neg f(x)\)
  8. \(\forall x . b(x) \to \neg r(x)\)
  9. \(\forall x . a(x) \to (g(x) \lor r(x))\)
  10. \(\forall x . v(x) \to [g(x) \to (a(x) \lor b(x))]\)

Question 9

Simplify each of the following:

  1. \(\neg [\exists x . p(x) \lor q(x)]\)
  2. \(\neg [\forall x . p(x) \land \neg q(x)]\)
  3. \(\neg [\forall x . q(x) \to p(x)]\)
  4. \(\neg [\exists x . (p(x) \lor q(x)) \to r(x)]\)

The following two questions, 10 and 11, have been moved to assignment 3, so you do not need to submit answers to these for assignment 2. If you’ve already answered them, that’s okay: re-submit your answers to them as part of assignment 3.

Question 10

Prove that if \(n\) is an integer, then \(n\) and \(n+1\) can’t both be odd.

Question 11

Prove that if \(n\) is an odd integer, then \(n^2 + 3\) is always even.