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?
    P1 P2 C $(P1\land P2)\to C$ $(P1\to C)\lor (P2\to C)$
    1 1 1 1 1
    1 1 0 0 0
    1 0 1 1 1
    1 0 0 1 1
    0 1 1 1 1
    0 1 0 1 1
    0 0 1 1 1
    | 0 | 0 | 0 | 1 | 1 |
  2. Similarly, for each statement, find all situations where it is false. What do you see here?
    1. The only time $(P1\land P2)\to C$ is false is when $(P1\land P2)$ is true and $C$ is false.
    2. For $(P1\to C)\lor (P2\to C)$ to be false, both $(P1\to C)$ and $(P2\to C)$ need to be false ....
  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 \forall y [(x\neq y)\to P(x,y)]$ allows $P(a,a)$ to be true.
    1. Negate and simplify, what does this say?
    2. Suppose $P(x,y)$ is true iff x and y are pals. Write an English statment equivalent to this. Everyone is pals with everyone else.
  2. What does $\forall x[P(x)\to \exists y(P(y)\land x\neq y)]$ say? For every P thing, there is another (different) P thing.
    1. What is the negation of the previous statement?
      \[\exists x[P(x)\land \forall y(\neg P(y)\lor x=y)]\]
    2. The predicate $P(z)$ can be true or false.
      1. For how many z can can $P(z)$ be true? Any number but one. If only one z had $P(z)$ being true, there wouldn't be a different y as required.
      2. How many can be false? Any number.

Relations

  1. We've discussed four properties that relations can have.
reflexive symmetric anti-symmetric transitive
    1. Give an example of a relation that has all four properties.
      The equality relation.
    2. Wait! There is a relation that is both an equivalence relation and a partial order? What must the Hasse diagram of such a relation look like?
      A graph with no edges.
    3. Give an example of a symmetric and transitive relation that isn't reflexive
      The empty relation (on any non-empty set) is one example. Another is where both people have met me (some people have, but not everyone).

Induction

  1. A list of induction problems
  2. 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.
  3. 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 ...
  4. I claim that, for any fixed natural number C (however large), there is another constant D, for which the following is true
    \[\frac{n^3}{C}\geq n^2, n\geq D\]
    1. What is D, in terms of C? $D=C$ will work.
    2. Prove the statement is true by induction, using your answer to (a).
$\frac{(k+1)^3}{C}$ $=$ $\frac{k^3+3k^2+3k+1}{C}$ Expanding
  $=$ $\frac{k^3}{C}+3\frac{k^2}{C}+3\frac{k}{C}+\frac{1}{3}$ Searching for IH
  $\geq$ $k^2+ +3\frac{k^2}{C}+3\frac{k}{C}+\frac{1}{3}$ By IH
  $=$ $k^2+3k+3+\frac{1}{3}$ Using rewrites
  $>$ $k^2+2k+1$ Clearly $k+2+\frac{1}{3}>0$
  $=$ $(k+1)^2$ Done!

Graph Theory

  1. A forest is a graph with no cycles. A connected graph with no cycles is a tree.
    1. Explain (intuitively) why a graph, all of whose edges are bridges, would be a forest? Be contrary, assume there is a cycle. If there were a cycle, then deleting an edge in that cycle would still connect the endpoints, via the rest of the cycle. So no disconnections, hence no new connected components.
    2. The converse is trickier, try to explain why a forest consists entirely of bridges Try the contrapostive statement, a graph that isn't entirely made of bridges isn't a forest. Suppose the graph has an edge $e$ which isn't a bridge. So deleting $e$ doesn't disconnect the endpoints. Take the walk from the endpoints (in the graph without $e$) and add on $e$. That is a cycle!
    3. A tree is a connected forest, so a forest consists of trees smile Explain why, in a tree, $|V|=|E|+1$.When you delete an edge, one tree becomes two trees The hint implies that recursion (hence induction) should work Supose $T=(V,E)$ denotes the tree in question with vertices $V$ and edges $E$. You check the case when $|E|=0$. The IH is any tree with less than $k+1$ edges satisfies the equality. Now suppose $|E|=k+1$, when we delete an edge we get two trees $T_1=(V_1,E_1)$ and $T_1=(V_1,E_1)$ respectively. Induction step follows

|V| $=$ |V_1|+|V_2| Two trees
  $=$ |E_1|+1+|E_2|+1 IH
  $=$ (|E_1|+|E_2|+1)+1 Rearrange so edges come first
  $=$ |E|+1 In brackets are the edges