ICS 1F, Homework 3

Due Wednesday, February 4th, at the end of class

  1. ICS 161, an upper-division course in algorithms, is very full this quarter, so students are only allowed to take it if they are majoring in ICS or engineering, and if they need it either because they are planning to graduate this quarter or because without it they wouldn't have enough units to qualify for financial aid.

    Express this statement as a formula in boolean logic, using the five variables i, e, g, u, and t, where i is true if the given student is an ics major, e is true if the student is an engineering major, g is true if the student needs 161 to graduate this quarter, u is true if the student has enough units already, and t is true if the student is allowed to take 161.

    Your formula should be an expression of the form "t = ..." where the "..." is an expression which uses the and, or, and not operations to combine the values of the other four variables.

  2. Fill in the remaining blanks in the following truth table:

    xyzx v yy ^ z ~(y ^ z)(x v y) ^ ~(y ^ z)
    falsefalsefalsefalsefalsetruefalse
    falsefalsetrue
    falsetruefalse
    falsetruetrue
    truefalsefalse
    truefalsetrue
    truefalsefalse
    truefalsetrue

  3. Draw a boolean circuit which computes the value of the following boolean expression:
     
    (milk or sugar or lemon) and not (milk and lemon).
     
    Label the inputs to your circuit with the three variables "milk", "sugar", and "lemon".