title: Lab 4b: Binary representation of data; boolean logic
***This lab is optional.***
There are no labs during the week of February 20 because of the
holiday, but we're posting this optional lab for you to do on your
own---for extra practice and/or to help you in your work on the
problem sets.
[TOC]
### Task 0: representation of integers; binary arithmetic ###
In lecture, you have seen how we can represent numbers in base two (binary) and
base ten (decimal). For example, we can represent the decimal number 21 as
10101 in binary, and the decimal number 7 as 111 in binary.
Complete the following exercises. Write your solutions in a text file named
`lab4task0.txt`.
1. Convert the decimal number 44 to binary.
2. Convert the decimal number 35 to binary.
3. Convert the binary number 100111 to decimal.
4. Convert the binary number 10000 to decimal.
Now let's do some arithmetic on binary numbers.
5. Add the binary numbers 10110 and 1101.
6. Multiply the binary numbers 10110 and 1101.
###Task 1: truth tables for boolean expressions
Recall that we can represent a Boolean expression as a truth table by
enumerating all possible combinations of the variables in the expression.
In other words, if a Boolean expression has `n` variables, then we can use
a truth table to equivalently represent the logic using `2^n`
rows.
For example, to represent the formula `x and y` (two variables),
the truth table has `2^2 = 4` rows:
| x | y | x and y |
|---|---|:-------:|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Similarly, to represent the formula `x or y or z` (three variables),
the truth table has `2^3 = 8` rows:
| x | y | z | x or y or z |
|---|---|---|:-------:|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 |
Create a truth table for the following Boolean expression:
`(x or y) and z`. The rows of the truth table should "cover" all possible
combinations of true and false values for the variables. Put your
answer in a text file named `lab4task1.txt`.
### Task 2: recursive processing of binary numbers ###
In Problem Set 4, you will write recursive functions that
manipulate binary numbers that are represented as strings.
The ***bitwise OR*** of two binary numbers is formed by considering
the bits in the numbers from right to left. As you do so, each pair of
corresponding bits is ORed together to produce the appropriate bit
for the result.
For example, to obtain the bitwise OR of `10100` and `00101`, we would
begin by essentially lining up the two numbers as follows:
10100
00101
-----
We would then OR together each pair/column of bits from right to left.
For example, the rightmost column gives us `(0 OR 1)` which is `1`:
10100
00101
-----
1
The next pair/column of bits gives us `(0 OR 0)` which is `0`:
10100
00101
-----
01
Continuing in this way, we get:
10100
00101
-----
10101
And thus the bitwise OR of `10100` and `00101` is `10101`.
If one number has more bits than the other, the extra bits are effectively
ORed with 0s, and thus they are unchanged in the result. For example:
10101010
11000
--------
10111010
In IDLE, use the *File -> New Window* menu option to open a new editor
window for your code, and **save it using the name `lab4task2.py`**.
Make sure to specify the `.py` extension.
Write a function called `bitwise_or(b1, b2)` that takes as inputs two
strings `b1` and `b2` that represent binary numbers. The function should
***use recursion*** to compute the bitwise OR of the two numbers, and
***return*** the result in the form of a string. For example:
:::python
>>> bitwise_or('10100', '00101')
'10101'
>>> bitwise_or('10101010', '11000')
'10111010`
**Notes/hints:**
* *Base cases:* Because the function will be called recursively
on smaller and smaller strings, you will eventually get down
to an empty string for one or both of the inputs.
* If both inputs are the empty string, the function
should return the empty string.
* If only one of the inputs is the empty string, the function
should return a string that represents the result of ORing
the other input with 0s.
For example:
:::python
>>> bitwise_or('', '')
''
>>> bitwise_or('101', '')
'101'
>>> bitwise_or('', '11010')
'11010'
* You should use recursion to OR the rest of the bits in the two numbers.
When you do so, make sure that you end up considering the bits from right
to left, rather than from left to right.
* As usual, we recommend making the recursive call at the start
of the recursive case and storing its return value in a variable.
Then you can use that variable to construct the value that
you will return.
* You will need to use conditional execution (`if-elif-else`) to
decide what to return, based on the bits that are being ORed
by the current call of the function. Use concrete cases as needed
to figure out the logic.
### Task 3: evaluation and creation of circuit diagrams ###
When representing Boolean logic using circuit diagrams, we can use the
following logic gates to represent AND, OR, and NOT:
![The three basic digital logic gates.](../img/labs/lab5/logic_gates.svg)
Consider the following circuit diagram, where the inputs have been colored for
clarity. Write your solutions to the following problems in a text file named
`lab4task3.txt`.
![A digital logic circuit.](../img/labs/lab5/circuit.svg)
1. Find the output of this circuit if the inputs are `A = 1`, `B = 0`, and
`C = 1`.
2. Find the output of this circuit if the inputs are `A = 0`, `B = 1`, and
`C = 0`.
3. Draw a circuit diagram (you don't need to submit it) that is equivalent to
the Python boolean expression
A and ((B and C) or (not D))
Note that you do ***not*** need to use minterm expansion for this problem.