Dedução: síntese e desafios

Resumo

Esta aula encerra a unidade dedicada à dedução. Reconstrói a cadeia dedutiva que vai da definição do sistema de Łukasiewicz (três esquemas de axiomas e o modus ponens) ao teorema da dedução e ao limite desse sistema na língua da negação conjunta; daí às quatro técnicas básicas e à regra da substituição da dupla negação, que completa o sistema do curso; do lema fundamental da negação conjunta à substituição de equivalentes e às simetrias, e daí às regras da lógica clássica e às leis de De Morgan e às leis distributivas, indicando em cada elo que resultados usa e em que aula se demonstra. Distingue o que a unidade demonstrou do que admitiu, situa o que foi alcançado em relação ao plano do curso e explica por que a pergunta que a unidade deixa aberta, a de saber se o dedutível coincide com o verdadeiro, conduz à unidade de semântica. 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 os resultados anteriores em que cada um se apoia e a aula em que se demonstra.
Explicar como se encadeiam o teorema da dedução, a dupla negação, a regra da substituição da dupla negação, a contraposição, o lema fundamental e a substituição de equivalentes, e por que deles dependem as regras clássicas, as leis de De Morgan e as leis distributivas.
Distinguir o que a unidade demonstrou do que admitiu (os esquemas de axiomas, as duas regras primitivas, a indução forte, a estrutural e a leitura única) e do que deixou para as unidades seguintes, em particular a relação entre dedução e verdade.
Resolver problemas que combinam as marcas, a regra da substituição da dupla negação, o teorema da dedução, a prova por casos, a redução ao absurdo, a substituição de equivalentes, as leis de De Morgan e as leis distributivas.

O que a unidade alcançou

A unidade se propôs dotar a linguagem da unidade anterior de um sistema dedutivo, isto é, de um modo puramente sintático de obter fórmulas a partir de outras, e demonstrar com esse sistema, linha por linha, as técnicas com que a matemática raciocina. O propósito foi cumprido com algumas poucas ressalvas, cada uma declarada em seu lugar: os três esquemas de axiomas e as duas regras primitivas, que não se demonstram, mas se escolhem, e cuja escolha acertada é uma pergunta que a unidade coloca sem respondê-la de todo; a indução forte e a estrutural, a leitura única e a definição por recursão, que se demonstraram na unidade anterior e aqui se usam; e o indispensável da teoria dos conjuntos (subconjuntos, uniões e conjuntos finitos), que se recordou onde foi necessário. Com essas ressalvas, o caminho percorrido pode ser lido como uma única cadeia dedutiva em quatro trechos.

O sistema de Łukasiewicz e seu limite

A aula sobre os sistemas dedutivos formais definiu um sistema como uma linguagem, alguns axiomas e algumas regras, todos eles verificáveis olhando apenas as cadeias, e fixou a primeira etapa do sistema do curso, o sistema de Łukasiewicz: os esquemas A1, A2 e A3 e o modus ponens como regra única, que a leitura única torna aplicável sem ambiguidade. Definiu a dedução a partir de um conjunto $\Gamma$ de premissas e a relação $\Gamma \vdash \varphi$ , deduziu $\vdash (\varphi \rightarrow \varphi)$ em cinco linhas e demonstrou as propriedades estruturais: reflexividade, monotonicidade, modus ponens entre deduções, corte e finitude. Com elas e com a indução forte sobre o número de linhas demonstrou o teorema da dedução, cujo segundo caso exige ter deduzido antes $(\varphi \rightarrow \varphi)$ , e sua recíproca; deles obteve a equivalência demonstrável, reflexiva, simétrica e transitiva. Por fim, estabeleceu o limite desse sistema: uma marca de $0$ e $1$ , definida por recursão sobre a forma primitiva $(\alpha \downarrow \beta)$ , trata a negação e a implicação como sempre, é conservada por A1, A2, A3 e pelo modus ponens, e deixa livre o valor de fórmulas como $(v_{1} \downarrow v_{2})$ . Disso decorre que $((v_{1} \downarrow v_{2}) \rightarrow \neg v_{1})$ não é teorema do sistema de Łukasiewicz, e que de $(v_{1} \downarrow v_{2})$ não se deduz $(\neg\neg v_{1} \downarrow v_{2})$ , nem o inverso. Como toda marca dá o mesmo valor a $\theta$ e a $\neg\neg\theta$ , a aula advertiu ainda que nem sequer a dupla negação, uma vez demonstrada, remediaria esse limite.

