Lógica: uma introdução — parte 5

Introdução

Na parte 4 da nossa série sobre lógica, foi apresentado a sintaxe e a semântica da lógica de 1ª ordem e as diferenças que tinha com a lógica proposicional. Tratamos especialmente da sua semântica de estruturas e a noção de consequência semântica e suas propriedades, além de conhecer o novo símbolo de identidade (=).

Agora iremos retomar os conceitos de inferência e consequência sintática como apresentados na parte 3, mas aplicando-os à lógica de 1ª ordem.

1. Dedução natural

De maneira geral, a dedução natural com a lógica de 1ª ordem permanece a mesma, as regras são as mesmas para as fórmulas atômicas e moleculares. Podemos ver isso observando o seguinte argumento:

1. Pa⊃Qb
2. Pa∧¬Rab
3. Rab∨(Qb⊃Pa) ?(Pa⇔Qb)∧(Qb∨C)

Temos nossas premissas e a conclusão que desejamos alcançar. E, se recorda-se do processo que fizemos na parte 3, verá que não tem diferença alguma aqui no processo de dedução, como se vê a seguir:

1. Pa⊃Qb
2. Pa∧¬Rab
3. Rab∨(Qb⊃Pa) ?(Pa⇔Qb)∧(Qb∨C)
4. ¬Rab 2, sep.
5. Qb⊃Pa 3,4, S.D.
6. Pa 2, sep.
7. Qb 1,6, M.P.
8. Qb∨C 7, exp.
9. Pa⇔Qb 1,5, C.B.
10. .·. (Pa⇔Qb)∧(Qb∨C) 9,8, add.

Perceba que os passos são os mesmos de um argumento na lógica proposicional, única coisa que muda é a presença das constantes, mas nem mexemos com elas (ainda). O único cuidado a ser tomado quanto a isso é não confundir as fórmulas, pois, por exemplo, Pa é diferente de Pb e assim por diante.

O mesmo ainda se segue para argumentos com hipóteses, como, por exemplo:

1. (Pa∨Rb)⊃(Da∧¬Cb) ? Rb⊃(¬Cb∨Fa)
2. |Rb hipótese
3. |Rb∨Pa 2, exp.
4. |Da∧¬Cb 3,1, M.P.
5. |¬Cb 4, sep.
6. |¬Cb∨Fa 5, exp.
7. .·. Rb⊃(¬Cb∨Fa) 2-6, R.P.C.

O método já apresentado de reductio ad absurdum também funciona da mesmíssima maneira:

1. Pa⊃Qba
2. Qba⊃Rdsj
3. |¬(Pa⊃Rdsj) ? CTR
4. |Pa∧¬Rdsj 3, N.C.
5. |¬Rdsj 4, sep.
6. |¬Qba 5,2, M.T.
7. |¬Pa 6,1, M.T.
8. |Pa 4, sep.
9. |Pa∧¬Pa 7,8, add.
10. .·. Pa⊃Rdsj 3-9, R.A.A.

2. Regras para quantificadores

Chegamos, então, a algo novo para lidar. Sabemos o que fazer com cada operador, independente de ser uma letra sentencial ou uma fórmula com constante. Mas o que deduzir, por exemplo, de ∀xPx? Ou então ¬∃xQxa? É o que veremos agora.

2.1. Quantificador universal

Seguindo o padrão dos operadores, cada quantificador terá por si mesmo duas regras: uma de introdução e outra de eliminação. Começando pelo universal, temos o seguinte:

Instanciação do universal (I.∀)

1. ∀xϕx
2. .·. ϕc

Isto é, se temos que ∀xϕx, em que ϕ é um predicado qualquer, podemos deduzir que ϕc, para qualquer constante c e para todas as instâncias de c em ϕ. Significa que podemos deduzir que ϕa, ϕb, ϕc, etc., até que se finde nosso universo de discurso.

Generalização (G.∀)

1. ϕc
2. .·. ∀xϕx

Isto é, se ϕc é verdadeiro para qualquer ϕ e qualquer c, então segue-se que ∀xϕx. Contudo, esta regra possui uma restrição: a constante c não pode estar presente nem em uma premissa nem em uma hipótese aberta em que a fórmula ocorra.

Daremos alguns exemplos para que fique bem claro. Tememos o seguinte argumento: “Todos os gregos são sábios. Platão é grego, logo, Platão é sábio”. Formalizando…

1. ∀x(Gx⊃Sx)
2. Gp ? Sp
3. Gp⊃Sp 1, I.∀
4. .·. Sp 2,3, M.P.

