Linguagem: síntese e desafios

Resumo

Esta aula encerra a unidade dedicada à linguagem da lógica proposicional. Reconstrói a cadeia dedutiva que vai da distinção entre validade e verdade, e da análise dos paradoxos, até a leitura única das fórmulas e a formalização de enunciados e argumentos, indicando em cada elo que princípio se usa e em que aula se demonstra; situa o que foi alcançado em relação ao plano do curso e explica por que a linguagem já construída coloca a pergunta da unidade seguinte, dedicada à dedução. Repete em sua avaliação de saída as habilidades da avaliação de entrada e termina com seis desafios, de dificuldade superior à dos problemas das aulas, que exigem combinar os instrumentos de várias delas.

Objetivos de aprendizagem

Reconstruir a ordem lógica dos resultados da unidade, identificando o princípio em que se apoia cada um e a aula em que se demonstra.
Explicar como se encadeiam o princípio do fecho, a decomposição em palavras, o lema do peso e a leitura única, e por que desta dependem as definições recursivas e a comparação de formalizações.
Distinguir o que a unidade demonstrou do que admitiu como hipótese (a bivalência, o esquema da verdade, o princípio de indução e a leitura da negação conjunta) e do que deixou para as unidades seguintes.
Resolver problemas que combinam o lema diagonal, a contagem de cadeias, a indução sobre as fórmulas, o argumento do peso e o desdobramento das abreviaturas.

O que a unidade alcançou

A unidade se propôs construir, a partir de um alfabeto de dois símbolos, uma linguagem em que cada fórmula se leia de uma só maneira, demonstrar com rigor as propriedades dessa linguagem e lançar uma ponte entre ela e a língua em que raciocinamos. O propósito foi cumprido com algumas poucas ressalvas, cada uma declarada em seu lugar: a bivalência e o esquema da verdade, que a primeira aula não admitiu como verdades, mas como hipóteses explícitas, para examinar o que ocorre quando se sustentam ao mesmo tempo; o princípio de indução sobre os naturais, que se admite como o quinto axioma de Peano; a leitura informal da negação conjunta, que se estipula e que a unidade de semântica converterá em definição; e o indispensável da teoria dos conjuntos (pertinência, inclusão e união), que se ensinou onde foi necessário. Com essas ressalvas, o caminho percorrido pode ser lido como uma única cadeia dedutiva em quatro trechos.

Raciocinar e falar da linguagem

A aula sobre o que é a lógica matemática fixou o objeto do curso: não a verdade dos enunciados, que cabe a cada ciência, mas sua transmissão. Um argumento é válido quando sua forma não admite nenhuma instância com premissas verdadeiras e conclusão falsa, e dessa definição se deduziu o único que a validade garante: se as premissas são verdadeiras, a conclusão também o é; donde um argumento válido com conclusão falsa tem alguma premissa falsa, e uma forma é inválida exatamente quando tem um contraexemplo. Esse mesmo resultado converteu a análise dos paradoxos em um procedimento: se os passos de um raciocínio que termina em contradição são válidos, alguma hipótese é falsa, e resolver o paradoxo é encontrar qual. Assim se tratou o mentiroso, no qual a bivalência e o esquema da verdade não podem sustentar-se ao mesmo tempo para uma sentença que se declara falsa, e assim se trataram o paradoxo de Berry e o adjetivo “heterológico”. Do barbeiro se extraiu um lema geral, o lema diagonal, que demonstra que o barbeiro não existe e que o princípio de compreensão sem restrições é contraditório. A aula estabeleceu, por último, a distinção entre linguagem-objeto e metalinguagem, e entre o uso de uma expressão e sua menção, que governa tudo o que se segue: os resultados da unidade sobre as fórmulas não são fórmulas, mas metateoremas.

A língua de círculos e discos

A aula sobre a linguagem da lógica proposicional introduziu os conjuntos e as cadeias, contou as cadeias de cada comprimento (há $2^{n}$ de comprimento $n$ , e $2^{N + 1} - 2$ de comprimentos $1$ a $N$ ) e construiu a língua base: as variáveis $v_n = \sigO^{n}\sigI$ e uma única regra, que de duas fórmulas $\varphi$ e $\psi$ forma $\sigI\varphi\psi$ . A cláusula “nada mais é fórmula” tornou-se precisa ao definir as fórmulas como as cadeias que pertencem a todos os conjuntos fechados, e dessa definição se deduziu o princípio do fecho, com o qual se demonstrou que toda fórmula é uma variável ou é $\sigI\varphi\psi$ , e não ambas as coisas, que toda fórmula termina em um disco e que contém um número ímpar de discos. A observação de que as variáveis e o disco solto formam um código de prefixos deu a decomposição única em palavras, e com ela a noção de peso. A aula construiu também a metalinguagem com que se trabalha daí em diante: as metavariáveis, a negação conjunta escrita $(\varphi \downarrow \psi)$ e as seis abreviaturas oficiais, cada uma definida uma única vez a partir das anteriores, de modo que toda expressão abreviada designa uma única cadeia.

