Categorias
Filosofia

Demonstração de alguns teoremas da lógica clássica

Demonstração de alguns teoremas da lógica clássica, especialmente proposicional. Na foto, Jan Łukasiewicz, lógico que provou a completude da lógica proposicional, i.e., todas as verdades são prováveis no sistema.

WARNING: unbalanced footnote start tag short code found.

If this warning is irrelevant, please disable the syntax validation feature in the dashboard under General settings > Footnote start and end short codes > Check for balanced shortcodes.

Unbalanced start tag short code found before:

“p∨q)∧¬p)⊃q Prova. Silogismo disjuntivo também é uma regra tomada como primitiva; pode, no entanto, ser derivada de outras regras da seguinte forma: |”

1. Introdução

Teorema, segundo a definição clássica, é toda proposição que possa ser derivada do conjunto vazio, i.e., β é um teorema se e somente se ∅⊢β. E, feito já vimos em outro lugar, a noção de teorema se confunde com a nossa de validade ou tautologia.

No presente texto, dou a prova de alguns dos principais teoremas da lógica clássica, pois senti a falta de mais exemplos de dedução em meus textos anteriores. Adianto que tais demonstrações são um ótimo exercício ao leitor para a prática da dedução natural.

Como se observará, todos os argumentos seguirão uma forma hipotética, em que se abre uma hipótese para Prova por Condicional ou por Reductio Ad Absurdum, haja vista que queremos prová-las a partir do conjunto vazio.

Teorema 1. (p⇔¬¬p)

Prova. A regra de dupla negação nos diz que p é o caso se e somente se não é o caso que não é o caso que p. É um princípio evidente, por assim dizer; contudo, não quer dizer que não haja uma prova para tal.

Por se tratar de uma bi-implicação, precisamos, antes, provar cada lado dela, i.e., (p⊃¬¬p) e (¬¬p⊃p). Isso se fará a partir do dois seguintes lemas:

Lema 1. (p⊃¬¬p)

Prova. Tal demonstração se dará por reductio ad absurdum, feito se segue:

  1. |¬(p⊃¬¬p) ?CTR
  2. |p∧¬¬¬p 1, N.C.
  3. ||¬p Hipótese
  4. ||p 2, sep.
  5. ||p∧¬p 3, 4, add.
  6. |¬¬p 3-5, R.A.A.
  7. |¬¬¬p 2, sep.
  8. |¬¬p∧¬¬¬p 6,7, add.
  9. .·. p⊃¬¬p 1-8, R.A.A.

Lema 2. (¬¬p⊃p)

Prova. Pode facilmente ser dada por reductio ad absurdum mais uma vez:

  1. |¬(¬¬p⊃p) ?CTR
  2. |¬¬p∧¬p 1, N.C.
  3. .·. ¬¬p⊃p 1-2, R.A.A.

Teorema 1. (p⇔¬¬p)

Prova. Sabendo que (α⇔β) é o mesmo que ((α⊃β)∧(β⊃α)), tendo, pois, que α:= (p⊃¬¬p) e β:= (¬¬p⊃p), podemos usar C.B. (Condicionais para bi-condicional) e está provado que (p⇔¬¬p).

Teorema 2. (p∧(p⊃q))⊃q

