Exercício 38:
Defina a união cupi=1^n ai e a interseção capi=1^n ai por recursão e demonstre as leis distributivas:
(i) .
(ii) .

Passo 1

O exercício trata de definir recursivamente a união cupi=1^n ai e a interseção capi=1^n ai, e em seguida provar por indução as duas leis distributivas: (i) a cap cupi=1^n ai=cupi=1^n(acap ai) e (ii) a cup capi=1^n ai=capi=1^n(acup ai). Vamos precisar da definição recursiva dessas operações e das leis de distributividade para dois conjuntos.

Passo 2

Definimos recursivamente:
cupi=1^1 ai = a1,
capi=1^1 ai = a1,
e para n+1:
cupi=1^n+1 ai = l(cupi=1^n air) cup an+1,
capi=1^n+1 ai = l(capi=1^n air) cap an+1

Passo 3

Antes da indução recordamos as leis de distributividade para três conjuntos quaisquer A,B,C:
Acap(Bcup C) = (Acap B)cup(Acap C),
Acup(Bcap C) = (Acup B)cap(Acup C)

Passo 4

Prova de (i) por indução sobre n:
— Base n=1: temos cupi=1^1 ai = a1, então
acapcupi=1^1 ai = acap a1 = cupi=1^1(acap ai)

Passo 5

— Passo indutivo: suponha que acapcupi=1^n ai = cupi=1^n(acap ai). Então
acapcupi=1^n+1 ai = acapl((cupi=1^n ai)cup an+1r) = (acapcupi=1^n ai)cup(acap an+1)
= l(cupi=1^n(acap ai)r) cup (acap an+1) = cupi=1^n+1(acap ai)

Passo 6

Prova de (ii) por indução sobre n:
— Base n=1: capi=1^1 ai = a1 e
acupcapi=1^1 ai = acup a1 = capi=1^1(acup ai)

Passo 7

— Passo indutivo: suponha acupcapi=1^n ai = capi=1^n(acup ai). Então
acupcapi=1^n+1 ai = acupl((capi=1^n ai)cap an+1r) = (acupcapi=1^n ai)cap(acup an+1)
= l(capi=1^n(acup ai)r) cap (acup an+1) = capi=1^n+1(acup ai)

Passo 8

Concluímos que ambas as leis se mantêm para todo n.

Resposta

Foram definidas as operações recursivamente e provadas por indução as igualdades (i) acapcupi=1^n ai = cupi=1^n(acap ai) e (ii) acupcapi=1^n ai = capi=1^n(acup ai) para todo n.

Exercícios relacionados