Español
English
中文 (中国)
العربية
हिन्दी
Русский
Français
Deutsch
Ελληνικά
Italiano
日本語
한국어
LatineResumo
Esta aula abre a segunda unidade do curso, dedicada à dedução. Apresenta suas cinco aulas e o fio que as une, desde a definição de um sistema dedutivo formal até as leis de De Morgan e as leis distributivas; situa a unidade no caminho do curso, entre a linguagem, já construída, e a semântica e a metateoria, que virão, e antecipa o que estas dirão dela; justifica a escolha de um sistema axiomático, que se constrói em duas etapas (o sistema de Łukasiewicz, com três esquemas de axiomas e o modus ponens, e o sistema do curso, que lhe acrescenta a regra da substituição da dupla negação), e explica por que essa segunda regra é necessária e por que é postulada em vez de demonstrada; mostra com uma dedução breve quanto trabalho esconde um raciocínio elementar; precisa o que se toma da unidade anterior, que é a leitura única, a indução (a forte sobre os naturais e a estrutural) e o desdobramento das abreviaturas, e dá conselhos para estudá-la.
Objetivos de aprendizagem
- Descrever a sequência das cinco aulas da unidade e explicar que resultados de cada uma a seguinte usa.
- Situar a dedução no percurso do curso, distinguir a dedutibilidade da consequência semântica e explicar o que afirmarão a correção e a completude.
- Explicar por que o sistema do curso acrescenta ao de Łukasiewicz uma segunda regra primitiva, a substituição da dupla negação, a partir do que os três esquemas podem e não podem ver numa negação conjunta.
- Ler uma dedução breve por linhas numeradas, distinguir a dedução de fórmulas da dedução sobre deduções, reconhecer o que a unidade toma da anterior e organizar seu estudo a partir da avaliação de entrada.
Avaliação de entrada
Antes de percorrer a unidade, convém medir o ponto de partida. Esta avaliação é uma autoavaliação: não se pontua, e seu único propósito é orientar o estudo. Suas treze perguntas são de dois tipos. As três primeiras tratam do que a unidade dá por sabido da anterior: a leitura única, a indução forte e o desdobramento das abreviaturas; quem errar alguma deve rever, antes de seguir, a aula que a pergunta nomeia. As dez restantes tratam, em ordem, das cinco aulas desta unidade: três da primeira, três da segunda, duas da terceira, uma da quarta e uma da quinta. Quem nunca estudou um sistema dedutivo não deve esperar acertá-las, e isso não importa: cada resposta, certa ou não, explica o ponto e nomeia a aula que o trata. As mesmas habilidades voltam a ser medidas no final, na aula de síntese.
Antes de começar a unidade, meça seu ponto de partida. É uma autoavaliação breve: não recebe nota e seu resultado fica guardado apenas no seu navegador.
Pergunta 1De unidades anterioresA cadeia é uma fórmula composta, da forma . Quais são seus componentes e ?
não é uma fórmula: um disco conectivo exige duas fórmulas em seguida, e aqui só o segue a variável ; seu peso acumulado é , não . Tampouco o resto, duas variáveis seguidas, é uma fórmula.O teorema da leitura única o exclui: se e os quatro componentes são fórmulas, então e . Um corte em outro lugar deixa pelo menos uma parte que não é fórmula.Uma fórmula composta tem dois componentes, e a cadeia vazia não é uma fórmula. Além disso, a cadeia que segue o disco inicial tem três variáveis e um só disco conectivo, e toda fórmula tem exatamente uma variável a mais que discos conectivos.Depois do disco inicial acumulam-se os pesos das palavras: o disco conectivo subtrai , e as variáveis e somam cada uma; o peso acumulado atinge pela primeira vez ao terminar , e ali termina . A fórmula é , e pela leitura única não admite outra decomposição: é isso que permite reconhecer sem ambiguidade o antecedente e o consequente de uma implicação ao aplicar o modus ponens.Revisar: Indução sobre os números naturais e sobre as fórmulas
Pergunta 2De unidades anterioresNuma demonstração por indução forte de que todo natural cumpre uma propriedade , o que se pode supor ao demonstrar ?
Essa é a hipótese da indução simples. Basta quando o caso se apoia só no anterior; quando se apoia em casos menores quaisquer, como o modus ponens nas linhas de uma dedução, é preciso supô-los todos.Inclui , que é o que se quer demonstrar: supô-lo torna o argumento circular.A indução forte não tem um caso base separado: ela o contém, porque para não há naturais menores e a hipótese não oferece nada. Só quando o argumento usa, por exemplo, , os primeiros casos devem ser tratados à parte.É a hipótese da indução forte. A unidade a usa para demonstrar o teorema da dedução: a última linha de uma dedução pode ser obtida por modus ponens de duas linhas anteriores quaisquer, não necessariamente da imediatamente anterior, e a hipótese deve alcançar ambas.Revisar: Indução sobre os números naturais e sobre as fórmulas
Pergunta 3De unidades anterioresCom as abreviaturas oficiais do curso, que fórmula designa , escrita com a negação conjunta e a negação?
Falta a negação exterior: a disjunção é a negação da negação conjunta, não a própria negação conjunta, que se lê “nem… nem”.Essa é a disjunção : na implicação, a negação interior recai sobre o antecedente, não sobre o consequente.Cada abreviatura é definida uma só vez e designa uma só cadeia, que o desdobramento determina. O que de fato ocorre é o inverso: uma mesma cadeia pode receber vários nomes.A implicação abrevia , e a disjunção abrevia a negação de uma negação conjunta; donde . A unidade desdobra assim as abreviaturas cada vez que precisa saber se duas expressões designam a mesma fórmula.Revisar: A linguagem da lógica proposicional
Pergunta 4O esquema A1 é . A fórmula é uma instância de A1?
Essa troca dá , não a fórmula proposta: a última ocorrência de também deve ser .A forma exterior não basta: o esquema exige, além disso, que o último componente repita o primeiro.As metavariáveis podem ser trocadas por fórmulas quaisquer, variáveis incluídas: é uma instância de A1.Uma instância troca cada metavariável de modo uniforme: todas as ocorrências de pela mesma fórmula. Metavariáveis distintas podem receber a mesma fórmula, mas uma mesma metavariável não pode receber duas.Revisar: Sistemas dedutivos formais
Pergunta 5Numa dedução já figuram as linhas e , em que e são fórmulas distintas. Que fórmula o modus ponens aplicado a essas duas linhas permite escrever?
Passar do consequente ao antecedente é a falácia de afirmar o consequente, não o modus ponens. A primeira aula prova, com uma marca que os axiomas e o modus ponens conservam, que não se deduz de de modo algum.É a recíproca da implicação escrita, e nenhuma regra a produz a partir dela: uma implicação não se inverte.Nada nas duas linhas fala da negação de ; o modus ponens só separa o consequente de uma implicação cujo antecedente já está escrito.De e obtém-se ; aqui já está escrita, e o modus ponens não autoriza a remontar a implicação.Revisar: Sistemas dedutivos formais
Pergunta 6Sabe-se que , isto é, que há uma dedução de cuja única premissa é . O que afirma então o teorema da dedução?
Suprimir a premissa muda o que se afirma: da premissa deduz-se , e não é um teorema. A premissa não desaparece; passa a ser o antecedente.Inverte o sentido: a premissa descarregada é o antecedente, e a conclusão, o consequente.As deduções não se percorrem ao contrário: da premissa deduz-se, com A1 e o modus ponens, para qualquer , e dessa implicação não se recupera .O teorema da dedução descarrega uma premissa e a converte em antecedente: se , então ; aqui é vazio. Demonstra-se por indução forte sobre o número de linhas.Revisar: Sistemas dedutivos formais
Pergunta 7O que se deduz, sem mais premissas, do conjunto ?
O modus ponens precisa do antecedente escrito, e não é uma premissa: de duas implicações obtém-se outra implicação, não uma fórmula solta.Encadeia em sentido inverso: as premissas vão de a e de a , e a cadeia não se percorre para trás.Afirmaria que se dão e , e as premissas não afirmam nenhuma das duas: só dizem o que se segue se se dá ou se se dá .É o silogismo hipotético: as implicações se encadeiam. Deduz-se em sete linhas com A1, A2 e o modus ponens, e a aula o converte numa regra aplicável sob qualquer conjunto de premissas.Revisar: Quatro técnicas de dedução
Pergunta 8A regra da substituição da dupla negação (SDN) muda, numa linha, uma só ocorrência de uma subfórmula, e atua sobre a cadeia da língua base. Quantas ocorrências da subfórmula contém a cadeia que designa?
Lê a abreviatura como se mostrasse toda a cadeia. A seta oculta a negação exterior, , que escreve duas vezes seu argumento.A implicação abrevia ; a negação de está na cadeia, embora a seta não a mostre, e a regra atua sobre a cadeia.Quatro seriam as cópias de um argumento sob duas negações seguidas, como em ; aqui há uma só negação exterior, que o duplica uma vez.Pelas definições oficiais, é , isto é, : a negação exterior duplica seu argumento. Segue-se que pôr uma dupla negação diante do antecedente exige duas aplicações da regra, uma em cada cópia; a segunda aula usa isso ao estender o teorema da dedução.Revisar: Quatro técnicas de dedução
Pergunta 9Que fórmula se obtém de por contraposição, sem acrescentar duplas negações?
É a recíproca: inverte o sentido sem mudar os sinais, e em geral não se deduz da fórmula dada.Muda os sinais sem inverter o sentido; tampouco se deduz, em geral, da fórmula dada.Mistura duas operações: nega ao passar, mas deixa como estava. A primeira forma da contraposição daria , com uma negação a mais.É a segunda forma da contraposição: os membros mudam de lado, e cada um muda de sinal ao passar; perde sua negação e a ganha. As duas fórmulas são demonstravelmente equivalentes.Revisar: Quatro técnicas de dedução
Pergunta 10 e designam a mesma fórmula?
A definição diz que é , não . Tomar uma pela outra é o erro que a unidade evita: em outros textos é uma definição; neste curso, um resultado.A leitura em português não decide a identidade de duas cadeias: ela se decide desdobrando as abreviaturas, e estas duas têm comprimentos distintos.São demonstravelmente equivalentes: a terceira aula o demonstra com duas aplicações da regra SDN, sem necessidade de outro instrumento.Ao desdobrar a implicação cujo antecedente é aparece no primeiro lugar da negação conjunta. Passar de uma fórmula à outra exige tirar ou pôr essa dupla negação dentro da negação conjunta, e é isso o que a regra SDN permite; como a negação exterior duplica seu argumento, a regra se aplica duas vezes, uma em cada cópia.Revisar: As simetrias dos conectivos
Pergunta 11Sabe-se que , isto é, que cada uma se deduz da outra. O que justifica que também ?
Negar ambos os lados não é uma regra do sistema, cujas únicas regras são o modus ponens e a substituição da dupla negação, que só intercambia uma subfórmula com . Que a operação seja legítima é um teorema, e é preciso demonstrá-lo.A definição diz que cadeia é , mas não relaciona com : duas fórmulas equivalentes não são a mesma cadeia, e suas negações tampouco.É verdade, e a unidade o demonstra; mais ainda, uma fórmula pode ser substituída por outra equivalente em qualquer lugar de qualquer fórmula.De obtém-se ; a contraposição dá , e a recíproca do teorema da dedução, ; o outro sentido é igual. Para a negação conjunta é preciso, além disso, o lema fundamental.Revisar: As simetrias dos conectivos
Pergunta 12Do conjunto de premissas deduzem-se uma fórmula e sua negação . O que se pode concluir?
Confunde a suposição com a conclusão: a contradição refuta a suposição , de modo que se conclui .Isso exigiria uma contradição deduzida só de . Aqui ela foi deduzida de , e pode dever-se à suposição acrescentada; de , sim, deduz-se qualquer fórmula, pela explosão.Ao contrário: que uma suposição conduza a uma contradição permite rejeitá-la. É o raciocínio pelo absurdo, presente em toda a matemática.É a redução ao absurdo em sua forma clássica: se supor junto com conduz a uma contradição, se deduz de . A quarta aula a demonstra com a explosão, o teorema da dedução, A3 e o teorema .Revisar: As técnicas da lógica clássica
Pergunta 13A que fórmula é equivalente a negação de uma implicação, ?
Nega cada membro sem tocar o conectivo. A negação de uma implicação não é outra implicação: a de “se chove, a rua se molha” não é “se não chove, a rua não se molha”, mas “chove e a rua não se molha”.Nega só o consequente. Se não se dá, tanto quanto se cumprem, e uma fórmula não pode cumprir-se ao mesmo tempo que sua negação.Inverte os papéis: uma implicação falha quando o antecedente se dá e o consequente não, não o contrário.Negar “se , então ” é afirmar que se dá e não se dá . A quinta aula o demonstra como uma variante das leis de De Morgan: é ; De Morgan dá , e a dupla negação, com a substituição de equivalentes, .
Carregando o conteúdo…