Prova. A regra de Modus Ponens é quase sempre tomada por primitiva, i.e., sem prova e evidentemente válida. Isso se dá pelo fato de ser simples, intuitiva e capaz de deduzir todas as outras verdades lógicas por si só. Contudo, podemos prová-la caso façamos assunção de outras regras de inferência, da seguinte forma:

  1. |(p∧(p⊃q) ?RPC
  2. |p 1, sep.
  3. |p⊃q 1, sep.
  4. | |¬q hipótese
  5. | |¬p 3,4, M.T.
  6. | |p∧¬p 2,6, add.
  7. |¬¬q 4-6, R.A.A.
  8. |q 7, D.N.
  9. .·. (p∧(p⊃q))⊃q 1-8, R.A.A.

Teorema 3. (¬q∧(p⊃q))⊃¬p

Prova. Versão negativa da regra Modus Ponens e que pode ser provada de forma similar — sendo uma regra derivada, não é necessário assumir outras regras além das primitivas para demonstrá-la, assim:

  1. |¬q∧(p⊃q) ?RPC
  2. |¬q 1, sep.
  3. |(p⊃q) 1, sep.
  4. | |p hipótese
  5. | |q 3,4, M.P.
  6. | |q∧¬q 2,5, add.
  7. |¬p 4-6, R.A.A.
  8. .·. (¬q∧(p⊃q))⊃¬p 1-7, RPC

Teorema 4. ((p∨q)∧¬p)⊃q

Prova. Silogismo disjuntivo também é uma regra tomada como primitiva; pode, no entanto, ser derivada de outras regras da seguinte forma:

  1. |((p∨q)∧¬p) ?RPC
  2. |p∨q 1, sep.
  3. |¬p 1, sep.
  4. |¬p⊃q 2, equiv.
  5. |q 3,4, M.P.
  6. .·. ((p∨q)∧¬p)⊃q 1-5, RPC

Como sabemos, (p⊃q) é definido por (¬p∨q); assim, é fácil perceber que (¬p⊃q) é equivale a (p∨q), que pode também ser verificado por uma tabela-verdade. Tendo isso em mãos, está provado que a regra de S.D. é consequência do conjunto vazio, i.e., válida.

Teorema 5. ((p⊃q)∧(q⊃r))⊃(p⊃r)

Prova. Assumindo como primitivas as regras de separação e Modus Ponens, podemos derivar a regra de Silogismo Hipotético da seguinte maneira:

  1. |(p⊃q)∧(q⊃r) ?RPC
  2. |p⊃q 1, sep.
  3. |q⊃r 1, sep.
  4. | |p hipótese
  5. | |q 2,4, M.P.
  6. | |r 3,5, M.P.
  7. |p⊃r 4-6, RPC
  8. .·. ((p⊃q)∧(q⊃r))⊃(p⊃r) 1-7, RPC

Teorema 6. ((p⊃q)⊃p)⊃p

Prova. Um tanto desconhecida pelo público geral, a Lei de Pierce pode ser assim demonstrada:

  1. |¬((p⊃q)⊃p)⊃p) ?CRT
  2. |((p⊃q)⊃p)∧¬p 1, N.C.
  3. |(p⊃q)⊃p 2, sep.
  4. |¬p 2, sep.
  5. |¬(p⊃q) 3,4, M.T.
  6. |p∧¬q 5, N.C.
  7. |p 6, sep.
  8. |p∧¬p 4,7, add.
  9. .·. ((p⊃q)⊃p)⊃p 1-8, R.A.A.

Teorema 7. p⊃(q⊃p)

Prova. Bastante usada como axioma nos principais sistemas da lógica proposicional — incluindo o sistema de Łukasiewicz —, a regra de prefixação é demonstrada como se segue:

  1. |¬(p⊃(q⊃p)) ?CRT
  2. |p∧¬(q⊃p) 1, N.C.
  3. |p∧q∧¬p 1, N.C.
  4. |p 3, sep.
  5. |¬p 3, sep.
  6. |p∧¬p 4,5, add.
  7. .·. p⊃(q⊃p) 1-6, R.A.A.

Teorema 8. ((p∧q)⊃r)⇔((p∧¬r)⊃¬q)

Prova. A regra de antilogismo, também não muito conhecida, feito a regra de dupla negação, por se tratar de uma bi-implicação, será demonstrada pelos dois seguintes lemas:

Lema 1. ((p∧q)⊃r)⊃((p∧¬r)⊃¬q)

  1. |(p∧q)⊃r ?RPC
  2. | |p∧¬r ?RPC
  3. | |¬r 2, sep.
  4. | |¬(p∧q) 1,3, M.T.
  5. | |¬p∨¬q 4, D.M.
  6. | |p 2, sep.
  7. | |¬q 5,6, S.D.
  8. |(p∧¬r)⊃¬q 2-7, RPC
  9. .·. ((p∧q)⊃r)⊃((p∧¬r)⊃¬q) 1-8, RPC

Lema 2. ((p∧¬r)⊃¬q)⊃((p∧q)⊃r)

  1. |(p∧¬r)⊃¬q ?RPC
  2. | |p∧q ?RPC
  3. | |q 2, sep.
  4. | |¬(p∧¬r) 1,3, M.T.
  5. | |¬p∨¬¬r 4, D.M.
  6. | |¬p∨r 5, D.N.
  7. | |p 2, sep.
  8. | |r 6,7, S.D.
  9. |(p∧q)⊃r) 1-8, RPC
  10. .·. ((p∧¬r)⊃¬q)⊃((p∧q)⊃r) 1-9, RPC

Teorema 8. ((p∧q)⊃r)⇔((p∧¬r)⊃¬q)

Prova. Tendo provado os dois lados da bi-implicação, por C.B. está provado que ((p∧q)⊃r)⇔((p∧¬r)⊃¬q).

Teorema 9.1. ¬(p∧q)⇔(¬p∨¬q)

A demonstração da Primeira Lei de De Morgan se dará a partir dos dois seguintes lemas:

Lema 1. ¬(p∧q)⊃(¬p∨¬q)

