Logic 1

Recall that in Engr 121 we used arithmetic operations instead of $\land$, $\lor$ and $\neg$
  1. What was the symbol for each? $\land$ should be natural, the others a little forced
  2. Draw a truth table for $\to$ and determine which arithmetic operation is appropriate An inequality

Logic 2

On first glance, the statements $(P1\land P2)\to C$ and $(P1\to C)\lor (P2\to C)$ appear to say different things.
  1. Compute a truth table for both. What is the result?
  2. Similarly, for each statement, find all situations where it is false. What do you see here?
  3. Rewrite both statements using the law of contrapositive. Is this clearer?
  4. Directly prove that if $(P1\to C)\lor (P2\to C)$ is true, then $(P1\land P2)\to C$ is true. You might need cases Assume either $(P1\to C)$ or $\lor (P2\to C)$ is true .....
  5. It is difficult to prove the converse statement, if $(P1\land P2)\to C$, then $(P1\to C)\lor (P2\to C)$. Give it a go! Focus on $P1\to C$, consider the possibilities Either $P1\to C$ is true, or it is false. One case is easy ..

Quantifiers

  1. Explain why $\forall x,y [(x\neq y)\to P(x,y)]$ allows $P(a,a)$ to be true.
  2. What does $\forall x[P(x)\to \exists y(P(y)\land x\neq y)]$ say?
  3. What is the negation of the previous statement?

Induction

  1. This is a statement of what induction does, the set $S$ is the collection of natural numbers collected by the process
    \[(\forall S\subseteq \mathbb{N})([0\in S \land \forall k\in \mathbb{N}(k\in S \to k+1\in S)]\to S=\mathbb{N})\]
    This is very complicated!
    1. Which part is the base case?
    2. Which part is the induction hypothesis and step?
    3. The last part is a promise, what is the promise?
    4. What is the negation of the statement and what does it say?
      \[(\exists S\subseteq \mathbb{N})([0\in S \land \forall k\in \mathbb{N}(k\in S \to k+1\in S)] \land S\neq \mathbb{N})\]
      There is some subset of $\mathbb{N}$ for which induction doesn't work, it misses some number.
  2. The least number principle (which we haven't seen) says that every non-empty subset of $\mathbb{N}$ has a least element
    \[(\forall L\subseteq \mathbb{N})(L\neq \phi \to (\exists n\in L)(\forall t\in \mathbb{N})[t<n \to t\notin L])\]
    1. Which part talks about the set being non-empty?
    2. What is the least element?
    3. Negate this statement and explain what is says
      \[(\exists L\subseteq \mathbb{N})(L\neq \phi \land (\forall n\in L)(\exists t\in \mathbb{N})[t<n \land t\in L]\]
      There is a subset of $\mathbb{N}$, no matter where we think the bottom of the set is, we can always go lower.
    4. Use induction to prove that the least number principle is true.
      Look at $\mathbb{N}-L$, the set of values that $L$ doesn't collect
      Do induction on $\mathbb{N}-L$, you should find that it satisfies the conditions, so it collects everything ...