As quatro técnicas e a regra nova

A aula sobre as quatro técnicas de dedução demonstrou primeiro o lema “do resultado à regra”: se $\{\alpha_{1}, \ldots, \alpha_{n}\} \vdash \beta$ , a mesma conclusão se obtém a partir de qualquer $\Gamma$ que deduza as $\alpha_{i}$ , e além disso $\vdash (\alpha_{1} \rightarrow (\alpha_{2} \rightarrow \cdots (\alpha_{n} \rightarrow \beta) \cdots))$ . Esse lema é o que permite usar cada técnica em três apresentações (a partir de premissas, como teorema e como regra), e as aulas sobre as simetrias e sobre De Morgan, que reúnem cadeias de equivalências com o corte, apoiam-se para isso nas propriedades da equivalência demonstrável da primeira aula, que são a mesma ideia aplicada a uma única premissa; na cadeia cada resultado figura uma só vez, onde se demonstra. Com ele, a aula deduziu o silogismo hipotético a partir de A1 e A2 em sete linhas, o intercâmbio de premissas com o teorema da dedução, a dupla negação (cuja primeira direção aplica A3 duas vezes a uma implicação fabricada com A1, e cuja segunda aplica a primeira a $\neg\varphi$ e A3) e a contraposição em suas três formas, que repartem de três maneiras as negações de uma implicação; as quatro já valem no sistema de Łukasiewicz.

Demonstrada a dupla negação, a aula completou o sistema do curso com uma segunda regra primitiva, a substituição da dupla negação (SDN): de $\chi$ infere-se $\chi'$ quando $\chi'$ resulta de substituir em $\chi$ uma ocorrência de uma subfórmula $\theta$ por $\neg\neg\theta$ , ou uma de $\neg\neg\theta$ por $\theta$ . A regra deve ser postulada, porque a marca $m_{1}$ dá $1$ aos teoremas da dupla negação e, no entanto, separa $(v_{1} \downarrow v_{2})$ de $(\neg\neg v_{1} \downarrow v_{2})$ ; a SDN não conserva $m_{1}$ , e por isso amplia o dedutível, mas conserva a marca honesta, e por isso não o amplia demais. A regra age sobre a cadeia da língua base, onde uma negação duplica seu argumento: $(\varphi \rightarrow \psi)$ contém duas vezes a subfórmula $\neg\varphi$ , e pôr uma dupla negação diante de seu antecedente exige duas aplicações. Essa mesma observação sustenta a extensão do teorema da dedução: se uma linha se obtém pela regra, a hipótese de indução dá a implicação cujo consequente é a linha anterior, e duas aplicações da regra, uma em cada cópia desse consequente, dão a implicação procurada; as demais propriedades estruturais valem com a mesma demonstração. As primeiras consequências são que uma fórmula equivale a toda fórmula que resulte dela pela regra, em particular $(\varphi \downarrow \psi) \dashv\vdash (\neg\neg\varphi \downarrow \psi)$ e $(\varphi \downarrow \psi) \dashv\vdash (\varphi \downarrow \neg\neg\psi)$ , e que as implicações correspondentes, que outros sistemas tomam como axiomas, são aqui teoremas.

Conectivos e substituição

