Demonstre ou mostre que é falsa cada uma destas afirmações para os subconjuntos A, B e C de V^{*}, em que V é um alfabeto.
b) A(B \cap C)=A B \cap A C

Passo 1

Resumo do enunciado e conceito
Temos três linguagens A,B,C\subseteq V^{*}. Queremos ver se vale
A\,(B\cap C)\;=\;A\,B\;\cap\;A\,C.
Aqui a concatenação de linguagens é dada por
X\,Y=\{\,xy\mid x\in X,\;y\in Y\},
e a interseção é a usual de conjuntos.

Passo 2

Inclusão A(B\cap C)\subseteq AB\cap AC
Se w\in A\,(B\cap C), então existem a\in A e x\in B\cap C tais que w=ax. Como x\in B e x\in C, segue que w\in A\,B e também w\in A\,C. Logo
w\in A\,B\;\cap\;A\,C
e, portanto,
A\,(B\cap C)\;\subseteq\;A\,B\;\cap\;A\,C.

Passo 3

Contraexemplo para a inclusão inversa
Vamos ver que nem sempre AB\cap AC\subseteq A(B\cap C).
Escolhemos
V=\{0,1\},\quad A=\{0,01\},\quad B=\{1\},\quad C=\{11\}.
Então
B\cap C=\emptyset \quad\Longrightarrow\quad A\,(B\cap C)=A\,\emptyset=\emptyset.
Por outro lado,
A\,B=\{\,01,011\}, \quad A\,C=\{\,011,0111\},
de modo que
A\,B\;\cap\;A\,C=\{\,011\}\neq\emptyset.
O elemento w=011 pertence a AB\cap AC mas não a A(B\cap C), pois este último é vazio.

Resposta

A igualdade
A\,(B\cap C)=A\,B\;\cap\;A\,C
é em geral falsa. O contraexemplo acima mostra que a inclusão inversa não vale.

Exercícios de Livros Relacionados