Prova. Podemos comprová-lo por R.A.A., da seguinte forma:

  1. |¬(¬(p∧q)⊃(¬p∨¬q)) ?CTR
  2. |¬(p∧q)∧¬(¬p∨¬q) 1, N.C.
  3. |¬(p∧q) 2, sep.
  4. |¬(¬p∨¬q) 2, sep.
  5. |p⊃¬q 3, equiv.
  6. |¬(p⊃¬q) 4, equiv.
  7. .·. ¬(p∧q)⊃(¬p∨¬q) 1-6, R.A.A.

Através de uma tabela-verdade, é fácil verificar que (3) é equivalente a (5) e (4) é equivalente a (6). Disso se explícita a contradição entre ambas as proposições, demonstrando que, de fato, tal implicação da Lei de De Morgan é válida.¹

Lema 2. (¬p∨¬q)⊃¬(p∧q)

Prova. Tendo com base as equivalências já descritas em [1], o lema 2 segue-se facilmente:

  1. |(¬p∨¬q) ?RPC
  2. |(p⊃¬q) 1, equiv.
  3. |¬(p∧¬¬q) 2, equiv.
  4. |¬(p∧q) 3, D.N.
  5. .·. (¬p∨¬q)⊃¬(p∧q)

Prova. A bi-implicação de (α⇔β) é assim definida:

(α⊃β)∧(β⊃α).

Ora, temos que α:= ¬(p∧q); e β:= (¬p∨¬q), como já demonstrado pelos lemas (1) e (2), um implica no outro e vice-versa, segue-se seguramente que: ¬(p∧q)⇔(¬p∨¬q), i.e., a Primeira Lei de De Morgan.

Teorema 9.2. ¬(p∨q)⇔(¬p∧¬q)

Prova. Os passos para se demonstrar este teorema serão os mesmos do anterior. Uma vez que se trata também de uma bi-implicação, precisamos provar cada lado seu para, então, aplicarmos a regra de C.B.

Lema 1. ¬(p∨q)⊃(¬p∧¬q)

Prova. Este lema pode ser facilmente deduzido por RPC, da seguinte forma:

  1. |¬(p∨q) ?RPC
  2. |¬(¬p⊃q) 1, equiv.
  3. |¬p∧¬q 2, equiv.
  4. .·. ¬(p∨q)⊃(¬p∧¬q) 1-3, RPC

O ponto principal aqui é a passagem de (1) para (2). Usando uma tabela-verdade, pode-se ver que as fórmulas são equivalentes.² O restante já é bem conhecido.

Lema 2. (¬p∧¬q)⊃¬(p∨q)

Prova. A prova é deduzida por reductio ad absurdum da seguinte maneira:

  1. |¬((¬p∧¬q)⊃¬(p∨q)) ?CTR
  2. |(¬p∧¬q)∧¬¬(p∨q) 1, N.C.
  3. |(¬p∧¬q)∧(p∨q) 2, D.N.
  4. |¬p∧¬q 3, sep.
  5. |p∨q 3, sep.
  6. |¬p 4, sep.
  7. |q 5,6, S.D.
  8. |¬q 4, sep.
  9. |q∧¬q 7,8, add.
  10. .·. (¬p∧¬q)⊃¬(p∨q) 1-9, R.A.A.

Teorema 9.2. ¬(p∨q)⇔(¬p∧¬q)

Prova. Ora, tendo provado tanto que ¬(p∨q)⊃(¬p∧¬q) quanto que (¬p∧¬q)⊃¬(p∨q), utilizando a regra de C.B. deduzimos que ¬(p∨q)⇔(¬p∧¬q). Assim, verificamos que a Segunda Lei de De Morgan é válida.

Teorema 10. ((p⊃q)∧(r⊃s)∧(p∨r))⊃(q∨s)

Prova. A regra de trilema construtivo, que é a forma disjuntiva do Modus Ponens, pode ser assim provada:

  1. |(p⊃q)∧(r⊃s)∧(p∨r) ?RPC
  2. |p∨r 1, sep.
  3. ||¬p hipótese
  4. ||r 2,3, S.D.
  5. |¬p⊃r 3-4, RPC
  6. |¬¬p∨r 5, equiv.
  7. |p∨r 6, D.N.
  8. .·. ((p⊃q)∧(r⊃s)∧(p∨r))⊃(q∨s) 1-7, RPC