Como se pode ver, instanciamos o universal em um caso particular (p) e disso deduzimos que Sp, que era justamente o que desejávamos. Agora, um exemplo em que a generalização pode ser usada:

1. ∀x(Ax⊃Bx) ? ∀x(¬Bx⊃¬Ax)
2. Ac⊃Bc 1, I.∀
3. |¬Bc hipótese
4. |¬Ac 3,2, M.T.
5. ¬Bc⊃¬Ac 3-4, R.P.C.
6. .·. ∀x(¬Bx⊃¬Ax) 5, G.∀

Não usamos em nenhuma hipótese ainda senso usado, nem premissa vigente, portanto, o uso é correto.

Outra coisa que é importante lembrar é que todas as instâncias de uma variável devem ser substituídas. Ou seja, se temos que ∀xPxx, temos que obrigatoriamente derivar Paa (para qualquer constante que seja), não podemos deduzir Pxa, por exemplo. O mesmo vale para G.∀: não podemos, de Paa derivar ∀xPxa, nem nada semelhante; todas as instâncias tem que ser trocadas.

2.2. O quantificador existencial

Assim como para o universal, temos duas regras para o existencial. São elas:

Eliminação do existencial (E.∃)¹

1. ∃xϕx
2. .·. ϕc

É semelhante com a primeira regra do universal. Ora, se estamos dizendo que existe um x tal que ϕ, parece óbvio deduzirmos que há um c do nosso universo de discurso que é ϕ. Contudo, esta fórmula também têm restrições: ela só pode ser usada uma vez. Diferentemente de I.∀, que podemos deduzir ϕa, ϕb, ϕc, etc., aqui não temos essa liberdade; justamente pelo quantificador existencial não falar de todos os indivíduos do universo de discurso, mas de pelo menos um. Claro, podemos ter dois ou mais indivíduos com essa propriedade, mas não há nada que nos diga isso. Portanto, não temos como deduzir que mais de um possua tal propriedade ϕ.

E, da mesma forma que G.∀, a constante c não pode estar presente em premissa ou hipótese vigente. Então, se temos que:

1. Pa
2. ∃xPx
3. .·. Pa 2, E.∃ (INCORRETO!)

Não podemos usar Pa, pois ela já está presente em (1). Mas também nada nos impede de deduzir Pb disso, por exemplo. Aí não tem erro.

Introdução do existencial (I.∃)

1. ϕc
2. .·. ∃xϕx

Uma regra também um tanto clara: se temos que Pa, por exemplo, podemos concluir que existe um x tal que Px. Esta regra não possui restrições.

Vamos há alguns exemplos:

“Existem gatos pretos; logo, gatos existem.”

1. ∃x(Gx∧Px) ? ∃xGx
2. Ga∧Pa 1, E.∃
3. Ga 2, sep.
4. .·. ∃xGx 3, I.∃

Perceba que aqui fizemos uso das duas regras: em (1) pela eliminação do existencial (usando uma constante nova, no caso, a) e em (4) utilizamo-nos da introdução do existencial para termos aquilo que queríamos.

1. ∀x(Qx∨Px)
2. ∃y¬Py ?∃zQz
3. ¬Pa 2, E.∃
4. Qa∨Pa 1, I.∀
5. Qa 3,4, S.D.
6. .·. ∃zQz 5, I.∃

Mais um caso em que usamos tanto E.∃ em (2) quanto I.∃ em (6) para obtermos o resultado desejado. Cremos que assim já tenha ficado claro o uso de cada regra.

2.3. Interconversão de quantificadores

Gottlob Frege, em sua Conceitografia — e no restante de seus trabalhos lógicos — tomou como fundamental apenas o quantificador universal, o qual, em sua notação, era representado por uma concavidade na barra de conteúdo. Mas então como ele expressava proposições como “existe um x tal que P” ou “existe um x e existe um y tal que P ou Q”?

A forma como Frege utilizava o quantificador existencial era em função do quantificador universal. De que forma? Da seguinte maneira: se dizemos, por exemplo, que ¬∀xPx, i.e., não é o caso que todo x é P, estamos, em outras palavras, dizendo que existe um x tal que não é P; pois, se nem todo x é P, então pelo menos um x não é P. Formalmente:

¬∀xPx⇔∃x¬Px

Por ser uma bi-implicação, sabemos que este intercâmbio vale para os dois lados.

Ora, isso também vale para ¬∀x¬Px, pois, se dizemos que nem todo x é não-P, então, estamos dizendo que existe um x que é P. Portanto:

¬∀x¬Px⇔∃xPx

Dessa forma, definimos o existencial a partir do universal.

O mesmo pode ser feito com o quantificador existencial. Se não existe um x tal que x não é P, então todo x é P, pois não existe um x que seja P:

¬∃x¬Px⇔∀xPx

Sabemos então que essas proposições são equivalentes e podemos usá-las numa dedução. Por exemplo:

1. ¬∃x¬(Gx⊃Dx)
2. ¬Da ? ¬Ga
3. ∀x(Gx⊃Dx) 1, I.Q.
4. Ga⊃Da 3, I.∀
5. .·. ¬Ga 2,4, M.T.

Nos casos em que temos uma quantificação múltipla, nós apenas movemos a negação entre os quantificadores. Por exemplo, se temos que ¬∃x∀y∃z(Qxy⊃Pz), movemos a negação e obtemos ∀x¬∀y∃z(Qxy⊃Pz); fazemos o passo mais uma vez ∀x∃y¬∃z(Qxy⊃Pz) e, por último, uma vez mais ∀x∃y∀z¬(Qxy⊃Pz). O resultado final é os quantificadores invertidos e a fórmula negada. O mesmo se segue para todo e qualquer caso.

3. Identidade e regras de inferência

O sinal de identidade também tem suas regras de inferência que pode ser usadas numa dedução. Temos duas regras:

Introdução da identidade (I=)

1. c=c

Apenas isto. Podemos introdução que algo é idêntico a si mesmo em qualquer linha da dedução sem abrir hipótese nova. Não há restrição. Ela pode parecer trivial, à primeira vista, mas conseguimos usá-la para provar algumas coisas interessantes.

Eliminação da identidade (E=)

1. a=b
2. ϕa
3. .·. ϕb

Isto é, se a=b, então b pode ser substituído onde a ocorre (que no caso é ϕ, um predicado qualquer). O porquê disso é claro: se a e b são idênticos, então tudo que é verdadeiro para a é também verdadeiro para b.

Vejamos alguns exemplos:

1. Lab∨Lbc
2. ¬Lab
3. b=c ? Lcc
4. Lbc 1,2, S.D.
5. .·. Lcc 4,3, E=

Substituímos o b em (4) pelo c e obtivemos o resultado: Lcc.

Agora, um exemplo da introdução da identidade:

1. (Pa∨Qb)⊃a≠a
2. ¬Rd ?¬Qb∧¬Rd
3. a=a I=
4. ¬(Pa∨Qb) 1,3, M.T.
5. ¬Pa∧¬Qb 4, D.M.
6. ¬Qb 5, sep.
7. .·. ¬Qb∧¬Rd 2,6, add.

Esta regra também será bastante útil quando tivermos que provar certos teoremas sobre a identidade.

Mas o que é um teorema? É disso que falaremos a seguir.

4. Teoremas

Como vimos na parte 4, caso não se recorde, definimos o que era uma fórmula válida, aquelas fórmulas que eram modelo do conjunto vazio. Agora, temos uma noção analoga para a sintaxe: os teoremas.

• α é um teorema se e somente se há uma forma de deduzir α do conjunto vazio, i.e., um conjunto vazio de premissas. O que representamos por ∅⊢α ou, simplesmente, ⊢α.

Mas como podemos deduzir uma fórmula sem premissas? Simples: basta iniciarmos com uma hipótese que pode ser tanto para (RPC) quanto para (R.A.A.). Vamos provar, por exemplo, que (Pa⊃Qa)⊃(¬Qa⊃¬Pa) é um teorema.

1. |Pa⊃Qa hipótese
2. ||¬Qa hipótese
3. ||¬Pa 2,1, M.T.
4. |¬Qa⊃¬Pa 2-3, RPC
5. .·. (Pa⊃Qa)⊃(¬Qa⊃¬Pa) 1-4, RPC

Começamos com uma hipótese e, com RPC, chegamos à conclusão.

Mais um! Vamos provar que ¬∃x(x≠x), ou seja, que tudo é idêntico a si mesmo (ou o famoso Princípio de Identidade):

1. |∃x(x≠x) hipótese ?CTR
2. |a≠a 1, E.∃
3. |a=a I=
4. |a=a∧a≠a 2,3, add.
5. .·. ¬∃x(x≠x) 1-4, R.A.A.

Provemos a propriedade de transitividade da identidade e demonstremos que é um teorema:

1. |a=b∧b=c ?a=c
2. |a=b 1, sep.
3. |b=c 1, sep.
4. |a=c 2,3, E=
5. .·. (a=b∧b=c)⊃a=c 1-4, RPC

E várias outras fórmulas podem ser demonstradas como teoremas. Mas a melhor parte de tudo isso vem a seguir.

5. Consequência sintática e consequência semântica

A noção de consequência sintática é bem simples:

• α é consequência sintática de Γ se e somente se há uma prova de α a partir de Γ, ou seja, Γ⊢α.

Tendo dito isso, a parte mais interessante e bonita da lógica da lógica de 1ª ordem é que a consequência tanto sintática quanto semântica coincidem. Isto é:

• Γ⊨α se e somente se Γ⊢α

É isso que nos garante dizer que o método de dedução natural é correto e completo. Correto porque tudo que provamos é consequência semântica das premissas; e completo porque tudo é consequência semântica é provável.

Temos ainda o caso especial do enunciado acima em que Γ é o vazio, isto é:

• ⊨α se e somente se ⊢α

Sendo isto verdadeiro, temos que todo teorema é uma fórmula válida e toda fórmula válida é um teorema. Este é o famoso Teorema da Corretude e Completude da lógica de 1ª ordem.

A parte que compete à completude, isto é, se α é consequência semântica de Γ, então é consequência sintática, foi provada por Kurt Gödel em 1930 — ironicamente, Gödel também é autor dos teoremas da incompletude de sistemas aritméticos —, embora ele usasse um método diferente para isso: o método axiomático. Contudo, este ficará para depois.

O importante é ressaltar que as propriedades dadas para a consequência semântica na parte 4 também valem para a consequência sintática, já que, mais uma vez, elas coincidem.

Apêndice I — Sobre a negação de quantificadores

Dentro dos meus estudos em lógica, sempre vi dizerem que é necessário, antes de qualquer derivação, inverter os quantificadores um a um e negar a formular principal. Por exemplo:

¬∀xPx

deve-se, antes de tudo, transformá-lo em

∃x¬Px

e só então, provavelmente, derivar disso Pa.

A questão complica um pouco quando estamos falando de quantificação múltipla. Imagine repetir o mesmo processo acima na fórmula:

∀x∀y∀z∃w∃x₁∃y₁[(Px∧Qy)∨Rz)⊃(Tx₁y₁⊃Sz)]

Claro, é um tanto difícil se deparar com fórmulas tão grandes; contudo, quando a fórmula já tem lá seus 3 ou 4 quantifidores, fica pedante repeti-la várias vezes numa dedução, alongando-a mais do que é necessário. Pois bem, como resolver isso, sendo que não tem uma regra de elimine ¬∀x ou ¬∃x?

Na verdade, pelo contrário, essas regras existem! No entanto, é incomum vê-las sendo usadas em dedução natural, sendo mais comumente utilizadas no método de tablôs semânticos. São elas as seguintes:

1. Eliminação da negação do universal (N.∀)

1. ¬∀xPx
2. .·. ¬Pc

Bastante intuitivo, não? Se temos que não é o caso que para todo x, então Px, é correto derivar ¬P para ao menos alguma constante c do universo de discurso — pois, lembrando, ¬∀xPx⇔∃x¬Px. Entretanto, ao invés de passar o universal para o existencial e só depois chegar ao resultado, essa regra deixa as coisas mais dinâmicas, por assim dizer.

Note que ela funciona exatamente como a regra de Eliminação do Existencial já exposta. Isso significa também, é claro, que as restrições são as mesmas: 1) apenas uma constante pode ser instanciada e 2) esta constante não pode já ter ocorrido em premissa ou hipótese vigente.

2. Eliminação da negação do existencial (N.∃)

1. ¬∃xPx
2. .·. ¬Pa
3. .·. ¬Pb
4. .·. ¬Pc
5. etc…

Como se pode bem notar, a regra para um existencial negativo é a mesma para um universal positivo, pois, lembrando: ¬∃xPx⇔∀x¬Px. E tal como a regra do universal, ela não possui restrições. Isso facilitará demais as deduções que possuem quantificadores múltiplos. Eis um exemplo:

1. ¬∀x∀y∃z((Px∧Qy)⊃Rz) ?Pa∧¬Rc
2. ¬∀y∃z((Pa∧Qy)⊃Rz) 1, N.∀
3. ¬∃z((Pa∧Qb)⊃Rz) 2, N.∀
4. ¬((Pa∧Qb)⊃Rc) 3, N.∃
5. Pa∧Qb∧¬Rc 4, N.C.
6. Pa 5, sep.
7. ¬Rc 6, sep.
8. .·. Pa∧¬Rc 6,7, add.

