CSE140 Homework 1 Solutions

Craig Mautner (cmautner@cs.ucsd.edu)

Problem 3.7a
Problem 3.7b

Problem 3.10a
Problem 3.10b
Problem 3.10c
Problem 3.10d

Problem 4.6a
Problem 4.6b
Problem 4.6c
Problem 4.6d

Problem 3.7a)

Rewrite as Canonical Sum of Products

F = x ^ y ^ z
  = (x'y + xy') ^ z
  = (x'y + xy')'z + (x'y + xy')z'
  = (x'y)'(xy')'z + (x'y + xy')z'
  = (x + y')(xy')'z + (x'y + xy')z'
  = (x + y')(x' + y)z + (x'y + xy')z'
  = (xx' + xy + x'y' + y'y)z + (x'y + xy')z'
  = (xy + x'y')z + (x'y + xy')z'
  = xyz + x'y'z + (x'y + xy')z'
  = xyz + x'y'z + x'yz' + xy'z'
Truth Table of above:

Rewrite as Canonical Product of Sums

F = xyz + x'y'z + x'yz' + xy'z' (from above)
  =  A0 +  A1   +  A2   +  A3
treat (A0 + A1 + A2) as one term and use the fact that
(a + bcd) = (a + b)(a + c)(a + d) to 
distribute A3 across (A0 + A1 + A2)
F = (A0 + A1 + A2 + x)( A0 + A1 + A2 + y')( A0 + A1 + A2 + z')
  = B0B1B2
B0 = (A0 + A1 + A2+ x) = (x + A0 + A1 + A2)
distribute A2 across (x + A0 + A1)
   = (x + A0 + A1 + x')(x + A0 + A1 + y)(x + A0 + A1 + z')
   = (1)(x + A0 + A1 + y)(x + A0 + A1 + z')
   = C0C1
C0 = (x + A0 + A1 + y) = (x + y + A0 + A1)
distribute A1 across (x + y + A0)
   = (x + y + A0 + x')(x + y + A0 + y')(x + y + A0 + z)
   = (x + y + A0 + z)
distribute A0 across (x + y + z)
   = (x + y + z + x)(x + y + z + y)(x + y + z + z)
   = (x + y + z)
C1 = (x + A0 + A1 + z') = (x + z' + A0 + A1)
distribute A1 across (x + z' + A0)
   = (x + z' + A0 + x')(x + z' + A0 + y')(x + z' + A0 + z)
   = (x + z' + A0 + y')
distribute A0 across (x + y' + z')
   = (x + y' + z' + x)(x + y' + z' + y)(x + y' + z' + z)
   = (x + y' + z')
B0 = C0C1 = (x + y + z)(x + y' + z')
B1 = (A0 + A1 + A2+ y') = (y' + A0 + A1 + A2)
distribute A2 across (y' + A0 + A1)
   = (y' + A0 + A1 + x')(y' + A0 + A1 + y)(y' + A0 + A1 + z')
   = (y' + A0 + A1 + x')(1)(y' + A0 + A1 + z')
   = D0D1
D0 = (y' + A0 + A1 + x') = (x' + y' + A1 + A0)
distribute A0 across (x' + y' + A1) 
   = (x' + y' + A1 + x)(x' + y' + A1 + y)(x' + y' + A1 + z)
   = (x' + y' + A1 + z)
distribute A1 across (x' + y' + z)
   = (x' + y' + z + x')(x' + y' + z + y')(x' + y' + z + z)
   = (x' + y' + z)
D1 = (y' + A0 + A1 + z') = (y' + z' + A0 + A1)
distribute A0 across (y' + z' + A1)
   = (y' + z' + A1 + x)(y' + z' + A1 + y)(y' + z' + A1 + z)
   = (y' + z' + A1 + x)
distribute A1 across (x + y' + z')
   = (x + y' + z' + x')(x + y' + z' + y')(x + y' + z' + z)
   = (x + y' + z')
B1 = D0D1 = (x' + y' + z)(x + y' + z')
B2 = (A0 + A1 + A2+ z') = (z' + A0 + A1 + A2)
distribute A0 across (z' + A1 + A2)
   = (z' + A1 + A2 + x)(z' + A1 + A2 + y)(z' + A1 + A2 + z)
   = (z' + A1 + A2 + x)(z' + A1 + A2 + y)(1)
   = E0E1
E0 = (z' + A1 + A2 + x) = (x + z' + A1 + A2)
distribute A1 across (x + z' + A2) 
   = (x + z' + A2 + x')(x + z' + A2 + y')(x + z' + A2 + z)
   = (x + z' + A2 + y')
distribute A2 across (x + y' + z')
   = (x + y' + z' + x')(x + y' + z' + y)(x + y' + z' + z')
   = (x + y' + z')
E1 = (z' + A1 + A2 + y) = (y + z' + A1 + A2)
distribute A1 across (y + z' + A2)
   = (y + z' + A2 + x')(y + z' + A2 + y')(y + z' + A2 + z)
   = (y + z' + A2 + x')
distribute A2 across (x' + y + z')
   = (x' + y + z' + x')(x' + y + z' + y)(x' + y + z' + z')
   = (x' + y + z')
B2 = E0E1 = (x + y' + z')(x' + y + z')
F = B0B1B2
  = (x + y + z)(x + y' + z')(x' + y' + z)(x + y' + z')
    (x + y' + z')(x' + y + z')
  = (x + y + z)(x + y' + z')(x' + y' + z)(x' + y + z')

Problem 3.7b)

F = zw' + xy'w' + xy'z

Rewrite as Canonical Sum of Products

F = zw' + xy'w' + xy'z
  = zw'(x + x')(y + y') + xy'w'(z + z') + xy'z(w + w')
  = xyzw' + x'yzw' + xy'zw' + x'y'zw' + xy'w'z + xy'w'z' + 
    xy'zw + xy'zw'
remove duplicates
  = xyzw' + x'yzw' + xy'zw' + x'y'zw' + xy'z'w' + xy'zw
x y z w | F
0 0 0 0 | 0
0 0 0 1 | 0
0 0 1 0 | 1
0 0 1 1 | 0
0 1 0 0 | 0
0 1 0 1 | 0
0 1 1 0 | 1
0 1 1 1 | 0
1 0 0 0 | 1
1 0 0 1 | 0
1 0 1 0 | 1
1 0 1 1 | 1
1 1 0 0 | 0
1 1 0 1 | 0
1 1 1 0 | 1
1 1 1 1 | 0

Rewrite as Canonical Products of Sum

F = zw' + xy'w' + xy'z
  = A0 + A1 + A2
distribute A2 across (A0 + A1)
  = (zw' + xy'w' + x)(zw' + xy'w' + y')(zw' + xy'w' + z)
  = B0B1B2
B0 = (zw' + xy'w' + x) = (x + zw' + xy'w')
distribute xy'w' across (x + zw')
   = (x + zw' + x)(x + zw' + y')(x + zw' + w')
   = (x + zw')(x + y' + zw')(x + w')
   = (x + z)(x + w')(x + y' + zw')(x + w')
   = (x + z)(x + w')(x + y' + zw')
   = (x + z)(x + w')(x + y' + z)(x + y' + w')
   = (x + z)(x + w') 
B1 = (zw' + xy'w' + y')
   = (y' + zw' + x) (y' + zw' + y') (y' + zw' + w')
   = (y' + z + x)(y' + w' + x)(y' + zw')(y' + w')
   = (y' + z + x)(y' + zw')(y' + w')
   = (y' + z + x)(y' + z)(y' + w')(y' + w')
   = (y' + z)(y' + w')
B2 = (zw' + xy'w' + z)
   = (z + xy'w')
   = (z + x)(z + y')(z + w')
F = B0B1B2
  = (x + z)(x + w')(y' + z)(y' + w')(z + x)(z + y')(z + w')
  = (x + z)(x + w')(y' + z)(y' + w')(z + w')
  = (x + y + z + w) (x + y + z + w') (x + y' + z + w)(x + y' + z + w')(x + w')(y' + z)(y' + w')(z + w')
  = (x + y + z + w) (x + w')(y' + z)(y' + w')(z + w')
  = (x + y + z + w) (x + y + z + w') (x + y + z' + w') (x + y' + z + w') (x + y' + z' + w')(y' + z)
      (y' + w')(z + w')
  = (x + y + z + w) (x + y + z' + w') (y' + z)(y' + w')(z + w')
  = (x + y + z + w) (x + y + z' + w') (x + y' + z + w) 
      (x + y' + z + w') (x' + y' + z + w) (x' + y' + z + w')
      (y' + w')(z + w')
  = (x + y + z + w) (x + y + z' + w') (x + y' + z + w) 
      (x' + y' + z + w) (y' + w')(z + w')
  = (x + y + z + w) (x + y + z' + w') (x + y' + z + w) 
      (x' + y' + z + w) (x + y' + z + w') (x + y' + z' + w') 
      (x' + y' + z + w') (x' + y' + z' + w')(z + w')
  = (x + y + z + w) (x + y + z' + w') (x + y' + z + w) 
      (x' + y' + z + w) (x + y' + z' + w') (x' + y' + z' + w')
      (z + w')
  = (x + y + z + w) (x + y + z' + w') (x + y' + z + w) 
      (x' + y' + z + w) (x + y' + z' + w') (x' + y' + z' + w') 
      (x + y + z + w') (x + y' + z + w') (x' + y + z + w') 
      (x' + y' + z + w')

Problem 3.10a)

Minimize 
        F = x'y' + xy + xy'
          = (x' + x)y' + xy
          = y' + xy
          = (y' + x)(y' + y)
          = (y' + x)

Problem 3.10b)

Minimize 
        F = (x + y)(x + y')
          = x + xy + xy' + yy'
          = x(1 + y + y') + 0
          = x

Problem 3.10c)

Minimize 
        F = x'y' + x'y + xz
          = x'(y' + y) + xz
          = x' + xz
          = (x' + x)(x' + z)
          = x' + z

Problem 3.10d)

Minimize 
        F = y'z' + x'y' + x'z + yz'
          = (y' + y)z' + x'y' + x'z
          = z' + x'y' + x'z
          = (z' + x')(z' + z) + x'y'
          = (z' + x') + x'y'
          = z' + x'(1 + y')
          = z' + x'

Problem 4.6a)

F = w'x' + w'xy + wx + wx'y' + xy

F = wx + w'y + x'y'
F = (w + x' + y)(x + y' + w')

Problem 4.6b)

F = yz + w'z' + wy'z

F = w'z' + wz + yz OR
  = w'z' + wz + w'y
F = (w' + z)(w + y + z')

Problem 4.6c)

F = x'y'z' + wy'z + xyz + w'yz'

F = x'y'z' + wy'z + xyz + w'yz'
F = wx'y' + wxz + w'xy + w'x'z'
F = (w + x' + y)(w + x + z')(w' + x + y')(w' + x' + z)
F = (x' + y' + z')(w + y + z')(x + y' + z')(w' + y' + z)

Problem 4.6d)

F = wy'z' + wx'y' + w'y + w'x'y'z + wxyz'

F = wy'z' + x'y'z + w'y + xyz'
F = wx'y' + w'x'z' + w'y + wxz'
F = (w + y + z)(x' + y + z')(w' + y' + z')(w' + x + y')
F = (w + y + z)(w + x' + y)(w' + x' + z')(w' + x + y')