tmalsburg/week04.org

## week04.org

      
    Raw
  

              week04.org
            
          
    Foundations of Math

Agenda for today


  Solutions for homework from last week
    
      Exercises 36.1 – 36.16 (submit one .pdf)
    
  
  Homework for next week.

Plan for the rest of the term (tentative):


  Chapter 1: Standard functions and techniques
  Chapters 2-4: Differentiation
  Chapters 14-15: Integration
  Chapters 7–10: Linear Algebra
  Chapters 39-40: Probability and statistics

Self-tests


  It is strongly recommend to do them.
  A variant usually appears in the exercises.
  Sometimes they are the key to solving exercises.
  If you have problems with the self-test, you are not ready to move ahead.

Exercise 36.1:

Read through Example 36.1.  Now prove the other absorption law:
  $$a * (a ⊕ b) = a$$

  (Example 36.1 and this result illustrate the duality principle, which states that any theorem which can be proved in Boolean algebra implies another theorem with $*$ and $⊕$ interchanged for the same elements.)\nl
Idea was not to use laws in box 36.3.

For all $a,b∈ B$ \pause
  \begin{align*}
  a * (a ⊕ b) & = (a ⊕ 0) * (a ⊕ b) & (\text{Identity law})  

  & = a ⊕ (0 * b)            & (\text{Distributive law})
  \end{align*}
\pause Now \pause
  \begin{align*}
  0 * b & = \overline{b} * b * b & (\text{Complement law})  

  & = \overline{b} * b     & (\text{Definition of $*$}) \
  & = 0                    & (\text{Complement law})
  \end{align*}
\pause Finally \pause
  \begin{align*}
  a * (a ⊕ b) & = a ⊕ 0 & 

  & = a          & (\text{Identity law})
  \end{align*}
Exercise 36.2:

(Section 36.1).  Prove the de Morgan result
  $$\overline{a ⊕ b} = \overline{a} * \overline{b},$$
  by showing that $(a ⊕ b) ⊕ (\overline{a} * \overline{b}) = 1$.  Explain how the duality result (Problem 36.1) gives the other de Morgan theorem.\nl\pause
First of all:\small
  \begin{align*}
  \overline{a ⊕ b}                     & = \overline{a} * \overline{b}                     & (\text{Add $a ⊕ b$ on both sides.})

  (a ⊕ b) ⊕ \overline{a ⊕ b} & = (a ⊕ b) ⊕ \overline{a} * \overline{b} & \pause\
  1 & = (a ⊕ b) ⊕ \overline{a} * \overline{b} & (\text{Complement law})
  \end{align*}

\begin{align*}
  a ⊕ b ⊕ \overline{a} * \overline{b} & = \pause b ⊕ (a ⊕ \overline{a}) * (a  ⊕ \overline{b})  & (\text{Distr.})

  & =  b ⊕                                 (a  ⊕ \overline{b})  & (\text{Identity})\
  & = (b ⊕ \overline{b}) ⊕ a                                    & (\text{Comm., Assoc.})\
  & = 1 ⊕ a                                                          & (\text{Identity})\
  & = 1                                                                   & (\text{Identity})
  \end{align*}
Exercise 36.3:

(Section 36.1).  Let $B$ be the Boolean algebra with the two elements 0 and 1.  For arbitrary $a,b∈ B$, prove the following:\nl

  
$a * (\overline{a} ⊕ b) = a * b$ \pause

\begin{align*}
  a * (\overline{a} ⊕ b) & = \pause(a * \overline{a}) ⊕ (a * b) & (\text{Distributive law})

  & = 1 ⊕ a * b                          & (\text{Complement law})\
  & = a * b                                   & (\text{Identity law})
  \end{align*}


  $(a ⊕ b) * (a ⊕ \overline{b}) = a$

\begin{align*}
  (a ⊕ b) * (a ⊕ \overline{b}) & = \pause a ⊕ b * \overline{b} 

  & = a ⊕ 0 \
  & = a
  \end{align*}
  \pause

  
$(a ⊕ b) * \overline{a} * \overline{b} = 0$ \pause

\begin{align*}
  (a ⊕ b) * \overline{a} * \overline{b} & = \pause (\overline{a} * a ⊕ \overline{a} * b) * \overline{b} 

  & = \overline{a} * b * \overline{b} \
  & = \overline{a} * 0 \
  & = 0
  \end{align*}