A aula sobre as simetrias dos conectivos enfrentou a dificuldade própria da língua de círculos e discos: os axiomas de Łukasiewicz só falam de negações e de implicações, e quase nenhuma negação conjunta é uma coisa ou outra. O lema fundamental, $(\varphi \downarrow \psi) \dashv\vdash \neg(\neg\varphi \rightarrow \psi)$ , lança a ponte: como $\neg(\neg\varphi \rightarrow \psi)$ é $\neg\neg(\neg\neg\varphi \downarrow \psi)$ , a regra SDN põe a dupla negação interior e a dupla negação, a exterior; em sentido inverso, a dupla negação e a regra as retiram. Com ele, a substituição de equivalentes, demonstrada primeiro sob a negação e dos dois lados da implicação com a contraposição e o silogismo hipotético, estendeu-se aos dois argumentos da negação conjunta e, daí, à disjunção e à conjunção. A regra e a substituição não se tornam supérfluas uma à outra: a regra só intercambia $\theta$ e $\neg\neg\theta$ , ao passo que a substituição admite equivalentes quaisquer; e a substituição, demonstrada com o lema fundamental, apoia-se por sua vez na regra. A aula demonstrou depois que as formas que outros textos tomam por definições são equivalências: $(\varphi \vee \psi) \dashv\vdash (\neg\varphi \rightarrow \psi)$ , que exige duas aplicações da regra, uma em cada cópia que a negação exterior cria, e $(\varphi \wedge \psi) \dashv\vdash (\neg\varphi \downarrow \neg\psi)$ , que exige a dupla negação; em contrapartida, $(\varphi \wedge \psi)$ e $\neg(\varphi \rightarrow \neg\psi)$ são a mesma cadeia. Por fim, demonstrou as cinco simetrias na ordem que as definições impõem: a da negação conjunta com o lema fundamental e a contraposição, e cada uma das demais com a anterior, levada com a substituição sob a negação quando é necessário.

As regras clássicas e as leis

A aula sobre as técnicas da lógica clássica demonstrou, todas com um conjunto $\Gamma$ de premissas que se arrasta de linha em linha, a introdução e a eliminação da disjunção e da conjunção, o terceiro excluído e a não contradição, a explosão, a redução ao absurdo em suas duas formas e a prova por casos, com uma fórmula e sua negação e com uma disjunção qualquer. A ordem das dependências é estrita: a explosão apoia-se nas regras da disjunção; a redução ao absurdo clássica, na explosão e em A3; a prova por casos, na contraposição e na redução ao absurdo. Nenhuma dessas demonstrações invoca a regra SDN diretamente: a regra age por meio das formas equivalentes e da substituição de equivalentes. A aula sobre as leis de De Morgan e as leis distributivas pôs essas regras para trabalhar juntas: a primeira lei de De Morgan resulta da definição da conjunção e da dupla negação; a segunda exige entrar na negação conjunta, onde a regra SDN intervém duas vezes, uma em cada argumento e sem necessidade da simetria, e dela decorre que $(\varphi \downarrow \psi)$ equivale a $(\neg\varphi \wedge \neg\psi)$ , a leitura “nem $\varphi$ nem $\psi$ ” que a unidade anterior havia estipulado; as variantes incluem $\neg(\varphi \rightarrow \psi) \dashv\vdash (\varphi \wedge \neg\psi)$ . As duas leis distributivas foram demonstradas em seus dois sentidos por casos, escolhendo em cada um a forma da prova por casos que convém.

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 e os instrumentos 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 esta cadeia não demonstra (os esquemas de axiomas, que se admitem, e os instrumentos da unidade anterior), que se desenham como anéis. A regra da substituição da dupla negação, embora também se admita sem demonstração, figura unida ao elo que a introduz, porque ali se explica por que deve ser postulada. 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 teorema da dedução e a dupla negação são, depois dos axiomas, os apoios mais visitados da unidade, e que a regra nova sustenta tudo o que a unidade diz da negação conjunta: o teorema da dedução ampliado, o lema fundamental, as formas equivalentes e a segunda lei de De Morgan.

Apoios da cadeia

