Saltar para o conteúdo
Topos Uranos
Português

Leis generalizadas de De Morgan e distributivas

Resumo

As leis de De Morgan e as leis distributivas foram enunciadas até aqui para dois termos; as formas normais, por outro lado, reúnem conjunções e disjunções de qualquer número de termos, e as exigem nessa generalidade. Esta aula define por recursão a conjunção e a disjunção de uma lista de fórmulas (φ1,…,φn)(\varphi_1, \ldots, \varphi_n), que se escrevem ⋀i=1nφi\bigwedge_{i=1}^{n} \varphi_i e ⋁i=1nφi\bigvee_{i=1}^{n} \varphi_i, associando pela esquerda, e demonstra por indução sobre o número de termos o lema do valor (uma conjunção é verdadeira se e somente se todos os seus termos o são; uma disjunção, se e somente se algum o é), a associatividade generalizada, que autoriza a reagrupar, a independência da ordem e das repetições, as leis de De Morgan generalizadas e a distributividade generalizada na forma que a aula sobre as formas normais usará: a conjunção de duas disjunções, de nn e de mm termos, equivale à disjunção das nmnm conjunções de um termo de cada uma, e dualmente. Os problemas contam valorações, localizam o erro de uma demonstração que faz passar um reagrupamento por uma definição, medem o crescimento de uma distribuição e obtêm dela uma tautologia de 2n2^n termos.

Objetivos de aprendizagem

  1. Escrever conjunções e disjunções de nn termos com a notação ⋀\bigwedge e ⋁\bigvee, desdobrá-las como cadeias associadas pela esquerda e calcular seu valor de verdade com o lema do valor.
  2. Demonstrar por indução sobre o número de termos a associatividade generalizada, a independência da ordem e das repetições e as leis de De Morgan generalizadas, distinguindo em cada passo a identidade de cadeias da equivalência semântica.
  3. Demonstrar a distributividade generalizada e sua dual organizando a indução sobre dois índices, e contar os termos que uma distribuição produz.
  4. Localizar o erro de uma demonstração por indução cujo caso base está mal escrito ou cujo passo esconde um reagrupamento, e repará-la.

Leis para qualquer número de termos

A aula sobre consequência e equivalência semânticas estabeleceu as leis de equivalência para dois termos: entre elas, a comutatividade e a associatividade de ∧\wedge e de ∨\vee, as leis de De Morgan e as duas distributividades. Ora, uma fórmula em forma normal disjuntiva é uma disjunção de conjunções, cada uma com tantos termos quantos forem necessários, e transformar uma fórmula nessa forma exige negar, reagrupar e distribuir conjunções e disjunções de qualquer comprimento. Se isto é assim, as leis binárias não bastam tal como estão: é preciso estendê-las a nn termos, e fazê-lo de uma vez para todos os nn.

Para cada nn fixo, a lei de De Morgan de nn termos poderia ser verificada com uma tabela-verdade de 2n2^n linhas, escrita com nn variáveis, e a substituição uniforme da aula anterior, aplicada ao bicondicional entre ambos os lados, a estenderia a fórmulas quaisquer. Mas há infinitos valores de nn, e nenhuma quantidade de tabelas os esgota. Daí se segue que a afirmação “para todo nn” não é uma equivalência entre duas fórmulas, mas um enunciado sobre infinitas equivalências, formulado na metalinguagem; sua demonstração é, como as da aula sobre a indução sobre os números naturais e sobre as fórmulas, uma demonstração externa, e seu instrumento é a indução sobre o número de termos. A notação ⋀i=1nφi\bigwedge_{i=1}^{n} \varphi_i também pertence à metalinguagem: não é um símbolo novo da linguagem, mas um nome para uma cadeia de círculos e discos, do mesmo modo que (φ∧ψ)(\varphi \wedge \psi) o é.

Convém fixar desde já três relações que não devem ser confundidas. A igualdade α=β\alpha = \beta diz que α\alpha e β\beta são a mesma cadeia; as definições, que se escrevem com :=:=, introduzem nomes para cadeias, e o que se obtém desdobrando uma definição é igual, não meramente equivalente. A equivalência semântica α≡β\alpha \eqsem \beta diz que v(α)=v(β)v(\alpha) = v(\beta) para toda valoração vv. A equivalência demonstrável α⊣⊢β\alpha \dashv\vdash \beta da unidade de dedução diz que cada uma se deduz da outra. Esta aula trabalha com as duas primeiras; a terceira aparece só em um comentário.

O que se usa

