ICS 1F, Homework 3 Solutions

  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.


    t = (i v e) ^ (g v ~u)

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

    xyzx v yy ^ z ~(y ^ z)(x v y) ^ ~(y ^ z)
    falsefalsetrue false false true false
    falsetruefalse true false true true
    falsetruetrue true true false false
    truefalsefalse true false true true
    truefalsetrue true false true true
    truetruefalse true false true true
    truetruetrue true true false false

  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".