Saltar para o conteúdo
Topos Uranos
Português

Leis de De Morgan e leis distributivas

Resumo

Esta aula encerra a unidade de dedução com duas famílias de equivalências que toda a matemática usa: as leis de De Morgan, que dizem como a negação atravessa uma conjunção ou uma disjunção, e as leis distributivas, que dizem como uma conjunção se distribui sobre uma disjunção e uma disjunção sobre uma conjunção. Antes de demonstrá-las, esclarece-se uma distinção da qual dependem: duas expressões que designam a mesma cadeia podem ser postas uma no lugar da outra sem mais, porque são a mesma fórmula; duas fórmulas apenas equivalentes, por outro lado, só podem ser substituídas uma pela outra dentro de outra fórmula por meio da substituição de equivalentes, camada por camada. Com essa precaução, demonstram-se por dedução as duas leis de De Morgan, suas variantes (entre elas, a negação de uma implicação) e as duas leis distributivas, cada uma em seus dois sentidos. Os problemas as usam para obter a idempotência, a absorção e a associatividade, formas normais simples e deduções que combinam De Morgan com a contraposição.

Objetivos de aprendizagem

  1. Distinguir a identidade de cadeias, que permite substituir uma abreviatura por seu desdobramento em qualquer lugar, da equivalência demonstrável, que só permite substituir dentro de uma fórmula por meio da substituição de equivalentes, e encadear equivalências em uma dedução.
  2. Demonstrar por dedução as duas leis de De Morgan e suas variantes, incluída a negação de uma implicação, e reconhecer nelas o papel da regra da substituição da dupla negação.
  3. Demonstrar nos dois sentidos a distributividade da conjunção sobre a disjunção e da disjunção sobre a conjunção, escolhendo em cada caso a prova por casos adequada.
  4. Transformar fórmulas em formas normais simples por meio de uma cadeia de equivalências justificada passo a passo, e obter por dedução as leis de idempotência, absorção e associatividade.
  5. Construir deduções com premissas que combinem as leis de De Morgan com a contraposição e com as regras de introdução e de eliminação dos conectivos.

As aulas anteriores desta unidade construíram, uma sobre a outra, as ferramentas da dedução: o sistema de axiomas e o modus ponens, as quatro técnicas básicas e a substituição da dupla negação, as simetrias dos conectivos e as técnicas da lógica clássica. Esta aula não acrescenta nenhuma regra nova; põe-nas para trabalhar juntas. Se isso é assim, seu interesse não está tanto nos enunciados, que talvez já se conheçam de outros cursos, quanto no modo de obtê-los: cada linha deve justificar-se por um axioma, uma premissa, uma definição, uma das duas regras primitivas ou um resultado já demonstrado, e nenhuma pode apoiar-se no que “parece evidente”.

O que se usa e como se encadeia

