Agora é hora de revisar outra propriedade frequentemente usada na lógica proposicional, nomeadamente as provas das leis de DeMorgan de Distribuição para conjunção e disjunção. O uso dessas leis é comum na teoria dos conjuntos e, por extensão, permeia toda a matemática: desde a teoria das probabilidades, topologia e até tem presença na eletrônica e na programação. Como de costume, vamos detalhar as provas dessas leis usando as técnicas de dedução que obtivemos até agora.

Leis de DeMorgan

As leis de DeMorgan são um conjunto de equivalências que formalizam a distribuição das negações com conjunção e disjunção. Formalmente, são expressas através das equivalências:

\neg(\alpha \wedge \beta) \dashv \vdash (\neg\alpha \vee \neg \beta)

\neg(\alpha \vee \beta) \dashv \vdash (\neg\alpha \wedge \neg \beta)

Essas equivalências provadas podem ser obtidas sem a necessidade de fazer uma prova como a que fizemos até agora, pois podemos nos valer das definições que relacionam conjunções com disjunções e um pouco de jogo com a equivalência da dupla negação e substituições. Da definição de conjunção, segue-se que:

(A \wedge B):= \neg(\neg A \vee \neg B)

Aplicando uma negação a ambos os lados dessa expressão, temos que

\neg(A \wedge B):= \neg\neg(\neg A \vee \neg B)

Então, pela equivalência da dupla negação, obtemos

\neg(A \wedge B)\dashv \vdash (\neg A \vee \neg B)

Finalmente, substituindo A=\alpha e B=\beta, obtemos a primeira equivalência de DeMorgan

\boxed{\neg(\alpha \wedge \beta) \dashv \vdash (\neg\alpha \vee \neg \beta)}

Para obter a segunda, podemos continuar jogando com a expressão que tínhamos antes de fazer a substituição, adicionando uma negação a ambos os lados novamente, obtendo

\neg\neg(A \wedge B)\dashv \vdash \neg(\neg A \vee \neg B)

E então, pela dupla negação, obtemos

\neg(\neg A \vee \neg B) \dashv \vdash (A \wedge B)

Se nesta última expressão substituirmos A=\neg\alpha e B=\neg\beta, chegaremos a

\neg(\neg \neg\alpha \vee \neg \neg\beta) \dashv \vdash (\neg\alpha \wedge \neg\beta)

Que, devido à equivalência da dupla negação, conduzirá à segunda equivalência de DeMorgan

\boxed{\neg( \alpha \vee \beta) \dashv \vdash (\neg\alpha \wedge \neg\beta)}

Além disso, de forma completamente análoga, podemos obter algumas formas adicionais, que são apenas variações das que acabamos de revisar

\neg(\neg\alpha \wedge \beta) \dashv \vdash (\alpha \vee \neg \beta)

\neg(\neg\alpha \vee \beta) \dashv \vdash (\alpha \wedge \neg \beta)

\neg(\alpha \wedge \neg\beta) \dashv \vdash (\neg\alpha \vee \beta)

\neg(\alpha \vee \neg\beta) \dashv \vdash (\neg\alpha \wedge \beta)

Regras de Distributividade Entre Conjunção e Disjunção

Como o nome sugere, essas regras nos permitem distribuir os conjuntos e disjunções dentro de uma expressão. Essas leis são resumidas nas seguintes duas equivalências:

Como já vimos até agora, embora este seja um resultado conhecido, sua prova não é nada trivial. Embora, para completar essa prova, deve-se raciocinar em ambas as direções, desta vez darei a prova em apenas um sentido; a prova no sentido reverso será deixada como um exercício para o leitor.

∧ – Distributividade

Para provar que \{(\alpha \wedge(\beta \vee\gamma))\}\vdash((\alpha \wedge \beta)\vee(\alpha \wedge \gamma)) ocorre, temos o seguinte raciocínio.

Com isso, fica provado que \{(\alpha \wedge(\beta \vee\gamma))\}\vdash((\alpha \wedge \beta)\vee(\alpha \wedge \gamma)). Agora é a sua vez de testar o que aprendeu e se aventurar a provar por conta própria que \{((\alpha \wedge \beta)\vee(\alpha \wedge \gamma))\}\vdash (\alpha \wedge(\beta \vee\gamma)).

∨ – Distributividade

A prova de \{(\alpha \vee(\beta \wedge\gamma))\}\vdash((\alpha \vee \beta)\wedge(\alpha \vee \gamma)) é obtida a partir do seguinte raciocínio:

Esta é metade da prova; agora, falta a prova reversa, mas isso fica como exercício para o leitor :3

Considerações Finais

Com esta revisão das provas das leis de De Morgan de distribuição de conjunção e disjunção, podemos concluir nosso estudo sobre técnicas de dedução na lógica proposicional e como elas convergem na prova das leis da lógica clássica, ou pelo menos as mais importantes.

É importante completar todas as provas propostas para reforçar o conhecimento dessas técnicas. Para tornar isso um pouco menos complicado, é muito conveniente comparar as provas em busca de semelhanças, pois é possível que a estratégia que funcionou em uma prova funcione com algumas variações para alcançar outra.

Uma última coisa que vale a pena notar é a ordem que escolhi para desenvolver essas provas. Você deve notar que cada prova usou os resultados de algumas das provas anteriores. Escolhi essa ordem porque pessoalmente achei mais fácil dessa forma. Um bom exercício para melhorar suas habilidades nessas coisas é perguntar a si mesmo: “Posso construir essas provas em uma ordem diferente seguindo essa mesma metodologia?” Recomendo fortemente que você tente obter essas provas em uma ordem diferente e use cada prova para obter as seguintes, porque, mesmo que você não consiga, a prática que surge da tentativa lhe dará uma melhor compreensão das provas e dos métodos usados na lógica.