Exercise 36.4:

(Section 36.1). Using the laws of Boolean algebra for the set with two elements 0 and 1, show that:

  $a * b ⊕ a * \overline{b} = a$
  $a ⊕ \overline{a} * \overline{b} * c = a ⊕ \overline{b} * c$

Use the result to obtain the truth tables in each case.\nl

\begin{align*}
  a * b ⊕ a * \overline{b} & = \pause a * (b ⊕ \overline{b}) 

  & = a * 1 \
  & = a
  \end{align*}
  \pause
Truth table:

  
$a$
$b$
$\overline{b}$
$a * b$
$a * \overline{b}$
$a * b ⊕ a * \overline{b}$

  
0
0
1
0
0
0

  
0
1
0
0
0
0

  
1
0
1
0
1
1

  
1
1
0
1
0
1


\begin{align*}
  a ⊕ \overline{a} * \overline{b} * c & = \pause a ⊕ (\overline{a} * \overline{b} * c) 

  & = (a ⊕ \overline{a}) * (a ⊕ \overline{b}) * (a ⊕ c) \
  & = (a ⊕ \overline{b}) * (a ⊕ c) \
  & = a ⊕ (\overline{b} * c) \
  & = a ⊕ \overline{b} * c \
  \end{align*}
  \pause

  How do we know that the distributive generalizes to products with more than two factors?


Truth table:

  
$a$
$b$
$c$
$\overline{b} * c$
$a ⊕ \overline{b} * c$

  
0
0
0
0
0

  
0
0
1
1
1

  
0
1
0
0
0

  
0
1
1
0
0

  
1
0
0
0
1

  
1
0
1
1
1

  
1
1
0
0
1

  
1
1
1
0
1


Exercise 36.5:

(Section 36.4).  In Problem 36.4b, it is shown that
  $$a ⊕ \overline{a} * \overline{b} * c = a ⊕ \overline{b} * c.$$
  Design two sequences of gates which give the same output for the inputs $a$, $b$, and $c$.  The resultant gates are said to be logically equivalent.
Exercise 36.6:

(Section 36.4).  Design a circuit of gates to produce the output
  $$(a ⊕ \overline{b}) * (a ⊕ \overline{c}).$$
  Construct the truth table for this Boolean expression.
Exercise 36.7:

(Section 36.1). Show that the Boolean expression $(a ⊕ b) * (\overline{a} ⊕ b) ⊕ a$ and $a ⊕ b$ are equivalent.
\begin{align*}
  (a ⊕ b) * (\overline{a} ⊕ b) ⊕ a & = \pause (a ⊕ a ⊕ b) * (a ⊕ \overline{a} ⊕ b)

  & = (a ⊕ b) * (a ⊕ \overline{a} ⊕ b)\
  & = (a ⊕ b) * (1 ⊕ b)\
  & = (a ⊕ b) * 1\
  & = a ⊕ b\
  \end{align*}
Exercise 36.8:

(Section 36.1).  Show that the following Boolean expression are equivalent:

  $a ⊕ b$
  $a ⊕ b * b$

\pause
\vspace{-2em}
  \begin{align*}
  a ⊕ b * b & = a ⊕ (b * b)

  & = a ⊕ b
  \end{align*}
  \pause
But how do we know that $b*b = b$?\pause

  
$b$ could be 1, then $b * 1 = b$.
  
$b$ could be 0, then $b * 0 = 0 = b$.

Exercise 36.9:

(Section 36.3).  Find a Boolean expression $f$ which corresponds to the truth table shown in Table 36.13.

  
$a$
$b$
$c$
$f$

  
0
0
0
1

  
0
0
1
1

  
0
1
0
0

  
0
1
1
0

  
1
0
0
1

  
1
0
1
1

  
1
1
0
0

  
1
1
1
0


\pause
$(\overline{a} * \overline{b}) ⊕ (a * \overline{b}) = (\overline{a} ⊕ a) * \overline{b} = \overline{b}$
Exercise 36.10:

(Section 36.3).  Construct Boolean expression for the output $f$ in the devices shown in Figs. 36.17a–d.  Construct the truth tables in each case.
(a)

