Print this problem set out (there are X problems!) and answer the problems on the given sheet.
  1. Below is an inductive proof that any boolean function can be defined by a propositional formula using only $\wedge$, $\vee$ or $\neg$. (We gave a different proof of this early in the course.) Clearly identify all the important features that any inductive proof should have:
    1. the size
    2. the base case
    3. the inductive case
    4. where the inductive hypothesis is used

    Let $f(x_1,\ldots,x_k)$ be a boolean function. There is a defining formula for $f$ that uses only the $\wedge$, $\vee$ and $\neg$ operators.
    We prove this by induction on $n = k-1$ (i.e. one less than the number of inputs to $f$. If $n = 0$, $f$ is one of the following four functions (these are all possible truth tables with one input):

    1. which is equivalent to $\neg(x1 \vee \neg x1)$   2. which is equivalent to $\neg x1$
    3. which is equivalent to $x1$ 4. which is equivalent to $x1\vee\neg x1$

    Suppose $n > 0$. Then consider the following two functions: $$ f_0(x_1,\ldots,x_{k-1}) = f(x_1,\ldots,x_{k-1},0) \text{, and } f_1(x_1,\ldots,x_{k-1}) = f(x_1,\ldots,x_{k-1},1) $$ Then $f(x_1,\ldots,x_k) = 1$ if any only if $f_0(x_1,\ldots,x_{k-1}) = 1 \wedge \neg x_k \vee f_1(x_1,\ldots,x_{k-1}) = 1 \wedge x_k$. By the inductive hypothesis, there are formulas $G_0$ defining $f_0$ and $G_1$ defining $f_1$, both of which use only $\wedge$, $\vee$ and $\neg$. Therefore, $$ G_0 \wedge \neg x_k \vee G_1 \wedge x_k $$ is a defining formula for $F$. So we deduce that the theorem holds for any value of $n$.
  2. If $R_1$ and $R_2$ are rings, then we can form a new ring called $R_1 \times R_2$ whose elements are all pairs $(a,b)$ for which $a$ comes from $R_1$ and $b$ comes from $R_2$. We define + and * as follows: So, for eample, in the ring $\mathbb{Z}\times\mathbb{Z}$, $(2,5) + (-3,1) = (-1,6)$ and $(2,5) * (-3,1) = (-6,5)$.
    1. What is the additive identity in the ring $\mathbb{Z}\times\mathbb{Z}$? Justify!
    2. What is the multiplicative identity in the ring $\mathbb{Z}\times\mathbb{Z}$? Justify!
    3. What is the additive inverse of $(-5,8)$? Justify!

  3. Funny to say, but the ring axioms are actually satisfied if we have nothing but 0, i.e. there is only one element of the ring and it is zero. You can check for yourself! (In this case 0+0=0 and 0*0=0 and 0 is also "1".) We call this the trivial ring. If we don't want that, we need to specify that there is more than one element to the ring!
    A ring is non-trivial if and only if $\exists x[ x \neq 0 ]$.
    Below is a painfully detailed proof that in a non-trivial ring, 0 ≠ 1. This proof uses a technique called proof by contradiction, where we assume the negation of the thing we are trying to prove, and derive a contradiction (i.e. a formula that is false for all interpretations) from it, and that allows us to deduce that the thing we want to prove is true. The point is that this technique is not a new deduction rule, as you will see when you do your part, which is to fill in the reasons for each step.

    In a non-trivial ring, $0 \neq 1$.
    Note: Line 8 assumes multiplication is commutative This is not needed, but makes the proof a little bit easier.
    1:∃x[x ≠ 0]
    2:c ≠ 0
    3:∀x[1*x = x]
    4:1*c = c
    5:0 = 1Assumption A
    6:∀z[z*0 = 0]
    7:c*0 = 0
    8:0*c = 0
    9:1*c = 0
    10:c = 0
    11:c = 0 & c ≠ 0
    12:false
    13:0 = 1 => false
    14:true => ~(0 = 1) 
    15:~(0 = 1)
  4. Below is a proof of the same theorem, but in prose as a mathematician might normally write it. Next to each line of this proof, write the numbers of the corresponding lines from the above step-by-step proof. This is really important, because we are going to start transitioning to these shorter "prose" proofs, and we have to understand them as being abbreviated versions of the full first-order logic style proofs.

    Since the ring is non-trivial, let $c \neq 0$.

    By the ring axioms, $1*c = c$.

    Assume, by way of contradiction, that $0=1$.

    Then $0*c = 0$ by ,

    but since $0=1$, $0*c = 1*c = c$, and so $c = 0$.

    This contradicts our assumption, so $0 \neq 1$.