Problem 1: (15 points)
Consider the Boolean algebra (B,+, *,' , 0, 1) represented by this Hasse diagram:
Give the tables of +, *, and '.
Problem 2: (2' points)
For any integer n > 1 let Dn be the set of positive divisors of n. Define , and ' on
Dn by = lcm (a, b) (that is, least common multiple of a and b), = gcd(a, b) (that
is, greatest common divisor of a and b), and a' = n/a. Define in Dn the relation : if
a) Show that if and only if a divides b .
b) Prove that is a partial order relation in Dn.
c) Draw the Hasse diagrams of D4, D6, D8 and D10.
d) Which of the following sets is a Boolean algebra : D4, D6, D8 and D10? Explain why.
For each Boolean algebra indicate what its 0 and 1 elements are.
Problem 3: (15 points)
Let be a Boolean algebra and let be the Boolean function such
a) Write f in disjunctive normal form and in conjunctive normal form.
b) Give the truth table of f' (the complement of f).
c) Give f' in disjunctive normal form and in conjunctive normal form.
Problem 4: (2' points)
Minimize each of the following Boolean expressions using Karnaugh maps. Show the
Problem 5: (15 points)
Let f and g be two Boolean functions of x, y, z, w where f(x, y, z,w) = 1 if and only
if at least two of x , y, z, w have value 1, and g(x, y, z,w) = 1 if and only if at most two of
x, y, z, w have value 1.
a) Give the truth tables of f and g.
b) Minimize f and g using Karnaugh maps
Problem 6: (15 points)
Let (B,+, *,' , 0, 1) be a Boolean algebra . Define as follows:
b) Express using the operation but without using +, *, or '.
c) Express x + y using the operation but without using +, *, or '.