Question

Recall that, fixed a set U (which we call the universe of discourse), we have certain operations on subsets of U so that, for all A, B, C CU the following equivalences and equalities hold. >> AC BUC, ABCC CCA⇒B >> CnACB, A" = A, (AUB)* = A*n B', (An B)* = A*UB*. ACB →B'CA, You can answer just one of the following parts, not both. You can support your answer with drawings of Venn diagrams, but you need to give an argument according to the specifications for full credit. (a) Prove that for any given sets A, BCU, we have that B\A= (AB)* using only the above equations and equivalences. (Hint: Notice that two sets X, Y CU are equal if and only if, for every CCU, we have XCC YCC.) (b) Prove that for any given sets A, BCU, we have that B* A* = (AB)* using the definitions of the operations (). \, and in terms of the elements of U, A, and B.

Answer 1

(a) To prove that B\A = (AB)* using only the above equations and equivalences, we need to show that B\A is equivalent to (AB)*.

First, we will show that B\A is a subset of (AB)*.

Let x be an element of B\A. Then, x is in B and x is not in A. Therefore, x is in AB and not in A. This means that x is in (AB)*. Thus, we have shown that B\A is a subset of (AB)*.

Next, we will show that (AB)* is a subset of B\A.

Let x be an element of (AB)*. Then, x is in AB or x is not in AB.

If x is in AB, then x is in B and x is in A. Therefore, x is not in B\A.

If x is not in AB, then x is not in A or x is not in B. Therefore, x is not in A and x is in B. This means that x is in B\A.

Thus, we have shown that (AB)* is a subset of B\A.

Since we have shown that B\A is a subset of (AB)* and (AB)* is a subset of B\A, we can conclude that B\A = (AB)*.

(b) To prove that B* A* = (AB)*, we need to show that B* A* is a subset of (AB)* and (AB)* is a subset of B* A*.

First, we will show that B* A* is a subset of (AB)*.

Let x be an element of B* A*. Then, x is in (B*) and x is in (A*).

If x is in B*, then x is in B or x is not in B.

If x is in A*, then x is in A or x is not in A.

If x is in B and x is in A, then x is in AB.

If x is not in B and x is not in A, then x is not in AB.

If x is in B and x is not in A, then x is in B\A.

If x is not in B and x is in A, then x is in A\B.

Therefore, we have shown that x is in (AB)*.

Next