### 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.

1.  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.

2.  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)?

3.  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.

4. We leave this to you.
5. This should be straightforward. However, have a look at the arithmetic as you go along.
7. 1 + 1 = 1. Not in arithmetic nor even modulo arithmetic.
8. 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$
1. $xy$;
2. $xy + yz + za$;
3. 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.
4. 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!
5. This should be straightforward by looking through the text.
6. $0' = 1$ and $1' = 0$.
7. 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$.

8. $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$.)

9. 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