Da aula sobre sistemas dedutivos formais tomam-se os axiomas A1, A2 e A3 de Łukasiewicz, o modus ponens (MP), também com premissas, a reflexividade (Refl: se φ∈Γ\varphi \in \Gamma, então Γ⊢φ\Gamma \vdash \varphi), a monotonicidade (Mon), o corte (Corte: se Γ⊢φi\Gamma \vdash \varphi_i para cada ii e Γ∪{φ1,…,φn}⊢ψ\Gamma \cup \{\varphi_1, \ldots, \varphi_n\} \vdash \psi, então Γ⊢ψ\Gamma \vdash \psi), o teorema da dedução (TD) e a equivalência demonstrável (φ⊣⊢ψ\varphi \dashv\vdash \psi se {φ}⊢ψ\{\varphi\} \vdash \psi e {ψ}⊢φ\{\psi\} \vdash \varphi), com suas propriedades: é reflexiva, simétrica e transitiva, e, se φ⊣⊢ψ\varphi \dashv\vdash \psi, então Γ⊢φ\Gamma \vdash \varphi se e somente se Γ⊢ψ\Gamma \vdash \psi. Da aula sobre as quatro técnicas de dedução, a dupla negação (DN: φ⊣⊢¬¬φ\varphi \dashv\vdash \neg\neg\varphi), a contraposição (CP), em particular (φ→ψ)⊣⊢(¬ψ→¬φ)(\varphi \rightarrow \psi) \dashv\vdash (\neg\psi \rightarrow \neg\varphi), e a segunda regra primitiva do sistema do curso, a substituição da dupla negação (SDN), com a qual o teorema da dedução continua valendo: se χ′\chi' resulta de χ\chi ao substituir uma ocorrência de uma subfórmula θ\theta por ¬¬θ\neg\neg\theta, ou uma de ¬¬θ\neg\neg\theta por θ\theta, de χ\chi infere-se χ′\chi'; a linha assim obtida da linha ii justifica-se SDN(i)(i). Entre suas consequências imediatas estão (φ↓ψ)⊣⊢(¬¬φ↓ψ)(\varphi \downarrow \psi) \dashv\vdash (\neg\neg\varphi \downarrow \psi), (φ↓ψ)⊣⊢(φ↓¬¬ψ)(\varphi \downarrow \psi) \dashv\vdash (\varphi \downarrow \neg\neg\psi) e, em geral, χ⊣⊢χ′\chi \dashv\vdash \chi' quando χ′\chi' resulta de χ\chi por SDN; disso se segue que SDN(i)(i) se aplica também a uma linha da forma χ⊣⊢φ\chi \dashv\vdash \varphi, para mudar uma dupla negação em φ\varphi. Da aula sobre as simetrias dos conectivos, a substituição de equivalentes (Subst) e as simetrias (Sim), entre elas (φ∨ψ)⊣⊢(ψ∨φ)(\varphi \vee \psi) \dashv\vdash (\psi \vee \varphi) e (φ∧ψ)⊣⊢(ψ∧φ)(\varphi \wedge \psi) \dashv\vdash (\psi \wedge \varphi).

Da aula sobre as técnicas da lógica clássica tomam-se, todas com um conjunto Γ\Gamma de premissas, as regras seguintes. A introdução da disjunção (∨\veeI): se Γ⊢φ\Gamma \vdash \varphi, então Γ⊢(φ∨ψ)\Gamma \vdash (\varphi \vee \psi) e Γ⊢(ψ∨φ)\Gamma \vdash (\psi \vee \varphi). A eliminação da disjunção (∨\veeE, silogismo disjuntivo): se Γ⊢(φ∨ψ)\Gamma \vdash (\varphi \vee \psi) e Γ⊢¬φ\Gamma \vdash \neg\varphi, então Γ⊢ψ\Gamma \vdash \psi. A introdução da conjunção (∧\wedgeI): se Γ⊢φ\Gamma \vdash \varphi e Γ⊢ψ\Gamma \vdash \psi, então Γ⊢(φ∧ψ)\Gamma \vdash (\varphi \wedge \psi). A eliminação da conjunção (∧\wedgeE): se Γ⊢(φ∧ψ)\Gamma \vdash (\varphi \wedge \psi), então Γ⊢φ\Gamma \vdash \varphi e Γ⊢ψ\Gamma \vdash \psi. O terceiro excluído (TE): ⊢(φ∨¬φ)\vdash (\varphi \vee \neg\varphi). E a prova por casos (Casos) em suas duas formas: se Γ∪{φ}⊢χ\Gamma \cup \{\varphi\} \vdash \chi e Γ∪{¬φ}⊢χ\Gamma \cup \{\neg\varphi\} \vdash \chi, então Γ⊢χ\Gamma \vdash \chi; e se Γ∪{φ}⊢χ\Gamma \cup \{\varphi\} \vdash \chi, Γ∪{ψ}⊢χ\Gamma \cup \{\psi\} \vdash \chi e Γ⊢(φ∨ψ)\Gamma \vdash (\varphi \vee \psi), então Γ⊢χ\Gamma \vdash \chi. Nas deduções, a primeira forma cita-se com duas linhas, Casos(i,j)(i, j), e a segunda, com três, Casos(i,j,k)(i, j, k), na ordem do enunciado: os dois casos e, no final, a disjunção. Essa aula lembra, além disso, que toda regra já demonstrada vale dentro de um contexto Γ\Gamma, e é assim que se usam aqui a dupla negação e a contraposição.

Nomes de uma cadeia e fórmulas equivalentes

