Answers

Switching circuits

    1. Switch $x$ Switch $y$ Result
      on on on
      on off off
      off on off
      off off off

      Simplifies to $x$ and $y$ in series.

    2. Switch $x$ Switch $y$ Result
      on on on
      on off on
      off on off
      off off off

      Simplifies to just the switch $x$.

    3. Switch $x$ Switch $y$ Result
      on on on
      on off off
      off on on
      off off off

      Simplifies to just the switch $y$.

    4. Switch $x$ Switch $y$ Switch $z$ Result
      on on on on
      on on off on
      on off on on
      off on on on
      off on on on
      off on off off
      off off on off
      off off off off

      Simplifies to the pair $y$ and $z$ in series and the pair in parallel with $x$.

    5. Switch $x$ Switch $y$ Switch $z$ Result
      on on on on
      on on off on
      on off on on
      on off off off
      off on on on
      off on off off
      off off on off
      off off off off

      Simplifies to $x$ and $y$ in series, $y$ and $z$ in series and $z$ and $x$ in series. Then these three series pieces in parallel.

    6. Switch $x$ Switch $y$ Switch $z$ Result
      on on on on
      on on off off
      on off on off
      on off off off
      off on on on
      off on off off
      off off on off
      off off off off

      Simplifies to $y$ and $z$ in series.

  2. Jamal John Light
    on on on
    on off off
    off on off
    off off off

    This is the same as $x $and $y$ in series.

  3. Veronique Jamal John Light
    on on on on
    on on off on
    on off on on
    on off off off
    off on on on
    off on off off
    off off on off
    off off off off

    Does this remind you of Q1(e)?

  4. Switch $x$ Switch $y$ Light
    on on off
    on off on
    off on on
    off off off

    This is the same as $x$ and $y$ in series.

  5. We leave this to you.
  6. This should be straightforward. However, have a look at the arithmetic as you go along.
  7. Addition, +, almost.
  8. 1 + 1 = 1. Not in arithmetic nor even modulo arithmetic.
  9. What we've done below assumes that you will allow 1 + 1 = 1.
      1. $x + y$;
      2. $x$:
      3. $y$;
      4. $x + yz$
      5. $y + yz + zx$;
      6. $yz$
    2. $xy$;
    3. $xy + yz + za$;
    4. This is problematic. We'll come back to this after we've done complements.
  1. Note that if $x$ is on (1), then $x'$ is off (0) and vice-versa.

    Check the algebraic answers we have given here to make sure that they are correct. We will give an efficient way to arrive at these results later. From the results here can you guess an efficient method?

    1. Switch $x$ Switch $y$ Result
      1 1 0
      1 0 0
      0 1 1
      0 0 0

      This is $x'y$.

    2. Switch $x$ Switch $y$ Switch $z$ Result
      1 1 1 0
      1 1 0 0
      1 0 1 0
      1 0 0 1
      0 1 1 0
      0 1 0 0
      0 0 1 0
      0 0 0 0

      This is $xy'z'$.

    3. Switch $x$ Switch $y$ Result
      1 1 1
      1 0 1
      0 1 1
      0 0 0

      This is $x + y$.

    4. Switch $x$ Switch $y$ Switch $z$ Result
      1 1 1 0
      1 1 0 0
      1 0 1 0
      1 0 0 1
      0 1 1 0
      0 1 0 0
      0 0 1 0
      0 0 0 0
      $x + y + z'$.
    5. Switch $x$ Switch $y$ Switch $z$ Result
      1 1 1 0
      1 1 1 0
      1 1 0 1
      1 0 1 0
      1 0 0 0
      0 1 1 1
      0 1 0 1
      0 0 1 0
      0 0 0 0

      $x'y + yz' = y(x' + z')$.

    6. Switch $x$ Switch $y$ Switch $z$ Result
      1 1 1 0
      1 1 1 1
      1 1 0 0
      1 0 1 0
      1 0 0 0
      0 1 1 0
      0 1 0 0
      0 0 1 0
      0 0 0 1
      $xyz + x'y'z'$.
  2. $xy' + x'y$
  3. We leave this to you.
  4. First we want 0 + 0 = 0. So what might 0 be? What's the nothing set? How about the empty set $\emptyset$.
    • Union
      $\emptyset \cup \emptyset= \emptyset--$ fine so far as a parallel for 0 + 0 = 0. $\emptyset \cup I = I$ $\dots$ good; and$I \cup I = I$ So union seems to tie in nicely with +.
    • Intersection
      $\emptyset \cap \emptyset = \emptyset; \emptyset \cap I = \emptyset$ and $I \cap I = I$. Clearly intersection isn't the same as + in switching circuits. But what does intersection parallel?
  1. Intersection looks pretty good for multiplication.
  2. $A \cup I = I$ and this mirrors addition from switching circuits, at least for $A = \emptyset$.
    3. $A \cap I = A$ and this mirrors multiplication or what you might think multiplication might be.
  3. Complementation. This is defined naturally on sets. It has the property that $A\cup A' = I$ and $A\cap A' =\emptyset$. These are consistent with 0 + 1 = 1 and 1 + 0 = 1; $0 \times 1 = 0$ and $1 \times 0 = 0$. We have consistency!
  4. This should be straightforward by looking through the text.
  5. $0' = 1$ and $1' = 0$.
  6. Yes. You will need to use: $0 = \emptyset$, $1 = I, \{x\}' =\{y\} $ and $\{y\}' = x$. The + is the union and the $\times$ is intersection.

    For any set $I$, the corresponding Boolean algebra is the set of all subsets of $I$ along with union and intersection as the two operations. (This is known as the power set of $I$.) If $A$ is any subset of $I$, then $A'$ is the complement of $A$ in$I$.

  7. $0 = 1; 1 = pq, p' = q$and $q' = p$.

    In general you need the Boolean algebra of the biggest number, $n$, along with of all its factors. In this algebra, the complement of the number $a$ is $n/a$, $0 = 1$ and $1 = n$.

    It is not possible for $n$ to have repeated prime factors. (Why not? You will certainly have problems with $ p + p'$ and $p \times p$ if $p^2$ is a factor of $n$.)

  8. Whatever you come up with it must satisfy all of the ten axioms we have given for a Boolean algebra.

    You might consider the Boolean algebra consisting of all finite and cofinite sets of integers. By a cofinite set we mean any subset of integers whose complement is finite. In this case, + is union of sets and $\times$ is the intersection of sets, $0 = \emptyset$, 1 = the set of integers, and the complement of a finite set is a cofinite one and vice versa.

    Does this idea work if you replace 'integers' with 'fractions'? How about real numbers?

    If $A$ and $B$ are Boolean algebras, then so is $A \times B = \{(x, y): x \in A \mbox{ and } y \in B\}$. What is zero, the one and the complement of $(x, y)$? What about $A \times B \times C$?

    You may find other examples of sets that qualify for Boolean algebras on the web. Can you change the definition of + and $\times$ to make such a set work?

    1. $\hspace{10px}x + 1 = (x + 1) \times 1 = (x + 1) \times (x + x') = x + (1 \times x') = x + x' = 1$.
    2. $\hspace{5px}x \times 0 = x \times (x \times x') = (x \times x) \times x' = x \times x' = 0$.
    3. $x \times (x + y) = (x + 0) \times (x + y) = x + (0 \times y) = x + 0 = x$.
    4. $x + (x \times y) = (x \times 1) + (x \times y) = x \times (1 + y) = x \times 1 = x$.

      Are there quicker ways to do any of these?

    1. $\hspace{10px}$False: $a$ can never equal $a' x + x' = 1$, but $x + x = x.$ So $x = 1$. However $1 \times 1 = 1$ and $1 \times 1' = 0$.
    2. $\hspace{5px}$True: $1 = 1 \times 1 = (x' + x) \times (x' + x'') = x' + (x \times x'')$ so $x = x \times x''$ and $x'' = x$.
    3. False by assuming that $y$ is also an inverse of $x: x' = x' \times 1 = x' \times (x + y) = (x' \times y) + (x' \times y) = x' \times y$. But we can replace $x'$ by $y$ and $y$ by $x'$ in this series of equations to get $x' = x' \times y = y \times x'= y$.
  1. To do this we need to prove that $(x + y) + (x' \times y') = 1$ and $(x + y) \times (x' \times y') = 0$. In the former case, $x + y + (x' \times y' ) = x + [(y + x') \times (y + y')] = x + (y + x') \times 1 = x + 1 = 1$. In the latter case, $(x + y) \times (x' \times y') = x \times x' \times y' + y \times x' \times y' = 0$.
  2. $(x \times y)' = x' + y'$. For example, $(0 \times 1)'= 0'= 1$ and $0'+ 1'= 1 + 0 = 1$. The general result can be proved by going through the steps of Q24 and replacing them by their duals.
    1. $\hspace{10px}x + (x \times y) = (x \times 1) + (x \times y) = x \times (1 + y) = x \times 1 = x$;
    2. $\hspace{5px}x + (x' \times y) = (x + x') \times (x+ y) = 1 \times(x + y) = x + y.$

      The duals are (i) $x \times (x + y) = x$; and (ii) $x \times (x'+ y) = x \times y$.

  1. Strictly speaking the principle of duality becomes a new axiom and we can reduce Axioms 2, 3, 4, 5, 6, 7 and 8 'by half'.
    1. $\hspace{10px}x'z + y'$;
    2. $\hspace{5px}$1;
    3. $x + z$.
  1. A switch in series with a wire is the same as the switch alone.
  2. Note that we use the table method of proof. Why?
    $x$ $y$ $z$ $x+yz$ $(x+y)(x+z)$
    0 0 0 0 0
    0 0 1 0 0
    0 1 0 0 0
    0 1 1 1 1
    1 0 0 1 1
    1 0 1 1
    1 1 0 1 1
    1 1 1 1 1
  3. Switch $x$ $y$ $x+xy$ $(x+y)(x+z)$
    0 0 0 0
    1 0 1 1
    0 1 0 0
    1 1 1 1
  4. This is because we can interchange + and $\times$ etc. in the above axioms.
    • $xy(x + y) = xxy + xyy = xy + xy = xy; $
    • $x(x + y)(y + x) = x(x + y) = xx + xy = x + xy = x(1 + y) = x;$
    • $(x + y + x)[(x + y)y] = (x + y)y = xy + y = y;$
    • $(x + y)(x + z) = x + xz + yx + yz = x + yz;$
    • $(xy + z)(x + yz) = xy + xyz + xz + yz = x(y + z) + yz = xy + yz+ zx;$
    • $z(xy + x + yz)y= xyz + xz + xyz = xyz + yz = yz.$
    • $x'y$ - no simplification;
    • $xy'z'$ - no simplification;
    • $x + x'y = x + y;$
    • $xyz'$- no simplification;
    • $xyz'+ x'y + yz'= xyz'+ yz' + x'y = x'y + yz'= y(x'+ z');$
    • $(xz + y')(yz + x'z') = xyz + xzx'z' + y'yz + x'y'z'= xyz+ x'y'z'.$
  1. Does $xy' + x'y$ work?

Next page - Answers to functions