ALeitura única e recursão. Se $\sigI\varphi\psi = \sigI\varphi'\psi'$ , sendo as quatro cadeias fórmulas, então $\varphi = \varphi'$ e $\psi = \psi'$ ; donde uma regra que calcula o valor de $\sigI\varphi\psi$ a partir de $\varphi$ , de $\psi$ e de seus valores define uma única função sobre as fórmulas. Demonstrou-se na unidade anterior. Admitido sem demonstração nesta unidade.
BIndução forte. Se uma propriedade vale para um natural sempre que vale para todos os menores, vale para todos os naturais. Deduziu-se da indução simples na unidade anterior, e aqui se aplica ao número de linhas de uma dedução. Admitido sem demonstração nesta unidade.
CAxiomas de Łukasiewicz. Os esquemas A1, $(\varphi \rightarrow (\psi \rightarrow \varphi))$ ; A2, $((\varphi \rightarrow (\psi \rightarrow \chi)) \rightarrow ((\varphi \rightarrow \psi) \rightarrow (\varphi \rightarrow \chi)))$ ; e A3, $((\neg\psi \rightarrow \neg\varphi) \rightarrow (\varphi \rightarrow \psi))$ . Admitem-se. Admitido sem demonstração nesta unidade.
DSubstituição da dupla negação. Segunda regra primitiva do sistema do curso: de $\chi$ infere-se $\chi'$ 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$ . Postula-se depois de demonstrar a dupla negação. Estabelecido em: 8. Substituição da dupla negação.
ETeorema da dedução. $\Gamma \cup \{\varphi\} \vdash \psi$ se e somente se $\Gamma \vdash (\varphi \rightarrow \psi)$ ; demonstra-se no sistema de Łukasiewicz e vale, com um caso a mais, no sistema do curso. Estabelecido em: 3. Teorema da dedução e equivalência demonstrável.
FDo resultado à regra. Se $\{\alpha_{1}, \ldots, \alpha_{n}\} \vdash \beta$ e $\Gamma \vdash \alpha_{i}$ para cada $i$ , então $\Gamma \vdash \beta$ : toda técnica demonstrada a partir de premissas se aplica sob qualquer conjunto de premissas. Estabelecido em: 5. Do resultado à regra.
GDupla negação. $\varphi \dashv\vdash \neg\neg\varphi$ , com os teoremas $\vdash (\neg\neg\varphi \rightarrow \varphi)$ e $\vdash (\varphi \rightarrow \neg\neg\varphi)$ . Estabelecido em: 7. Dupla negação.
HSubstituição de equivalentes. Se $\varphi \dashv\vdash \varphi'$ , pode-se pôr $\varphi'$ no lugar de $\varphi$ sob uma negação, dos dois lados de uma implicação, de uma negação conjunta, de uma disjunção e de uma conjunção, sem alterar a equivalência. Estabelecido em: 12. Substituição de equivalentes.

Trecho 1 O sistema de Łukasiewicz e seu limite
- Reconhecer as instâncias dos esquemas e decidir se uma sequência de fórmulas é uma dedução a partir de um conjunto de premissas.
- Demonstrar as propriedades estruturais da dedução e o teorema da dedução por indução forte sobre o número de linhas.
- Construir deduções sobre deduções com reflexividade, monotonicidade, corte, o teorema da dedução e sua recíproca.
- Demonstrar que uma fórmula não se deduz por meio de uma marca que os axiomas e o modus ponens conservam, e explicar com ela o limite do sistema de Łukasiewicz.
1. Sistema, dedução e identidade. Os axiomas do sistema de Łukasiewicz são as instâncias uniformes de A1 a A3, e sua regra única é o modus ponens. $\Gamma \vdash \varphi$ se existe uma sequência finita de fórmulas que termina em $\varphi$ , cada uma axioma, elemento de $\Gamma$ ou obtida por modus ponens de duas anteriores. O primeiro teorema, $\vdash (\varphi \rightarrow \varphi)$ , deduz-se em cinco linhas com A1 e A2.
  Apoia-se em: A (Leitura única e recursão), C (Axiomas de Łukasiewicz). Demonstrado em: Sistemas dedutivos formais.
2. Propriedades estruturais. Se $\varphi \in \Gamma$ , $\Gamma \vdash \varphi$ ; se $\Gamma \subseteq \Delta$ e $\Gamma \vdash \varphi$ , $\Delta \vdash \varphi$ ; de $\Gamma \vdash \varphi$ e $\Gamma \vdash (\varphi \rightarrow \psi)$ decorre $\Gamma \vdash \psi$ ; se $\Gamma \vdash \varphi_{i}$ para cada $i$ e $\Gamma \cup \{\varphi_{1}, \ldots, \varphi_{r}\} \vdash \psi$ , $\Gamma \vdash \psi$ ; e se $\Gamma \vdash \varphi$ , algum subconjunto finito de $\Gamma$ basta.
  Usa: 1. Sistema, dedução e identidade. Demonstrado em: Sistemas dedutivos formais.
