Week 5 Individual Assignment
Chapter 15
Supplementary Exercises, problems 1, 5, & 6 1. Let n ≥ 2. If xi is a Boolean variable for all 1 ≤ i ≤ n, prove that
a) (x1 + x2 + ・ ・ ・ + xn) _ x1x2 ・ ・ ・ xn

Assume the result for n _ k (≥ 2) and consider the case of n _ k + 1.

b) (x1x2 ・ ・ ・ xn) _ x1 + x2 + ・ ・ ・ + xn
Follows from part (a) by duality. 5. Let_be a Boolean algebra that is partially ordered by≤. If x, y, z ∈ _, prove that x + y ≤ z if and only if x ≤ z and y ≤ z.
If x ≤ z and y ≤ z, then from Exercise 6(b) of Section 15.4 we have x + y ≤ z + z. z + z _ z. Conversely, suppose that x + y ≤ z.We find that x ≤ x + y, because x(x + y) _ x + xy _ x.
Since x ≤ x + y and x + y ≤ z, we have x ≤ z, because a partial order is transitive. 6. State and prove the dual of the result in Exercise 5.
Exercise 15.1, problems 1, 2, 11, 12, 14, & 15

1. Find the value of each of the following Boolean expressions if the values of the Boolean variables w, x, y, and z are 1, 1, 0, and 0, respectively.
a) xy + x y = 1 b) w + xy = 1
c) wx + y + yz = 1
d) (wx + yz) + wy + (w + y)(x + y) = 1

2. Let w, x, and y be Boolean variables where the value of x is 1. For each of the following Boolean expressions, determine, if possible, the value of the expression. If you cannot determine the value of the expression, then find the number of assignments of values for w and y that will result in the value 1 for the expression.
a) x + xy + w
b) xy + w
c) xy + xw
d) xy + w

11. Simplify the following Boolean expressions. a) xy + (x + y)z + y = y + x b) x + y + (x + y + z) = x+y c) yz + wx + z + [wz(xy + wz)] = wx+z

12. Find the values of the Boolean variables w, x, y, z that satisfy the following system of simultaneous (Boolean) equations. x + xy _ 0 xy _ xz xy + x z + zw _ zw

x+x ̅y=0→(x+x ̅ )(x+y)=0 Distributive Law of + over 
1(x+y)=0 Inverse Law of + x+y =0 Identity law of  x =0 and y = 0 Property of +
Since x ̅y=x ̅z→0 ̅0=0 ̅z→10=1z→0=1z→0=z
Then z =0
SInce: x = y = z = 0 and x ̅y+x ̅z ̅+zw=z ̅w
0 ̅0+0 ̅0 ̅+0w=0 ̅w→10+11+0=1w
0+1+0=w
[0+1]+0=w
1+0=w
1=w
Solution: x=y=z=0 , w =1

14. Let f, g: Bn →B. Define the relation “≤” on Fn, the set of all Boolean functions of n variables, by f ≤ g if the value of g is 1 at least whenever the value of f is 1. a) Prove that this relation is a partial order on Fn. b) Prove that fg ≤ f and f ≤ f + g. c) For n _ 2, draw the Hasse diagram for the 16 functions in F2. Where are the minterms and maxterms located in the diagram? Compare this diagram with that for the power set of {a, b, c, d} partially ordered under the subset relation.

15. Define the closed binary operation⊕(Exclusive Or) on Fn, the set of all Boolean functions on n variables, by f ⊕ g _ f g + fg, where f, g: Bn →B.
a) Determine f ⊕ f , f ⊕ f , f ⊕ 1, and f ⊕ 0. f ⊕ f _ 0; f ⊕ f _ 1; f ⊕ 1 _ f ; f ⊕ 0 _ f b) Prove or disprove each of the following. i) f ⊕ g _ 0⇒f _ g f ⊕ g _ 0⇐⇒f g + fg _ 0⇒f g _ fg _ 0. [f _ 1 and f g _ 0]⇒g _ 1.
[f _ 0 and fg _ 0]⇒g _ 0. f _ g

ii) f ⊕ (g ⊕ h) _ (f ⊕ g) ⊕ h

iii) f ⊕ g _ f ⊕ g f ⊕ g _ f g + f g _ fg + f g _ f g + fg _ f ⊕ g

iv) f ⊕ gh _ (f ⊕ g)(f ⊕ h)
Not True

v) f (g ⊕ h) _ fg ⊕ fh fg ⊕ fh _ fgf h + fgfh _ (f + g)f h + fg(f + h) _ ff h + f gh + ffg + fgh _ f gh + fgh _ f (gh + gh) _ f (g ⊕ h)

vi) (f ⊕ g) _ f ⊕ g _ f ⊕ g f ⊕ g _ f g + fg _ fg + f g _ f ⊕ g f ⊕ g _ f g + fg _ (f + g)(f + g) _ f g + fg _ f ⊕ g

vii) f ⊕ g _ f ⊕ h⇒g _ h

4. a) Find the fundamental conjunction made up from the variables w, x, y, z, or their complements, where the value of the conjunction is 1 precisely when i) w _ x _ 0, y _ z _ 1. ii) w _ 0, x _ 1, y _ 1, z _ 0. iii) w _ 0, x _ y _ z _ 1. iv) w _ x _ y _ z _ 0.
b) Answer part (a) this time for fundamental disjunctions, instead of fundamental conjunctions, where the value of each fundamental disjunction is 0 precisely for the stated values of w, x, y, z.

5. Suppose that f : B3 →B is defined by f (x, y, z) _ (x + y) + (xz).
a) Determine the d.n.f. and c.n.f. for f .
d.n.f. xyz + xyz + xy z + xyz + xyz
c.n.f. (x + y + z)(x + y + z)(x + y + z)

b) Write f as a sum of minterms and as a product of maxterms
(utilizing binary labels). 8. Let f : B4 →B. Find the disjunctive normal form for f if
a) f
−1(1) _ {0101 (that is, w _ 0, x _ 1, y _ 0, z _ 1),
0110, 1000, 1011}.
b) f
−1(0) _ {0000, 0001, 0010, 0100, 1000, 1001, 0110}.

9. Let Bn →B. If the d.n.f. of f has m fundamental conjunctions and its c.n.f.

m + k _ 2n