Exercício 38:
Defina a união
e a interseção
por recursão e demonstre as leis distributivas:
(i)
.
(ii)
.
Defina a união
(i)
(ii)
Passo 1
O exercício trata de definir recursivamente a união
e a interseção
, e em seguida provar por indução as duas leis distributivas: (i)
e (ii)
. Vamos precisar da definição recursiva dessas operações e das leis de distributividade para dois conjuntos.
Passo 2
Definimos recursivamente:
e para
Passo 3
Antes da indução recordamos as leis de distributividade para três conjuntos quaisquer
:
Passo 4
Prova de (i) por indução sobre
:
— Base : temos
, então
— Base
Passo 5
— Passo indutivo: suponha que
. Então
Passo 6
Prova de (ii) por indução sobre
:
— Base :
e
— Base
Passo 7
— Passo indutivo: suponha
. Então
Passo 8
Concluímos que ambas as leis se mantêm para todo
.
Resposta
Foram definidas as operações recursivamente e provadas por indução as igualdades (i)
e (ii)
para todo
.