3. Teorema da dedução e equivalência demonstrável. $\Gamma \cup \{\varphi\} \vdash \psi$ se e somente se $\Gamma \vdash (\varphi \rightarrow \psi)$ , por indução forte sobre o número de linhas, com A1, A2 e a identidade. Disso, a equivalência demonstrável, $\varphi \dashv\vdash \psi$ , é reflexiva, simétrica e transitiva, e duas fórmulas equivalentes se deduzem dos mesmos conjuntos.
  Usa: 1. Sistema, dedução e identidade, 2. Propriedades estruturais. Apoia-se em: B (Indução forte), C (Axiomas de Łukasiewicz). Demonstrado em: Sistemas dedutivos formais.
4. Limite do sistema de Łukasiewicz. Uma marca de $0$ e $1$ definida por recursão satisfaz $m(\neg\varphi) = 1 - m(\varphi)$ e $m((\varphi \rightarrow \psi)) = 1 - m(\varphi) \left( 1 - m(\psi) \right)$ , e A1, A2, A3 e o modus ponens conservam a marca $1$ ; donde $((v_{1} \downarrow v_{2}) \rightarrow \neg v_{1})$ não é teorema do sistema de Łukasiewicz, e $\{(v_{1} \downarrow v_{2})\} \nvdash (\neg\neg v_{1} \downarrow v_{2})$ , nem o inverso. Como toda marca dá $1$ à dupla negação, a substituição deve ser postulada.
  Usa: 1. Sistema, dedução e identidade. Apoia-se em: A (Leitura única e recursão), B (Indução forte), C (Axiomas de Łukasiewicz). Demonstrado em: Sistemas dedutivos formais.
Trecho 2 As quatro técnicas e a regra nova
- Converter um resultado a partir de premissas em um teorema e em uma regra aplicável sob qualquer conjunto de premissas.
- Encadear implicações, reordenar antecedentes, pôr e retirar duplas negações e escolher a forma da contraposição que corresponde a cada implicação.
- Aplicar a regra da substituição da dupla negação, localizando as ocorrências que as abreviaturas ocultam e repetindo-a em cada cópia que uma negação cria.
- Explicar com a marca por que a regra é postulada, e demonstrar que o teorema da dedução vale com ela.
1. Do resultado à regra. Se $\{\alpha_{1}, \ldots, \alpha_{n}\} \vdash \beta$ , então de $\Gamma \vdash \alpha_{1}$ , $\ldots$ , $\Gamma \vdash \alpha_{n}$ decorre $\Gamma \vdash \beta$ , e $\vdash (\alpha_{1} \rightarrow (\alpha_{2} \rightarrow \cdots (\alpha_{n} \rightarrow \beta) \cdots))$ ; em particular, se $\alpha \dashv\vdash \alpha'$ , $\Gamma \vdash \alpha$ se e somente se $\Gamma \vdash \alpha'$ .
  Usa: 2. Propriedades estruturais. Apoia-se em: E (Teorema da dedução). Demonstrado em: Quatro técnicas de dedução.
2. Silogismo hipotético e intercâmbio. $\{(\varphi \rightarrow \psi), (\psi \rightarrow \chi)\} \vdash (\varphi \rightarrow \chi)$ , com uma dedução de sete linhas a partir de A1 e A2; e $\{(\varphi \rightarrow (\psi \rightarrow \chi))\} \vdash (\psi \rightarrow (\varphi \rightarrow \chi))$ .
  Usa: 1. Sistema, dedução e identidade. Apoia-se em: C (Axiomas de Łukasiewicz), E (Teorema da dedução), F (Do resultado à regra). Demonstrado em: Quatro técnicas de dedução.
3. Dupla negação. $\vdash (\neg\neg\varphi \rightarrow \varphi)$ , aplicando A3 duas vezes a uma implicação que A1 fabrica a partir de $\neg\neg\varphi$ ; $\vdash (\varphi \rightarrow \neg\neg\varphi)$ , aplicando o anterior a $\neg\varphi$ e A3; donde $\varphi \dashv\vdash \neg\neg\varphi$ , já no sistema de Łukasiewicz.
  Apoia-se em: C (Axiomas de Łukasiewicz), E (Teorema da dedução). Demonstrado em: Quatro técnicas de dedução.