Indução e leitura única

A aula sobre a indução sobre os números naturais e sobre as fórmulas justificou as contagens que a aula anterior havia concluído com “e assim por diante”, deduziu a indução forte da simples e, com ela aplicada ao comprimento, obteve a indução estrutural, que resulta ser a mesma indução sobre os naturais transladada para as fórmulas. Com esse instrumento demonstrou o lema do peso: toda fórmula pesa $+1$ , e todo prefixo por palavras próprio e não vazio pesa no máximo $0$ . Disso se seguem, nesta ordem, que nenhuma fórmula é prefixo próprio de outra e que toda fórmula composta se lê de um único modo. A leitura única é o elo do qual pende o resto da unidade: justifica o procedimento de decisão que a aula sobre a linguagem havia descrito como uma dívida que se salda, e legitima as definições por recursão (o comprimento, o número de variáveis e de discos conectivos, as subfórmulas, a profundidade e a substituição), que sem ela poderiam atribuir a uma fórmula dois valores distintos.

Do português às fórmulas

A aula sobre a formalização da linguagem natural lançou a ponte para a língua. Fixou a convenção das letras $p$ , $q$ , $r$ , $s$ e $t$ como nomes de cinco variáveis determinadas, exigiu que toda formalização declare seu dicionário e deduziu, apenas da leitura estipulada da negação conjunta, a leitura de cada abreviatura. Com a leitura única demonstrou que dois agrupamentos distintos dos mesmos conectivos são fórmulas distintas, e com a definição recursiva do comprimento calculou quanto medem as abreviaturas desdobradas, o que dá um critério rápido para separar formalizações. Mostrou que o condicional material é falso somente quando o antecedente é verdadeiro e o consequente falso, e que essa é a única leitura, dependente apenas da verdade das partes, que torna verdadeiros os teoremas condicionais da matemática; assinalou o que a formalização perde (quantificadores, tempo, causalidade, modalidade) e terminou formalizando argumentos completos como um conjunto de premissas $\Gamma$ e uma conclusão.

A figura seguinte reúne os quatro trechos numa única cadeia. Cada nó da coluna é uma definição ou um resultado, numerado segundo a ordem lógica e unido por um arco aos elos anteriores que sua demonstração usa; ao redor flutuam os apoios, isto é, os princípios aos quais a cadeia recorre uma e outra vez, cada um unido por um traço firme aos elos que se apoiam nele e por um pontilhado ao elo onde se estabelece, exceto os que se admitem sem demonstração, que se desenham como anéis. Ao clicar num apoio destacam-se todos os elos que o usam, e cada elo remete à aula em que se demonstra. Observe-se que o procedimento de decisão, embora seja exposto na aula sobre a linguagem, ocupa seu lugar lógico depois da leitura única, na qual se apoia.

Apoios da cadeia

ABivalência. Toda proposição é verdadeira ou falsa, e não ambas as coisas; ser falsa equivale a não ser verdadeira. Admite-se como hipótese explícita na análise dos paradoxos. Admitido sem demonstração nesta unidade.
BEsquema da verdade. Uma sentença é verdadeira se e somente se o que ela diz é o caso. Admite-se como hipótese explícita; a solução de Tarski o conserva, mas somente para as sentenças de uma linguagem que não contém seu próprio predicado de verdade. Admitido sem demonstração nesta unidade.
CPrincípio de indução. Se uma propriedade vale para $1$ e, cada vez que vale para um natural $k$ , vale para $k + 1$ , então vale para todos os naturais. É o quinto axioma de Peano, e se admite. Admitido sem demonstração nesta unidade.
DLema diagonal. Nenhum objeto $b$ de uma coleção cumpre $R(b, x) \Leftrightarrow \neg R(x, x)$ para todo $x$ da coleção. Estabelecido em: 3. Lema diagonal.
EPrincípio do fecho. Uma propriedade que todas as variáveis têm e que passa de $\varphi$ e $\psi$ para $\sigI\varphi\psi$ é tida por todas as fórmulas. Estabelecido em: 5. Princípio do fecho.
FIndução estrutural. A indução sobre a complexidade das fórmulas, deduzida da indução forte sobre o comprimento: seu caso base são as variáveis, e seu passo indutivo, a única regra de formação. Estabelecido em: 9. Indução estrutural.
GLeitura única. Se $\sigI\varphi\psi = \sigI\varphi'\psi'$ , com as quatro cadeias fórmulas, então $\varphi = \varphi'$ e $\psi = \psi'$ . Estabelecido em: 11. Leitura única.
HLeitura da negação conjunta. A fórmula $(\varphi \downarrow \psi)$ é verdadeira exatamente quando $\varphi$ e $\psi$ são ambas falsas. É a única leitura que se estipula; as demais se deduzem dela, e a unidade de semântica a precisará. Admitido sem demonstração nesta unidade.

