Lab 4b: Binary representation of data; boolean logic

This lab is optional.
There are no labs during the week of February 19 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.

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:

Similarly, to represent the formula x or y or z (three variables), the truth table has 2^3 = 8 rows:

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:

>>> 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:

  >>> 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:

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.

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.