\begin{circuitikz} \draw
  (0,2) node[and port] (myand1) {}
  (myand1.in 1) node [anchor=east] {a}
  (myand1.in 2) node [anchor=east] {b}
(0,0) node[or  port] (myor)   {}
  (myor.in 1) node [anchor=east] {c}
  (myor.in 2) node [anchor=east] {d}
(2,1) node[and port] (myand2) {}
(myand1.out) – (myand2.in 1)
  (myor.out)   – (myand2.in 2);
  \end{circuitikz}
  \pause

  $a * b * (c ⊕ d)$

(b)

\begin{circuitikz} \draw
  (0,2) node[and port] (myand1) {}
  (myand1.in 1) node [anchor=east] {a}
  (myand1.in 2) node [anchor=east] {b}
(0,0) node[or  port] (myor)   {}
  (myor.in 1) node [anchor=east] {b}
  (myor.in 2) node [anchor=east] {c}
(2,1) node[and port] (myand2) {}
(myand1.out) – (myand2.in 1)
  (myor.out)   – (myand2.in 2);
  \end{circuitikz}
  \pause

  $a * b * (b ⊕ c) = a * b$

(c)

\begin{circuitikz} \draw
  (0,2) node[and port] (myand1) {}
  (myand1.in 1) node [anchor=east] {a}
  (myand1.in 2) node [anchor=east] {b}
(1,2) node[not port] (mynot1) {}
(0,0) node[or  port] (myor1)   {}
  (myor1.in 1) node [anchor=east] {c}
  (myor1.in 2) node [anchor=east] {d}
(4,1) node[or port] (myor2) {}
(myand1.out) – (mynot1.in)
  (mynot1.out) – (myor2.in 1)
  (myor1.out)  – (myor2.in 2);
  \end{circuitikz}
  \pause

  $\overline{a * b} ⊕ (c ⊕ d) = \overline{a} ⊕ \overline{b} ⊕ c ⊕ d$

(d)

\begin{circuitikz} \draw
  (0,2) node[xor port] (myxor1) {}
  (myxor1.in 1) node [anchor=east] {a}
  (myxor1.in 2) node [anchor=east] {b}
(1,2) node[not port] (mynot1) {}
(0,0) node[and port] (myand1)   {}
  (myand1.in 1) node [anchor=east] {c}
  (myand1.in 2) node [anchor=east] {d}
(4,1) node[or port] (myor2) {}
(myxor1.out) – (mynot1.in)
  (mynot1.out) – (myor2.in 1)
  (myand1.out)  – (myor2.in 2);
  \end{circuitikz}
  \pause

  $\overline{\overline{a} * b ⊕ a * \overline{b}} ⊕ c * d = a * b ⊕ \overline{a} * \overline{b} ⊕ c * d$

Exercise 36.11:

Find the output $f$ and $g$ in the logic circuits shown in Fig. 36.18.  This device can represent binary addition in which $g$ is the ’carry’ in the binary table shown in Table 36.14.  The output $g$ gives the ’1’ in the ’10’ in the binary sum $1+1=10$.\pause


  $g = a * b$
  $f = \overline{a * b} * (a ⊕ b)$


$x=a$
$y=b$
$x+y$
$g$
$f$

  
0
0
0
0
0

  
0
1
1
0
1

  
1
0
1
0
1

  
1
1
10
1
0


Exercise 36.12:

(Section 36.3). Reproduce the logic gate in Fig. 36.6 using just the \textsc{NOR} gate.  (Circuit is $a * b ⊕ c ⊕ d$).\nl\pause
We need to build $*$ and $⊕$ using just \textsc{NOR} ($↓$):

  
$a * b = \pause\overline{a} ↓ \overline{b}$ \pause
  
$\overline{a} = \pause a ↓ a$ \pause
  Therefore: $a * b = \pause (a ↓ a) ↓ (b ↓ b)$ \pause
  
$a ⊕ b = \pause \overline{a ↓ b} = (a ↓ b) ↓ (a ↓ b)$ \pause
  All taken together:

