Exercício 1.15. Demonstre a segunda lei de De Morgan.
Passo 1
O enunciado pede para demonstrar a segunda lei de De Morgan. Vou provar explicitamente a identidade a seguir (vou escrever qual das duas leis estou provando):
onde
e
são conjuntos qualquer e o complemento
é tomado em relação a um universo fixo
.
Informações dadas:
Informações dadas:
- Existem dois conjuntos
e contidos num universo . - A operação
é interseção, é união e é complemento relativo a .
O objetivo é mostrar que os dois conjuntos acima são iguais.
Passo 2
Estratégia de prova (explicada passo a passo e bem didática):
- Para provar que dois conjuntos
e são iguais normalmente mostramos duas inclusões: -
. -
.
Se ambas valem, então.
-
- Vou aplicar isso com
e .
Antes de começar, lembro as definições elementares que vamos usar: - Definição de complemento:
. - Definição de interseção:
. - Definição de união:
. - Observação lógica útil (uma regra básica de lógica): a negação de uma conjunção é uma disjunção das negações; em símbolos lógicos,
Intuição: se “não (P e Q)” é verdade, então pelo menos um entre P e Q é falso.
Passo 3
Prova da inclusão
:
- Pegue um elemento arbitrário
. - Pela definição de complemento isso significa que
. - Pela definição de interseção, a afirmação
é a negação da afirmação " e ". Em notação lógica: - Usando a equivalência lógica citada no Passo 2, essa negação é equivalente a
- Mas
significa e significa . Logo temos isto é, - Como
foi um elemento arbitrário de , concluímos que
Passo 4
Prova da inclusão
:
- Pegue um elemento arbitrário
. - Pela definição de união, isso significa que
ou . - Reescrevendo em termos de não-pertinência:
ou . Em lógica: - A partir daqui usamos a equivalência lógica inversa do Passo 2: se
é verdadeiro então é verdadeiro; isto é, - Essa última afirmação é exatamente
, isto é . - Como
foi escolhido arbitrariamente em , temos
Passo 5
Conclusão final (juntando as inclusões) e comentário didático:
- Das inclusões do Passo 3 e do Passo 4 obtemos
- Portanto, por dupla inclusão,
- Intuição prática: o complemento da interseção são os elementos que falham em pertencer a pelo menos um dos conjuntos; por isso pertencem ao complemento de
ou ao complemento de . - Exemplo rápido para fixar (pode fazer na prova): tome
, , . Então e conferindo a igualdade.