4. Substituição da dupla negação. Postula-se a regra SDN, porque a marca dá $1$ à dupla negação e não à substituição dentro de uma negação conjunta. Se $\chi'$ resulta de $\chi$ pela regra, $\chi \dashv\vdash \chi'$ ; em particular, $(\varphi \downarrow \psi) \dashv\vdash (\neg\neg\varphi \downarrow \psi)$ e $(\varphi \downarrow \psi) \dashv\vdash (\varphi \downarrow \neg\neg\psi)$ .
  Usa: 3. Teorema da dedução e equivalência demonstrável, 4. Limite do sistema de Łukasiewicz. Apoia-se em: G (Dupla negação). Demonstrado em: Quatro técnicas de dedução.
5. Teorema da dedução no sistema do curso. Reflexividade, monotonicidade, corte e finitude valem com a regra nova, e também $\Gamma \cup \{\varphi\} \vdash \psi$ se e somente se $\Gamma \vdash (\varphi \rightarrow \psi)$ : no caso novo, como $(\varphi \rightarrow \chi)$ é $((\neg\varphi \downarrow \chi) \downarrow (\neg\varphi \downarrow \chi))$ , a regra se aplica duas vezes, uma em cada cópia de $\chi$ . Disso, $\vdash ((\varphi \downarrow \psi) \rightarrow (\neg\neg\varphi \downarrow \psi))$ e sua recíproca são teoremas.
  Usa: 2. Propriedades estruturais, 3. Teorema da dedução e equivalência demonstrável. Apoia-se em: B (Indução forte), D (Substituição da dupla negação). Demonstrado em: Quatro técnicas de dedução.
6. Contraposição. $(\varphi \rightarrow \psi) \dashv\vdash (\neg\psi \rightarrow \neg\varphi)$ , $(\neg\varphi \rightarrow \psi) \dashv\vdash (\neg\psi \rightarrow \varphi)$ e $(\varphi \rightarrow \neg\psi) \dashv\vdash (\psi \rightarrow \neg\varphi)$ : os membros mudam de lado, e cada um muda de sinal ao passar.
  Usa: 6. Silogismo hipotético e intercâmbio. Apoia-se em: C (Axiomas de Łukasiewicz), E (Teorema da dedução), G (Dupla negação), F (Do resultado à regra). Demonstrado em: Quatro técnicas de dedução.
Trecho 3 Conectivos e substituição
- Desdobrar as abreviaturas para decidir se duas expressões designam a mesma cadeia ou fórmulas cuja equivalência exige uma dedução.
- Traduzir a negação conjunta para a negação e a implicação com o lema fundamental.
- Levar uma equivalência ao interior de uma fórmula com a substituição de equivalentes, distingui-la da regra da substituição da dupla negação e encadear equivalências.
- Demonstrar as cinco simetrias na ordem que as definições impõem.
1. Lema fundamental. $(\varphi \downarrow \psi) \dashv\vdash \neg(\neg\varphi \rightarrow \psi)$ : como $\neg(\neg\varphi \rightarrow \psi)$ é $\neg\neg(\neg\neg\varphi \downarrow \psi)$ , a regra SDN põe a dupla negação interior e a dupla negação, a exterior; em sentido inverso, a dupla negação e a regra as retiram.
  Apoia-se em: D (Substituição da dupla negação), G (Dupla negação). Demonstrado em: As simetrias dos conectivos.
2. Substituição de equivalentes. Se $\varphi \dashv\vdash \varphi'$ , então $\neg\varphi \dashv\vdash \neg\varphi'$ , $(\varphi \rightarrow \psi) \dashv\vdash (\varphi' \rightarrow \psi)$ e $(\psi \rightarrow \varphi) \dashv\vdash (\psi \rightarrow \varphi')$ ; com o lema fundamental, o mesmo dos dois lados da negação conjunta, e daí, da disjunção e da conjunção. Diferentemente da regra SDN, admite equivalentes quaisquer.
  Usa: 6. Silogismo hipotético e intercâmbio, 10. Contraposição, 11. Lema fundamental. Apoia-se em: E (Teorema da dedução). Demonstrado em: As simetrias dos conectivos.
3. Formas equivalentes. $(\varphi \vee \psi) \dashv\vdash (\neg\varphi \rightarrow \psi)$ , com duas aplicações da regra SDN, uma em cada cópia que a negação exterior cria; $(\varphi \wedge \psi) \dashv\vdash (\neg\varphi \downarrow \neg\psi)$ , pela dupla negação; e $(\varphi \wedge \psi)$ é a mesma cadeia que $\neg(\varphi \rightarrow \neg\psi)$ .
  Apoia-se em: D (Substituição da dupla negação), G (Dupla negação). Demonstrado em: As simetrias dos conectivos.
