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.