Trecho 1 Raciocinar e falar da linguagem
- Distinguir a validade da verdade e refutar uma forma inválida com um contraexemplo.
- Reconhecer as ambiguidades da linguagem natural e separar as leituras de um enunciado.
- Distinguir a linguagem-objeto da metalinguagem, e o uso de uma expressão de sua menção.
- Analisar um paradoxo isolando suas hipóteses e decidindo qual deve ser abandonada.
1. O que a validade garante. Se um argumento é válido e todas as suas premissas são verdadeiras, sua conclusão é verdadeira; donde um argumento válido com conclusão falsa tem alguma premissa falsa, e uma forma é inválida exatamente quando tem um contraexemplo.
  Demonstrado em: O que é a lógica matemática.
2. O paradoxo do mentiroso. Aplicadas à sentença $m$ , “a sentença $m$ é falsa”, a bivalência e o esquema da verdade dão $V(m) \Leftrightarrow \neg V(m)$ ; para uma linguagem que contém $m$ , alguma das duas hipóteses deve ser abandonada, e a saída de Tarski é que nenhuma linguagem contenha seu próprio predicado de verdade, de modo que $m$ não pode ser formada.
  Usa: 1. O que a validade garante. Apoia-se em: A (Bivalência), B (Esquema da verdade). Demonstrado em: O que é a lógica matemática.
3. Lema diagonal. Se $R$ é uma relação entre os objetos de uma coleção $D$ , de modo que cada $R(x, y)$ é verdadeira ou falsa, nenhum $b$ de $D$ cumpre $R(b, x) \Leftrightarrow \neg R(x, x)$ para todo $x$ de $D$ .
  Apoia-se em: A (Bivalência). Demonstrado em: O que é a lógica matemática.
4. O barbeiro e Russell. Não existe um homem do povoado que barbeie exatamente os homens do povoado que não se barbeiam a si mesmos; e o princípio de compreensão sem restrições é contraditório, porque afirma a existência do conjunto $Z = \{ x : x \notin x \}$ .
  Apoia-se em: D (Lema diagonal). Demonstrado em: O que é a lógica matemática.
Trecho 2 A língua de círculos e discos
- Descrever conjuntos de cadeias e contar as cadeias de cada comprimento.
- Definir as fórmulas como o menor conjunto fechado e deduzir disso o princípio do fecho.
- Demonstrar propriedades de todas as fórmulas e usá-las para descartar cadeias.
- Decompor uma cadeia em palavras e desdobrar as abreviaturas até a língua base.
1. Princípio do fecho. O conjunto $\mathcal{F}$ das fórmulas é o menor conjunto de cadeias que contém as variáveis $v_n = \sigO^{n}\sigI$ e que, com $\varphi$ e $\psi$ , contém $\sigI\varphi\psi$ ; portanto, uma propriedade que as variáveis têm e que passa de $\varphi$ e $\psi$ para $\sigI\varphi\psi$ é tida por todas as fórmulas.
  Demonstrado em: A linguagem da lógica proposicional.
2. Forma das fórmulas. Toda fórmula é uma variável ou é $\sigI\varphi\psi$ com $\varphi$ e $\psi$ fórmulas, e não ambas as coisas: toda variável começa com $\sigO$ , e toda fórmula composta, com $\sigI$ .
  Apoia-se em: E (Princípio do fecho). Demonstrado em: A linguagem da lógica proposicional.
3. Último símbolo e número de discos. Toda fórmula termina em um disco e contém um número ímpar de discos; donde nem a concatenação de duas fórmulas nem a cadeia $\sigI\varphi$ são fórmulas.
  Apoia-se em: E (Princípio do fecho). Demonstrado em: A linguagem da lógica proposicional.
4. Decomposição em palavras. Toda cadeia que termina em um disco se decompõe de um único modo em palavras, isto é, em variáveis $\sigO^{n}\sigI$ e discos soltos, porque cada palavra termina em seu único disco e nenhuma é prefixo próprio de outra.
  Demonstrado em: A linguagem da lógica proposicional.
Trecho 3 Indução e leitura única
- Demonstrar por indução simples e forte, e deduzir delas a indução sobre a complexidade das fórmulas.
- Demonstrar o lema do peso e deduzir a leitura única.
- Decidir se uma cadeia é fórmula e reconstruir sua formação.
- Definir funções sobre as fórmulas por recursão e demonstrar relações entre elas.
1. Indução estrutural. A indução forte se deduz da simples; aplicada ao comprimento, dá o princípio de indução sobre a complexidade: se as variáveis têm uma propriedade e esta passa de $\varphi$ e $\psi$ para $\sigI\varphi\psi$ , todas as fórmulas a têm.
  Usa: 6. Forma das fórmulas. Apoia-se em: C (Princípio de indução). Demonstrado em: Indução sobre os números naturais e sobre as fórmulas.