4. As cinco simetrias. $(\varphi \downarrow \psi) \dashv\vdash (\psi \downarrow \varphi)$ , pelo lema fundamental e pela contraposição; dela, sucessivamente, as simetrias de $\vee$ , $\wedge$ , $\leftrightarrow$ e $\veebar$ , cada uma com a anterior, levada com a substituição sob a negação quando é necessário.
  Usa: 11. Lema fundamental, 10. Contraposição. Apoia-se em: H (Substituição de equivalentes). Demonstrado em: As simetrias dos conectivos.
Trecho 4 As regras clássicas e as leis
- Demonstrar com premissas a introdução e a eliminação da disjunção e da conjunção, o terceiro excluído e a não contradição.
- Demonstrar a explosão, a redução ao absurdo e a prova por casos com premissas, e explicar por que não bastam sem elas.
- Demonstrar por dedução as leis de De Morgan, suas variantes e as leis distributivas em seus dois sentidos.
- Transformar fórmulas em formas normais simples por meio de cadeias de equivalências justificadas.
1. Regras dos conectivos. Com qualquer $\Gamma$ : de $\varphi$ decorre $(\varphi \vee \psi)$ ; de $(\varphi \vee \psi)$ e $\neg\varphi$ , $\psi$ ; de $\varphi$ e $\psi$ , $(\varphi \wedge \psi)$ ; de $(\varphi \wedge \psi)$ , $\varphi$ e $\psi$ ; além disso, $\vdash (\varphi \vee \neg\varphi)$ e $\vdash \neg(\varphi \wedge \neg\varphi)$ .
  Usa: 1. Sistema, dedução e identidade, 2. Propriedades estruturais, 6. Silogismo hipotético e intercâmbio, 10. Contraposição, 13. Formas equivalentes, 14. As cinco simetrias. Apoia-se em: C (Axiomas de Łukasiewicz), E (Teorema da dedução), F (Do resultado à regra), G (Dupla negação). Demonstrado em: As técnicas da lógica clássica.
2. Explosão e redução ao absurdo. Se $\Gamma \vdash \varphi$ e $\Gamma \vdash \neg\varphi$ , então $\Gamma \vdash \psi$ para toda $\psi$ ; se $\Gamma \cup \{\neg\varphi\}$ deduz $\psi$ e $\neg\psi$ , então $\Gamma \vdash \varphi$ ; e se $\Gamma \cup \{\varphi\}$ as deduz, $\Gamma \vdash \neg\varphi$ .
  Usa: 1. Sistema, dedução e identidade, 2. Propriedades estruturais, 15. Regras dos conectivos. Apoia-se em: C (Axiomas de Łukasiewicz), E (Teorema da dedução), G (Dupla negação). Demonstrado em: As técnicas da lógica clássica.
3. Prova por casos. Se $\Gamma \cup \{\varphi\} \vdash \psi$ e $\Gamma \cup \{\neg\varphi\} \vdash \psi$ , então $\Gamma \vdash \psi$ ; e se $\Gamma \cup \{\varphi\} \vdash \chi$ , $\Gamma \cup \{\psi\} \vdash \chi$ e $\Gamma \vdash (\varphi \vee \psi)$ , então $\Gamma \vdash \chi$ .
  Usa: 2. Propriedades estruturais, 10. Contraposição, 15. Regras dos conectivos, 16. Explosão e redução ao absurdo. Apoia-se em: E (Teorema da dedução). Demonstrado em: As técnicas da lógica clássica.
4. Leis de De Morgan. $\neg(\varphi \wedge \psi) \dashv\vdash (\neg\varphi \vee \neg\psi)$ , pela definição e pela dupla negação; $\neg(\varphi \vee \psi) \dashv\vdash (\neg\varphi \wedge \neg\psi)$ , com uma aplicação da regra SDN em cada argumento da negação conjunta; donde $(\varphi \downarrow \psi) \dashv\vdash (\neg\varphi \wedge \neg\psi)$ e $\neg(\varphi \rightarrow \psi) \dashv\vdash (\varphi \wedge \neg\psi)$ .
  Apoia-se em: D (Substituição da dupla negação), G (Dupla negação), H (Substituição de equivalentes). Demonstrado em: Leis de De Morgan e leis distributivas.