Recorde-se, da aula sobre a linguagem da lógica proposicional, que os conectivos distintos de ↓\downarrow são abreviaturas com uma definição oficial e única: ¬φ:=(φ↓φ)\neg\varphi := (\varphi \downarrow \varphi), (φ∨ψ):=¬(φ↓ψ)(\varphi \vee \psi) := \neg(\varphi \downarrow \psi), (φ∧ψ):=¬(¬φ∨¬ψ)(\varphi \wedge \psi) := \neg(\neg\varphi \vee \neg\psi), (φ→ψ):=(¬φ∨ψ)(\varphi \rightarrow \psi) := (\neg\varphi \vee \psi), (φ↔ψ):=((φ→ψ)∧(ψ→φ))(\varphi \leftrightarrow \psi) := ((\varphi \rightarrow \psi) \wedge (\psi \rightarrow \varphi)) e (φ⊻ψ):=¬(φ↔ψ)(\varphi \veebar \psi) := \neg(\varphi \leftrightarrow \psi). Uma definição não afirma nada sobre as fórmulas: dá um segundo nome a uma cadeia que já existia. Disso se segue que, se duas expressões designam a mesma cadeia, uma pode ocupar o lugar da outra em qualquer ponto, também dentro de uma fórmula maior, porque o que se escreve é a mesma sequência de círculos e discos. Assim, ¬(φ∧ψ)\neg(\varphi \wedge \psi) e ¬¬(¬φ∨¬ψ)\neg\neg(\neg\varphi \vee \neg\psi) são a mesma cadeia: a segunda resulta de escrever, dentro da primeira, o desdobramento da conjunção. Nas deduções, essa mudança de nome justifica-se com “Def”, seguido do conectivo que se desdobra ou se recolhe.

Ora, uma equivalência demonstrável não é uma identidade. Que φ⊣⊢¬¬φ\varphi \dashv\vdash \neg\neg\varphi significa que de cada uma se deduz a outra, não que sejam a mesma cadeia: ¬¬φ\neg\neg\varphi é muito mais longa que φ\varphi. Portanto, saber que φ⊣⊢φ′\varphi \dashv\vdash \varphi' não autoriza, sem mais, a escrever φ′\varphi' no lugar de φ\varphi dentro de uma fórmula maior. Tampouco autoriza a “negar ambos os lados”: que de φ⊣⊢φ′\varphi \dashv\vdash \varphi' se siga ¬φ⊣⊢¬φ′\neg\varphi \dashv\vdash \neg\varphi' é um teorema, a substituição de equivalentes, cuja demonstração usa a contraposição, e não uma operação evidente. Há um único caso em que o sistema autoriza a substituição diretamente, em qualquer lugar de uma fórmula: o de θ\theta por ¬¬θ\neg\neg\theta, ou o inverso, que é a regra SDN; e a aula sobre os sistemas dedutivos mostrou, com a marca, que nem sequer esse caso se deduz dos axiomas e do modus ponens, de modo que foi preciso postulá-lo. Esse cuidado não é pedantismo; é o que distingue uma demonstração de uma manipulação de símbolos que poderia, aplicada a outros conectivos ou em outros sistemas, conduzir a falsidades.

Dois resultados fixam com precisão o que é permitido. O primeiro é a proposição sobre as propriedades da equivalência demonstrável da aula sobre sistemas dedutivos formais: se Γ⊢φ\Gamma \vdash \varphi e φ⊣⊢φ′\varphi \dashv\vdash \varphi', então Γ⊢φ′\Gamma \vdash \varphi', de modo que uma equivalência demonstrável pode aplicar-se à fórmula inteira de uma linha; e a equivalência demonstrável é reflexiva, simétrica e transitiva, de modo que as equivalências se encadeiam (se χ⊣⊢φ\chi \dashv\vdash \varphi e φ⊣⊢φ′\varphi \dashv\vdash \varphi', então χ⊣⊢φ′\chi \dashv\vdash \varphi') e duas expressões que designam a mesma cadeia são, por reflexividade, demonstravelmente equivalentes. O segundo, o lema seguinte, reúne, para citá-la com comodidade, a extensão da substituição de equivalentes à disjunção e à conjunção, que a aula sobre as simetrias demonstra para a negação, a implicação e a negação conjunta e estende a esses dois conectivos em um de seus problemas resolvidos.

LemaSubstituição na disjunção e na conjunção

