MTH/221

Week Five Individual Assignment

Supplementary Exercise (Problem 1):

1. Let n≥2.If x_i is a Boolean variable for all 1≤i≤n, prove that

((x_1+x_2…+x_n)) ̅=(x_1 ) ̅|(x_2 ) ̅…(x_n ) ̅

When n=2,x_1+x_2 denotes the Boolean sum of x_1 and x_2. For n≥2, we define x_1+x_2+⋯+x_n+x_(n+1) recursively by (x_1+x_2+⋯+x_n )+x_(n+1). For n=2,(x_1+x_2 ) ̅=(x_1 ) ̅(x_2 ) ̅ is true, for this is one of the DeMorgan Laws. Assume the result for n=k(≥2) and consider the case of n=k+1.((x_1+x_2+⋯+x_k+x_(k+1))) ̅=((x_1+x_2+⋯+x_k )+x_(k+1) ) ̅=((x_1+x_2+⋯+x_k)) ̅*(x_(k+1) ) ̅=(x_1 ) ̅(x_2 ) ̅…(x_k ) ̅ (x_(k+1) ) ̅. Consequently, the result follows for all n≥2 by the Principle of Mathematical Induction.

((x_1 x_2…x_n )=) ̅(x_1 ) ̅+(x_2 ) ̅+⋯+(x_n ) ̅

The answer to this formula follows from part (a) from duality, you can see that the formula in (b) is a mirror-image (reversed) from part (a).

Supplementary Exercise (Problem 5):

5. Let B be a Boolean algebra that is partially ordered by ≤. If x,y,z∈B, prove that x+y≤z if and only if x≤z and y≤z.

Proof: If x≤z and y≤z then from Exercise 6(b) of Section 15.4 we have x+y≤z+z, and by the indempotent law we have z+z=z. Conversely, suppose that x+y≤z. We find that x≤x+y,because x(x+y)=x+xy (by the indempotent law)=x (by the absorption law). Since x≤x+y and x+y≤z we have x≤z, because a partial order is transitive. (The proof that y≤z follows in a similar way.)

Supplementary Exercise (Problem 6):

6. State and prove the dual of the result in Exercise 5.

Statement: Let B be a Boolean algebra partially ordered by ≤. If x,y,z∈B, then xy≥z if and only if x≥z and y≥z.

Proof: If x≥z and y≥z, then from Exercise 6(a) of Section 15.4 we have xy≥zz. The result now follows from the indempotent law, because zz=z. Conversely, suppose that xy≥z. We claim that x≥xy. This follows because (xy)x=x(yx)=x(xy)=(xx)y=xy. Since ≤ is transitive, x≥xy and xy≥z⇒x≥z. (The proof that y≥z follows in a similar manner.)

Exercise 15.1 (Problem...