Se fôssemos usar a regra convencional, teríamos que na linha (2) instanciar

∃x¬∀y∃z((Px∧Qb)⊃Rz)

e “passar” a negação um por um até chegar na fórmula quantificada e apenas depois disso instanciar as constantes, o que seria plenamente feito apenas na linha (8), quando podemos, feito demonstrado acima, chegar no mesmo resultado logo na linha (4).

Por isso, é agora recomendado a todos que façam suas deduções com essas regras, pois poupará ainda mais tempo e espaço para fazê-las.

Apêndice II — Sobre os axiomas

Em momento algum falamos sobre axiomas durante nossa explicação a não ser para mencioná-los. E de fato, explicar como todo o método axiomático funciona demandaria um artigo próprio; o que será feito aqui é um tanto mais simples: explicar qual o papel dos axiomas para a lógica como um todo.

O chamado até hoje de fundador do método axiomático é o matemático grego Euclides que, nos seus Elementos, traz no início de cada livro uma série de axiomas. São noções primárias, tão simples e intuitivas que seria absurdo para a razão negá-las; seriam, em outras palavras, evidentes. Com isso ele forjou um método muito sólido de prova do qual, através de poucas verdades intuitivas, poderia-se provar muitas coisas a mais.

O método de Euclide foi aperfeiçoado com o passar da história. E com isso acabou por surgir na matemática aquilo que hoje se chama “geometrias não-euclidianas”. Elas partiam de postulados diferentes — por vezes contraditórios com os de Euclides —, mas ainda assim conseguiam derivar disso sistemas tão corretos e completos quanto o do matemático grego.

Por conta disso, acabou-se por descartar a noção de que um axioma é uma verdade “autoevidente”, “autojustificável”, “cuja a negação é absurda”. O conceito de axioma que se tem hoje é de qualquer sentença que seja aceita num sistema sem que seja derivada de outras fórmulas, i.e., sem que seja provada ou justificada. Fazemos isso, claro, para evitar cair em um ad infinitum ou em uma petitio principii, isto é, cair em infinitas justificaçōes ou em justificações circulares.

Outra coisa que motivou tal descarte foi o fato de “autoevidencia”, “obviedade” e derivadas não são conceitos lógico, mas sim psicológicos — e, diga-se de passagem, um tanto quanto subjetivos. É claro que os lógicos ainda levam em conta tal questão na hora de formular seus axiomas, mas não é algo que faça parte da essência do que é um axioma na lógica.

Os sistemas axiomáticos mais populares da lógica clássica certamente são os de Frege², Quine³, Łukasiewicz⁴, Meredith⁵, Gödel⁶ e o de Henkin⁷. Tudo o mais que sabemos sobre a lógica clássica hoje em dia foi provado por esses e outros autores através do método axiomático.

Conclusão

De maneira geral, era isso que tinha para se falar sobre a lógica de 1ª ordem; o nosso caminho, entretanto, não acaba aqui, a lógica não acaba aqui. Ainda há muito o que se falar das lógicas não-clássicas e é delas que falaremos nos próximos artigos.

Adendos e dúvidas podem ser deixados nos comentários. E isso é tudo.

Notas

[1] A regra de Eliminação do existencial é apresentada de forma diferente por Cezar A. Mortari (Cf.: Introdução à lógica), tendo a forma de uma regra hipotética; aqui, optamos por enunciá-la de maneira mais simplificada;

[2] Cf.: Frege, Gottlob, Conceitografia;

[3] Cf.: Quine, W. V. O., Completeness of the proposicional calculus, The Journal of symbolic logic, vol. 3 (1938);

[4] Cf.: Este artigo (aqui) de Nicholas Ferreira, onde ele expõe o sistema de Łukasiewicz;

[5] Cf.: C.A. Meredith (1953). “Single axioms for the systems (C,N), (C,0), and (A,N) of the two-valued propositional calculus“. Journal of Computing Systems. O sistema de Meredith é bastante interessante, pois contém um único axioma.

[6] Gödel, Kurt, Die Vollständigkeit der Axiome des logischen Funktionenkalküls, Monatshefte für Mathematik und Physik, vol. 37 (1930);

[7] Henkin, Leon, The Completeness of the first order functional calculus, Ths Journal of Symbolic Logic, Vol. 14, No. 3 (Sep.