Se φ⊣⊢φ′\varphi \dashv\vdash \varphi', então, para toda fórmula ψ\psi, (φ∨ψ)⊣⊢(φ′∨ψ)(\varphi \vee \psi) \dashv\vdash (\varphi' \vee \psi), (ψ∨φ)⊣⊢(ψ∨φ′)(\psi \vee \varphi) \dashv\vdash (\psi \vee \varphi'), (φ∧ψ)⊣⊢(φ′∧ψ)(\varphi \wedge \psi) \dashv\vdash (\varphi' \wedge \psi) e (ψ∧φ)⊣⊢(ψ∧φ′)(\psi \wedge \varphi) \dashv\vdash (\psi \wedge \varphi').

Demonstração

  1. (φ∨ψ)=¬(φ↓ψ)(\varphi \vee \psi) = \neg\resaltar{(\varphi \downarrow \psi)}

    A disjunção é, por definição, a negação de uma negação conjunta.

  2. (φ↓ψ)⊣⊢(φ′↓ψ)\dato{int}{(\varphi \downarrow \psi) \dashv\vdash (\varphi' \downarrow \psi)}

    A substituição de equivalentes para a negação conjunta dá a equivalência da camada interior.

  3. (φ∨ψ)⊣⊢(φ′∨ψ)\dato{disy}{\resaltar{(\varphi \vee \psi)} \dashv\vdash \resaltar{(\varphi' \vee \psi)}}

    A substituição de equivalentes para a negação a leva à camada exterior, ¬(φ↓ψ)⊣⊢¬(φ′↓ψ)\neg(\varphi \downarrow \psi) \dashv\vdash \neg(\varphi' \downarrow \psi), que é a disjunção. Do mesmo modo, com (ψ↓φ)⊣⊢(ψ↓φ′)(\psi \downarrow \varphi) \dashv\vdash (\psi \downarrow \varphi'), obtém-se a substituição à direita.

  4. (φ∧ψ)=¬(¬φ∨¬ψ),¬φ⊣⊢¬φ′(\varphi \wedge \psi) = \neg(\resaltar{\neg\varphi} \vee \neg\psi), \qquad \neg\varphi \dashv\vdash \neg\varphi'

    A conjunção é a negação de uma disjunção de negações. A substituição para a negação dá primeiro ¬φ⊣⊢¬φ′\neg\varphi \dashv\vdash \neg\varphi'.

  5. ¬(¬φ∨¬ψ)⊣⊢¬(¬φ′∨¬ψ),(φ∧ψ)⊣⊢(φ′∧ψ)\neg(\neg\varphi \vee \neg\psi) \dashv\vdash \neg(\neg\varphi' \vee \neg\psi), \qquad \resaltar{(\varphi \wedge \psi)} \dashv\vdash \resaltar{(\varphi' \wedge \psi)}

    A parte já demonstrada para a disjunção, aplicada a ¬φ\neg\varphi e ¬φ′\neg\varphi', dá (¬φ∨¬ψ)⊣⊢(¬φ′∨¬ψ)(\neg\varphi \vee \neg\psi) \dashv\vdash (\neg\varphi' \vee \neg\psi), e de novo a substituição para a negação leva a equivalência à conjunção; à direita raciocina-se da mesma maneira.

Daqui em diante, “Subst” designa a substituição de equivalentes em qualquer de suas formas, também as deste lema, e pode aplicar-se várias vezes seguidas, camada por camada, para chegar a uma subfórmula situada a qualquer profundidade. Quando uma linha se obtém da linha ii aplicando uma equivalência já demonstrada, seja à fórmula inteira, seja, com Subst, a uma de suas partes, justifica-se com o nome dessa equivalência e o número da linha: DN(i)(i), “Subst, DM(i)(i)”. Uma mudança de nome, que não aplica nenhuma equivalência, mas reescreve a mesma cadeia, justifica-se do mesmo modo, com Def seguido do conectivo que se desdobra ou se recolhe: Def ∧\wedge (i)(i). A proposição da aula sobre os sistemas dedutivos formais garante que essas linhas estão justificadas, tanto se a linha ii afirma Γ⊢φ\Gamma \vdash \varphi como se afirma uma equivalência χ⊣⊢φ\chi \dashv\vdash \varphi que vai sendo prolongada.