Teorema 11. ((p⊃q)∧(r⊃s)∧(¬q∨¬s))⊃(¬p∨¬r)
  1. |(p⊃q)∧(r⊃s)∧(¬q∨¬s) ?RPC
  2. ||p hipótese
  3. ||p⊃q 1, sep.
  4. ||q 2,3, M.P.
  5. ||¬q∨¬s 1, sep.
  6. ||¬s 4,5, S.D.
  7. ||r⊃s 1, sep.
  8. ||¬r 6,7, M.T.
  9. |p⊃¬r 2-8, RPC
  10. |¬p∨¬r 9, equiv.
  11. .·. ((p⊃q)∧(r⊃s)∧(¬q∨¬s))⊃(¬p∨¬r) 1-10, RPC

Ora, sabendo que (p⊃r) é equivalente a (¬p∨r), tendo que (p⊃¬r), derivamos por equivalência que (¬p∨¬r).

Teorema 12. ∀ϕ∀x∀y[(x=y)⊃[ϕx⇔ϕy]]

Prova. A polêmica lei de indiscernibilidade dos idênticos pode ser deduzida da seguinte maneira:

  1. |∀x∀y[x=y] ?RPC
  2. |(y)[a=y] 1, E.∀
  3. |a=b 2, E.∀
  4. | |Pa hipótese
  5. | |Pb 3,4, E=
  6. |Pa⊃Pb 4-5, RPC
  7. | |Pb hipótese
  8. | |Pa 6,7, E=
  9. |Pb⊃Pa 7-8, RPC
  10. |Pa⇔Pb 6,9, C.B.
  11. ∀x∀y[(x=y)⊃(Pa⇔Pb)] 1-10, RPC
  12. .·. (ϕ)(x)(y)[(x=y)⊃[ϕx⇔ϕy]] 11, I.∀

Teorema 13. ∀x∀y∀z[(x=y∧y=z)⊃x=z]

Prova. A transitividade da identidade pode ser assim demonstrada:

  1. |¬∀x∀y∀z[(x=y∧y=z)⊃x=z] ?CRT
  2. |¬∀y∀z[(a=y∧y=z)⊃a=z] 1, N.∀
  3. |¬∀z[(a=b∧b=z)⊃a=z] 2, N.∀
  4. |¬((a=b∧b=c)⊃a=c) 3, N.∀
  5. |a=b∧b=c∧a≠c 4, N.C.
  6. |a=b 5, sep.
  7. |b=c 5, sep.
  8. |a=c 6,7, E=
  9. |a≠c 5, sep.
  10. |a=c∧a≠c 8,9, add.
  11. .·. ∀x∀y∀z[(x=y∧y=z)⊃x=z] 1-10, R.A.A.

Teorema 14. ∀x∀y∀z[(x=z∧z=y)⊃x=y]

Prova. A Lei de Euclides, enunciada logo no Livro I dos Elementos, i.e., se duas coisas são iguais a uma terceira, então elas são iguais entre si, pode ser provada como se segue:

  1. |¬∀x∀y∀z[(x=z∧y=z)⊃x=y] ?CRT
  2. |¬∀y∀z[(a=z∧y=z)⊃a=y] 1, N.∀
  3. |¬∀z[(a=z∧b=z)⊃a=b] 2,N.∀
  4. |¬((a=c∧b=c)⊃a=b) 3, N.∀
  5. |a=c∧b=c∧a≠b 4, N.C.
  6. |a=c 5, sep.
  7. |b=c 5, sep.
  8. |b=a 6,7, E=
  9. |a≠b 5, sep.
  10. |b=a∧a≠b 8,9, add.
  11. .·. ∀x∀y∀z[(x=z∧y=z)⊃x=y] 1-10, R.A.A.

Já assumimos, com essa demonstração, a validade da simetria da identidade, i.e., (a=b⇔b=a) — que pode também ser facilmente provada (tente você mesmo).

Notas

[1] Ora, sabendo que (p⊃q) é igual a ¬(p∧¬q), então ¬(p∧q) é igual a (p⊃¬q), que por sua vez é igual ¬(p∧¬¬q); as negações anulam-se, portanto: ¬(p∧q). O mesmo se dá com ¬(¬p∨¬q): a implicação equivalente a (¬p∨¬q) é (p⊃¬q) — uma vez que ((p⊃q)⇔(¬p∨q)). Para obtermos ¬(¬p∨¬q) basta também negar a implicação, que seria ¬(p⊃¬q);

[2] Além da tabela-verdade, podemos verificar isso do seguinte modo: sendo (p⊃q) igual (¬p∨q). Assim, de (¬p⊃q) deriva-se que (¬¬p∨q), que por D.N. temos (p∨q). Como queremos a negação desta disjunção, colocamos que ¬(¬p⊃q) e disse segue-se que ¬(p∨q).

Deixe um comentário

O seu endereço de e-mail não será publicado. Campos obrigatórios são marcados com *