ELEN500 Homework 3 Solution

1. Do problem 18 on page 112 at the end of Chapter 3.
a. Is the lattice complemented?
NO. Counter-example: There does not exist a x such that ax=0 and a+x=1.
b. Is the lattice distributed?
NO. Counter-example: d(b+f)=d 1=d but db+df = 1+1=1
c. Is the lattice a Boolean Algebra?
NO. It must be both complemented and distributed to be a Boolean Algebra.

2. Do problem 45 parts a,b &c on pages 120-121 at the end of Chapter 3 Simplify, when possible, the following formulae by applying the consensus theorem.
a. abc'd + b'c'e' + ac'de'
Form the mapping x=b; y= ac'd; and z=c'e' then apply consensus to get bac'd + b'c'e'.
b. wxy' +x'yz +wz
No simplification possible using the consensus theorem.
c. abe + a'cd' + bce + bde
Form the mapping x = a+d; y= be; and z=c then apply the consensus theorem to get abe + a'cd' +bde

3. Do problem 57 on page 124 at the end of Chapter 3 Find the minterm and maxterm canonical forms for the following functions by repeated application of the expansion theorem. Assume B = {0, a, b, 1}.
a. f(x,y) = x(y+x') + x'y'


x   y   f(x,y)
0   0   1
0   1   0
1   0   0
1   1   1

Minterm canonical form:  f(x,y) = x'y' + xy
Maxterm canonical form:  f(x,y) = (1 + x + y) (0+x + y')(0+x'+y)(1+x + y)
= (x + y')(x'+y) since 1+z = 1 for every z in B.

b. f(x,y)= ax + by


x   y   f(x,y)
0   0   0
0   1   b
1   0   a
1   1   a+b

Minterm canonical form: f(x,y) = bx'y + axy' +(a+b)xy
Maxterm canonical form:  f(x,y) = (x+y)(b+x+y')(a+x'+y)(a+b+x'+y')

c. f(x,y,z) = axy +a'(y+z') + xz

x   y  z   f(x,y,z)
0   0   0   a'
0   0   1   0
0   1   0   a'
0   1   1   a'
1   0   0   a'
1   0   1   1
1   1   0   1
1   1   1   1

Minterm Canonical Form:  f(x,y,z)= a'x'y'z' + a'x'yz' + a'x'yz + a'xy'z' +
xy'z + xyz' + xyz
Maxterm Canonical Form:  
f(x,y,z) =
(a'+x+y+z)(0+x+y+z')(a'+x+y'+z)(a'+x+y'+z')(a'+x'+y+z)(1+x'+y+z')(1+x'+y'+z)(1+x'+y'+z')
             = (a'+x+y+z)( x+y+z')(a'+x+y'+z)(a'+x+y'+z')(a'+x'+y+z) since
w+1=1 for every w in B.

4. For the incompletely specified switching function F(x,y,z) represented by the interval: [xy, x + yz]
4a. find the truth table

4b. find the triplet f, d, and r.

f = L = xy'
r=U' = (x+yz')' = x'(y'+z) = x'y'+x'z
d = y(z' +x) = yz' + xy