Da aula sobre a semântica da lógica proposicional tomam-se as valorações, funções das variáveis v1,v2,…v_1, v_2, \ldots em {0,1}\{0, 1\}, e sua extensão a todas as fórmulas, que se escreve com a mesma letra vv; o valor dos conectivos derivados, calculado a partir das abreviaturas oficiais: v(¬φ)=1−v(φ)v(\neg\varphi) = 1 - v(\varphi), v((φ∧ψ))=v(φ) v(ψ)v((\varphi \wedge \psi)) = v(\varphi)\,v(\psi), de modo que a conjunção vale 11 se e somente se valem 11 seus dois componentes, e v((φ∨ψ))=1v((\varphi \vee \psi)) = 1 se e somente se v(φ)=1v(\varphi) = 1 ou v(ψ)=1v(\psi) = 1; o lema da coincidência (se duas valorações coincidem nas variáveis de uma fórmula, coincidem na fórmula); e as fórmulas ⊤\top e ⊥\bot, uma tautologia e uma contradição fixas. Da aula sobre consequência e equivalência semânticas tomam-se que ≡\eqsem é reflexiva, simétrica e transitiva, o teorema da substituição semântica e o catálogo de leis com seus nomes: comutatividade, (φ∧ψ)≡(ψ∧φ)(\varphi \wedge \psi) \eqsem (\psi \wedge \varphi) e (φ∨ψ)≡(ψ∨φ)(\varphi \vee \psi) \eqsem (\psi \vee \varphi); associatividade, (φ∧(ψ∧χ))≡((φ∧ψ)∧χ)(\varphi \wedge (\psi \wedge \chi)) \eqsem ((\varphi \wedge \psi) \wedge \chi) e sua análoga para ∨\vee; De Morgan, ¬(φ∧ψ)≡(¬φ∨¬ψ)\neg(\varphi \wedge \psi) \eqsem (\neg\varphi \vee \neg\psi) e ¬(φ∨ψ)≡(¬φ∧¬ψ)\neg(\varphi \vee \psi) \eqsem (\neg\varphi \wedge \neg\psi); distributividade, (φ∧(ψ∨χ))≡((φ∧ψ)∨(φ∧χ))(\varphi \wedge (\psi \vee \chi)) \eqsem ((\varphi \wedge \psi) \vee (\varphi \wedge \chi)) e (φ∨(ψ∧χ))≡((φ∨ψ)∧(φ∨χ))(\varphi \vee (\psi \wedge \chi)) \eqsem ((\varphi \vee \psi) \wedge (\varphi \vee \chi)); dupla negação, ¬¬φ≡φ\neg\neg\varphi \eqsem \varphi; idempotência, (φ∨φ)≡φ(\varphi \vee \varphi) \eqsem \varphi; identidade, (φ∧⊤)≡φ(\varphi \wedge \top) \eqsem \varphi; e terceiro excluído, ⊨(φ∨¬φ)\models (\varphi \vee \neg\varphi). As leis valem para fórmulas quaisquer φ\varphi, ψ\psi, χ\chi, que são metavariáveis.

Em cada passo das demonstrações que seguem, substitui-se uma parte de uma fórmula por outra equivalente. O teorema da substituição semântica o autoriza para uma ocorrência de cada vez; o lema seguinte, que é um caso particular dele, o dá de uma só vez para as partes de uma negação, de uma conjunção ou de uma disjunção. É preciso advertir que não é uma trivialidade sintática: ¬α\neg\alpha é a cadeia (α↓α)(\alpha \downarrow \alpha), na qual α\alpha ocorre duas vezes, e (α∧β)(\alpha \wedge \beta) contém, portanto, oito ocorrências de α\alpha e oito de β\beta.

LemaCompatibilidade dos conectivos com a equivalência

Se α≡α′\alpha \eqsem \alpha' e β≡β′\beta \eqsem \beta', então ¬α≡¬α′\neg\alpha \eqsem \neg\alpha', (α∧β)≡(α′∧β′)(\alpha \wedge \beta) \eqsem (\alpha' \wedge \beta') e (α∨β)≡(α′∨β′)(\alpha \vee \beta) \eqsem (\alpha' \vee \beta').

Demonstração

  1. v(α)=v(α′),v(β)=v(β′)\dato{h}{v(\alpha) = v(\alpha'), \qquad v(\beta) = v(\beta')}

    Seja vv uma valoração qualquer. Por hipótese, α\alpha e α′\alpha' têm o mesmo valor, e também β\beta e β′\beta'.

  2. v(¬α)=1−v(α)=1−v(α′)=v(¬α′),v((α∧β))=v(α) v(β)=v(α′) v(β′)=v((α′∧β′))v(\neg\alpha) = 1 - \resaltar{v(\alpha)} = 1 - \resaltar{v(\alpha')} = v(\neg\alpha'), \qquad v((\alpha \wedge \beta)) = \resaltar{v(\alpha)\,v(\beta)} = \resaltar{v(\alpha')\,v(\beta')} = v((\alpha' \wedge \beta'))

    O valor de uma negação e o de uma conjunção dependem só dos valores de seus componentes.

  3. v((α∨β))=1  ⇔  v(α)+v(β)≥1  ⇔  v(α′)+v(β′)≥1  ⇔  v((α′∨β′))=1v((\alpha \vee \beta)) = 1 \;\Leftrightarrow\; v(\alpha) + v(\beta) \geq 1 \;\Leftrightarrow\; v(\alpha') + v(\beta') \geq 1 \;\Leftrightarrow\; v((\alpha' \vee \beta')) = 1

    O mesmo ocorre com a disjunção: vale 11 se e somente se algum componente vale 11, e os componentes têm os mesmos valores em ambos os lados.

  4. ¬α≡¬α′,(α∧β)≡(α′∧β′),(α∨β)≡(α′∨β′)\neg\alpha \eqsem \neg\alpha', \qquad (\alpha \wedge \beta) \eqsem (\alpha' \wedge \beta'), \qquad (\alpha \vee \beta) \eqsem (\alpha' \vee \beta')

    Como vv era qualquer, as três equivalências valem.