2 Boolean Formula Evaluation

4.

(a) Consider the formula ((A B) (A C)) (B C) with assignment to the variables A, B TRUE, C FALSE. Evaluate the formula. You do not need to show your work.

(b) Consider the Boolean circuit, with assignment to the inputs A, B TRUE, C FALSE. Evaluate the Boolean circuit. Show your work by indicating the truth value produced by A 4 1 7 B 5 10 output 2 9 C 8 3 6 each gate. Use the table in the back of this assignment. The senario: You are working as a computer programmer for the Alpha Beta Gamma Software company. It is your dream job. Your manager calls you into the office with the following comment:

" We hired you because you have a Computer Science degree from one of those fancy colleges. Nobody else here at Alpha Beta Gamma Software has your education or ability. We are moving into the business of Boolean formula evaluation. Starting next month, every morning we will be receiving a large number of large Boolean formulas. For each formula, the assignment of TRUEs and FALSEs to the variables will be given. We will evaluate each formula. We at Alpha Beta Gamma believe that we can rely on you to write a lightning fast program to evaluate these Boolean formulas."

You have no idea how to write such a program. You scour the internet but cannot find a satisfactory program to evaluate Boolean formulas. However, you do find a great program to evaluate Boolean circuits. 5. It turns out that it is easy to evaluate Boolean formulas directly in linear time. The spirit of this problem is to avoid doing so! A connective in a Boolean formula is an AND, OR, or NOT.

(a) For concreteness, assume that you are only allowed to use the program that evaluates Boolean circuits; everything else has to be done by hand. In one or two sentences, explain how you would use the Boolean circuit evaluation program to evaluate Boolean formulas.

(b) Show what you would do on the following example (from above): ((A B) (A C)) (B C)

(c) Assume that your roommate is very bright, and knows about Boolean formulas and circuits. You have a formula with a large number of connectives that you would like to evaluate. You still have the program that evaluates Boolean circuits; as before, everything else has to be done by hand. You are too lazy (or busy) to evaluate the formula yourself, but your roommate is willing to do it for you. In a few sentences, state what you would tell your roommate to do. (NOTE: A Boolean formula is actually two smaller Boolean formulas separated by an AND or OR, or the NOT of a smaller Boolean formula.)

(d) How fast is this, as a function of n, the number of connectives? Justify. (Dont overthink this! The simple, obvious answer is all you need.)

6. (a) Assume that the Boolean circuit evaluation program works in linear time (m), where m is the number of gates and/or wires in the Boolean circuit. Using your result above, how fast can you evaluate a formula of size n, where n is the number of connectives? Justify.

(b) Assume that the Boolean circuit evaluation program works in time (mr ), for some constant r 1. Using your result above, how fast can you evaluate a formula of size n, where n is the number of connectives? Justify.

7. Assume the scenario is reversed: You need to evaluate Boolean circuits; you have available a great program that evaluates Boolean formulas.

(a) Explain briefly how to use the Boolean formula program to evaluate Boolean circuits.

(b) Assume that the Boolean formula evaluation program works in time (mr ) for some constant r 1. How fast can you evaluate a Boolean circuit of size n? Justify.