2. Lema do peso. Se cada ocorrência de variável pesa $+1$ e cada disco conectivo $-1$ , toda fórmula pesa $+1$ e todo prefixo por palavras próprio e não vazio de uma fórmula pesa no máximo $0$ ; em particular, toda fórmula tem uma ocorrência de variável a mais que discos conectivos.
  Usa: 8. Decomposição em palavras. Apoia-se em: F (Indução estrutural). Demonstrado em: Indução sobre os números naturais e sobre as fórmulas.
3. Leitura única. Nenhuma fórmula é prefixo próprio de outra; donde, se $\sigI\varphi\psi = \sigI\varphi'\psi'$ com as quatro cadeias fórmulas, então $\varphi = \varphi'$ e $\psi = \psi'$ .
  Usa: 7. Último símbolo e número de discos, 8. Decomposição em palavras, 10. Lema do peso. Demonstrado em: Indução sobre os números naturais e sobre as fórmulas.
4. Procedimento de decisão. Uma cadeia que termina em $\sigO$ não é fórmula; se termina em $\sigI$ , decompõe-se em palavras. Se a primeira palavra é uma variável, a cadeia é fórmula exatamente quando essa variável é sua única palavra. Se é um disco, leva-se a dívida depois dele: se nunca se anula, a cadeia não é fórmula; se se anula, o corte entre $\varphi$ e $\psi$ está onde isso ocorre pela primeira vez, e cada trecho se examina do mesmo modo, tendo em conta que a cadeia vazia não é fórmula.
  Usa: 6. Forma das fórmulas, 7. Último símbolo e número de discos, 8. Decomposição em palavras. Apoia-se em: G (Leitura única). Demonstrado em: A linguagem da lógica proposicional.
5. Definição por recursão. Dados um valor para cada variável e uma regra que calcula o valor de $\sigI\varphi\psi$ a partir de $\varphi$ , de $\psi$ e de seus valores, existe exatamente uma função sobre as fórmulas que os respeita; assim se definem o comprimento, as subfórmulas, a profundidade e a substituição, que sempre produz fórmulas.
  Usa: 6. Forma das fórmulas. Apoia-se em: C (Princípio de indução), F (Indução estrutural), G (Leitura única). Demonstrado em: Indução sobre os números naturais e sobre as fórmulas.
Trecho 4 Do português às fórmulas
- Formalizar enunciados com um dicionário explícito, decidindo o escopo de cada conectivo.
- Desdobrar abreviaturas para decidir se duas formalizações são a mesma fórmula.
- Distinguir o condicional material do “se… então” da língua e assinalar o que a formalização perde.
- Formalizar argumentos completos como um conjunto de premissas e uma conclusão.
1. Comprimento das abreviaturas. Se $L(\varphi) = a$ e $L(\psi) = b$ , as cadeias de $\neg\varphi$ , $(\varphi \vee \psi)$ , $(\varphi \rightarrow \psi)$ e $(\varphi \wedge \psi)$ medem $2a + 1$ , $2a + 2b + 3$ , $4a + 2b + 5$ e $8a + 8b + 15$ ; duas formalizações de comprimentos distintos são fórmulas distintas.
  Usa: 13. Definição por recursão. Demonstrado em: Formalização da linguagem natural.
2. Escopo e fórmulas distintas. Os agrupamentos $((p \wedge q) \vee r)$ e $(p \wedge (q \vee r))$ são cadeias distintas: se coincidissem, a leitura única, aplicada duas vezes, obrigaria a variável $r$ a coincidir com a fórmula composta $(p \wedge q)$ .
  Usa: 6. Forma das fórmulas. Apoia-se em: G (Leitura única). Demonstrado em: Formalização da linguagem natural.
3. Condicional material. A implicação $(\varphi \rightarrow \psi)$ , que abrevia $(\neg\varphi \vee \psi)$ , é falsa somente quando $\varphi$ é verdadeira e $\psi$ falsa; é a única leitura, dependente apenas da verdade das partes, que torna verdadeiros os teoremas condicionais da matemática.
  Apoia-se em: H (Leitura da negação conjunta). Demonstrado em: Formalização da linguagem natural.

Rumo à dedução. A cadeia se detém onde a linguagem está construída e os argumentos estão formalizados como um conjunto de premissas e uma conclusão. Resta decidir quando uma fórmula se segue de outras: primeiro manipulando símbolos com regras, na unidade seguinte, e depois atendendo à sua verdade.