\begin{align*}
  a * b ⊕ c ⊕ d = & \pause (((a ↓ a) ↓ (b ↓ b)) ↓ ((c ↓ d) ↓ (c ↓ d))) ↓ 

   & (((a ↓ a) ↓ (b ↓ b)) ↓ ((c ↓ d) ↓ (c ↓ d)))\
  = & (a ↓ c ↓ d) ↓ (b ↓ c ↓ d)
  \end{align*}

Scratchpad:
Exercise 36.13:

(Section 36.4).  Using the disjunctive normal form, construct a Boolean expression $f$ for the truth tables given in Tables 36.15 and 36.16.
  \vspace{-2.5em}


$a$
$b$
$f$

  
0
0
0

  
0
1
1

  
1
0
1

  
1
1
1


\vspace{-2em}\pause
  \begin{align*}
  f = &\overline{a} * b ⊕

  & a * \overline{b} ⊕\
  & a * b = a⊕ b
  \end{align*}
  \pause
\scriptsize\vspace{-1em}

  
$a$
$b$
$c$
$f$

  
0
0
0
1

  
0
0
1
0

  
0
1
0
0

  
0
1
1
1

  
1
0
0
1

  
1
0
1
0

  
1
1
0
1

  
1
1
1
0


\normalsize\vspace{-2em}\pause
  \begin{align*}
  f = & \overline{a} * \overline{b} * \overline{c}  ⊕

  & \overline{a} * b * c  ⊕\
  & a * \overline{b} * \overline{c}  ⊕\
  & a * b * \overline{c}
  \end{align*}
Exercise 36.14:

(Section 36.3).  Show that any Boolean expression can be modelled using just a \textsc{NAND} gate.   (Hint: use a method similar to that explained in Example 36.4.)\nl
\vspace{-1.5em}\small

  
$a$
$b$
$a ↑ b$
$\overline{a}$
$a * b$
$a ⊕ b$

  
0
0
1
1
0
0

  
0
1
1
1
0
1

  
1
0
1
0
0
1

  
1
1
0
0
1
1


\normalsize\pause
We have to show that $*$ (conjunction), $⊕$ (disjunction), and $\overline{a}$ (negation) can be expressed in terms of just \textsc{NAND}:

  
$\overline{a} = \pause a ↑ a$ \pause
  
$a * b = \pause \overline{a ↑ b} = (a ↑ b) ↑ (a ↑ b)$ \pause
  $a ⊕ b = \pause \overline{a} ↑ \overline{b} = (a ↑ a) ↑ (b ↑ b)$

Exercise 36.15:

(Section 36.4).  Find switching functions for the switching circuits shown in Figs 36.19a,b.\pause

  
$a_1 ⊕ a_2 ⊕ ((a_3 ⊕ a_4) * a_5)$ \pause
  $a_1 ⊕ ((a_2 * a_3 ⊕ a_4) * a_5)$

Exercise 36.16:

\vspace{-0.5em}
\small
  A lecture theatre has three entrances and the lighting can be controlled from each entrance; that is, it can be switched on or off independently.  The light is ’on’ if the output $f$ equals 1 and ’off’ if $f=0$.  Let $a_i=1$ $(i=1,2,3)$ when switch $i$ is up, and let $a_i=0$ $(i=1,2,3)$ when it is down.  Construct a truth table for the state of the lighting for all states of the switches.  Also specify a Boolean expression which will control the lighting.
  \pause
\vspace{-2em}

  
$a_1$
$a_2$
$a_3$
$f$

  
0
0
0
0

  
0
0
1
1

  
0
1
0
1

  
0
1
1
0

  
1
0
0
1

  
1
0
1
0

  
1
1
0
0

  
1
1
1
1


\pause

\vspace{-3.5em}\small
  \begin{align*}
  f = \pause & (\overline{a_1} * \overline{a_2} * a_3) ⊕

  & (\overline{a_1} * a_2 * \overline{a_3}) ⊕\
  & (a_1 * \overline{a_2} * \overline{a_3}) ⊕\
  & (a_1 * a_2 * a_3)
  \end{align*}
  \pause
\vspace{-3em}

  Is there another solution?\pause

    Yes, the complement, $\overline{f}$!

Homework for next week


  Read sections 1.1–1.9 in Chapter 1 (27 pages).
  Do exercises: 1.1 – 1.14, 1.18, 1.20, 1.21.


\vfill

  End of file.

\vfill