CMI2016-B-4

Question

Let $\Sigma  = \{0, 1\}$. Let $A, \: B$ be arbitrary subsets of $\Sigma^\ast$. We define the following operations on such sets:

• $ A+B :=  \{ w \in \Sigma^\ast \mid w \in A \text{ or } w \in B \}$
• $A \cdot B  :=  \{ uv \in \Sigma^\ast \mid u \in A \text{ and } v \in B \} $
• $ 2A  :=  \{ ww \in \Sigma^\ast \mid w \in A \}$

Is it true that $(A+B) \cdot (A+B) = A \cdot A + B \cdot B +2(A \cdot B)$ for all choices of $A$ and $B$? If yes, give a proof. If not, provide suitable $A$ and $B$ for which this equation fails.

Answer 1

Comments

@soujanyareddy13 , Could you please ellaborate a little more ?

Answer 2

@soujanyareddy13 , Saw your answer. Coud you please ellaborate on that a little more ?

Can’t we treat this problem like digital logic ?

(A+B)(A+B) = ( A or B ) and ( A or B ) = A or B = A + B. – LHS.

For RHS : X.X = X and X.Y = 0 ( if X != Y ) --(1) ---- for this case LHS = RHS – the eqn will be true.

                                           = XY ( if X = Y ) --(2). --- for this case eqn is false – suitable counter example.

Thus in general the eqn does not hold.