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

Passo 1

O enunciado pede para mostrar que, para quaisquer linguagens A, B e C sobre o alfabeto V, vale a igualdade
A(B \cup C) \;=\; A\,B \;\cup\; A\,C.
O conteúdo envolvido é a definição de concatenação de linguagens e a propriedade distributiva da concatenação sobre a união.

Passo 2

Mostramos primeiro que
A(B \cup C)\;\subseteq\;A\,B\;\cup\;A\,C.
Seja x\in A(B\cup C). Pela definição de concatenação, existem u\in A e v\in B\cup C tais que x=uv. Como v\in B\cup C, ou v\in B ou v\in C.
  • Se v\in B, então x=uv\in A\,B.
  • Se v\in C, então x=uv\in A\,C.
    Em ambos os casos, x\in A\,B\cup A\,C. Logo
A(B \cup C)\subseteq A\,B\cup A\,C.

Passo 3

Agora mostramos que
A\,B\;\cup\;A\,C\;\subseteq\;A(B \cup C).
Seja x\in A\,B\cup A\,C. Então x\in A\,B ou x\in A\,C.
  • Se x\in A\,B, existem u\in A e v\in B com x=uv. Como v\in B\subseteq B\cup C, segue x\in A(B\cup C).
  • Se x\in A\,C, existem u\in A e v\in C com x=uv. Como v\in C\subseteq B\cup C, segue x\in A(B\cup C).
    Assim
A\,B\cup A\,C\subseteq A(B \cup C).

Passo 4

Pelas inclusões dos Passos 2 e 3, concluímos que
A(B \cup C) \;=\; A\,B \;\cup\; A\,C.

Resposta

A igualdade A(B \cup C) = A\,B \cup A\,C é verdadeira.

Exercícios de Livros Relacionados