5. Leis distributivas. $(\varphi \wedge (\psi \vee \chi)) \dashv\vdash ((\varphi \wedge \psi) \vee (\varphi \wedge \chi))$ e $(\varphi \vee (\psi \wedge \chi)) \dashv\vdash ((\varphi \vee \psi) \wedge (\varphi \vee \chi))$ , cada uma em seus dois sentidos por casos; com as simetrias, também pela direita.
  Usa: 14. As cinco simetrias, 15. Regras dos conectivos, 17. Prova por casos. Apoia-se em: H (Substituição de equivalentes). Demonstrado em: Leis de De Morgan e leis distributivas.

Rumo à semântica. A cadeia se detém onde a dedução alcança todas as técnicas com que a matemática raciocina. Resta saber se o que se deduz é exatamente o que é verdadeiro em toda valoração: a unidade seguinte definirá a verdade, e a última comparará ambas as noções.

As abreviaturas das justificativas

As deduções da unidade justificam cada linha com uma abreviatura, a mesma em todas as aulas. Reúnem-se aqui, ordenadas pela aula que as introduz. “Premissa” designa uma hipótese do enunciado e, nas deduções sobre deduções, uma hipótese da regra que se demonstra. Os números entre parênteses citam as linhas às quais a regra se aplica; uma equivalência já demonstrada cita-se sem número quando se escreve como linha, e com o número da linha que transforma quando se aplica a essa linha, também a uma de suas partes com “Subst”.

Primeira aula: A1, A2 e A3 (os esquemas de axiomas); MP $(i, j)$ (modus ponens); Def (desdobramento ou recolhimento de uma abreviatura, com o conectivo que se desdobra: “Def $\vee$ ”, “Def $\dashv\vdash$ ”); Id (identidade, o teorema $\vdash (\varphi \rightarrow \varphi)$ ); Refl (reflexividade: se $\varphi \in \Gamma$ , então $\Gamma \vdash \varphi$ ); Mon (monotonicidade); Corte (o que foi deduzido pode ser usado como premissa); Fin (finitude); TD (teorema da dedução) e RTD (sua recíproca).
Segunda aula: SH (silogismo hipotético); IP (intercâmbio de premissas); DN (dupla negação); SDN $(i)$ (substituição da dupla negação na linha $i$ ; SDN sem número cita a equivalência entre uma fórmula e a que resulta dela pela regra); CP (contraposição, em qualquer de suas três formas); “Resolvido $n$ ” (um resultado do problema resolvido $n$ da mesma aula, escrito como linha).
Terceira aula: LF (lema fundamental, $(\varphi \downarrow \psi) \dashv\vdash \neg(\neg\varphi \rightarrow \psi)$ ); Subst (substituição de equivalentes, em qualquer de suas formas, seguida da equivalência que se aplica: “Subst, DM $(i)$ ”); Eq (formas equivalentes da disjunção e da conjunção, $(\varphi \vee \psi) \dashv\vdash (\neg\varphi \rightarrow \psi)$ e $(\varphi \wedge \psi) \dashv\vdash (\neg\varphi \downarrow \neg\psi)$ ); Sim (simetria de um conectivo).
Quarta aula: $\vee$ I e $\vee$ E (introdução e eliminação da disjunção); $\wedge$ I e $\wedge$ E (introdução e eliminação da conjunção); TE (terceiro excluído); NC (não contradição; a abreviatura nomeia o teorema, mas não justifica nenhuma linha da unidade); Exp (explosão); Casos $(i, j)$ e Casos $(i, j, k)$ (prova por casos, com uma fórmula e sua negação ou com uma disjunção); “Casos sem premissas” (a prova por casos sem conjunto $\Gamma$ , que só aparece em um problema); RA (redução ao absurdo, em suas duas formas).
Quinta aula: DM (leis de De Morgan); Dist (distributividade); Assoc (associatividade da disjunção); Instância $(i)$ (a linha $i$ , que vale para fórmulas quaisquer, escrita de novo com outras fórmulas no lugar de suas metavariáveis; indica-se a troca).
Desafios desta aula: M3 (o esquema que o terceiro desafio põe no lugar de A3).